中文斷詞系統 (CWSS)

Design an useful system on demand

一開始的起因在寫了一些爬蟲抓了一些文章，想要自動分析並且試圖寫一個自動產生文章的系統。在抓了三萬多篇文章 (共有 19792917 個字) 之後，想要了解是否可以設計一個簡單的斷詞系統，並且利用這個系統來自動產生新的文章。

斷詞

在斷詞系統中首先要找到可以分段的部分，在日耳曼語系中詞與詞中間都會使用空白作為間隔，本身就不需要斷詞。然而在中文語系中，詞與詞中間並不會有明顯的空白或符號，而在句讀大量使用之前中文書寫中並沒有顯著的段落，因此需要使用額外的演算法協助幫忙斷詞。

在一個已經藉由非中文字來當作分隔字元之後就可得到一段需要分析的中文句子，在這個句子中還需要額外的資訊來當作是斷詞的手段。斷詞的方式可以分為統計式、規則式與混合式。統計方式是使用現有資料利用統計學來找出潛在的分隔文字，而中文匯使用很多介詞、連詞或虛詞來修飾，這些詞出現的頻率會比其他的詞彙還要高。藉由先挑選出來這些詞，斷詞系統可以將原本較長的中文句子切割為若干更短的段落。

用我在 blog 上的文章為例，使用一個簡單的 Python 程式就可以得到 2328 個非 ASCII 字元 (386 個不重複字元)，其中有 115 個字元只出現過一次。這表示大多數的字都可以被當作關鍵字，而出現最多的字的就出現了 126 次，佔了全部數量的 5%，遠超過第二名的語 (55 次)，這些常見的字也可以被當作是分隔字元來使用。

import string
import json

words = [_ for _ in lines if _ not in string.printable]
words = {_: words.count(_) for _ in set(words)}

可以藉由句讀將一個片段，根據不同長度的詞來找到潛在的常用詞，因此可分割為若干較小的句子。藉由以下的程式可以找到文章中出現超過 20 次的詞有：語言、一個、程式、設計這四個詞，這也表示我們還可以利用這些常見的短詞將文章分割為更小的片段。

import re

pattern = re.compile(   r'[a-zA-Z0-9(){}\[\]<>/\.\-_#*=:;?,+\\\^%\'\"]|'
                        ur'[：。，、]',
                        flags=re.UNICODE)
lines = pattern.sub(u' ', lines)

words = [line for line  in lines.split()]
words = [line[_:_+width] 	for line in words
                            for width in range(2, len(line))
                            for _ in range(0, len(line)-width)]
words = {_: words.count(_) for _ in set(words)} ))}

問題：合併處理

當常見單字與常見單詞合併處理時，我們就需要一個策略來解決衝突的狀況。像是我們用上述的例子，得到了程是前 15 常出現的單次，然而我們也清楚這個字在常見中文中並不常出現。反之，從常見兩字單詞中可以找到程式是最常出現的單詞，而常見的詞來說長度代表著這個詞的重要程度。

因此可以有一個策略解決不同長度的常見詞：將長度跟出現的頻率同時考量進去。如果將單純將出現的頻率乘上詞的長度，則無法突顯出長度的重要性，因為一個長度為 4 的複合單詞，出現的頻率一定低於或等於分別統計的頻率，所以長度這個參數需要額外加權：假若在這個前提之下發現同時符合兩個關鍵詞時，以長度為優先：例如什麼跟 為什麼 同時出現，則會選擇用後者 (因為長度優先) 作為斷詞的依據。

問題：歧義 Ambiguity

中文斷詞中若不考慮詞之間的關聯性，則會容易產生歧義的狀況發生。以 柯民調這麼低沒道理讓他直接連任 為例只少有以下兩種斷詞方式：

柯/民調/這麼/低/沒/道理/讓/他/直接/連任
柯民/調/這麼/低/沒/道理/讓/他/直/接連/任

在 15 個字當中有以上兩種拆解的方式，分別拆成 10 跟 11 兩種片段。在沒有額外的資訊下，會選擇較少片段的拆解方式，這也表示我們可以用較少的關鍵字來拆解時，會得到比較好的結果。

問題：Unicode

再處理斷詞的時候，遇到了一個詭異的問題：unicode 在不同的 OS 會有不同的處理方式。在 Unicode 中有支援繪文字 (emoji) 。但在 Mac OS X 與 Linux 下分別使用 Python 2.7 卻得到不同的長度，因此在斷詞之前需要將 emoji 先替換成空白字元來當作是隱含的分隔字：

