自然语言处理——3.4 有限自动机在NLP中的应用

作者: SpareNoEfforts | 来源:发表于2018-10-02 21:36 被阅读222次

英语单词拼写检查[Oflazer, 1996]

1. 编辑距离

设 $X$ 为拼写错误的字符串，其长度为 $m$ , $Y$ 为 $X$ 对应的正确的单词(答案)，其长度为 $n$ 。则 $X$ 和 $Y$ 的编辑距离 $ed(X[m], Y[n])$ 定义为：从字符串 $X$ 转换到 $Y$ 需要的插入、删除、替换和交换两个相邻的基本单位(字符)的最小个数。如：

$ed ({\text{recog}}\underline {{\text{in}}} {\text{ze}}, {\text{recog}}\underline {{\text{in}}} {\text{ze}}) = 1$
$ed (\underline {\text{s}} {\text{ailn}}, \underline {\text{f}} {\text{ail}}\underline {\text{i}} {\text{n}}\underline {\text{g}} ) = 3$

2. 拼写检查例子计算

假设 $Z = z_1 z_2 … z_p$ 为字母表 $A$ 上的 $p$ 个字母构成的字符串， $Z[j]$ 表示含有 $j (j \geqslant 1)$ 个字符的子串。 $X[m]$ 为拼写错误的字符串，其长度为 $m，Y[n]$ 为与 $X$ 串接近的字符串(一个候选)，其长度为 $n$ 。则给定两个串 $X$ 和 $Y$ 的编辑距离 $ed(X[m], Y[n])$ 可以通过循环计算出从字符串 $X$ 转换到 $Y$ 需要进行插入、删除、替换和交换两个相邻的字符操作的最少次数。

(1) 如果 $x_{i+1}= y_{j+1}$ （两个串的最后一个字母相同），则 $ed(X[i+1], Y[j+1]) = ed(X[i], Y[j])$ ;

(2) 如果 $x_i = y_{j+1}$ ，并且 $x_{i+1} = y_j$ （最后两个字符需要交换位置），则 $ed(X[i+1], Y[j+1]) = 1+min\{ed(X[i-1], Y[j-1]), ed(X[i], Y[j+1]), ed(X[i+1], Y[j])\}$

图示

(3) 其它情况下 $(x_{i+1} \ne y_{j+1}且(x_i \ne y_{j+1}或x_{i+1} \ne y_j))$
$ed(X[i+1], Y[j+1]) = 1+min\{ed(X[i], Y[j]), ed(X[i], Y[j+1]), ed(X[i+1], Y[j])\}$
其中
$ed(X[0], Y[j]) =j,(0 \leqslant j \leqslant n)$ （X长度为0）
$ed(X[i], Y[0])=i, (0 \leqslant j \leqslant m)$ , （Y长度为0）
$ed(X[-1], Y[j])=ed(X[i], Y[-1])=max\{m,n\}$ , （边界约定）

图示

3. 拼写检查自动机构造

构造一个确定的有限状态机 $R$ ：
$R = \{ Q,A,\delta ,{q_0},F\}$
其中， $Q$ 表示状态集； $A$ 表示输入字符集；
$\delta :Q \times A \to Q$
$q_0 \in Q$ 为起始状态；
$F \subseteq Q$ 为终止状态集；

如果表示有限状态机 $R$ 接受的语言，字母构成的所有合法单词都是有限状态机中的一条路径。给定一个输入串，对其进行检查的过程就是在给定阈值 $t (t > 0)$ 的情况下，寻找那些与输入串的编辑距离小于 $t$ 的路径。那么，一个字符串能够被 $R$ 识别的条件是存在非空集合：
$C = \{ Y[n]|Y[n] \in L$ $and$ $ed(X[m],Y[n]) \leqslant t\}$