SunPinyin代码导读(九)

让我们来看看ime部分的概念模型(concept model):

插图1


Static SLM,Lexicon:
我们在前面介绍slm部分的代码时已经了解过了。访问统计语言模型和拼音词表的代码,分别位于ime/src/slmime/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。)

插图2


Lattice Builder
:对每个有效的音节,从Lexcion及History Cache中查到对应的词(通常有很多个),将它们放到Lattice上。Lattice的宽度会影响搜索的速度。在这里会进行了一定的剪枝(pruning):优先将History Cache中的词放到Lattice上;再将Lexicon中出现频率较高的词,也放到Lattice上。上图中,蓝色加粗显示的竖线,就是Lattice的一列(或称为frame)。如果我们从左向右对Lattice的列进行编号,L0是<S>(即句子开始),L1上的词有(西,戏,系,喜),L2上的词有(安,案,暗,先,现,西安),L3上的词有(是,市,示,使,西安市,暗示)... 我们也可以将每个拼音字母作为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这一列了。如颜色较浅的第二行所示。

插图3


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


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

下面,我们来介绍一下主要的数据结构,看看在程序中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中的示例来说,B2(由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中的示例来说,B0上的LexiconStates为空,B1上为[(B0, ce')](ce'表示Pinyin Trie树上的一条边,即c-e-'),B2上为[(B0, ce'shi'), (B1, shi')],B3上为[(B1, shi'pin'), (B2, pin')](因为在ce'shi'这个节点的子树中,不存在pin'这条子边;而在shi'的子树中存在)... ...

struct TLatticeState;
m_Score是该节点上的概率值。m_BoneAfter就是该Lattice节点所在Bone,例如插图3示例中的B4[3]节点(B4那一列最下面那个节点),其m_BoneAfter就是B4;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部分的代码。

One thought on “SunPinyin代码导读(九)

Leave a Reply

Your email address will not be published. Required fields are marked *

To submit your comment, click the image below where it asks you to...
Clickcha - The One-Click Captcha