雙向最大比對算法python_基于詞典比對的中文分詞

中文分詞在中文的自然語言處理裡非常重要，比如在中文的搜尋引擎(動手做一個簡單的本地搜尋引擎)或者語義分析中，詞語粒度的分析效果是非常好的。

本篇介紹基于詞典比對的中文分詞算法。

1. 使用效果

1.1 輸入

輸入待分詞的句子或文章，如：

黑夜給了我黑色的眼睛，我卻用它尋找光明。

1.2 輸出

傳回分詞結果：

黑夜/給/了/我/黑色/的/眼睛/，/我/卻/用/它/尋找/光明/。

2. 使用過程

2.1 模型訓練

1. 根據已經分好詞的訓練語料，統計詞頻，得到詞典。

Done。

基于詞典比對的中文分詞就是這麼簡單。

當然，其它的效果更好的模型，訓練過程就複雜得多了，後續會不斷分享。

2.2 模型測試

1. 加載詞典。
2. 對輸入語句進行分詞。

2.3 模型評估

2.3.1 測試資料

自然語言是一個不好量化的領域，中文分詞的結果沒有事實上的标準，語言學家标注的分詞結果有的時候也存在争議。

在對比不同的中文分詞模型的效果與性能時，選擇同樣的标注資料進行評估，可以在一定程度上對比下模型之間的優劣。

本篇選用第二屆國際漢語分詞評測比賽(http://sighan.cs.uchicago.edu/bakeoff2005/)提供的資料中的msr資料，包括:

訓練資料：training/msr_training.utf8

測試資料：testing/msr_test.utf8

測試資料基準資料：gold/msr_test_gold.utf8

2.3.2 評價名額

标準的中文分詞評測的次元很多，包括詞典内外的分詞效果等，本篇隻關注3個名額：

精準率: Precision

召回率: Recall

Precision與Recall的調和均值: F1_score

分詞結果對比示例，

測試結果: [中國/人/真/偉大]， 一共4個詞語。

基準結果: [中國人/真/偉大]，一共3個詞語。

正确分出的詞語是2個：[真，偉大]

Precision = 2 / 4

Recall = 2 / 3

2.3.3 測試過程

1. 使用分詞算法對待測試檔案testing/msr_test.utf8分詞。
2. 将分詞結果與測試資料基準資料gold/msr_test_gold.utf8進行比對。

3. 模型訓練

3.1 生成詞典

4. 模型測試：分詞

4.1 加載詞典

以下正向、反向以及雙向最大比對算法均需要首先加載詞典。

4.2 正向最大比對算法

從左到右掃描待分詞句子，從最大長度開始比對，如假定最大分詞長度為5。

這鐘聲，傳遞出中華民族從磨難中奮起的昂揚鬥志，彰顯出偉大民族精神在新時代煥發出的熠熠光輝。

1. 依次判斷“這鐘聲，傳”、“這鐘聲，”、“這鐘聲”、“這鐘”以及“這”是否在詞典裡，如果有一個在詞典裡，則在該詞語處切分。
2. 如果所有詞語都不在詞典裡，則在第一個字處切分。
3. 往右繼續相同切分方式。

最終得到正向最大比對分詞結果：

這/鐘聲/，/傳遞/出/中華民族/從/磨難/中/奮起/的/昂揚/鬥志/，/彰/顯出/偉大/民族/精神/在/新時代/ 煥發/出/ 的/熠熠/光輝/。

4.3 反向最大比對算法

一些學者發現的現象是，在中文裡，往往作者表達更含蓄，最想要表達的含義在句子的末尾部分；在現實中反向最大比對算法有時候表現得更好。

反向最大比對算法從右往左從句子的末尾開始比對，假定仍然選擇最大詞語長度為5，

1. 依次判斷“熠熠光輝。”、“熠光輝。”、“光輝。”、“輝。”以及“。”是否在詞典裡，如果在，則在該詞語處切分。
2. 如果所有詞語都不在詞典裡，則在最後一個字處切分。
3. 往左繼續相同切分方式。

反向最大比對分詞結果：

這/鐘聲/，/傳遞/出/中華民族/從/磨難/中/奮起/的/昂揚/鬥志/，/彰/顯出/偉大/民族/精神/在/新時代/ 煥/發出/ 的/熠熠/光輝/。

與正向最大比對最明顯的不同是，反向會把“煥發出”分成“煥”與“發出”；而正向分成“煥發”與“出”。方向性非常明顯。

4.4 雙向最大比對算法

雙向最大比對算法同時進行正向與反向最大比對，從兩個結果裡啟發式地選擇最好的一個：

1. 比較兩種分詞結果分出的詞的總數量，選擇詞語數量少的那一個；如在“中華/民族/真/偉大”與“中華民族/真/偉大”裡選擇後者，前者有4個詞語，後者有3個詞語，認為後者對詞典利用得更好。
2. 如果兩種分詞詞語數量相等，選擇單字個數少的那一個；如在“中國人/真/偉/大”與“中國/人/真/偉大”中選擇後者，二者都有4個詞語，後者隻有2個單字，而前者有3個單字，單字少的意味着兩字以上的詞語更多，多字詞語比單字往往能表達更多含義。

5. 模型評估

5.1 對測試檔案分詞

對測試檔案周遊每行分詞。

5.2 模型評估

5.2.1 模型評估計算

同步對比測試與基準資料。

精準率Precision等于測試資料正确分詞個數除以測試資料總的分詞個數。

Precision = num_words_correct / num_words_predict

召回率Recall等于測試資料正确分詞個數除以基準資料總的詞語個數。

Recall = num_words_correct / num_words_baseline

是以，核心是要計算測試資料正确分詞個數。

這裡不能直接計算兩個數組的交集個數，因為分詞結果是有序的。如：

測試資料：['大', '家', '都是', '大學生']

基準資料：['大家', '都', '是', '大', '學生']

直接考慮交集，會認為'大'是一個正确的分詞。然而一個'大'在句子的開頭，一個在句子的靠後位置，實際上測試資料一個詞也沒有切分正确。

在計算交集的時候，必須要考慮詞語在句子中的位置。

将每一個詞在句子中的位置用起始位置表示出來，用python的區間表示方式，左邊為閉區間，右邊為開區間，則上述資料的位置表示為，

測試資料：[(0, 1), (1, 2), (2, 4), (4, 7)]

基準資料：[(0, 2), (2, 3), (3, 4), (4, 5), (5, 7)]

得到了互相不重疊的順序的區間起始集，進而可以轉換成集合set來取交集。

計算起來就比較直接了。

5.2.2 模型評估結果

模型	Precision	Recall	F1_score
正向最大比對	0.9120	0.9541	0.9325
反向最大比對	0.9101	0.9522	0.9306
雙向最大比對	0.9121	0.9536	0.9324

注：最大詞語長度設定為6。

6. 總結

本篇介紹了簡單的基于詞典比對的中文分詞算法，簡單易用。

當然，也因為過于簡單，在工業界生産系統上使用效果會不夠好；我們需要研究更好的中文分詞算法。

7. 參考資料

1. jieba分詞：https://github.com/fxsjy/jieba
2. HanLP分詞：https://github.com/hankcs/HanLP
3. 《自然語言處理入門》，何晗(HanLP作者)。

詳細代碼見我的Github，有問題歡迎一起讨論。