sunpinyin輸入法

0. 輸入法的概念模型

讓我們來看看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

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的公式稍有不同。到時我們再具體說明。

1. 資料結構及核心算法

原先SunPinyin是使用CBone/CSkeleton來組織search lattice的，參見sunpinyin代碼導讀（九）。每一個Bone對應一個syllable（或者嚴格的說，是一個segment），而CSkeleton是CBone的雙向連結清單（std::list）。這個結構不太适合對模糊切分的支援。是以在SunPinyin2中，lattice不再以syllable為機關了，而是以單個的拼音字元為機關。

我們定義了一個CLattice的類，表示整個的search lattice，其對應于原來的CSkeleton。将每個column稱為一個CLatticeFrame，對應于原來的CBone/CBoneInnerData。而TLexiconState和TLatticeState和以前的差别不大，隻是把位置資訊從iterator換成了index。另外為了支援使用者詞典，在TLexiconState加入了一些相應的字段，例如m_words，m_syls。

CIMIContext類的主要入口是buildLattice (segments, rebuildFrom, doSearch)。rebuildFrom這個參數值其實就是IPySegmentor::updatedFrom() + 1，因為在lattice上，拼音字元串是從index 1開始的，而在切分器中是從0開始的。buildLattice周遊segments（由IPySegmentor::getSegments所傳回的），跳過rebuildFrom之前的那些segments，然後調用_forwardXXX方法，build每個目标frame上的lexiconStates。直到segments的結束或者超過一定長度，調用_forwardTail處理結尾。然後，在doSearch為true的情況下，調用searchFrom進行搜尋。

CIMIContext類中的_forwardXXX方法，和原來的forwardXXX方法大同小異。_forwardSingleSyllable中對使用者詞典做了一些額外的處理。因為我們現在的使用者詞典是基于sqlite實作的，不是一棵trie樹，是以和基于trie樹的系統詞典處理起來有所不同。例如，使用者詞典中有“測試拼音”這個詞，當使用者輸入到ceshipin的時候，從資料庫中得到的詞的清單是空的，且對系統詞典（CPinyinTrie）的transfer也會傳回一個空節點。但這種情況下，我們不能drop掉ceshipin這個音節序列，還是要把它加入到目标latticeFrame的lexiconStates中。

CIMIContext::searchFrom也和前作基本相同，都是通過frame上的lexiconStates，調用transferBetween方法來建構latticeStates，同時調用語言模型進行句子的評分。最後調用backTraceBestPath，把最佳路徑辨別出來。稍有不同的是，searchFrom對fuzzyForwarding進行了一些處理，收窄了易混淆音節的搜尋範圍，并降低了其初始的評分。

其他的方法，例如_transferBetween, getBestSentence, getCandidates都和之前的實作大體相同。cancelSelection和makeSelection得到了簡化。memorize方法加入了将<=6個字元的短句（其中含有使用者選擇的），作為使用者詞條儲存的功能。

另外CIMIContext有兩個助手類，CGetFullPunctOp和CGetFullSymbolOp，用來處理标點符号和字元的全角轉換。這兩個類也是可配置的，并且CIMIContext的所有執行個體都share同一份拷貝。是以，也屬于shared & global的配置選項。

新版本的CIMIContext，在将拼音切分剝離之後，其職責更加明确和清晰；采用新的資料結構之後，邏輯也更簡單和直覺。代碼行數也由原來的1.5k下降到0.6k；同時可配置性也得到了提升。

2. History Cache

這一回我們來考察History Cache：

class CBigramHistory{
    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(x), bf為C(x, y)，而uf1是C(y)。求解機率的計算公式為:

這個公式是Pml(y|x)、Pml(y)的插值，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)。

3. 使用者詞典

