N-Gram（有時也稱為N元模型）是自然語言處理中一個非常重要的概念再扭，通常在NLP中财边，人們基于一定的語料庫肌括，可以利用N-Gram來預計或者評估一個句子是否合理。另外一方面酣难，N-Gram的另外一個作用是用來評估兩個字符串之間的差異程度谍夭。這是模糊匹配中常用的一種手段黑滴。本文將從此開始，進而向讀者展示N-Gram在自然語言處理中的各種powerful的應用慧库。
基于N-Gram模型定義的字符串距離
利用N-Gram模型評估語句是否合理
使用N-Gram模型時的數(shù)據(jù)平滑算法

歡迎關注白馬負金羈的博客 http://blog.csdn.net/baimafujinji跷跪，為保證公式、圖表得以正確顯示齐板，強烈建議你從該地址上查看原版博文吵瞻。本博客主要關注方向包括：數(shù)字圖像處理筏餐、算法設計與分析烹植、數(shù)據(jù)結構、機器學習拜效、數(shù)據(jù)挖掘济舆、統(tǒng)計分析方法卿泽、自然語言處理。
基于N-Gram模型定義的字符串距離
在自然語言處理時滋觉，最常用也最基礎的一個操作是就是“模式匹配”签夭，或者稱為“字符串查找”。而模式匹配（字符串查找）又分為精確匹配和模糊匹配兩種椎侠。

所謂精確匹配第租，大家應該并不陌生，比如我們要統(tǒng)計一篇文章中關鍵詞 “information” 出現(xiàn)的次數(shù)我纪，這時所使用的方法就是精確的模式匹配慎宾。這方面的算法也比較多，而且應該是計算機相關專業(yè)必修的基礎課中都會涉及到的內(nèi)容浅悉，例如KMP算法趟据、BM算法和BMH算法等等。
另外一種匹配就是所謂的模糊匹配术健，它的應用也隨處可見汹碱。例如，一般的文字處理軟件（例如荞估，Microsoft Word等）都會提供拼寫檢查功能比被。當你輸入一個錯誤的單詞，例如 “ informtaion” 時泼舱，系統(tǒng)會提示你是否要輸入的詞其實是 “information” 等缀。將一個可能錯拼單詞映射到一個推薦的正確拼寫上所采用的技術就是模糊匹配。
模糊匹配的關鍵在于如何衡量兩個長得很像的單詞（或字符串）之間的“差異”娇昙。這種差異通常又稱為“距離”尺迂。這方面的具體算法有很多，例如基于編輯距離的概念，人們設計出了 Smith-Waterman 算法和Needleman-Wunsch 算法噪裕，其中后者還是歷史上最早的應用動態(tài)規(guī)劃思想設計的算法之一《着蹋現(xiàn)在Smith-Waterman 算法和Needleman-Wunsch 算法在生物信息學領域也有重要應用，研究人員常常用它們來計算兩個DNA序列片段之間的“差異”（或稱“距離”）膳音。甚至于在LeetCode上也有一道“No.72 Edit Distance”召衔，其本質就是在考察上述兩種算法的實現(xiàn)〖老荩可見相關問題離我們并不遙遠苍凛。
N-Gram在模糊匹配中的應用
事實上，筆者在新出版的《算法之美——隱匿在數(shù)據(jù)結構背后的原理》一書中已經(jīng)詳細介紹了包括Needleman-Wunsch算法兵志、Smith-Waterman算法醇蝴、N-Gram算法、Soundex算法想罕、Phonix算法等在內(nèi)的多種距離定義算法（或模糊匹配算法）悠栓。而今天為了引出N-Gram模型在NLP中的其他應用，我們首先來介紹一下如何利用N-Gram來定義字符串之間的距離按价。
我們除了可以定義兩個字符串之間的編輯距離（通常利用Needleman-Wunsch算法或Smith-Waterman算法）之外惭适，還可以定義它們之間的N-Gram距離。N-Gram（有時也稱為N元模型）是自然語言處理中一個非常重要的概念楼镐。假設有一個字符串 s
腥沽，那么該字符串的N-Gram就表示按長度 N 切分原詞得到的詞段，也就是 s
中所有長度為 N 的子字符串鸠蚪。設想如果有兩個字符串，然后分別求它們的N-Gram师溅，那么就可以從它們的共有子串的數(shù)量這個角度去定義兩個字符串間的N-Gram距離茅信。但是僅僅是簡單地對共有子串進行計數(shù)顯然也存在不足，這種方案顯然忽略了兩個字符串長度差異可能導致的問題墓臭。比如字符串 girl 和 girlfriend蘸鲸，二者所擁有的公共子串數(shù)量顯然與 girl 和其自身所擁有的公共子串數(shù)量相等，但是我們并不能據(jù)此認為 girl 和girlfriend 是兩個等同的匹配窿锉。
為了解決該問題酌摇，有學者便提出以非重復的N-Gram分詞為基礎來定義 N-Gram距離這一概念，可以用下面的公式來表述：
|GN(s)|+|GN(t)|?2×|GN(s)∩GN(t)|

