N-Gram

这是我参与8月更文挑战的第12天，活动详情查看： 8月更文挑战

N-Gram（N元模型）是自然语言处理中一个非常重要的概念，通常在NLP中，人们基于一定的语料库，可以利用N-Gram来评估一个句子是否合理。N-Gram的另外一个作用是用来评估两个字符串之间的差异程度，这是模糊匹配中常用的一种手段。本文将从此开始，进而向读者展示N-Gram在自然语言处理中的各种Powerful的应用

1. 基于N-Gram模型定义的字符串距离
2. 利用N-Gram模型评估语句是否合理
3. 使用N-Gram模型时的数据平滑算法

基于N-Gram模型定义的字符串距离

在自然语言处理中，最常用也是最基础的一个操作就是“模式匹配”，或者称为“字符串查找”。而模式匹配又分为精确匹配和模糊匹配两种

精确匹配，大家并不陌生，比如我们要统计一篇文章中关键词infomation出现的次数，这时所用的方法就是精确匹配。这方面算法也很多，例如KMP算法、BM算法等

模糊匹配，它的应用也随处可见。一般的文字处理软件（Word等）都会提供拼写检查的功能，当你输一个错误的单词，例如informtaion，系统会提示你要输入的词是否其实是information。将一个可能拼错的单词映射到一个推荐的正确拼写上，采用的技术就是模糊匹配

模糊匹配的关键在于如何衡量两个长得很像的单词（或字符串）之间的“差异”。这种差异通常又称为“距离”。这方面的算法有很多，甚至于在LeetCode上也有一道题No.72 Edit Distance

首先介绍一下如何利用N-Gram来定义字符串之间的距离。假设有一个字符串$s$，那么该字符串的N-Gram就表示按长度N切分原词得到的词段，也就是$s$中所有长度为N的子字符串。设想如果有两个字符串，然后分别求它们的N-Gram，那么就可以从它们公有字串的数量这个角度去定义两个字符串间的N-Gram距离。但是仅仅是简单地对公有子串进行计数显然也存在不足，这种方案显然忽略了两个字符串长度差异可能导致的问题。比如字符串girl和girlfriend，二者所拥有的公共子串数量显然与girl和其自身所拥有的公共子串数量相等，但是我们并不能据此认为girl和girlfriend是两个等同的匹配

为了解决该问题，有学者提出以非重复的N-Gram分词为基础来定义N-Gram距离这一概念，具体公式如下：