这是我离散数学课的大作业，用图论算法解决某个复杂的问题，我选的题目是基于统计语言模型的拼音输入法。通俗地讲，就是实现一个支持智能组句的拼音输入法。注意是智能组句，不是智能组词，组词其实就是查词典，哪怕是人也是这么做的，只不是这部词典在大脑中而已，否则就是“造词”了。而电脑组句的方法就和人有很大区别了，因为让电脑理解一个句子的结构是极端困难的，尤其是作为分析语的中文，所以说这里面蕴含著许多难题。说到这里我想到了关于人工智能的讨论，心理学家和工程科学家在对人工智能的认识上有著根本的分歧，即工程科学家认为人工智能就是实际效果显得有类似人类的智能，而心理学家则把具有模仿认为思考、推理和行为的能力作为人工智能的判断标准。在不同的认知基础上人工智能的研究朝著不同的方向发展，事实情况是基于效果的人工智能的水平不断在进步，而基于模仿的人工智能难有突破。作为一个拼音输入法，实际效果比所谓智能的理解更为重要（况且作为表达思想和意志的工具，许多人并不希望自己输入的所有内容被电脑“理解”），而统计语言模型就是一个被广为应用的手段。

统计语言模型(Statistical Language Model)是听起来像是个很深奥的东西，其实说出来并不复杂，简而言之就是一个经过整理的大量语料的统计数据。这个数据有什么用呢？用处非常大，像机器翻译、语音识别、中文分词、信息检索乃至数据挖掘，都可能要用到统计语言模型，把它用到输入法上面其实是最直接的使用。举个简单的例子来说，“wo shi zhong guo ren”这个音节序列中，“wo shi”可能对应了“我是”、“卧室”、“我市”、“卧式”等词，而“zhong guo ren”则可能是“中国人”或者“种果人”，最佳的组句方案是什么呢？这就要用到统计语言模型了，我们在这一大堆统计数据中，分别找到词频最大的单词，如“我是”和“中国人”，句子就可以组合出来了。听起来是不是很自然的想法呢？找出词频最大的词组合到一起，就成了句子。事实上就是这样，不少输入法都以这种方式实现，而且效果也不差。例如早期的拼音加加、紫光拼音，Linux平台下ibus-pinyin。追溯一下，使用这种方法的鼻祖应该是智能ABC输入法吧，在当年这可是改变了中国人输入习惯的一个划时代产品。然而统计语言模型的应用远远不止于此，例如我们收集到的统计语言模型中，从单词的词频上来说，“卧室”可能会比“我是”更高一些，但显然“我是中国人”比“卧室中国人”更好，所以单看每个单词的词频有时候不一定是最好的，这怎么办呢？我们可以不但考虑单词的词频，也考虑两个词组合在一起的频率，这样的话“我是中国人”肯定是最好的结果了。甚至我们可以统计每三个词、四个词、乃至多元组的频率，则必定会有更好的效果，于是N-gram模型应运而生。如果没记错的话，微软拼音应该是最早做这种尝试的输入法了，只可惜微软拼音的输入模式偏偏那么怪异，再加上推广手段不力，一直默默无闻，反而是搜狗拼音在2006年异军突起，迅速占据了桌面市场。目前像搜狗、Google、QQ拼音等输入法都采用了2-gram或者3-gram语言模型，在Linux和mac平台下，开源的SunPinyin也是基于3-gram的。

统计语言模型说到底依赖于大量语料的统计，词汇是数以十万计的，两个词组合起来数据量就达到了百亿，三元组则更是天文数字，何处找如此大的规模的语料来进行统计呢？想必一般人是没有办法，只有做搜索引擎的商业巨擘才有实力来做。但是时间和空间毕竟有限，不可能把输入法做成如此一个庞然大物，桌面用户是消受不起的，因此实际上在使用统计语言模型时，是需要对不少情况进行数学计算拟合出一个近似结果的，这便是从有穷模拟无穷的量化思想的体现。另一个方面，不少公司开始热衷于做云输入法，用一台超级计算机来计算庞大的数据，只需给出用户结果，这样就不必考虑用户终端的计算能力了。

说了这么多，谈谈我的设计吧。我用了尽可能简单的建模方法实现了一个基于2-gram的拼音输入法，为了突出图论（毕竟是图论课），我还设计了具有歧义的拼音字串的多重解析（如“翻案”和“发难”，对应fanan）。在我的设计中，我大量参考了SunPinyin，也得到了来自SunPinyin作者孙勇的不少帮助。我的程序的全部源码和数据在slm_based_pinyin_ime.7z，源码以Apache License 2.0发布，数据来自open-gram项目。因为和SunPinyin使用了同样的词库和语言模型，所以在测试中不少组句结果会与SunPinyin很接近，有心人可以试试比较一下。此外程序的图标是ibus-pinyin的。写完以后我发现我求k优最长路径的算法写得不好，在k比较大的时候会很慢，其实可以做到线性复杂度的。下面是一个演示文稿。

演示文稿