N-Gram（有時(shí)也稱為N元模型）是自然語言處理中一個(gè)非常重要的概念镇饮，通常在NLP中，人們基于一定的語料庫术羔，可以利用N-Gram來預(yù)計(jì)或者評估一個(gè)句子是否合理杨箭。另外一方面寞焙，N-Gram的另外一個(gè)作用是用來評估兩個(gè)字符串之間的差異程度。這是模糊匹配中常用的一種手段互婿。本文將從此開始捣郊，進(jìn)而向讀者展示N-Gram在自然語言處理中的各種powerful的應(yīng)用。
- 基于N-Gram模型定義的字符串距離
- 利用N-Gram模型評估語句是否合理
- 使用N-Gram模型時(shí)的數(shù)據(jù)平滑算法
基于N-Gram模型定義的字符串距離
模糊匹配的關(guān)鍵在于如何衡量兩個(gè)長得很像的單詞（或字符串）之間的“差異”擒悬。這種差異通常又稱為“距離”模她。這方面的具體算法有很多，例如基于編輯距離的概念懂牧，人們設(shè)計(jì)出了 Smith-Waterman 算法和Needleman-Wunsch 算法，其中后者還是歷史上最早的應(yīng)用動(dòng)態(tài)規(guī)劃思想設(shè)計(jì)的算法之一∽鹞穑現(xiàn)在Smith-Waterman 算法和Needleman-Wunsch 算法在生物信息學(xué)領(lǐng)域也有重要應(yīng)用僧凤，研究人員常常用它們來計(jì)算兩個(gè)DNA序列片段之間的“差異”（或稱“距離”）。
我們除了可以定義兩個(gè)字符串之間的編輯距離（通常利用Needleman-Wunsch算法或Smith-Waterman算法）之外元扔，還可以定義它們之間的N-Gram距離躯保。N-Gram（有時(shí)也稱為N元模型）是自然語言處理中一個(gè)非常重要的概念。假設(shè)有一個(gè)字符串 澎语，那么該字符串的N-Gram就表示按長度 N 切分原詞得到的詞段途事，也就是 中所有長度為 N 的子字符串。設(shè)想如果有兩個(gè)字符串擅羞，然后分別求它們的N-Gram尸变，那么就可以從它們的共有子串的數(shù)量這個(gè)角度去定義兩個(gè)字符串間的N-Gram距離。但是僅僅是簡單地對共有子串進(jìn)行計(jì)數(shù)顯然也存在不足减俏，這種方案顯然忽略了兩個(gè)字符串長度差異可能導(dǎo)致的問題召烂。比如字符串 girl 和 girlfriend，二者所擁有的公共子串?dāng)?shù)量顯然與 girl 和其自身所擁有的公共子串?dāng)?shù)量相等娃承，但是我們并不能據(jù)此認(rèn)為 girl 和girlfriend 是兩個(gè)等同的匹配奏夫。
為了解決該問題，有學(xué)者便提出以非重復(fù)的N-Gram分詞為基礎(chǔ)來定義 N-Gram距離這一概念历筝，可以用下面的公式來表述：
此處酗昼，|GN(s)| 是字符串 s 的 N-Gram集合，N 值一般取2或者3梳猪。以 N = 2 為例對字符串Gorbachev和Gorbechyov進(jìn)行分段麻削，可得如下結(jié)果（我們用下畫線標(biāo)出了其中的公共子串）。
結(jié)合上面的公式，即可算得兩個(gè)字符串之間的距離是8 + 9 ? 2 × 4 = 9碟婆。顯然电抚，字符串之間的距離越小，它們就越接近竖共。當(dāng)兩個(gè)字符串完全相等的時(shí)候蝙叛，它們之間的距離就是0。
利用N-Gram模型評估語句是否合理
從現(xiàn)在開始公给，我們所討論的N-Gram模型跟前面講過N-Gram模型從外在來看已經(jīng)大不相同借帘，但是請注意它們內(nèi)在的聯(lián)系（或者說本質(zhì)上它們?nèi)匀皇墙y(tǒng)一的概念）。
為了引入N-Gram的這個(gè)應(yīng)用淌铐，我們從幾個(gè)例子開始肺然。
首先，從統(tǒng)計(jì)的角度來看腿准，自然語言中的一個(gè)句子 s 可以由任何詞串構(gòu)成际起，不過概率 P(s) 有大有小。例如：
- s1 = 我剛吃過晚飯
- s2 = 剛我過晚飯吃
顯然吐葱，對于中文而言 s1 是一個(gè)通順而有意義的句子街望，而s2 則不是，所以對于中文來說弟跑，P(s1)>P(s2) 灾前。但不同語言來說，這兩個(gè)概率值的大小可能會(huì)反轉(zhuǎn)孟辑。
其次哎甲，另外一個(gè)例子是，如果我們給出了某個(gè)句子的一個(gè)節(jié)選饲嗽，我們其實(shí)可以能夠猜測后續(xù)的詞應(yīng)該是什么炭玫，例如
the large green __ . Possible answer may be “mountain” or “tree” ?
Kate swallowed the large green __ . Possible answer may be “pill” or “broccoli” ?
顯然，如果我們知道這個(gè)句子片段更多前面的內(nèi)容的情況下喝噪，我們會(huì)得到一個(gè)更加準(zhǔn)確的答案础嫡。這就告訴我們，前面的（歷史）信息越多酝惧，對后面未知信息的約束就越強(qiáng)榴鼎。
如果我們有一個(gè)由 m 個(gè)詞組成的序列（或者說一個(gè)句子），我們希望算得概率 P(w1,w2,?,wm) 晚唇，根據(jù)鏈?zhǔn)揭?guī)則巫财，可得
P(w1,w2,?,wm)=P(w1)P(w2|w1)P(w3|w1,w2)?P(wm|w1,?,wm?1)
這個(gè)概率顯然并不好算，不妨利用馬爾科夫鏈的假設(shè)哩陕，即當(dāng)前這個(gè)詞僅僅跟前面幾個(gè)有限的詞相關(guān)平项，因此也就不必追溯到最開始的那個(gè)詞赫舒，這樣便可以大幅縮減上訴算式的長度。即
P(wi|w1,?,wi?1)=P(wi|wi?n+1,?,wi?1)
特別地闽瓢，對于 n 取得較小值的情況
當(dāng) n=1, 一個(gè)一元模型（unigram model)即為
當(dāng) n=2, 一個(gè)二元模型（bigram model)即為
當(dāng) n=3, 一個(gè)三元模型（trigram model)即為
接下來的思路就比較明確了接癌，可以利用最大似然法來求出一組參數(shù)，使得訓(xùn)練樣本的概率取得最大值扣讼。
使用N-Gram模型時(shí)的數(shù)據(jù)平滑算法
有研究人員用150萬詞的訓(xùn)練語料來訓(xùn)練 trigram 模型缺猛，然后用同樣來源的測試語料來做驗(yàn)證，結(jié)果發(fā)現(xiàn)23%的 trigram 沒有在訓(xùn)練語料中出現(xiàn)過椭符。這其實(shí)就意味著上一節(jié)我們所計(jì)算的那些概率有空為 0荔燎，這就導(dǎo)致了數(shù)據(jù)稀疏的可能性，我們的表3中也確實(shí)有些為0的情況销钝。對語言而言有咨，由于數(shù)據(jù)稀疏的存在，極大似然法不是一種很好的參數(shù)估計(jì)辦法蒸健。
這時(shí)的解決辦法座享，我們稱之為“平滑技術(shù)”（Smoothing）或者 “減值” （Discounting）。其主要策略是把在訓(xùn)練樣本中出現(xiàn)過的事件的概率適當(dāng)減小似忧，然后把減小得到的概率密度分配給訓(xùn)練語料中沒有出現(xiàn)過的事件征讲。實(shí)際中平滑算法有很多種，例如：
? Laplacian (add-one) smoothing
? Add-k smoothing
? Jelinek-Mercer interpolation
? Katz backoff
? Absolute discounting
? Kneser-Ney
對于這些算法的詳細(xì)介紹橡娄，我們將在后續(xù)的文章中結(jié)合一些實(shí)例再來進(jìn)行討論。
一個(gè)實(shí)際的例子
搜索引擎（Google或者Baidu）癣籽、或者輸入法的猜想或者提示挽唉。你在用百度時(shí)，輸入一個(gè)或幾個(gè)詞筷狼，搜索框通常會(huì)以下拉菜單的形式給出幾個(gè)像下圖一樣的備選瓶籽，這些備選其實(shí)是在猜想你想要搜索的那個(gè)詞串。再者埂材，當(dāng)你用輸入法輸入一個(gè)漢字的時(shí)候塑顺，輸入法通常可以聯(lián)系出一個(gè)完整的詞俏险，例如我輸入一個(gè)“劉”字严拒，通常輸入法會(huì)提示我是否要輸入的是“劉備”。通過上面的介紹竖独，你應(yīng)該能夠很敏銳的發(fā)覺裤唠，這其實(shí)是以N-Gram模型為基礎(chǔ)來實(shí)現(xiàn)的，如果你能有這種覺悟或者想法莹痢，那我不得不恭喜你种蘸，都學(xué)會(huì)搶答了墓赴！
參考：https://blog.csdn.net/baimafujinji/article/details/51281816
