本来计划这一回介绍主要数据结构的，但是出于篇幅和连贯性的考虑，把它们附到上一回了。这一回主要介绍构造和搜索Word Lattice的方法。

CIMIContext类是整个ime部分代码的核心，对应上一回中的概念模型，它充当了Syllable Segmentor、Lattice Builder和Context Searcher的角色：

CIMIContext::modifyAndReseg (boneStart, boneEnd, skel, cursor, cursorIdx, candiStart)：

实际使用时，boneStart、boneEnd、candiStart均指向m_Skeleton中的节点。调用segPinyin()，对参数skel中的诸Bone节点（外加boneStart之前的2/3个节点，避免切分的不充分），和[boneEnd, T1-1)进行重新切分，得到的结果保存在newskel中。重新计算cursor及其index。然后调用modify(its, T1-1, newskel)，重新进行搜索。

CIMIContext::segPinyin (head1, tail1, head2, tail2, newskel)：

[head1, tail1)和[head2, tail2)在逻辑上组成一个待切分的拼音串儿。实际使用时，[head2, tail2)是CIMIContex::m_Skeleton中的节点。将切分的结果保存到newskel变量中。

CIMIContext::modify (boneStart, boneEnd, skel)：

将[boneStart, boneEnd)中的bone从其所在的skeleton列表（即m_Skeleton)中删除，将参数skel中的bone插入其间。调用searchFrom()，从新插入的Bone开始，重新进行搜索。

CIMIContext::searchFrom (boneStart)：

遍历boneStart到第二个尾节点（T2），根据前一个Bone，调用forwardXXX()方法扩展自己的Lexicon状态节点，然后调用buildLatticeStates()构造自己的Lattice状态节点。遍历结束之后，回溯得到最佳路径。

从某一个bone开始进行搜索，意味着从这个Bone到T2，每个Lattice Frame上原有的Lexicon和Lattice状态节点都被清空并重新计算。

CIMIContext::forwardOnePinyinBone (bone)：

将该bone的后续（boneNext）中的Lexicon状态节点集合（lexss2）清空。遍历bone上的Lexicon状态节点，用本bone上的拼音字符串，尝试扩展它，并将新的Lexicon节点加入到lexss2中。迭代结束之后，尝试用bone上的拼音字符串，从Pinyin Trie的根节点进行扩展，并加入到lexss2中。最后返回boneNext。其它的forwardXXX()方法比较简单，这里就不多介绍了。

CIMIContext::buildLatticeStates (bone)：

得到bone的前继bonePrev（这意味着传入的参数不能是第一个Bone节点），清空bone的Lattice状态节点。遍历当前bone的Lexicon状态节点，找到该节点的起始bone，对Pinyin Trie节点上对应的词表，调用transferBetween（boneFrom, boneTo, wid, 1.0)，构造bone上的Lattice状态节点。

对上一回的插图3来说，B₃上有两个Lexicon状态，(B₁, shi'pin')和(B₂, pin')，可以用“食品”、“视频”、“饰品”等词来扩展B₁上的Lattice节点，然后用“品”、“频”、“拼”等词再次来扩展B₂上的Lattice节点，将新得到的状态节点加入到B₃的Lattice状态节点集合中。

CIMIContext::transferBetween (from, to, wid, ic)：

得到from Bone的Lattice状态节点集合latss1。遍历latss1，对每个LatticeState节点，用其中保存的SLM状态节点m_State（即后续Lattice状态节点的history），调用CThreadSlm::transfer()来计算P_slm(wid|history)的值。

如果转移之后的状态节点，其历史（回退）节点为pseudo root节点（即level为0，表示平均分布），而最近的历史记录中却见到过这个词，则将这个pseudo unigram节点的index设置为wid；这样对下一个词w'，才能通过CThreadSlm::lastWordId(state)得到上一个词的ID（即wid），以正确计算Pcache(w'|wid)的概率值。

然后计算P_cache(w|h)，和P_slm(w|h)进行插值，得到句子的概率评分保存到node.m_Score中。将这个新的Lattice节点，插入到to Bone的Lattice状态节点集合latss2中（同时也进行了beam pruning）。

下一回我们会介绍如何利用搜索的结果，以及对用户选择的处理。

让我们来看看ime部分的概念模型（concept model）：

Static SLM，Lexicon：我们在前面介绍slm部分的代码时已经了解过了。访问统计语言模型和拼音词表的代码，分别位于ime/src/slm和ime/src/lexicon目录中。这里就不多介绍了。

View：由Window-Handler接收用户的输入，通过回调（call-back），将pre-edit string和candidates返回给Window-Handler来进行显示。用户的按键输入，可能会对当前的拼音串儿进行添加、删除、插入等操作，然后将拼音串儿传递给Syllable Segmentor进行音节切分。在用户提交（commit）候选句（或词）之后，它要更新History Cache来记录用户最近的输入。如果用户通过数字键对候选进行了选择，它要通知Lattice Builder对用户选择进行相应的处理（给用户选择的词一个很高的评分。并不是将用户选择之外的词及由它们转移得到的状态从Lattice上删除，因为用户后面的编辑可能会取消该选择，保留这些信息可以节省重构建Lattice的工作量）。

Syllable Segmentor：使用Lexicon，对拼音串进行切分。因为切分可能存在歧义，例如mingan可以切分为ming'an或min'gan，故而生成一个Syllable Graph，将其传递给Lattice Builder。（不过，目前的实现尚不支持模糊音节切分，用户需要通过输入'键来明确指定音节边界，所以Graph目前只是一个List。就下面的示例来说，得到的切分结果为xian'shi'min'gan。）

