prunning，剪枝，顾名思义就是减掉那些不重要的。

从理论上来讲，剪枝达到的效果就是剪枝后的q和剪枝前的 p 最大化相似，有两种算法 entroy-based以及rank-based。

针对model，使用相对熵来刻画D(q||p) 来刻画，保证两个model的熵区别最小，就是entropy-based。假设使用rank(p|q)来描写叙述，保证整个model的rank区别最小(主要是针对同一个bigram pair的left word)，就是rank-based。

对于smoothing，我们使用的是katz平滑。

entropy-based 计算的套路：

1.针对每一条数据，计算删除后的模型參数，对于katz，又一次计算alpha，基于新/老alpha，看看整个model熵的变化，详细值參考论文公式。

參数计算：

这个事情真正的难点在于，怎样分布式的计算这些信息。每次删除一条数据，明显不可行，一下子删除完也不行

通过公式来看，这里面的重点是怎样更新alpha，以及alpha确定后，怎样迭代。

rank-based算法当时也做过尝试，感觉和entropy-based差点儿相同，而且这两个都没有达到期望的效果，所以并没有深入研究

上面的算法属于理论上的算法，来刻画两个模型的距离，在输入法这个应用上，并不合适。

一般来讲，输入法原始model 的规模可能在30亿，而一个local的model须要的最多也是在1000w-2000w左右。基本上须要剪掉90%的数据，终于的model和原始model区别还是比較大的。

基于熵的剪枝，一般意义上期望是剪掉后和原始模型区别不大，依据经验来讲，剪掉20%左右的数据就非常不错了

所以真正意义上的剪枝应该基于输入法的特性来做