Export

View

SunPinyin代码导读-IME部分

NOTE: The input-method project is no longer active on this website so information here may be out of date. Current Oracle Solaris 11 product documentation can be found here. Information about downloading Oracle Solaris 11 can be found here.

0. 综述

这一部分主要介绍Sunpinyin中ime部分的代码。
要构建ime部分的代码，可以执行下面的操作：
$ ./autogen.sh --prefix=/usr --enable-debug --enable-gtkstandalone
$ make
使用--enable-gtkstandalone选项，会生成一个不依赖于输入法框架的演示程序，位于wrapper/gtk_standalone目录中。你可以通过这个演示程序来了解或调试Sunpinyin输入法的代码。我们后面的系列，也会从这个演示程序入手。
同时，在configure.ac中，--enable-cle是缺省打开的（你可以通过--disable-cle来关闭这个选项），因此在执行make时，还同时会为iiimf-cle（Chinese Language Engine）构建一个输入法模块，执行make install，会把它安装到/usr/lib/iiim/le/cle的目录下。如果要在Mac OS上编译，需要export LDFLAGS=-liconv。
Sunpinyin支持两种输入风格，“经典风格”和“及时转换风格”。“及时转换风格”和微软拼音的风格类似，用户在输入拼音时，只在preedit区域中显示当前的最佳句子，可以通过左右键，对其中任意不满意的部分进行编辑（即用户选择，user selection）。

“经典风格”和紫光拼音（以及后来的搜狗拼音、Google拼音）的风格类似。用户在输入拼音时，preedit区域中显示的是输入的拼音串（或用户选择），候选区中显示当前的最佳句子，以及拼音串开始部分的拼音可能得到的词和字。但这种风格下，第一次用户选择只能从拼音串的起始部分开始。

Sunpinyin采用了view/window-handler的结构。上述的两种风格，在代码中分别对应于两个视图（view）类：CIMIModernView和CIMIClassicView。所谓window-handler，就是view的一个callback类。ime/wrapper目录下有五个window-handler的实现，cle, scim, beos, macos和gtk_standalone。要将Sunpinyin移植到其它输入法框架或平台，主要的工作就是为其编写一个wrapper。
下一节，我们会介绍ime部分的概念模型（concept model）。

1. 概念模型

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

插图1

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。）

插图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

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

2. 数据结构及核心算法

下面，我们来介绍一下主要的数据结构，看看在程序中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;
它为搜索保存了两方面的状态数据。一是拼音词表（Pinyin Trie树）的若干状态，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）排序。
下面让我们来看看构造和搜索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来说，B3上有两个Lexicon状态，(B1, shi'pin')和(B2, pin')，可以用“食品”、“视频”、“饰品”等词来扩展B1上的Lattice节点，然后用“品”、“频”、“拼”等词再次来扩展B2上的Lattice节点，将新得到的状态节点加入到B3的Lattice状态节点集合中。

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

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

如果转移之后的状态节点，其历史（回退）节点为pseudo root节点（即level为0，表示平均分布），而最近的历史记录中却见到过这个词，则将这个pseudo unigram节点的index设置为wid；这样对下一个词w'，才能通过CThreadSlm::lastWordId(state)得到上一个词的ID（即wid），以正确计算Pcache(w'|wid)的概率值。
然后计算Pcache(w|h)，和Pslm(w|h)进行插值，得到句子的概率评分保存到node.m_Score中。将这个新的Lattice节点，插入到to Bone的Lattice状态节点集合latss2中（同时也进行了beam pruning）。

3. 处理候选

下面的数据结构和方法用来组织候选词列表（即如何利用搜索结果）：
class CCandidate：

[m_BoneStart, m_BoneEnd)是这个候选词对应的bone区间；m_WordID是候选词对应的id；m_String是宽字节字符串的指针。通常 m_String就是m_WordID对应的宽字节字符串表示，但有时候选词并不在词表中（例如无效的拼音串儿）。

CIMIContext::getCandidates (bone, result)：

如果bone是尾节点，则直接返回。如果不是一个有效的pinyin Bone节点，将bone上的拼音string作为候选，放到result中，并返回。如果这个bone上有用户选择或最佳词，设置cp（候选词和评分 pair），将它保存在以word_id为索引的map中。

然后遍历[bone+1, T1]。对每个Bone节点，遍历其lexicon状态节点，找到起始节点为bone的状态节点（itlex-> m_BoneStart == bone），将pytrie上的词（如果不是拼音节点，则是Bone上的拼音字符串）加入到map中；遍历其lattice状态节点，如果该节点是从参数bone上转移而来的（its->m_pBackTraceNode->m_BoneAfter == bone），则将m_BackTraceWordId对应的候选词，加入到map中。最后，按评分（TCandiRank），对这个map进行堆排序，将排序后的结果保存在result中。
评分的原则是：首先列出用户选择的词，或者位于最佳路径上的词；优先列出从Lattice状态中得到的词；然后是Lexicon中的词。且词的长度越长，评分越高。