此處嗡载，|GN(s)|
是字符串 s
的 N-Gram集合窑多，N 值一般取2或者3。以 N = 2 為例對字符串Gorbachev和Gorbechyov進行分段洼滚，可得如下結果（我們用下畫線標出了其中的公共子串）埂息。

import org.apache.lucene.search.spell.*;
public class NGram_distance {
public static void main(String[] args) {

    NGramDistance ng = new NGramDistance();
    float score1 = ng.getDistance("Gorbachev", "Gorbechyov");
    System.out.println(score1);
    float score2 = ng.getDistance("girl", "girlfriend");
    System.out.println(score2);
}
}

有興趣的讀者可以在引用相關JAR包之后在Eclipse中執(zhí)行上述Java程序幕侠，你會發(fā)現(xiàn)，和我們預期的一樣碍彭，字符串Gorbachev和Gorbechyov所得之距離評分較高（=0.7）晤硕，說明二者很接近；而girl和girlfriend所得之距離評分并不高（=0.3999）庇忌，說明二者并不很接近舞箍。
利用N-Gram模型評估語句是否合理
從現(xiàn)在開始，我們所討論的N-Gram模型跟前面講過N-Gram模型從外在來看已經(jīng)大不相同皆疹，但是請注意它們內(nèi)在的聯(lián)系（或者說本質上它們?nèi)匀皇墙y(tǒng)一的概念）疏橄。
為了引入N-Gram的這個應用，我們從幾個例子開始略就。首先捎迫，從統(tǒng)計的角度來看，自然語言中的一個句子 s
可以由任何詞串構成表牢，不過概率 P(s)
有大有小窄绒。例如：
s1
= 我剛吃過晚飯
s2
= 剛我過晚飯吃

顯然，對于中文而言 s1
是一個通順而有意義的句子崔兴，而s2
則不是颗祝，所以對于中文來說浊闪，P(s1)>P(s2)
。但不同語言來說螺戳，這兩個概率值的大小可能會反轉搁宾。
其次，另外一個例子是倔幼，如果我們給出了某個句子的一個節(jié)選盖腿，我們其實可以能夠猜測后續(xù)的詞應該是什么，例如
the large green __ . Possible answer may be “mountain” or “tree” ?
Kate swallowed the large green __ . Possible answer may be “pill” or “broccoli” ?

顯然损同，如果我們知道這個句子片段更多前面的內(nèi)容的情況下翩腐，我們會得到一個更加準確的答案。這就告訴我們膏燃，前面的（歷史）信息越多茂卦，對后面未知信息的約束就越強。
如果我們有一個由 m
個詞組成的序列（或者說一個句子）组哩，我們希望算得概率 P(w1,w2,?,wm)
等龙，根據(jù)鏈式規(guī)則，可得
P(w1,w2,?,wm)=P(w1)P(w2|w1)P(w3|w1,w2)?P(wm|w1,?,wm?1)

這個概率顯然并不好算伶贰，不妨利用馬爾科夫鏈的假設蛛砰，即當前這個詞僅僅跟前面幾個有限的詞相關，因此也就不必追溯到最開始的那個詞黍衙，這樣便可以大幅縮減上訴算式的長度泥畅。即P(wi|w1,?,wi?1)=P(wi|wi?n+1,?,wi?1)

特別地，對于 n
取得較小值的情況當 n=1
, 一個一元模型（unigram model)即為P(w1,w2,?,wm)=∏i=1mP(wi)

當 n=2
, 一個二元模型（bigram model)即為P(w1,w2,?,wm)=∏i=1mP(wi|wi?1)

當 n=3
, 一個三元模型（trigram model)即為P(w1,w2,?,wm)=∏i=1mP(wi|wi?2wi?1)

接下來的思路就比較明確了琅翻，可以利用最大似然法來求出一組參數(shù)位仁，使得訓練樣本的概率取得最大值。
對于unigram model而言方椎，其中c(w1,..,wn)
表示 n-gram w1,..,wn
在訓練語料中出現(xiàn)的次數(shù)聂抢，M
是語料庫中的總字數(shù)（例如對于 yes no no no yes 而言，M=5
）P(wi)=C(wi)M

對于bigram model而言辩尊，P(wi|wi?1)=C(wi?1wi)C(wi?1)

對于n
-gram model而言，P(wi|wi?n?1,?,wi?1)=C(wi?n?1,?,wi)C(wi?n?1,?,wi?1)

來看一個具體的例子康辑，假設我們現(xiàn)在有一個語料庫如下摄欲，其中<s1><s2>
是句首標記，</s2></s1>
是句尾標記：
<s1><s2>yesnonononoyes</s2></s1><s1><s2>nononoyesyesyesno</s2></s1>

下面我們的任務是來評估如下這個句子的概率：<s1><s2>yesnonoyes</s2></s1>

我們來演示利用trigram模型來計算概率的結果P(yes|<s1><s2>)=12,P(no|<s2>yes)=1P(no|yesno)=12,P(yes|nono)=25P(</s2>|noyes)=12,P(</s1>|yes</s2>)=1