emoji = re.compile( u'(\ud83d[\ude00-\ude4f])|'
                    u'(\ud83c[\udf00-\uffff])|'
                    u'(\ud83d[\u0000-\uddff])|'
                    u'(\ud83d[\ude80-\udeff])|'
                    u'(\ud83c[\udde0-\uddff])|'
                    u'(\ud83e[\udd10-\uddbf]) '
                    , flags=re.UNICODE)
content = emoji.sub(u' ', post.content)

策略 / Strategy

斷詞策略是用來處理斷詞的一種方式：在斷詞之前，需要若干前置步驟來獲得基本的資料，之後再利用這些資料來針對文章做斷詞的處理。最基本的方式，可以利用統計方式來獲得斷詞的詞庫，也就是利用統計學找出來最常出現的詞。雖然統計方式的斷詞擁有高執行效率的特性，但大多只能處理單、雙字詞，但過程中需要儲存暫存的潛在詞而需要龐大的儲存空間。而啟發式 (heuristic) 斷詞則可以利用有限資訊找到近似解。

統計式斷詞

做斷詞之前我們需要有基本策略來區分常見詞，接著才會利用各種演算法來對文章斷詞。在找出常見詞之前，我們會先定義屬於我們的常見詞規則：像是出現高頻率出現的詞、短期頻繁出現的詞等。在這種架構下，我們可以快速利用統計學的方式找出來潛在的詞庫：

1. 單獨出現的單詞。
2. 全部文章常出現的單詞。
3. 單篇文章常出現的單詞。

根據上述的方法，我們可以找到統計學上的常見詞並建立詞庫。但是當一個單詞分別滿足所有條件時，就需個別賦予權重來表示我們更加看重哪一個規則 (預設權重=1)。像是對於單獨出現的單詞，我們就可以賦予較高的權重 (w=100)，因為這代表這個詞本身就常出現在段落當中，而單篇文章頻繁出現的詞則賦予較低的權重 (w=1)，因為單篇文章中的樣本空間小不具有代表性，但又需額外加權單篇文章中頻繁出現的單詞。

假若單純地從所有文章中列出所有長度為 1 的單字 (全部共有 16484900 個字)。經過統計之後，我們可以得到總共有 6530 個不重複單字，而最常出現的單字分別為的 (4.289%)、我 (3.696%)、了 (1.702%)、一 (1.693%)、不 (1.668%)、是 (1.638%)、有 (1.021%)、在 (0.973%)、他 (0.963%)。這些單字佔了全部單字的 17%，在斷詞中，可以藉由這些額外的資訊來增加斷詞的可能性。

跟常見詞相反，關鍵詞則是用來表示這段文字中最核心的概念，也就是在斷詞之後需要的處理策略。最常見的做法是利用 TF-IDF 來加權處理這個詞的重要程度，概念是：關鍵詞出現在文章的次數成正比，但與常用詞出現成反比。

啟發式斷詞

雖然統計式斷詞可以快速的找到常用詞庫，但對於新單詞 (流行詞) 卻難以找到，也就是很難快速找到罕用詞或關鍵詞，所以需要額外的演算法來預測潛在的單詞。啟發式斷詞則利用一個小範圍的啟發函數 (heuristic function) 來斷詞，並根據結果來修正這個函數。例如根據中文的特性，我們可以有幾個簡單的假設：

1. 發語詞、主詞、虛詞或語尾助詞一定是個常見詞
2. 段落開頭一定是一個單詞、發語詞或主詞
3. 段落結尾一定是一個單詞或語尾助詞
4. 虛詞前後一定是一個單詞
5. 單詞長度通常介於 2~4 個字，尤其以兩個字為大宗

根據這些簡單的假設就可以增加潛在的詞庫。但上述的假設需要賦予每個詞額外的屬性，建立辭庫階段，還沒辦法擁有足夠的資訊來建立 (假設不使用監督式學習 )，所以要轉換成更簡單的規則，其中常見詞 (F) 我們可以透過統計式斷詞得到：

1. 定義：單詞 (W)、開頭單詞 (S)、結尾單詞 (E) 與常見詞 (F)
2. 句子：S ( W+ E)?
3. {S, E, F} ∈ W
4. F ∈ {S, E}
5. P(F|W) ≈ 0.68
6. P(len(W) == 2 | W) ≈ 0.95

這就表示我們認為同樣長度的單詞，佔了前 68% 的單詞我們稱之為常見詞。