CIMIContext::getBestSentence(result, boneStart, boneEnd, original_format)：

如果boneStart上没有最佳词，则向前（左）查找，直到某个存在最佳词的Bone，保存在realStart中。沿着最佳路径的这一段（[realStart, boneEnd)），将最佳词添加到result中，记录期间有效拼音节点的个数，并返回。

下面的方法，和用户选择的设定和取消有关：
CIMIContext::cancelSelection(bone, update)：

注意，m_Skeleton上的最佳词（无论是用户选择还是计算确定）是前后相连的。从bone开始向左查找。如果某个Bone（记为uBone）的类型为 UserSelectedBestWord，则将其改为NoBestWordStartHere，设置found为true，退出循环；否则，如果该 Bone是计算确定的最佳词，则退出循环；否则，则继续向左查找，直到第一个Bone。如果found为true，且update参数为true， uBone开始搜索，并返回它；否则，因为无需搜索，直接返回参数bone。将[firstBone, bone]这个区间离bone最近的用户选择取消。

CIMIContext::cancelSelectionCover(bone, update)：

这个方法和上面的类似，只是当参数bone的类型是最佳词时，直接返回。相当于将[firstBone, bone)这个区间离bone最近的用户选择取消。

CIMIContext::makeSelection(candi)：

找到候选candi的起始Bone（m_BoneStart），调用cancelSelection()将其所处的用户选择取消（返回值为boneLeft），并将候选起始Bone的类型设置为UserSelectedBestWord，然后从boneLeft重新搜索。

4. 用户编辑

