N-Gram（有时也称为 N 元模型）是自然语言处理中一个非常重要的概念，通常在 NLP 中，人
们基于一定的语料库，可以利用 N-Gram 来预计或者评估一个句子是否合理。另外一方面，
N-Gram 的另外一个作用是用来评估两个字符串之间的差异程度。这是模糊匹配中常用的一
种手段。本文将从此开始，进而向读者展示 N-Gram 在自然语言处理中的各种 powerful 的应
用。
� 基于 N-Gram 模型定义的字符串距离
� 利用 N-Gram 模型评估语句是否合理
� 使用 N-Gram 模型时的数据平滑算法
在自然语言处理时，最常用也最基础的一个操作是就是“模式匹配”，或者称为
“字符串查找”。而模式匹配（字符串查找）又分为精确匹配和模糊匹配两种。
所谓精确匹配，大家应该并不陌生，比如我们要统计一篇文章中关键词
“
information
” 出现的次数，这时所使用的方法就是精确的模式匹配。这方
面的算法也比较多，而且应该是计算机相关专业必修的基础课中都会涉及到的内
容，例如 KMP 算法、BM 算法和 BMH 算法等等。
另外一种匹配就是所谓的模糊匹配，它的应用也随处可见。例如，一般的文字处
理软件（例如，Microsoft Word 等）都会提供拼写检查功能。当你输入一个错
误的单词，例如 “
informtaion
” 时，系统会提示你是否要输入的词其实是
“
information
” 。将一个可能错拼单词映射到一个推荐的正确拼写上所采用
的技术就是模糊匹配。
模糊匹配的关键在于如何衡量两个长得很像的单词（或字符串）之间的“差
异”。这种差异通常又称为“距离”。这方面的具体算法有很多，例如基于编辑
距离的概念，人们设计出了 Smith-Waterman 算法和 Needleman-Wunsch
算法，其中后者还是历史上最早的应用动态规划思想设计的算法之一。现在
评论0