在學習自然語言處理 (Natural Language Processing) 時，經常會從語言模型 (Language Model) 開始學起，N-gram 便是一個入門常見語言模型。在這篇文章將帶你一探究竟 N-gram，並且利用 N-gram 實作一個模型，能夠像似搜尋引擎根據使用者的輸入推薦相關的字詞。
語言模型 (Language Model) 與 N-gram 原理
語言模型這 4 個字看似很博大精深，但是它僅僅指的就是「一個句子的機率」，在一個句子中的每個字，我們可以給它 P(S)，代表每個字的機率。
假設我們給定一個句子「花博即將在台中__ 」，在留空的地方一般人都會想到該填入「舉行」，也就是當出現「花博即將在台中」，電腦能夠推斷出在這句話的後方出現「舉行」的機率最高。
所以我們假設第 i 個字會跟第 1 個字到 i-1 個字有關，這時你會發現如果這個句子很長，該機率計算量將會變得非常大，因此我們可以利用 Markov 假設，也就是當前的這個字僅僅與前幾個有限的字相關，如此一來，將不必追溯至第 1 個字，可以減少該機率的計算量：
當 m = 3 時，也就是第 i 個字與前 3 個字有相關，稱作 3-gram 或 trigram。用上述的例子舉例，我們要找一個字會令 P(w|在台中) 的機率最高，假設推算出 P(舉|在台中) 的機率最高後，再繼續找出另一個字讓 P(w|台中舉) 的機率最高。
這時你會想該如何計算 P(w|在台中) 這種條件機率？我們可以使用最大似然估計 (Maximum Likelihood Estimation )，詳細推導可以看這篇 🔗文章：
藉由計算字詞出現的次數來推估 N-gram 的機率，所以我們要做的事情是計算「在台中 w」與「在台中」分別出現的次數，再相除得到 P(w|在台中) 的機率。
從零開始實現 N-gram
在這個範例中，我們會使用 Open data 作為資料集，並且利用 N-gram 訓練一個語言模型。
我們會用到 Collections 中的 namedtuple 與 Counter。namedtuple 提供的功能是像 C 語言的 struct，能夠清楚表達一個資料的結構；而 Counter 則是能夠快速地幫助我們計算數量，例如 list 中每個元素的數量各有幾個。
引入資料集
在這篇文章中使用的資料集是政府資料開放平台提供的 🔗桃園市官網市政新聞，由於 N-gram 所產生的結果會根據資料集而有所不同，因此在選擇資料集時必須評估該資料集是否合適。假設使用的資料集中包含許多火星文，根據 N-gram 產生的語言模型，其結果將會與火星文相關。
資料前處理
桃園市官網市政新聞包含了許多的資料欄位，而我們需要的僅有報導文章的部分，因此將報導單獨取出。
而報導中包含許多許多英文、數字與表點符號，為了實作方便，將除了繁體中文字以外的字用正規表達式 (Regular Expression) 去除。
N-gram 實作
在實作 N-gram 時，首先，我們要將每一篇文章做 tokenize；而我們想知道一篇文章的開頭與結尾，所以在 tokenize 之後，在前後分別加上 <s> 和 </s> 作為標示。
而在計算每個字出現的機率後，可以利用 set，將重複的字與機率去除，例如計算出兩次在「桃園」後出現「縣」的機率都是 1，我們可以只保留一組。
訓練模型與排序
我們使用的模型是 trigram，也就是計算接在兩個字之後第三個字的機率。接著，可以對結果進行排序，因此在預測下一個字時，能夠直接取得前幾個最高機率的字。
預測輸入的下一個字
最後，我們使用模型來預測接下來可能會出現的文字，輸入「韓國」後出現的下一個字為「仁、及、地、超、文」最高機率的這 5 個字。
結論
N-gram 是一個理論較為簡單，而且容易實作的語言模型，可以花少量的程式碼達到不錯的效果。
但是，也許你會思考在預測下一個字時，得出字組合起來沒有特別的意思，因為 N-gram 只是單純利用統計得出機率比較大的字詞組合，所以在預測時看似會較沒有邏輯。
如果想要得出更好的結果可以嘗試使用較為複雜的模型，例如 Transformer 或是 ConvS2S 等 Google 與 Facebook 曾經發表的模型。
