素心如何天上月 (Yong Sun's Blog): Yong Sun's Blog

我们上一回中，已经得到了线索化（threaded）的语言模型。那么如何来访问或使用这个模型呢？让我们看看slm.h文件，CThreadSlm类的public方法，只有下面几个：

1. load()：将语言模型加载到内存中
   
2. free()：释放语言模型所占据的内存
   
3. isUseLogPr()：是否使用log值作为概率值
   
4. transfer(history, wid, result)：从历史状态history，给定输入wid，转移到一个新的状态result，并返回P(wid|history)的概率值。
   
5. transferNegLog(history, wid, result)：和上面的方法一样，只不过返回的是-log(p(wid|history)。
   
6. history_state_of(st)：求得状态st的h'，并返回。
   
7. historify(st)：将状态st设置为它的h'。
   
8. lastWordId(st)：返回状态st的最后一个词的id。设st为(lvl, idx)，如果lvl>=N，则返回m_Levels[N][idx]；如果0<lvl<N，则返回m_level[lvl][idx]；如果lvl==0，且idx==0，则返回pseudo root的wid（即0），但如果idx>0，就返回idx（我们将来在介绍输入法的history cache时，会涉及到这种情况）。
   

让我们看看slmseg如何使用CThreadSlm类来进行基本的搜索。

$ make slmids3
./slmseg -d ../raw/dict.utf8 -f bin -s 10 -m ../data/lm_sc.t3g ../raw/corpus.utf8 >../swap/lm_sc.ids

来看slmseg/slmseg.cpp的代码：

struct TLatticeWord {
  int m_left;
  int m_right;   //[m_left, m_right)为这个词在lattice上的位置范围
  int m_wordId;  //词的ID
};

struct TLatticeStateValue{
  double             m_pr;       //该状态节点上的概率值。
  TLatticeWord*      mp_btword;  //回溯的(back-trace)词，即由哪个词跳转到当前状态的
  CThreadSlm::TState m_btstate;  //回溯的(back-trace）状态节点，即由哪个状态跳转过来的
};

/* 语言模型的状态节点，及其状态信息 */
typedef std::map<CThreadSlm::TState, TLatticeStateValue> TLatticeColumnStates;

/* 表示lattice上的一列 */
struct TLatticeColumn {
  TLatticeWordVec m_wordstarting;  //起始于该列上的词。其实就是在扩展本列状态节点时，将要输入的词。
                                   //转移得到的新状态节点，位于后面的lattice[word.m_right]上。
  TLatticeColumnStates m_states;   //该列上的状态节点及其对应的状态信息
};

processSingleFile()：

逐句读取文件。对每个句子，调用buildLattice()构建搜索需要的lattice（栅格），然后调用searchBest()进行搜索，通过getBestPath()得到最佳的切分，最后调用output()将其输出。

buildLattice(sentence, lattice)：

将lattice[0]上的状态，设置为pseudo root。将i初始化为0，对sntnc[i..n]进行最大正向匹配，得到词长len。然后调用getAmbiLen()得到最大交集歧义长度ambilen。如果ambilen<=len，则无交集歧义，调用insertLatticeWord()，将分词得到的词([i,i+len),Wid)，加入到lattice[i]的词列表中；令i=i+len，继续循环。如果有歧义，则调用fullSegBuildLattice()，对sntnc的[i..i+ambilen)子句进行全切分，将所有可能的词划分（包括所有的单字词），假设其位置为[left, right)，加入到lattice[left]中；然后i=i+ambilen，继续循环。遍历完整个句子之后，在最后面加入一个句子结束的标识（下面的例子中，我们用“。”来表示）。

我们还借用第二回中的例子：

对例句进行最大正向匹配，得到的词为“发扬”，且无歧义，则将“发扬”加入到lattice[0]上的词列表中。然后i=2，继续循环。FMM得到的词是“为人民”，但是歧义长度为6，则需要对sntnc[2..7]进行全切分。将idx由2向7移动，将idx上所有可能的词（包括单字词），加入到lattice[idx]中。然后i=2+6=8，继续循环。FMM得到的词为“的”，且无歧义。然后i=9，最大正向匹配得到的词为“精神”，且无歧义。循环结束，最后在末尾加上一个句子结束的ID。可以看到lattice[1]上没有词，而lattice[2]中的词有：“为”、“为人”和“为人民”。依次类推...

从0开始，遍历lattice。对lattice[i]上的所有状态节点，用该列上的各个词([left, right), Wid)，来扩展它（调用CThreadSlm::transferNegLog()），将新状态节点的h'（CThreadSlm::historify(his)），保存在lattice[word.m_right].m_states中。注意，两个不同的状态节点，例如(A, C)和(B, C)，给定一个输入词D，可能得到相同的h'（即(C, D)），那么这两条路径中只保留概率大者就可以了。

首先从lattice[0]的states开始，我们在buildLattice()时，已经将它设置为pseudo root节点(0, 0)了。lattice[0]上只有一个词，“发扬”；调用CThreadSlm::transferNegLog((0,0), wid_of("发扬"))，得到新的状态节点和概率值（P("发扬")），将该节点的h'（lvl=1, idx)，及其状态信息（概率值和回溯信息），放到lattice[2]上。然后查看lattice[1]，它上面没有要扩展的状态节点。进而判断lattice[2]，有一个状态节点，并有三个词（“为”，“为人”，“为人民”），将三个新的h'状态节点，分别保存在lattice[3]，lattice[4]和lattice[5]上。依次类推...

这是一个动态规划（dynamic programming）问题，这里使用的是Viterbi网格（Viterbi Lattice）算法。

从后向前，回溯lattice，将回溯的词id放到segResult中。最后再将segResult翻转一下，就得到了最佳的切分。对本例来说，就是上图中的蓝色路径。