Lattice Builder：对每个有效的音节，从Lexcion及History Cache中查到对应的词（通常有很多个），将它们放到Lattice上。Lattice的宽度会影响搜索的速度。在这里会进行了一定的剪枝（pruning）：优先将History Cache中的词放到Lattice上；再将Lexicon中出现频率较高的词，也放到Lattice上。上图中，蓝色加粗显示的竖线，就是Lattice的一列（或称为frame）。如果我们从左向右对Lattice的列进行编号，L₀是<S>（即句子开始），L₁上的词有（西，戏，系，喜），L₂上的词有（安，案，暗，先，现，西安），L₃上的词有（是，市，示，使，西安市，暗示）... 我们也可以将每个拼音字母作为Lattice的一个frame，这样并不会增加许多内存上的开销，而且对将来的插入删除操作更为方便。

Context Searcher：对得到的Word Lattice进行搜索。我们设置beam width（缺省为32），来限制每个Lattice frame上状态节点的数目。某些得分比较低的状态，可能就被剪枝掉了（例如下图中带红叉的节点）。如我们在第六回所讲的，这是一个动态规划问题，其搜索的复杂度为O(B*C*N)，其中B为beam width，C为Lattice每一帧上词的平均个数，N是Lattice的长度。因为两处都进行了剪枝，得到结果的可能并不是最优解。

另外要注意，在下图中（目前的实现），每个音节下面的状态节点，是属于前一个音节的。这种结构是不适用于Syllable Graph的。我们需要一个单独的、共有的起始帧，这样就不需要T2这一列了。如颜色较浅的第二行所示。

History Cache：记录用户最近提交的句子。这里使用的是一个类Bigram的模型。在计算P(z|xy)时，用P_smooth(z|xy)和P_cache(z|y)来插值得到。而P_cache(z|y)，是P(z|y)的MLE (Maximum Likelihood Estimation)，和P(z)的MLE的插值。

注：在实现中，计算P_cache的公式稍有不同。到时我们再具体说明。

下面，我们来介绍一下主要的数据结构，看看在程序中Lattice是如何表示的。

class CBone;
CBone类对应于Word Lattice上的一个frame。CBone的public成员包括，m_BoneType（表示Bone的类型，拼音或标点等），
m_BoundaryType（表示边界的类型，是自动边界或用户指定的边界等），以及m_String（如果是拼音节点，就是这个syllable的拼音字符串）。它还有一个protected成员，CBoneInnerData *m_pInnerData，这个数据结构记录了属于前一个Bone的Lattice信息（参见插图3）。CIMIContext是CBone的友类，可以访问这个保护成员。

class CSkeleton;
Bone的列表，即std::list<CBone>，就是我们上面所说的Syllable List。例如插图三中的列表，[ce]-[shi]-[pin]-[yin]-[shu]-[ru]-[T1]-[T2]，除了T1和T2，所有的Bone都是拼音类型的Bone。

class CBoneInnerData;
它为搜索保存了两方面的状态数据。一是拼音词表（PinyinTrie树）的若干状态，m_LexiconStates，当新的拼音Bone加入之后，我们通过尝试扩展它们来判断是否存在更长的词可以加入Lattice。其二是Lattice的若干搜索状态，m_LatticeNodes，这些状态可以用后续Bone中的词来扩展。最后还包括与用户交互相关的成员变量：这个Bone是否位于最佳路径上；如果是，该Bone上的最佳词（m_BestWord）。就插图3中的示例来说，B₂（由0开始从左到右编号）处于最佳路径上，且其m_BestWord为“拼音”。

class CLexiconState;
m_pPYNode是Pinyin Trie上节点的指针，m_BoneStart记录了这个拼音节点是从哪个Bone开始的，如果该状态不是一个PINYIN节点（m_bPinyin == False，例如标点等），则直接使用m_WordId。

class CLexiconStates;
即std::vector<CLexiconState>。我们并不需要像插图2那样，将实际的词放到Lattice上。因为随时可以从Pinyin Trie树的节点上得到按unigram排序的词列表。对插图3中的示例来说，B₀上的LexiconStates为空，B₁上为[(B₀, ce')]（ce'表示Pinyin Trie树上的一条边，即c-e-'），B₂上为[(B₀, ce'shi'), (B₁, shi')]，B₃上为[(B₁, shi'pin'), (B₂, pin')]（因为在ce'shi'这个节点的子树中，不存在pin'这条子边；而在shi'的子树中存在）... ...

struct TLatticeState;
m_Score是该节点上的概率值。m_BoneAfter就是该Lattice节点所在Bone，例如插图3示例中的B₄[3]节点（B4那一列最下面那个节点），其m_BoneAfter就是B₄；Bone和TLatticeState是一个1:n的关系，我们可以很容易地遍历得到Bone下所有的Lattice状态节点，而这个反向引用是为了方便回查。m_State是CThreadSlm上的状态节点（即后续Lattice状态节点的history），当前节点是由m_pBackTraceNode通过m_BackTraceWordId转移得到的。这里顺便提一下
Sunpinyin的coding style，以C开头的类型是class，以T开头的类型是struct或union。

class CLatticeStates;
这个类实际上是CLatticeStateVec（即std::vector<TLatticeState>）的一个包装类（wrapper）,设置了最大容量（即beam width，缺省为32）。其内部使用了堆（heap）排序。

下一回，我们将介绍构造和搜索Lattice部分的代码。