簡介
分詞是NLP的基本功能之一，現在發展比較成熟了，目前比較熱門的分詞工具有jieba，snownlp，pkuseg等等。分詞工具的使用是比較簡單的，具體查詢相應的github項目即可，上面有比較好的示例。本文我們主要講解一下分詞的相關算法：前向最大比對，後向最大比對，語言模型，維特比算法等。現分别講解如下。
前向最大比對算法
一句話總結：根據參數最大比對長度max_len，擷取一句話中的最大比對長度的子句，逐漸判斷子句是否在詞典中，是則分詞成功，否則删除子句中的最後一個字再進行判斷，子句是否在字典中。
輸入：一句話sent，詞典dic，最大比對長度max_len
輸出：分詞後的單詞清單words
①擷取sent中最大比對長度的子句sub_sent，判斷sub_sent是否在詞典dic中
②如果在清單中，則将sub_sent存放進words中，原句sent更新為sent-sub_sent；
③否則，sub_sent中删除最後一個字，判斷sub_sent[:-2]是否在詞典中
④重複上述步驟，直到sent句子為空為止。
舉例：sent = 我要去上學了，詞典 = [我，要去，上學，了，上學了，要，去]，max_len = 5
①sub_sent = 我要去上學，不在詞典中，則将其更新為：sub_sent = 我要去上
②sub_sent = 我要去上，不在詞典中，将其更新為：sub_sent = 我要去
③sub_sent = 我要去，不在詞典中，将其更新為：sub_sent = 我要
④sub_sent = 我要，不在詞典中，将其更新為：sub_sent = 我
⑤sub_sent = 我，在詞典中，是以words = [我]
⑥順移一位，sub_sent = 要去上學了，不在詞典中，更新為sub_sent = 要去上學
⑦sub_sent = 要去上學，不在詞典中，更新為sub_sent = 要去上
⑧sub_sent = 要去上，不在詞典中，更新為sub_sent = 要去
⑨sub_sent = 要去，在詞典中，words = [我，要去]
⑩順移一位，sub_sent = 上學了，在詞典中，words = [我，要去，上學了]
最終傳回的分詞結果是：[我，要去，上學了]
後向最大比對算法
前向最大比對取前max_len個字元，後向最大比對取後面max_len個字元。
舉例：sent = 我要去上學了，詞典 = [我，要去，上學，了，上學了，要，去]，max_len = 5
①sub_sent = 要去上學了，不在詞典中，則将其更新為：sub_sent = 去上學了
②sub_sent = 去上學了，不在詞典中，将其更新為：sub_sent = 上學了
③sub_sent = 上學了，在詞典中，words=[上學了]
④順移一位，sub_sent = 我要去，不在詞典中，将其更新為：sub_sent = 要去
⑤sub_sent = 要去，在詞典中，是以words = [要去，上學了]
⑥順移一位，sub_sent = 我，在詞典中，words=[我，要去，上學了]
最終傳回的分詞結果是：[我，要去，上學了]
最大比對的缺點：
①不夠細分（有可能更好）
②局部最優
③效率（max_len）
④歧義（不能考慮語義）
考慮語言模型（考慮語義）
語言模型就是為了計算一句話符合語義的程度，通過計算一句話的機率表示這句話的自然程度（或者說符合語義的程度）
過程：輸入 -> 生成所有可能的分割 -> 選擇其中最好的分詞組合（工具，如unigram LM）
假設s1 = [我，要去，上學了]，s2 = [我，要，去，上學，了]
分别計算機率：p(s1)=p(我，要去，上學了)=0.2,
p(s2)=p(我，要，去，上學，了)=0.4，可知，s2的分詞效果更好。
這是unigram LM的模型，考慮了語義，選擇最好的分詞組合。（關于語言模型）
缺點：複雜度高，效率低；機率計算有可能會溢出（解決辦法是用log，這樣乘法就變成了加法）
維特比算法（解決效率問題）
生成所有可能的分詞後，可以将其轉化成圖來做，如下面例子所示。
轉化成圖之後，計算最佳的分詞組合就是計算圖的最短路徑（之是以最短路徑是取了詞的機率的負對數，這樣可以計算最小值），可以用維特比算法，核心是動态規劃。
總結
分詞的方法如下：
基于比對規則的方法（最大比對算法）
基于機率統計的方法（LM，HMM，CRF）
——來源于貪心科技NLP講解