所以我們要求的概率就等于：12×1×12×25×12×1=0.05

再舉一個來自文獻[1]的例子疮薇，假設現(xiàn)在有一個語料庫胸墙，我們統(tǒng)計了下面一些詞出現(xiàn)的數(shù)量

下面這個概率作為其他一些已知條件給出：P(i|<s>)=0.25P(english|want)=0.0011P(food|english)=0.5P(</s>|food)=0.68

吼野，則可以算得P(s1)=P(i|<s>)P(want|i)P(english|want)P(food|english)P(</s>|food)=0.25×0.33×0.0011×0.5×0.68=0.000031

使用N-Gram模型時的數(shù)據(jù)平滑算法
有研究人員用150萬詞的訓練語料來訓練 trigram 模型校哎，然后用同樣來源的測試語料來做驗證，結果發(fā)現(xiàn)23%的 trigram 沒有在訓練語料中出現(xiàn)過瞳步。這其實就意味著上一節(jié)我們所計算的那些概率有空為 0闷哆，這就導致了數(shù)據(jù)稀疏的可能性，我們的表3中也確實有些為0的情況单起。對語言而言抱怔，由于數(shù)據(jù)稀疏的存在，極大似然法不是一種很好的參數(shù)估計辦法嘀倒。
這時的解決辦法屈留，我們稱之為“平滑技術”（Smoothing）或者 “減值” （Discounting）。其主要策略是把在訓練樣本中出現(xiàn)過的事件的概率適當減小括儒，然后把減小得到的概率密度分配給訓練語料中沒有出現(xiàn)過的事件绕沈。實際中平滑算法有很多種，例如：　　? Laplacian (add-one) smoothing　　? Add-k smoothing　　? Jelinek-Mercer interpolation　　? Katz backoff　　? Absolute discounting　　? Kneser-Ney
對于這些算法的詳細介紹帮寻，我們將在后續(xù)的文章中結合一些實例再來進行討論乍狐。
A Final Word
如果你能從前面那些繁冗、復雜的概念和公式中挺過來固逗，恭喜你浅蚪，你對N-Gram模型已經(jīng)有所認識了。盡管烫罩，我們還沒來得及探討平滑算法（但它即將出現(xiàn)在我的下一篇博文里惜傲，如果你覺得還未過癮的話），但是其實你已經(jīng)掌握了一個相對powerful的工具贝攒。你可以能會問盗誊，在實踐中N-Gram模型有哪些具體應用，作為本文的結束隘弊，主頁君便在此補充幾個你曾見過的或者曾經(jīng)好奇它是如何實現(xiàn)的例子哈踱。
Eg.1 搜索引擎（Google或者Baidu）、或者輸入法的猜想或者提示梨熙。你在用百度時开镣，輸入一個或幾個詞，搜索框通常會以下拉菜單的形式給出幾個像下圖一樣的備選咽扇，這些備選其實是在猜想你想要搜索的那個詞串邪财。再者陕壹，當你用輸入法輸入一個漢字的時候，輸入法通呈鞑海可以聯(lián)系出一個完整的詞糠馆，例如我輸入一個“劉”字，通常輸入法會提示我是否要輸入的是“劉備”弥奸。通過上面的介紹榨惠，你應該能夠很敏銳的發(fā)覺，這其實是以N-Gram模型為基礎來實現(xiàn)的盛霎，如果你能有這種覺悟或者想法赠橙，那我不得不恭喜你，都學會搶答了愤炸！

Eg.2 某某作家或者語料庫風格的文本自動生成期揪。這是一個相當有趣的話題。來看下面這段話（該例子取材自文獻【1】）：
“You are uniformly charming!” cried he, with a smile of associating and now and then I bowed and they perceived a chaise and four to wish for.

你應該還沒有感覺到它有什么異樣吧规个。但事實上這并不是由人類寫出的句子凤薛，而是計算機根據(jù)Jane Austen的語料庫利用trigram模型自動生成的文段。（Jane Austen是英國著名女作家诞仓，代表作有《傲慢與偏見》等）
再來看兩個例子缤苫，你是否能看出它們是按照哪位文豪（或者語料庫）的風格生成的嗎？
This shall forbid it should be branded, if renown made it empty.
They also point to ninety nine point six billion dollars from two hundred four oh three percent of the rates of interest stores as Mexico and Brazil on market conditions.

答案是第一個是莎士比亞墅拭，第二個是華爾街日報活玲。最后一個問題留給讀者思考，你覺得上面兩個文段所運用的n-gram模型中谍婉，n應該等于多少舒憾？
推薦閱讀和參考文獻：
[1] Speech and Language Processing. Daniel Jurafsky & James H. Martin, 3rd. Chapter 4[2] 本文中的一些例子和描述來自 北京大學 常寶寶 以及 The University of Melbourne “Web Search and Text Analysis” 課程的幻燈片素材

轉載自 http://blog.csdn.net/baimafujinji/article/details/51281816}