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

鮑曙光

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

0 引 言

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

1 分詞算法

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

1.1 基本思路

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

1.2 基本框架

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

圖1 分詞算法代碼縮略圖

1.3 常見算法

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

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

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

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

“逆向最長(zhǎng)詞單匹配算法”簡(jiǎn)化代碼為：

例句：我愛中華人民共和國(guó)

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

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

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

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

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

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

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

ID、CCharacter、Word、Meaning（ID 號(hào)、字符、詞、詞的釋義）

表記錄格式為：

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

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

表中字段WordString，格式為：

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

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

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

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

19654 奧委會(huì)3 0 19 3 感謝|國(guó)際|奧|委|會(huì)|長(zhǎng)期|以來|為|中國(guó)|體育|事業(yè)|發(fā)展|作出|積極|貢獻(xiàn)

2.2 TXT 文件詞典

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

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

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

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

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

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

3 算法優(yōu)化

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 算法應(yīng)用

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

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

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

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

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

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

使用正向最長(zhǎng)詞分詞算法和逆向最短詞分詞算法的測(cè)試界面如圖3所示。

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

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

5 結(jié) 論

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