基于數(shù)據(jù)詞典的中文分詞算法優(yōu)化實現(xiàn)

鮑曙光

（武警海警學院 職業(yè)教育中心，浙江 寧波 315801）

0 引 言

分詞技術(shù)是中文自然語言理解的基礎，中文分詞技術(shù)的重點和難點是分詞算法、新詞發(fā)現(xiàn)、歧義消除等。目前，常用的中文分詞工具有很多，包括盤古分詞、Yaha 分詞、Jieba分詞、清華THULAC 等。中文分詞技術(shù)已經(jīng)比較成熟，有些研究者利用神經(jīng)網(wǎng)絡模型來實現(xiàn)分詞技術(shù)。本文作者查閱了相關(guān)文章，發(fā)現(xiàn)介紹中文分詞技術(shù)現(xiàn)狀和原理的文章比較多，但具體描述算法實現(xiàn)的文章并不多。本文力求用簡潔實用的模型和翔實可靠的實驗數(shù)據(jù)，闡述基于數(shù)據(jù)詞典中文分詞算法優(yōu)化的實現(xiàn)。文中所使用的分詞算法是課題小組基于C#自行開發(fā)的分詞算法，課題小組通過對算法的設計和改進，了解影響分詞算法運算速度的主要因數(shù)，完成了幾種基本分詞算法的設計與實現(xiàn)，并將之應用于新詞發(fā)現(xiàn)和歧義消除。

1 分詞算法

分詞算法可以分為三大類：第一類是基于數(shù)據(jù)詞典的分詞算法，第二類是基于統(tǒng)計分析的分詞算法，第三類是混合算法。本文介紹的是基于數(shù)據(jù)詞典的分詞算法。

1.1 基本思路

基于數(shù)據(jù)詞典的分詞算法的原理很簡單，即先將文章分成段，再將段分成句子，然后對句子進行分詞。假設句子由個字符組成，那么存在1+2+3…+=（+1）/2 種字符串組合（稱為“待匹配詞”），將待匹配詞與詞典中的現(xiàn)有詞進行匹配，最終輸出匹配結(jié)果。假設字符數(shù)=100，可能存在的待匹配詞為100×101/2=5 050 個，如果將段落分成5 句由20 個字符組成的句子，那么待匹配詞組合數(shù)為：5×20×21/2=1 050 次。

1.2 基本框架

本文作者采用Visual Studio 2012 作為開發(fā)環(huán)境，編寫了分詞算法類Segmentation、數(shù)據(jù)庫操作類DatabaseMethods、文件操作類FileMethods、數(shù)據(jù)庫詞典構(gòu)造和維護類DatebaseDictionary 等操作類，代碼如圖1所示。

圖1 分詞算法代碼縮略圖

1.3 常見算法

根據(jù)從字符串中獲取字符順序的不同，分為正向分詞算法和逆向分詞算法。根據(jù)匹配時最長詞與最短詞優(yōu)先順序的不同，分為最長詞匹配算法和最短詞匹配算法。根據(jù)是否匹配所有待匹配詞，分為全匹配算法和單匹配算法。

例如，字符串“我愛中華”，圖2展示了不同的取詞方式。

圖2 不同匹配算法取詞結(jié)果圖

通過上圖我們可以更好地理解正向、逆向分詞算法和最長、最短詞匹配算法，主要區(qū)別在于匹配時取詞方式不同。全匹配算法和單匹配算法主要區(qū)別在于匹配次數(shù)的不同，全匹配算法的匹配次數(shù)為（+1）/2 次，單匹配算法是全匹配算法的優(yōu)化算法，即對某一字符對應的所有待匹配詞進行匹配時，一旦有一個待匹配詞與數(shù)據(jù)詞典中的現(xiàn)有詞匹配就會結(jié)束匹配，因此單匹配算法的匹配次數(shù)小于前者。

“逆向最長詞單匹配算法”簡化代碼為：

例句：我愛中華人民共和國

逆向取詞算法中，對以上例句進行分詞，當=9，=5，=2 時，取字符Line.Substring(n- i - 1, 1)=“華”，待匹配詞Line.Substring(j, n-i-j)=“中華”。