原先的SunPinyin沒有使用者詞典，隻是通過User History Cache紀錄了使用者近期輸入的bi-gram資訊。如果一個bi-gram，其機率比系統詞典的某個uni-gram要低，這個bi-gram的組合就不會出現在使用者的候選清單中。例如，雖然使用者頻繁的輸入鑰匙，但是它依然很難出現在候選清單中，因為“要是”這個unigram的機率要更高。如果“鑰匙”出現在候選中，一定是第一候選，因為它是作為一個最佳候選句子來呈現給使用者的。如果使用者選擇了“要是”，那麼“鑰匙”又不知道要過多久才能出現了。這個缺陷也是廣受大家诟病的地方。其實，SunPinyin原先的架構是支援将使用者自定義詞放到lattice上進行搜尋的。

我們在SunPinyin2中，通過sqlite3來實作使用者詞典，目前我們的使用者詞典支援記錄<=6個的字元。

CUserDict::createTable/createIndexes:

這兩個私有方法嘗試建立一個table和index。這個表的結構是，首先詞的ID（從1開始的）和長度，接下來是6個聲母，然後是6個韻母，再其次是6個聲調。然後我們為長度＋6個聲母建立了一個索引。sqlite的query對搜尋條件和index有一些限制，要求條件的次序和index的次序相同，并且一旦某個條件是非相等性的（例如>），則該條件及其之後的條件都無法用index來加速。另外，每個from子句隻能使用一個index。

因為我們經常會有不完整拼音的查詢，或者換句話說使用者經常會輸入不完整拼音，是以table和index就被設計成了這個樣子。

CUserDict::addWord (syllables, word):

使用了sqlite中的prepared statement來進行插入。最後，在插入成功的情況下，調用sqlite3_last_insert_rowid得到上一次插入記錄的row id，加上一個offset并傳回。如果失敗，就傳回0。

CUserDict::removeWord (wid):

這個相對簡單，按照wid将記錄從資料庫中删除。

CUserDict::getWords (syllables, result):

這個方法将syllables在資料庫中對應的記錄，放到result中。我們傳回的詞id類型，和系統詞典的保持一緻，都是CPinyinTrie::TWordIdInfo。這裡再解釋一下，使用者詞典的最大容量為什麼是6萬多個。這個就是由于CPinyinTrie::TWordIdInfo的m_id的長度決定的，是2^18-1。

我們按照sqlite的限制，小心翼翼地組織好查詢的where子句，查詢，然後疊代結果，填充results，最後傳回。

CUserDict::operator (wid):

這個方法也相對簡單，就是傳回wid對應的字元串。因為sqlite隻支援utf8和utf16，而且utf16還要使用一套不同的接口，是以我們還是使用utf8作為資料庫内的字元串編碼。而sunpinyin-ime要求的是ucs-4編碼的字元串，是以還要進行一個編碼轉換。同時把(wid, wstr)這個pair加入到m_dict中。wstr是動态配置設定的，由m_dict在析構時釋放。這裡還利用了這樣一個事實，std::basic_string是COW的。我們在m_dict中儲存的其實是wstr的拷貝，不過這個拷貝和wstr共享同一個C string的buffer。

4. 使用者配置

SunPinyin2在設計和實作的過程中，希望能同時支援簡體、繁體的詞典及語言模型，支援不同的拼音方案，支援不同的輸入風格（包括微軟拼音和類似sogou或google拼音）。不同的輸入風格，對應了不同的view的實作。（雖然目前SunPinyin2還沒有重新實作微軟拼音的輸入風格——CIMIModernView。）

這些選項組合起來數目繁多，不過它們都是正交的，正好可以讓我們使用policy based的實作方式。

我們定義了一個CSunpinyinProfile的模闆類，它繼承了ISunpinyinProfile這個公共接口類（否則我無法聲明一個儲存其指針的container），和它的三個模闆參數，LanguagePolicy，PinyinSchemePolicy，InputStylePolicy。它的createProfile方法，調用policy類中的相關方法，來建立具體的一個view執行個體。為了避免建立policy的執行個體，并且更重要的是要共享policy的公共資料，policy類都是單件（singleton）。

