Daily Archives: August 12, 2007

SunPinyin代码导读（五）

Posted on by
Reply

让我们来看看最后一个步骤，将剪枝后的语言模型线索化（threading）。

$ make m3_thread
./slmthread ../swap/lm_sc.3gm ../data/lm_sc.t3g


线索化的目的是为了加快语言模型的查找速度。以trigram为例，如果我们要计算句子“ABCDE。”的概率，P(S) = P(A).P(B|A).P(C|AB).P(D|BC).P(E|CD).P(<EOS>|DE)，并假定这些条件概率的求解无需回退。

首先我们从level[1]（unigram中），可以通过二分查找，找到P(A)；然后从A的孩子节点中，二分找到B，得到P(B|A)；然后从B的孩子节点二分找到C，得到P(C|AB)。再接下来呢，我们要计算的是P(D|BC)。这时，我们只有重新在unigram中二分找到B，然后再在B的孩子节点中二分找到C，才能计算P(D|BC)的值。这无疑是很低效的。如果我们在计算P(C|AB)时，能够从它的节点上，直接定位到(B,C)，就可以大大加快查找的速度。

我们用(level, idx)来标识一个节点，节点上的信息用(W, h', p, b, c)来表示，其中：

  • W：跟在history后面的词ID。这个节点所在位置，还隐含了一个信息，就是它的历史由来。
  • h'：指向下一步要回退到的节点，用(level', idx')来表示。
  • p：p(W|h)
  • b：bow(h)
  • c：其下一个level中后续节点的开始位置

当然，叶子节点上是没有b和c的。现在，回退模型的结构，就从一棵树变成了一个网。它的基本操作是：在当前历史状态hi(level,idx)下，输入一个词W，则转移到一个新的历史状态hj(level', idx')，并返回P(W|h)。新节点hj的level'，并不总等于level-1。例如，C(ABC)>0，但是(B,C)在训练时没有见到，则这个节点的h'就是level[1]上的C节点。如果C也没有统计到，则h'就是pseudo root节点（level[0][0]）了。

让我们考察下面一个片段。

                                  level+1
h (level,idx)    ----------->   W1,p1,h'1,[b,c]
    h',bow       \              ... ...
                  \             Wi,pi,h'i,[b,c]
                   \            ... ...
                    -------->   Wk,pk,h'k,[b,c]


输入一个词W。如果W出现在h的孩子节点中，记为(level+1,idx')，其p值就是P(W|h)。
    如果该节点有子节点，那么(level+1,idx')就是新的历史节点；
    如果该节点没有子节点，则它的h'，即为新的历史节点。

如果W没有出现在h的孩子节点中，则从(level,idx)节点中的h'开始，继续进行上面相同的操作，找到新的历史节点，并将得到的概率值乘上bow(h)，作为P(W|h)返回。注意，这是一个递归的过程。

下面来看看代码：

slmthread.cpp：

CSIMSlmWithIteration::getIdString(it, history)：

成员变量m_history中保存的是各个level中的index，将节点上的词ID保存到传入的history参数中。next()方法将m_history最后面的下标（即当前level的下标）加1，然后调用adjustIterator()，找出新节点各前继节点的下标，保存在m_history中。

CSIMSlmWithIteration::findBackOffState(n, hw, bol, bon)：

寻找某个n-gram（长度为n，保存在hw[1..n]中）的回退节点（h'），返回它的level和idx。调用findState()去查找hw[2..n]在level[n-1]上的下标idx，如果下标>=0且该节点(n-1, idx)有子节点，则返回h'的位置。否则调用findState()查找hw[3..n]在level[n-2]上的下标，...，如果循环到hw[n]还是找不到，则返回pseudo root节点。

举例来说，查找trigram (A,B,C)的回退节点。查找(B,C)是否存在，如果存在则返回(2, idx_BC)。否则，查找(C)是否存在，如果存在则返回(1, idx_C)。否则返回(0, 0)。

CSIMSlmWithIteration::findState(n, hw)：

寻找n-gram（长度为n，保存在hw[1..n]中）在level[n]上状态节点的下标。如果该n-gram没有找到，则返回-1。

在threading的过程中，还对32位浮点数进行了压缩。其中bow被压缩到14个bits，pr被压缩到16个bits。大致思想是，对在bow（或pr）中出现的所有浮点数进行统计，将距离比较近的浮点数进行“合并”，将浮点数的总数控制在1<<BITS_BOW（或1<<BITS_PR）内；在生成的语言模型二进制文件中，会有两个浮点数的表，通过查表来得到原来的浮点数值。我对这个算法的细节还不是很清楚，有机会请原作者张磊来讲解一下。

现在，我们就得到了最终的语言模型--lm_sc.t3g。你可以用tslminfo来查看它的信息：

$ make m3_tslminfo
./tslminfo -p -v -l ../raw/dict.utf8 ../data/lm_sc.t3g >../swap/lm_sc.t3g.arpa

$ tail ../swap/lm_sc.t3g.arpa
点击 率 也   0.036363638937 (2,839922)
点击 率 最高   0.081818044186 (2,840054)
点击 率 的   0.096969485283 (2,840080)
点击 率 达到   0.036363638937 (2,840122)
点击 量 达   0.485714286566 (2,1132198)
点击 鼠标 ，   0.400000005960 (1,1)
点击 鼠标 左   0.309090882540 (2,1186378)
率队 取得 <unknown>   0.479999989271 (2,366031)
率队 在 <unknown>   0.130769222975 (2,431213)
率队 打 了   0.479999989271 (2,642183)


我们可以通过CThreadSlm类来访问或使用它，下一节将以slmseg为例，看看如何利用最终生成的语言模型来进行搜索。