影響分詞匹配速度和準確度的關(guān)鍵是數(shù)據(jù)詞典結(jié)構(gòu)和算法優(yōu)化。下文詳細介紹不同數(shù)據(jù)詞典和算法的實驗比較結(jié)果。

2 數(shù)據(jù)詞典

課題小組采用txt 文件和關(guān)系數(shù)據(jù)庫作為數(shù)據(jù)詞典的存儲介質(zhì)，它們各有利弊。

2.1 數(shù)據(jù)庫詞典

課題小組建立以下結(jié)構(gòu)的表，組織數(shù)據(jù)詞典。詞典內(nèi)容以《現(xiàn)代漢語詞典（第6 版）》為基礎，進行數(shù)字化：

（1）數(shù)據(jù)表AllWord（存儲所有字、詞或短語的表）

ID、CCharacter、Word、Meaning（ID 號、字符、詞、詞的釋義）

表記錄格式為：

（2）數(shù)據(jù)表CharacterIndex（存儲以某字為首字符的所有詞組成的字符串索引表）

ID、CCharacter、WordString、WordNum、CallNum、atFrontValues、atBackValues（ID 號、字符、該字對應所有詞組成的字符串、由該字組成詞的個數(shù)、該字在樣本中出現(xiàn)的次數(shù)、該字在詞首出現(xiàn)的概率、該字在詞尾出現(xiàn)的概率）

表中字段WordString，格式為：

阿：阿鼻地獄：阿昌族：阿斗：阿爾茨海默病：阿爾法粒子：阿爾法射線：阿飛：阿伏伽德羅常量：阿公：阿訇：阿拉伯人：阿拉伯數(shù)字：阿蘭若：阿羅漢：阿貓阿狗：阿門：阿片：阿婆：阿Q：阿是穴：阿嚏：阿姨：阿附：阿膠：阿彌陀佛：阿諛

（3）數(shù)據(jù)表NewWord（存儲提取的新詞的表）

ID、Word、WordLength、WordKind、ExtractNum、PossibleValues、ExampleSentence（ID 號、字詞、詞的長度、詞的類型、被提取次數(shù)、可能為新詞的概率、例句）

數(shù)據(jù)表記錄格式為：

19654 奧委會3 0 19 3 感謝|國際|奧|委|會|長期|以來|為|中國|體育|事業(yè)|發(fā)展|作出|積極|貢獻

2.2 TXT 文件詞典

可以將數(shù)據(jù)庫詞典轉(zhuǎn)化為txt 文件，即每一條記錄對應一行，去掉不需要的字段，保留關(guān)鍵字段。

例如：可將AllWord 表轉(zhuǎn)化為AllWord.txt，即去掉其他字段，只保留Word 字段。可將CharacterIndex 表轉(zhuǎn)化為CharacterIndex.txt，即去掉其他字段，只保留WordString 字段。

2.3 數(shù)據(jù)詞典優(yōu)劣比較

課題小組對Access 數(shù)據(jù)庫、SQL Server 數(shù)據(jù)庫與txt文件等不同介質(zhì)的數(shù)據(jù)詞典進行性能比較。本文中所有算法的測試選用配置較低的個人計算機（基本配置：CPU 為Intel(R) G630 2.7 GHz；內(nèi)存為12 GB；系統(tǒng)為win764 位旗艦版）來實現(xiàn)。不同數(shù)據(jù)詞典的測試結(jié)果如表1所示。

表1 不同數(shù)據(jù)詞典的測試結(jié)果列表

顯然，從以上實驗數(shù)據(jù)可以看出，數(shù)據(jù)詞典類型對算法速度的影響較大，txt 文件比大型數(shù)據(jù)庫SQL Server 和小型數(shù)據(jù)庫Access 更加高效和便捷，但是txt 文件在數(shù)據(jù)詞典維護和可視化方面存在一定的不足。在訪問速度上，SQLServer 具有較大優(yōu)勢；在安裝和使用方面，Access 更為簡單和靈活。經(jīng)過綜合考慮，對于單機版分詞算法，課題小組選擇Access 進行數(shù)據(jù)詞典的生成和維護，選擇txt 文件作為分詞算法的數(shù)據(jù)來源，使它們能夠充分發(fā)揮各自的優(yōu)勢。

