斷詞的目的
為什麼需要斷詞？在文字處理上，我們通常會使用一組向量代表文字，因此會需要把字詞從一個句子或文章中抽出來。
英文很簡單，用空白來斷詞就好了，像是 “Nice to meet you” 我們可以切割成 Nice/to/meet/you。然而中文卻很難這樣斷詞，「很高興認識你」這句，究竟要斷成「很/高興/認識/你」還是「很高/興認/識你」呢？簡單來說，斷詞可以視為把句子再切成更小的、有意義的單位。
中文斷詞的困難點在於沒有空白協助斷詞、有時候詞語會有交集的字，讓前後詞彙都合理、即使使用人工方法也會有不一樣的結果，因判斷標準不一致、新詞語的辨別……
然而資料又相當大量，在這時候，我們就可以利用電腦學習如何斷詞。
斷詞的方法
基本上有主要的三種方法：
- 辭典分詞法：利用海量的資料，也就是辭典，去依照一些策略選擇字串。
- 機器學習算法
- 深度學習算法
基於字典的分詞法
以字典為依據，從長度最長的詞開始進行掃描。如果字典裡面沒有（像是流行語、新的詞等等），那可能會識別不出來。
另外之前有介紹過根據不同目地，有很多種類的語料庫。就像這些語料庫一樣，為了提升效率我們也可以設計多個字典。
基於字典的分詞法，演算法上我們會利用最大匹配法（maximal matching），像是正向最大匹配法（forward maximum matching）、反向最大匹配法（backward maximum matching）以及雙向最大匹配法。
其實雙向最大匹配法就是正向和反向算法都分一遍後，選取其中一種結果輸出。
拿正向最大匹配法為例子：
句子：「很高興在動物園認識你」，字典：「很、高、高興、在、動、動物、動物園、物、園、認、認識、識、你」，字典最大長度為 3。
第一輪掃描：
1. “很高興”，沒有。
2. “很高”，沒有。
3. “很”，有。
去除掃描到的詞”很”後，繼續第二輪。
第二輪掃描：
1. “高興在”，沒有。
2. “高興”，有。
去除掃描到的詞”高興”後，繼續第三輪。
第三輪掃描：
1. “在動物”，沒有。
2. “在動”，沒有。
3. “在”，有。
去除掃描到的詞”在”後，繼續第四輪。
第四輪掃描：
1. “動物園”，有。
去除掃描到的詞”動物園”後，繼續第五輪。
第五輪掃描：
1. “認識你”，沒有。
2. “認識”，有。
第六輪掃描：
1. “你”，有。
最終結果為：很／高興／在／動物園／認識／你。
而反向，就是從另一頭反向操作XD 那麼雙向最大匹配法要挑選的結果，主要原則是分詞數越少越好，若分詞數一樣，則看單個詞的數量，越少越好。像是以上面那個例子來說：
正向：分詞數 6，單個詞的數量 3。
反向：分詞數 7，單個詞的數量 4。
明顯正向結果較佳，因此輸出正向最大匹配法的結果。
字典樹（Trie Tree）
這棵樹是根據一個辭典建構的，這個字典會包含詞、詞頻、詞性。如果說有好幾個詞前面的字相同，就可以用 Trie Tree 所儲存，規則如下：
- 根節點不包含任何字
- 從根節點開始到某一個節點路徑上所連結的字，就是該節點對應的字串
- 每個節點的子節點包含的字都不相同
字典樹的查詢效率很高，但空間利用率很低，也有一些方式可以壓縮空間，但就會影響到查詢效率。
有向無環圖（DAG, Directed Acyclic Graph）
在圖論中，如果有向圖從任意頂點出發，各種路徑都無法回到該點時，則我們稱這個圖是「有向無環圖」。可以想像成環是要回到原點的一個圈，如果沒有繞成回原點的路徑表示沒有環形成，因此無環。每個有向樹都是有向無環圖、有向無環圖不一定是樹。
由上方敘述可得知，我們可以結合字典樹和有向無環圖，藉由字典查詢列舉所有可能的分割。
動態規劃（Dynamic Programming）
動態規劃算是一種基於遞迴關係的一種演算方式。將一個大問題拆解成小問題，而各字的小問題可能又來自各自拆解的小小問題，最經典的例子就是費波納契數列。
經典的中文斷詞法
有一個演算法是目前主流的中文斷詞演算法－－「結巴」，名字很有趣吧XD 他是基於機器學習下的算法，因此也有部分需要辭典資料作為依據（不過以中國的簡體字開發，所以打開都是簡體字為主 → dict.txt）。
在此先簡單介紹流程：
- 對於已經存在於辭典的字詞，會根據辭典產生 Trie 樹，並根據這個 Trie 樹給訂輸入句的有向無環圖。接著使用動態規劃來找出最大機率路徑。
- 若是不存在的字詞，則使用隱馬可夫模型（HMM）和 Viterbi 演算法來進行辨識。
註：關於動態規劃可參考此演算法筆記。
另外機器學習和深度學習算法，之後會直接開另外一個篇章介紹。
