对于计算机而言，汉字的输入远不象英文那么方便。为了让计算机“接受”汉字，人们设计了各种输入法，其中拼音输入法最自然，应用也最广泛。

早期的拼音输入法是逐字输入的，即用户输入拼音，计算机提示该拼音对应的汉字，用户再从中进行选择。由于汉语中一个拼音可能对应大量汉字，人们不得不在一个长长的列表中进行选择，非常繁琐。后来，人们开发出基于整句输入法，用户一次性输入整句话的拼音串，机器即可将自动将其转换为正确的汉字串，几乎不用人为选择。例如，输入以下拼音串：

      Jiqixuexijiqiyingyong

机器可以自动将其转化为如下汉字串：

      机器学习及其应用

目前，几乎所有拼音输入法都支持这种整句模式。那么，计算机是如何自动选择这些汉字的呢？

事实上，计算机的“原则”很简单，就是选那些看起来“更正常”的句子，换成严格一点的说法，就是概率更大的句子。下面我们详细解释一下。

首先，如果每个拼音只对应一个汉字的话，那么从拼音串到汉字的转化将没有任何难度。可惜的是，同音字现象是汉语的一个特色，每个拼音都对应多个汉字，特别是当缺少音调时，一个无调拼音可能对应几十甚至上百个汉字（如无调拼音ji对应如下汉字：及、计、机、几、急...）。对一个拼音串来说，即使不考虑拼音划分上的不确定性（如xian可能是两个拼音xi an，也可能是一个拼音xian），将每个拼音所对应的汉字组合起来，可能的汉字串也是个庞大的数字。

以“Jiqixuexijiqiyingyong”为例，它对应的汉字串是个巨大的数字，如下图所示：

图1. 拼音-汉字的对应关系

人们对这些句子是有一个直觉的，比如下面三个句子：

1. “及期学系及期应勇”

2. “机器学习及其应用”

3. “机器学习机器应用”

我们一看就知道句1不是个正常的句子，句2要正常得多，句3还好，基本正常，但是不如第二个好。那么，对计算机来说，如何判断一个句子是否正常呢？一个关键之处在于将“正常与否”用“可能性“来衡量，一句话出现的可能性越大，这句话就越正常。

数学上，我们用概率来表示“可能性”，一组汉字  出现的概率记为  。依概率公式，  可以通过  中每个汉字  的概率计算出来。为简便起见，我们假设第  个汉字为  的概率只与它前面的汉字  相关，这样一句话的概率就可以表示为： 

其中  称为二元语法，表示前一个汉字是  时，后一个汉字为  的概率。相应地也有三元语法、四元语法等。语法的元数越大对概率的表达越精确，但计算也越复杂。有了上述概率表示，我们只要在所有可能的汉字串中找到  最大的那个串就可以了。

原则确定了，剩下的就是实现的问题。一般来说，我们会将所有可能的汉字串表示成一个有向图，图中节点表示汉字候选，图中的边表示  的负对数值。基于这一表示，图上的最短路径即对应  最大的汉字串  ，即最优汉字串。利用动态规划等算法，可以很容易实现高效的最短路径搜索。有了这些技术，计算机就可以轻松地帮我们完成汉字的输入了。

图2. 将寻找最优汉字串问题转化为求最短路径问题

By：清华大学  马少平 王东