3 算法優(yōu)化

分詞算法中的主要操作是詞的匹配和數(shù)據(jù)讀取。減少匹配次數(shù)可以通過“單匹配”算法實現(xiàn)。在實驗中發(fā)現(xiàn)，最短詞單匹配算法比全匹配算法可以減少約50%的匹配次數(shù)，最長詞單匹配算法比全匹配算法可以減少約30%的匹配次數(shù)，但是在訪問數(shù)據(jù)詞典相同次數(shù)的情況下，運算時間幾乎一樣。這也充分驗證了每次訪問數(shù)據(jù)庫或文件時，需要消耗的時間長、資源多，相較于讀取數(shù)據(jù)庫或文件（涉及硬盤數(shù)據(jù)讀取）的時間，循環(huán)匹配操作（主要為內(nèi)存之間數(shù)據(jù)操作）的時間可以忽略不計（測試實驗中發(fā)現(xiàn)，前者是秒級，后者是毫秒級）。為此，算法優(yōu)化的方法有兩個：一是減少數(shù)據(jù)詞典的訪問次數(shù)；二是優(yōu)化數(shù)據(jù)結(jié)構(gòu)，建立索引表。

3.1 減少數(shù)據(jù)詞典訪問

在分詞算法中，最原始的方法是匹配多少次，就要對數(shù)據(jù)詞典訪問同樣的次數(shù)。這種算法消耗的時間很長，可參看表2第1 條數(shù)據(jù)。

利用數(shù)組緩存的功能，盡量減少在循環(huán)算法中對數(shù)據(jù)詞典的訪問：

（1）讀取數(shù)據(jù)詞典次的思路。在分詞算法第1 層循環(huán)中，按照一定的順序讀取句子中的每個字符，然后在AllWord 文件或表中，取出以該字符為首字符的所有詞（以下稱“前綴詞”），再將這些前綴詞組成前綴詞字符串（WordString），與待匹配詞進行匹配。

（2）只讀取數(shù)據(jù)詞典1 次的思路。可以在分詞算法第1 層循環(huán)前，一次性取出句子中所有字符的前綴詞字符串，將其存放在數(shù)組中，供分詞算法在第2 層循環(huán)中匹配使用。

算法的測試數(shù)據(jù)如表2所示。

從表2中可以發(fā)現(xiàn)，從讀取數(shù)據(jù)詞典（+1）/2 次變成讀取數(shù)據(jù)詞典次的算法，所花費的運算時間呈數(shù)量級減少。

表2 讀取數(shù)據(jù)詞典不同次數(shù)的測試結(jié)果列表

3.2 訪問索引數(shù)據(jù)詞典

課題小組根據(jù)《現(xiàn)代漢語詞典（第6 版）》建立的AllWord 數(shù)據(jù)表，共包含65 134 條記錄，所建立的CharacterIndex 索引表共包含8 260 條記錄（整理過程可能存在一定誤差）。數(shù)據(jù)表AllWord 中的CCharacter 和Word 是一對多關(guān)系，而索引表CharacterIndex 中的字段CCharacter和WordString 是一對一關(guān)系。索引表CharacterIndex 的數(shù)據(jù)組織方式雖然不符合關(guān)系數(shù)據(jù)庫范式要求，但是在這里卻能夠發(fā)揮重要作用，也是本文分詞算法的創(chuàng)新點。在建立CharacterIndex 索引表后，可以將分詞算法優(yōu)化成只訪問一次數(shù)據(jù)詞典，就可以取出某一句子所有字符對應的WordString，并將其存放在數(shù)組中供第2 層循環(huán)中匹配。通過實驗對比可以證實，建立CharacterIndex 表對匹配算法的速度具有很重要的影響，測試結(jié)果如表3所示。

表3 使用索引表的測試結(jié)果列表

引入CharacterIndex 格式的數(shù)據(jù)詞典，在不同算法和不同數(shù)據(jù)結(jié)構(gòu)的情況下，運算速度上有較大差異。

通過實驗，將CharacterIndex 表按使用頻度倒敘排列，再對匹配算法進行改進，匹配速度又能提升1 倍。將CharacterIndex 表一次性讀取到內(nèi)存數(shù)組，匹配速度又能提升1 倍。測試結(jié)果如表4所示。

