之前第一篇主要介绍了关于 beam search 和输入切分相关的内容，以及提供的一些基础数据结构。接下来主要着重补全介绍上次没有提及的 UserLanguageModel 和 HistoryBigram 的实现细节。
声明，本文需要的很多前置知识都可以在大学本科的自然语言处理类课程找到，关键词「统计语言模型」，「N-gram」。概括的说，N-gram模型是对现实语言的不精确概括，它不关心语法，只关心词与词之间出现的频率，尽管不精确，但对于输入法，机器翻译，语音识别等等领域都有不错的效果。
首先上一篇当中提到了我们的输入法的算法核心是 N-gram 和 beam search。一般对采用这种算法的输入法来说，N会取 3 或者 2。可以取得效果和内存占用的平衡。这里姑且来说我们也继承了一部分 Sunpinyin 的精神，因为最初最初的数据就是采用 Sunpinyin 使用的 Open-Gram。当然这里顺便一提，在最新的版本我们重新用全新的数据训练了语言模型。但依然采用了和 Sunpinyin 一样的 Trigram。
HistoryBigram，顾名思义，是一个存储用户输入的 Bigram。它干的事情其实非常之简单，就是把用户的输入的句子根据词一条一条的储存起来。而在内存中，它被存储在 DATrie 中。你也许想问一个问题，就是 DATrie 抽象起来看，可以被看作一个字符串到 4 byte 数据的映射，那么它究竟是怎么存储 Bigarm 这样有两个级别的 Key 的映射表呢？
答案其实很简单，就是你把 Key 做特殊的编码让它能够承载更多的内容。简单的把两个字符串加一个分割符拼成一个就可以了。Bi-gram 和 Uni-gram 计算得分的公式也是来自 Sunpinyin 。最直 的来说，Bigram 的概率应该是 P(B|A) = Freq(AB) / Freq(B) 也即出现 AB 的次数除以 A 出现的次数。对于没有 AB 的情况只会得到 0。这对于一个模型来说效果并不好，语言模型会采取平滑（Smoothing）来保证即使数据很稀疏（用户输入的历史是很少的），也能得到有意义的结果。这里就是把 B 单独出现的次数也拿来做一个加权平均。来减少因为采样而导致的数据缺失。
而这距离实际的输入法的情况，还有两个问题亟待解决。1、如何混合系统模型和用户模型，2、如何保证用户的输入能够快速在排序上体现效果。
第一个问题，尽管不精确，但是我们采用的方式是两个概率值加权平均。当然这里也小提一下 sunpinyin 的实现。在最初实现 libime 的时候，很多具体的细节的方案都尝试参考了 sunpinyin 的做法，但也发现了 sunpinyin 很多「奇怪的设计」。例如概率值为了减少浮点数运算，通用的做法都是采用对数概率，这样概率的乘积就是简单的求和了，效率要高的多。但 sunpinyin 的概率权重却是用对对数概率计算加权的算术平均，这就非常奇怪了（很奇怪也不太符合数学）。libime 这里就采用了至少道理上更说得通的原始概率计算算术平均。不过这里有一个小问题，假设你有了 log(P_sys) 和 log(P_user) 怎么计算 log( w * P_sys + (1 – w) * P_user) 的问题。
如果你直接计算的话，我们代换一下数字就可以得到 log(a * pow(10, log(P_sys)) + (1 – a) * pow(10, log(P_user)))，总共调用了 3 次 math 的函数。能不能减少一些呢？其实是可以的。
假设我们需要计算 log10(exp10(a) + exp10(b)) log10(exp10(a) + exp10(b)) = log10(exp10(b) * (1 + exp10(a - b))) = b + log10(1 + exp10(a - b)) = b + log1p(exp10(a - b)) / log(10)
得到上面的公式之后，为什么特意弄出 log1p(exp10(a-b)) 的形式呢？是因为标准库中提供了这样一个函数 log1p10exp，可以一步到位计算这个数值。为了更加精确，可以根据 a b 相对大小来选择是 a – b 还是 b – a。其中 log(10) （e为底）这种常数都可以预先计算，就将 math 库函数调用精简到了 1 次。
可能你会问，原本公式的 w 和 (1 – w) 的权重去哪了呢？这个问题也很简单，你只需要把他们先转化为对数计算即可。
log10(w * exp10(log_sys) + （1-w) * exp10(log_user)) = log10(exp10(log10(w)) * exp10(log_sys) + exp10(log10(1-w)) * exp10(log_user)) = log10(exp10(log10(w) + log_sys) + exp10(log10(1-w) + log_user))
这样就可以完美带入到之前的公式当中了。log10(w) 和 log10(1-w) 对输入法来说也都是常数，可以直接计算。
另一个问题就是如何保证用户「新」输入的内容能够快速排序到结果的前列。sunpinyin 的做法我做了一定的参考，但是理性上觉得不太合理所以根据情况优化了一下。sunpinyin 只记录 1024 个词在历史当中，当有新的词进入历史的时候，会踢出老的历史。这个设计让用户输入不会偏离系统输入太远，但也会相对影响用户历史的记录。然后最近输入的一些词的频率会乘以一个系数，来变相增加新输入的内容的权重。但这个范围的数字其实很小，可能会导致这部分改变结果顺序的行为很快被遗忘。
libime 这里采取了类似但做了一些自己的改进。第一，将用户输入的词按句子记录，第二，将用户输入的句子分成三个不同大小的 pool （128，8192，65536），每个 pool 给予不同的概率权重。（具体的数字的选择纯粹就是所谓的 heuristic 的了），这样相对保证记住的历史较多（65536个句子 vs 1024 个词），同时也有根据输入时间有衰减的效果。
