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

这一回我们来考察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)。求解概率的计算公式为:



这个公式是P_ml(y|x)、P_ml(y)的插值，0.5是为了平滑P_ml(y|x)，而(actual_size + unused_size/10)是为了防止刚开始的时候history cache的size过小。最后这个概率值再和P_slm(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)。

这个blog系列终于要接近尾声了，下一回再介绍一些边角料的东西。