表4 不同排序索引表及讀取方式的測試結(jié)果列表

4 算法應用

4.1 新詞發(fā)現(xiàn)

很容易發(fā)現(xiàn)，對于個字符，如果進行排序組合的話可以有n種組詞可能（包括單字符詞）。對于由個字符組成的句子，在分詞過程中，匹配了個詞，那么新詞的可能組合是（+1）/2--種（不包括單字符詞）。課題小組制作的數(shù)據(jù)詞典共收錄漢字8 260 個，收錄兩個字以上的詞54 165 個，相對于8 260-54 165-8 260 種未登錄新詞的組合，數(shù)據(jù)詞典中的登錄詞只能算是滄海一粟。

在實驗過程中發(fā)現(xiàn)，根據(jù)《現(xiàn)代漢語詞典（第6 版）》制作的數(shù)據(jù)詞典中，竟然沒有收錄“游樂場、市長、女孩、中國、艦長、更多、美國、北京、中方、我國、西部、上海、面向”等常用的詞。

尋找新詞的關(guān)鍵是找到新詞組成的規(guī)律。通過觀察發(fā)現(xiàn)，一個句子經(jīng)過分詞后，連續(xù)單獨字符串中很有可能存在數(shù)據(jù)詞典中未登錄的新詞，例如：分詞結(jié)果“不斷||科學發(fā)展|的|根基”“也有||的|自主|創(chuàng)業(yè)|者”中的“夯|實”“敢|闖|新|路|的”都可稱之為連續(xù)單獨字符串，在這些連續(xù)單獨字符串中存在新詞“夯實”“敢闖新路”。或者，該單獨字符串前一個詞或后一個詞與單獨字符串毗鄰字符組成新詞，例如：分詞結(jié)果“在|”，存在新詞“黨中央”。課題小組根據(jù)這個規(guī)律發(fā)現(xiàn)新詞，然后通過詞長、被提取的頻度、詞的黏連度、詞性、上下文信息關(guān)聯(lián)度等來輔助新詞的發(fā)現(xiàn)。

4.2 歧義發(fā)現(xiàn)

引起切分歧義的情況有很多，對于基于數(shù)據(jù)詞典的分詞技術(shù)，有很大一部分歧義是因該收錄的詞而數(shù)據(jù)詞典中未收錄引起的，即未登錄詞的分詞歧義。除此之外的歧義可以分為交集型歧義、組合型歧義和真歧義三種類型。交集型歧義如“爭|當時|代|先鋒|”與“爭|當|時代|先鋒|”。組合型歧義如“維護|社會主義|法制”與“維護|社會|主義|法制”。真歧義如“乒乓球|拍賣|光|了”與“乒乓|球拍|賣光|了”。發(fā)現(xiàn)歧義的思路很簡單，就是采用不同算法進行分詞，如果得到不同分詞結(jié)果就表示存在歧義。

使用正向最長詞分詞算法和逆向最短詞分詞算法的測試界面如圖3所示。

圖3 分詞算法執(zhí)行代碼圖

課題小組對2010年人民日報社論文章（29 871 個字符，分隔后2 676 個句子），用正向最長詞分詞算法和逆向最短詞分詞算法，得到有歧義的句子418 句，其中交集型歧義和組合型歧義各占50%左右。用正向最長詞分詞算法和正向最短詞分詞算法，得到有歧義的句子383 句。實驗結(jié)果表明，最長詞分詞算法和最短詞分詞算法相互結(jié)合，更容易找出組合型歧義；正向算法和逆向算法相互結(jié)合，更容易找出交集型歧義。相形之下，使用正向最長詞分詞算法和逆向最短詞分詞算法最為高效實用。

5 結(jié) 論

課題小組采用自行設計分詞算法的方式，得到基于數(shù)據(jù)庫詞典的最優(yōu)分詞算法的代碼，通過數(shù)據(jù)實驗對比，分析了不同分詞算法的特點，闡述了不同算法在新詞和歧義發(fā)現(xiàn)中的應用，為課題小組在中文自然語言識別、人工智能開發(fā)領(lǐng)域提供一定的技術(shù)支撐。