N-gram的原理、用途和研究

N-gram的基本原理

N-gram是计算机语言学和概率论范畴内的概念，是指给定的一段文本或语音中N个项目（item）的序列。项目（item）可以是音节、字母、单词或碱基对。通常N-grams取自文本或语料库。

N=1时称为unigram，N=2称为bigram，N=3称为trigram，以此类推。

举例来说：将“informationretrieval”视为一段文本，它的5-grams的items依次为：

infor,nform,forma,ormat,rmati,matio,ation,tion,ionr,onre,nret,retr,retri,etrie,triev,rieva,ieval

有时为了便于分析，还会在前面加空格，这就多出4个items：____i,___in,__inf,_info

举例中文：“你今天休假了吗”，它的bigram依次为：

你今，今天，天休，休假，假了，了吗

制造这种语言模型的原因是基于这么一种思想：在整个语言环境中，句子T的出现概率是由组成T的N个item的出现概率组成的，如下公式所示

P(T)=P(W1W2W3Wn)=P(W1)P(W2|W1)P(W3|W1W2)…P(Wn|W1W2…Wn-1)

以上公式难以实际应用。此时出现马尔科夫模型，该模型认为，一个词的出现仅仅依赖于它前面出现的几个词。这就大大简化了上述公式。

P(W1)P(W2|W1)P(W3|W1W2)…P(Wn|W1W2…Wn-1)≈P(W1)P(W2|W1)P(W3|W2)…P(Wn|Wn-1)

通常采用bigram和trigram进行计算。

N-gram的用途

20世纪80年代至90年代初,n-gram技术被广泛地用来进行文本压缩,检查拼写错误,加速字符串查找,文献语种识别。90年代,该技术又在自然语言处理自动化领域得到新的应用,如自动分类,自动索引,超链的自动生成,文献检索,无分隔符语言文本的切分等。

目前N-gram最为有用的就是自然语言的自动分类功能。基于n-gram的自动分类方法有两大类,一类是人工干预的分类(Classification),又称分类;一类是无人工干预的分类(Clustering),又称聚类。人工干预的分类,是指人工预先分好类(如Yahoo!的层次结构类),然后,计算机根据特定算法自动地将新添加到数据库的文献划归某一类。这类方法缺点是,人们须预先具备关于整个文献库和分类的知识。无人工干预的分类,是指计算机自动地识别文献组(集合),人们勿需预先具备关于整个文献库和分类的知识。

可以想象，如今信息泛滥的时代，资源呈指数方式递增。依靠人工信息识别和分类已经变得不现实，人类依靠计算机对自然语言本文的自动分类正在成为现实。这又与KDA和SVM结合起来，利用机器学习，首先利用Trainingdata形成分类函数，然后利用Testingdata进行测试其准确性。

N-gram中的数据平滑

对于一个包含2000个词的文本，使用bigram方法就会形成2000×2000的矩阵，trigram就形成2000×2000×2000的矩阵，其中含有大量的0值，即稀疏矩阵。此时需要采用数据平滑技术（datasmoothing）使得；并且P(W_k)均不等于0。

N-gram的相关研究

以上介绍都很浅薄，有兴趣可以参考相关研究：

英家庆，使用N-gram模型對中文文件自動分類，硕士论文，

http://ethesys.lib.mcu.edu.tw/ETD-db/ETD-search/getfile?URN=etd-0817107-135543&filename=etd-0817107-135543.pdf

图  .N-gram处理中文流程

何浩，杨海棠，一种基于 N-Gram 技术的中文文献自动分类方法，情报学报，http://study.hbecrc.org/lcq/xueshuyanjiu/UploadFiles_9984/200704/20070417110725112.pdf

George Doddington，Automatic Evaluation of MachineTranslation Quality Using N-gram Co-Occurrence Statistics，http://dl.acm.org/citation.cfm?id=1289189.1289273