LanguagePolicy負責初始化詞典、使用者詞典和語言模型，以及根據這些資源建立CIMIContext類的執行個體。CSimplifiedChinesePolicy是一個具體的實作。另外還有一些方法，可以讓你設定CIMIContext類執行個體的預設屬性。例如，enableFullPunct和enableFullSymbol，setPunctMapping方法設定s_getFullPunctOp（被所有由該policy類建立的CIMIContext執行個體所共享）的标點符号影射。我們之前總結為shared & global的使用者配置項。可以設想，使用者在設定對話框自行定義标點符号的映射關系後，程式員隻需要調用CSimplifiedChinesePolicy::setPunctMapping。這個配置項的更改會應用到所有現有的輸入上下文（或會話），對輸入上下文來說是透明的。

PinyinSchemePolicy負責建立拼音切分器的執行個體。CQuanpinSchemePolicy和CShuangpinSchemePolicy是兩個具體的實作。以CQuanpinSchemePolicy類為例，createPySegmentor方法建立了CQuanpinSegmentor的一個執行個體并傳回。和CSimplifiedChinesePolicy類似，CQuanpinSchemePolicy也有一些shared & global的配置項，例如是否支援易混淆音和自動糾錯。

InputStylePolicy負責建立CIMIView的執行個體。CClassicStylePolicy是一個具體的實作。它隻是簡單的建立一個CIMIClassicView的執行個體并傳回。CSunPinyinProfile<…>::createProfile方法雖然也是傳回一個view的執行個體，不過這個view是已經設定停當、可以工作的view。

CSunpinyinSessionFactory是一個singleton的工廠類，其createSession方法根據factory中policy的設定，調用某個CSunpinyinProfile執行個體的createProfile方法，建立一個具體的view。要添加新的語言支援或拼音方案，不僅要完成自己的那部分coding，還要記得編寫相應的policy classes，并将支援的所有組合注冊到CSunpinyinSessionFactory中（沒辦法，在這個地方就隻能窮舉了）。

因為我們最後expose給外部的是一個view的執行個體，是以如果使用者的配置涉及到對policy的切換（我們之前總結為non-shared but global的配置項），以前建立的輸入上下文（即view），就面臨一個抉擇。要麼保持不變，繼續使用其目前的輸入風格；要麼要重新建立，discard掉以前上下文的狀态資訊（例如preedit/candidates）。通常，我們對某個平台的移植，都是建立一個包含view的會話類，這個會話類适配該平台的接口，并将輸入事件filter給view。那麼我們的這些會話類是如何知道發生了non-shared but global選項的改變呢？

CSunpinyinSessionFactory類提供了一個簡單的方法，updateToken/getToken。當平台相關的會話類調用CSunpinyinSessionFactory類建立一個view的執行個體，同時應該調用getToken得到一個token（密碼）。當會話類得到焦點的時候，它可以調用getToken再次得到一個token，比較與自己持有的這個token是否一緻。如果不一緻，就表明發生了non-shared but global選項的更改。與此相對應地，如果使用者對non-shared but global的選項發生了修改，程式員應該要調用updateToken去更新factory目前的token。

這個方式有些醜陋，稍微改觀一點的方法可能是，我們再加入一個抽象層次，例如CSunpinyinSession，然後它用signal/slot的方式connect到factory的reset_session信号。另一個問題，配置項還是比較分散，如果要編寫一個集中的CSunpinyinOption類的話，就會有很多duplicated的代碼。我對上面這些問題，還沒有想得很清楚，也非常歡迎大家多提寶貴意見！:)

5. 雜項

TDoubleAnatomy and TLongExpFloat:

TDoubleAnatomy是一個union，用來把一個雙精度的浮點數，分解為符号位、指數和尾數。這個方法适用于所有符合IEEE-754浮點數的平台。下面是雙精度浮點數的二進制布局：

這個浮點數對應的有理數為：

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

注意：其中指數使用的是移碼，對雙精度浮點數來說，指數是11位，是以實際的指數要減去2(11-1)-1，即0×3FF。TDoubleAnatomy::clearExp()方法将浮點數的指數部厘清除（即設定為0×3FF），然後再調用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）。

轉自https://code.google.com/p/sunpinyin/wiki/CodeTourOfIME