这一节我们以以“经典风格”为例，介绍对User Editing（包括insertPinyin，erase，move cursor，selection等）的处理。
class [[CIMIClassicVIew>>http://src.opensolaris.org/source/xref/nv-g11n/inputmethod/sunpinyin/ime/src/imi_view_classic.h]] {
     m_CursorBone：当前光标所在的Bone
     m_CursorIdx：光标在m_CursorBone中的位置索引
     m_CandiBone：候选列表起始的Bone
     m_CandiFirst：当前窗口中第一条候选在整个候选列表中的索引
     m_TailSetence：从m_CandiFirst开始的尾句
};
考察下面的例子，m_CursorBone指向的是'yin'所在的Bone；m_CursorIdx为2，指向的是'n'所在的位置；而m_CandiBone指向的是'pin'所在的Bone；因为没有翻页，所以m_CandiFirst为0；而候选1，即“拼音输入”，就是m_TailSetence。

在经典风格中，向左移动光标，意味着用户可能要修正以前的UserSelection，因此要清除以前的用户选择并重新搜索。而向后移动，后续的可能操作是插入、删除和添加等操作，不影响当下的候选结果，因此不会重新进行搜索。
CIMIClassicView::moveHome(changeMask, searchAgain):

将[firstBone, m_CursorBone]内所有的用户选择都清除，返回开始新搜索的Bone节点。如果存在用户选择，则从firstBone重新搜索。如果不存在用户选择，则返回lastBone。

CIMIClassicView::moveLeft(changeMask, searchAgain):

如果m_CursorIdx（光标在m_CursorBone中的索引）大于0，则减去1，返回lastBone（即不影响当前的候选结果）。如果m_CursorIdx为0，并且m_CursorBone不是firstBone，则将m_CursorBone左移一个单位，如果移出了当前的候选词范围（也就是进入了前一个候选词范围），则调用m_pIC->cancelSelection()取消其所在的UserSelection，然后调用getCandidates()重新得到候选，将m_CursorIdx设置为m_CursorBone中拼音字符串儿的长度（如果m_CursorBone不是一个拼音类型的Bone，则m_CursorIdx为0）。最后，返回新搜索的起始Bone节点。

CIMIClassicView::moveLeftSyllable(changeMask, searchAgain):

过程和上面的类似，只不过移动是以Bone为单位的，且移动之后，m_CursorIdx设置为0。

CIMIClassicView::moveRight(changeMask):

如果m_CursorIdx尚未到达m_CursorBone的尾部，则m_CursorIdx++并返回。如果已到尾部，若m_CursorBone是一个拼音类型的Bone节点，则m_CursorIdx++（相当于一个音节的边界）；否则将m_CursorIdx设置为0，且m_CursorBone向右移动一个单位。最后一种可能（m_CursorIdx == m_CursorBone->m_String.size()），是光标位于音节边界上，将m_CursorIdx设置为0，且m_CursorBone向右移动一个单位，并返回。

CIMIClassicView::moveRightSyllable(changeMask):

将m_CursorBone向右移动一个单位，并相应地设置m_CursorIdx。

CIMIClassicView::moveEnd(changeMask):

将m_CursorBone移动到结尾。

CIMIClassicView::makeSelection(idx, mask):

idx是在当前候选窗口中的索引，和m_CandiFirst相加，得到在整个候选列表中的索引。如果idx<0，则提交preedit并重置IC，然后返回。如果idx在候选列表的范围内，则得到索引下的候选对象cand，调用m_pIC->makeSelection(cand)设置用户选择。将m_CandiBone指向cand的结束位置（还记得么，[m_BoneStart, m_BoneEnd)是候选词对应的区间），如果它是不是一个拼音节点且未到达尾节点，则将m_CandiBone向右移动。如果一直移动到了尾节点，则提交preedit并重置IC；否则，如果m_Cursor位于[cand.m_BoneStart, m_CandiBone)之间，则将m_Cursor指向m_CandiBone，且将m_CursorIdx设置为0。然后将m_CandiFirst设置为0，调用getCandidates()来得到新的候选。

CIMIClassicView::erase(bLeft, changeMask):

bLeft标识是向左还是向右进行删除。如果向左删除，则调用moveLeft()将光标向左移动一个单位。然后，如果m_CursorIdx指向的是音节边界的位置（即m_CursorIdx == m_CursorBone->m_String.size()），且当前光标是用户确定的边界，则调用m_pIC->modifyAndReseg()对该部分重新节点进行切分和搜索，如果这影响到候选列表，则调用getCandidates()重新获取；如果当前光标不是用户确定的边界，且要向右删除，则调用moveRight()将光标向右移动一个单位。如果m_CursorIdx并非指向音阶边界的位置，则修改光标内的拼音字符串，并调用m_pIC->modifyAndReseg()对该部分节点进行重新切分和搜索，如果这影响到候选列表，则调用getCandidates()重新获取。

CIMIClassicView::insertPinyin(keyvalue, changeMask):

如果m_CursorBone是最后一个Bone（也就是在尾部添加拼音字母的情况），则将keyvalue作为一个自动切分的拼音节点，加到一个新的列表skel中，并将m_CursorBone设置为skel.begin()，且m_CursorIdx为1（m_CursorIdx指向的是音阶边界，因为Bone中只有一个拼音字母）。如果m_CursorBone不是一个拼音节点，当m_CursorIdx>0时（通常不会发生这种情况），将[0..cursorIdx)、keyvalue、 [cursorIdx..end)这三个字符串构造为Bone，加入到列表skel中，cursor2自加，m_CursorBone指向中间的Bone，m_CursorIdx设置为1；当m_CursorIdx为0时，将keyvalue作为一个自动切分的拼音节点，加到一个列表skel中，并将m_CursorBone设置为skel.begin()，且m_CursorIdx为0。最后是插入拼音字母的情况，将m_CursorBone压入到skel中，且将keyvalue附加到当前Bone的拼音字符串的尾部，m_CursorBone为skel.begin()，m_CursorIdx自加，且cursor2自加。然后调用m_pIC->modifyAndReseg()对该部分Bone节点重新切分并搜索，如果这影响到候选列表，则调用getCandidates()重新获取。

还有其它的一些insert方法，例如insertNormalChar()、insertBoundary()，都会涉及到对Bone列表的修改，而重新进行切分搜索，并获取更新的候选列表。这里就不多作介绍了。

5. History Cache

这一节我们来考察History Cache：
class [[CBigramHistory>>http://src.opensolaris.org/source/xref/nv-g11n/inputmethod/sunpinyin/ime/src/ic_history.h#88]]{
     typedef unsigned                              TWordId;
     typedef std::pair<TWordId, TWordId>           TBigram;
     typedef TWordId                               TUnigram;
     typedef std::map<TBigram, int>                TBigramPool;
     typedef std::map<TUnigram, int>               TUnigramPool;
     typedef std::deque<TWordId>                   TContextMemory;
     TContextMemory          m_memory;
     TUnigramPool            m_unifreq;
     TBigramPool             m_bifreq;
};
从上面的定义可以看出，m_unifreq和m_bifreq分别保存了每个Unigram和Bigram出现在History Cache中的次数。而m_memory是一个双向队列，context_memory_size是其空间的上限，缺省为8K。
CBigramHistory::incUniFreq(ug):

将TUnigram ug的出现次数加1。

CBigramHistory::decUniFreq(ug):

如果m_unifreq map中存在这个unigram，且出现的次数大于1，则减1；如果出现次数已经为0，则将其从m_unifreq中删除，以避免m_unifreq这个map占用的空间过大。

CBigramHistory::uniFreq(ug):

如果ug不是stopword（在CBigramHistory::initClass()时初始化，且要和slm词典的id相一致），且存在于m_unifreq中，则返回这个key对应的value。否则返回0。

CBigramHistory::incBiFreq(bg):

将TBigram bg的出现次数加1。

CBigramHistory::decBiFreq(bg):

如果m_bifreq map中存在这个bigram，且出现的次数大于1，则减1；如果出现次数已经为0，则将其从m_bifreq中删除，以避免m_bifreq这个map占用的空间过大。

CBigramHistory::biFreq(bg):

如果bg不是<DCWID, DCWID>，且存在于m_unifreq中，则返回这个key对应的value。否则返回0。

CBigramHistory::memorize(its_wid, ite_wid):

将词的序列[its_wid, ite_wid)记录下来。首先我们要在当前的历史记录中，插入一个分割符（DCWID，相当于</s>），以和前一个流分隔开来；如果此时m_memory已经达到上限，则需将m_memory头部的一个词弹出，并且要减少相应unigram和bigram的出现次数。接下来，遍历[its_wid, ite_wid)，假定当前的词为Wi（i从0开始），将Wi加入到m_memory中，将Wi出现的次数加1，并将bigram <Wi-1, Wi>（W-1为DCWID）出现的次数加1；期间，如果m_memory达到了上限，和上面的操作一样，将头部的记录弹出。

当视图类调用doCommit()时，会调用这个方法将用户提交的候选句子记录下来。

CBigramHistory::bufferize(buf_ptr, sz):

将m_memory持久化到buf_ptr指向的缓冲区中，同时注意大端和小端的问题。而m_unifreq和m_bifreq并不保存。

CBigramHistory::loadFromBuffer(buf_ptr, sz)：

加载已持久化的History Cache，并统计unigram和bigram的出现次数。

CBigramHistory::seenBefore(wid):

如果wid不是分割符，且非stopword，同时存在于m_unifreq中，则返回true。

CBigramHistory::pr(bigram):

求P(bigram.second|bigram.first)的概率值。以Bigram <x, y>举例来说，uf0是C, bf为C(x, y)，而uf1是C。求解概率的计算公式为:

$P(y|x) = \lambda \frac{C(x,y)}{C(x)+0.5} + (1-\lambda) \frac {C(y)}{actual\_size + unused\_size/10} \\ (\lambda == 0.68)$
这个公式是Pml(y|x)、Pml thumb_up 的插值，0.5是为了平滑Pml(y|x)，而(actual_size + unused_size/10)是为了防止刚开始的时候history cache的size过小。最后这个概率值再和Pslm(y|h)进行插值，参见ime/src/imi_context.cpp#902。

CBigramHistory::pr(its_wid, ite_wid):

y = *(ite_wid-1)，x = *(ite_wid-2)，求P(y|x)。

CBigramHistory::pr(its_wid, ite_wid, wid):

y = wid, x = *(ite_wid-1)，求P(y|x)。

6. 杂项

TDoubleAnatomy and TLongExpFloat:

TDoubleAnatomy是一个union，用来把一个双精度的浮点数，分解为符号位、指数和尾数。这个方法适用于所有符合IEEE-754浮点数的平台。下面是双精度浮点数的二进制布局：
$http://blogs.sun.com/yongsun/resource/General_double_precision_float_frac.PNG$
这个浮点数对应的有理数为：

V = sign * 2^{exp} * (1.fract)

注意：其中指数使用的是移码，对双精度浮点数来说，指数是11位，因此实际的指数要减去2(11-1)-1，即0x3FF。TDoubleAnatomy::clearExp()方法将浮点数的指数部分清除（即设置为0x3FF），然后再调用TDoubleAnatomy::getValue()得到的双精度浮点数，就是sign * (1.fraction)，这也就是TLongExpFloat::m_base的值。且在Sunpinyin中，所有的概率值都不会出现负值。
直接使用double进行概率值的连续相乘运算，容易溢出。而TLongExpFloat表示的范围要大了很多，相当于将64位（1+11+52）的浮点数扩展到96位（32+64）。因此能缓解溢出的状况。TLongExpFloat重载了部分算术操作符，让我们可以像对一个primitive数据类型那样进行比较和乘除的操作（但不支持加减）。
你可能会问另外一个问题，为什么不用对数将乘法操作转换为加法呢？这是因为插值的原因，回忆一下插值的公式。如果使用对数，必须将对数形式的结果转换回来，才能执行加法。

处理计算bow时由于浮点数累加所造成的误差

在计算bow时（参见CalcNodeBow()），可能因为浮点数的连续相加造成的误差，而导致sumnext或sum出现大于1的情况，此时使用下面的公式计算bow：

原来要考察的是sumnext和sum离1.0距离的比值，现在因为误差的原因，两者都有可能稍稍超过1.0，因此将比较的基准点向右移动一些（即γ = Max(sumnext, sum)+δ，且δ是一个较小的值，0.0001）。

Tags:

Created by admin on 2009/10/26 12:14

Last modified by admin on 2009/10/26 12:14