基于字符樹結(jié)構(gòu)的高性能中文詞庫技術(shù)①

楊光豹， 楊豐赫， 鄭慧錦

1(浙江廣播電視大學(xué) 青田學(xué)院，青田 323900)

2(東南大學(xué) 網(wǎng)絡(luò)空間安全學(xué)院，南京 211189)

3(浙江青田縣職業(yè)技術(shù)學(xué)校，青田 323900)

引言

利用大數(shù)據(jù)技術(shù)處理海量中文信息是當(dāng)今很成熟的技術(shù)，而中文分詞作為中文信息處理的基礎(chǔ)，它是大數(shù)據(jù)處理中文信息的基礎(chǔ). 而中文分詞的性能與準(zhǔn)確度一直是相互制約的. 業(yè)內(nèi)對該技術(shù)的研究一直在性能與精確度兩個(gè)方向在推進(jìn). 中文分詞方法的研究從大的方向來講，大體分為兩大類：(1) 基于詞庫的字典的機(jī)械分詞法. (2) 采用統(tǒng)計(jì)學(xué)理論的統(tǒng)計(jì)分詞法. 比如文獻(xiàn)[1]是使用人工制作的分詞語料進(jìn)行特征信息學(xué)習(xí)的機(jī)器學(xué)習(xí)分詞法. 文獻(xiàn)[2，3]是通過雙向LSTM神經(jīng)網(wǎng)絡(luò)模型進(jìn)行分詞. 文獻(xiàn)[4]利用上下文詞長特征作為分詞特征，從上下文信息中獲取信息進(jìn)行分詞，這些都屬于統(tǒng)計(jì)分詞法. 這類分詞法在對未登錄詞與歧義詞的處理上占優(yōu)勢，但性能上不及機(jī)械法. 一種好的分詞技術(shù)往往都是采用綜合方法，以機(jī)械分詞為基礎(chǔ)，再融入統(tǒng)計(jì)法以提高分詞精確度. 例如文獻(xiàn)[5]利用統(tǒng)計(jì)學(xué)上的概率，引入層次分析法將多種切分法優(yōu)劣排序，幫助選擇最優(yōu)排序法，它在一定程序上提高了準(zhǔn)確率.在機(jī)械分詞中，為了提高性能，文獻(xiàn)[6]提出了前四字hash索引樹技術(shù). 文獻(xiàn)[7]提出了首字hash查詢的方法，文獻(xiàn)[8，9]提出了雙字hash法; 文獻(xiàn)[10]提出了對四字hash索引的trie樹進(jìn)行改進(jìn)，文獻(xiàn)[11]提出了利用首字hash法進(jìn)行正向與逆向的多方案分詞的選擇以減少分詞的歧義. 而文獻(xiàn)[12]卻提出了首字拼音首字母表. 目前為止，基于詞庫的中文分詞都有一個(gè)共同特點(diǎn)就是詞庫結(jié)構(gòu)都是：索引+余詞表. 在索引上采用各自認(rèn)為速度快，占用內(nèi)存小的方式來進(jìn)行查詢. 目前業(yè)內(nèi)普遍認(rèn)為采用前4字trie索引樹法的分詞技術(shù)性能最好. 而本文在實(shí)際編程中發(fā)現(xiàn)，利用字符樹結(jié)構(gòu)的分詞技術(shù)能更好地進(jìn)行中文分詞，無論從時(shí)間復(fù)雜度還是空間復(fù)雜度，字符樹分詞技術(shù)都更勝于其它各種詞庫技術(shù)，它能進(jìn)一步改善大數(shù)據(jù)處理中文信息的性能.

1 字符樹分詞原理

1.1 單字符樹原理

單字符樹是在各個(gè)節(jié)點(diǎn)上都保存單個(gè)字符的樹.將詞庫文件加載到內(nèi)存時(shí)，所有的詞都將先被分割成一個(gè)個(gè)的單字，然后逐個(gè)“掛接”在一棵樹上. 一個(gè)詞的所有字加載完后在最后一個(gè)字節(jié)點(diǎn)上作詞串標(biāo)記，然后加載第二個(gè)詞的各個(gè)字，如果這棵字符樹上該位置已經(jīng)存在要加載的字，則視為已加載(不覆蓋)，但如果是詞的最后一個(gè)字符，則要對它的詞串標(biāo)記進(jìn)行修改.整棵樹的構(gòu)造如圖1所示.

單字符樹的各個(gè)節(jié)點(diǎn)都采用同樣的數(shù)據(jù)結(jié)構(gòu)，每個(gè)節(jié)點(diǎn)中都有一個(gè)詞串標(biāo)記isword，如果其值為true則表示從根到該節(jié)點(diǎn)為止的路徑構(gòu)成一個(gè)詞，否則僅僅是詞的中間節(jié)點(diǎn). 其數(shù)據(jù)結(jié)構(gòu)如圖2所示.

圖1 單字符樹詞庫構(gòu)造舉例

圖2 單字符樹詞庫節(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)

查詢一個(gè)詞只需要從根節(jié)點(diǎn)開始，例如查詢“中國”這個(gè)詞，只需要從根節(jié)點(diǎn)開始先找“中”，找到后再在“中”的子節(jié)點(diǎn)中找“國”找到后再看這個(gè)“國”的節(jié)點(diǎn)中的詞串標(biāo)記是否是true，如果是true，則說明詞庫中存在“中國”. 否則就不存在. 這樣構(gòu)造起來的字符樹最大的好處是不會(huì)出現(xiàn)無效查詢，當(dāng)查詢詞庫中存在的詞，比如想查詢“千方百計(jì)”，它從樹根逐級查詢會(huì)有一條路徑存在，最后依據(jù)路徑末端節(jié)點(diǎn)的詞串標(biāo)記來判斷.查詢詞庫中不存在的字符串時(shí)，要么路徑不存在，要么路徑末端節(jié)點(diǎn)的標(biāo)記是false.

1.2 多字符樹原理

多字符樹是從單字符樹演變過來的一種變異樹.它的設(shè)計(jì)思路與單字符樹類同. 只是為了減少節(jié)點(diǎn)數(shù)，把字符樹中出度為1，詞串標(biāo)記為false 的節(jié)點(diǎn)字符連在一起放在一個(gè)節(jié)點(diǎn)上，直到節(jié)點(diǎn)出度大于1或標(biāo)記位為true為止，但它的查詢思路與單字符樹是一樣的，都是從樹根開始向各個(gè)分支逐級查詢，加載時(shí)相同的前綴也只加載一份.

多字符樹的構(gòu)造過程是這樣的：例如“ABCDEF”是一個(gè)詞，開始加載這個(gè)詞時(shí)，將它作為整體掛在根節(jié)點(diǎn)的一級子節(jié)點(diǎn)上，此時(shí)如果加載第二個(gè)詞“ABCMN”，由于有共同的前綴“ABC”，于是將原來的節(jié)點(diǎn)“ABCDEF”進(jìn)行“裂變”，產(chǎn)生共同前綴的節(jié)點(diǎn)為父節(jié)點(diǎn)“ABC”，子節(jié)點(diǎn)為“DEF”，然后再把要插入的“ABCMN”這個(gè)詞的共同前綴去掉，剩下的字符構(gòu)成一個(gè)節(jié)點(diǎn)“MN”，并把它掛在“ABC”節(jié)點(diǎn)下的子節(jié)點(diǎn)數(shù)組中. 此時(shí)如果要加載ABC這個(gè)詞，則只需要將“ABC”節(jié)點(diǎn)的標(biāo)記位設(shè)為true即可. 而沒有共同前綴的詞都掛在根節(jié)點(diǎn)的一級子節(jié)點(diǎn)上，依此類推將所有詞庫文件中的詞加載到這棵樹上. 整棵樹的構(gòu)造如圖3所示，節(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)如圖4所示.

圖3 多字符樹詞庫構(gòu)造舉例

圖4 多字符樹詞庫節(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)

多字符樹結(jié)構(gòu)的詞庫節(jié)點(diǎn)總數(shù)比單字符樹少，但它的查詢過程與單字符樹相同，需要逐個(gè)比較字符，所以它的查詢性能與單字符樹是相同的. 它總節(jié)點(diǎn)數(shù)少是否意味著內(nèi)存占用少呢? 事實(shí)并非如此. 本實(shí)驗(yàn)詞庫加載成多字符樹時(shí)，節(jié)點(diǎn)總數(shù)是291 893個(gè)，約是單字符樹的節(jié)點(diǎn)數(shù)目的3/4; 它平均每個(gè)節(jié)點(diǎn)大約擁有1個(gè)詞，但因?yàn)槎嘧址麡渲械拿總€(gè)節(jié)點(diǎn)保存的字符數(shù)目是不確定的，所以它不能全部直接存儲(chǔ)在節(jié)點(diǎn)上，只能將節(jié)點(diǎn)字符串中第一個(gè)字符保存在節(jié)點(diǎn)上，而多出的字符只能以數(shù)組的形式用指針“掛”在節(jié)點(diǎn)上，這樣以來，每個(gè)節(jié)點(diǎn)必須要多出一個(gè)指針字段進(jìn)行掛接字符串，而且多出的字符需另外申請空間來存放，這將在內(nèi)存占用上比單字符樹要大得多，后文實(shí)驗(yàn)數(shù)據(jù)會(huì)證明這一點(diǎn).

2 各詞庫查詢性能分析

無論是單字符樹還是多字符樹，它們都不是索引樹. 因?yàn)樗鼈儧]有所謂的“余詞正文”，所有的詞都已經(jīng)在這棵樹上，它只是把詞庫的存儲(chǔ)方式從“表”變成“樹”，它不需要索引.

為了比較整詞法，trie索引樹法以及單字符樹與多字符樹等在詞庫成功查詢上的性能區(qū)別，我們采用順序訪問的平均訪問長度作為衡量各種詞庫性能的指標(biāo)，以此比較它們在查詢性能上的優(yōu)劣.

2.1 字符樹詞庫查詢長度統(tǒng)計(jì)分析

由于單字符樹與多字符樹在查詢原理上相同，所以查詢性能相同，在性能比較時(shí)以單字符樹為代表參與. 之所以引用兩種結(jié)構(gòu)的字符樹是為了研究它們占用的內(nèi)存區(qū)別.

單字符樹詞庫構(gòu)造完成后各節(jié)點(diǎn)的統(tǒng)計(jì)數(shù)據(jù)如表1所示. 本實(shí)驗(yàn)詞庫中最長的詞是16個(gè)字，所以單字符樹的最大層次是16，每一層的節(jié)點(diǎn)中如果有孩子，它會(huì)派生出下一層的子節(jié)點(diǎn)，它將作為下一層節(jié)點(diǎn)的父節(jié)點(diǎn)統(tǒng)計(jì)，而沒有孩子的節(jié)點(diǎn)不作為下一層節(jié)點(diǎn)的父節(jié)點(diǎn)統(tǒng)計(jì)，節(jié)點(diǎn)平均訪問長度是指從父節(jié)點(diǎn)到本節(jié)點(diǎn)需要的平均訪問次數(shù)，詞串的訪問長度是指一個(gè)詞各節(jié)點(diǎn)的訪問長度之和，而詞串平均訪問長度是指同一長度的詞串的訪問長度的平均值. 由表1可知，字符樹中各詞串的平均訪問長度是3371，其主要由一級節(jié)點(diǎn)數(shù)量 (常用漢字?jǐn)?shù)量) 決定. 它的詞庫查詢時(shí)間復(fù)雜度為O(1)

2.2 trie索引樹詞庫查詢長度統(tǒng)計(jì)分析

trie索引樹結(jié)構(gòu)以索引字?jǐn)?shù)分為四類：前1字trie索引樹trie1，前2字trie索引樹trie2，前3字trie索引樹trie3，前4字trie索引樹trie4. 它們前n字(n為1，2，3，4)與字符樹結(jié)構(gòu)相同，但字?jǐn)?shù)長度超過n的詞，其剩余部分全部存在同一張“余詞表”中，所以將余詞表視為同一層次的節(jié)點(diǎn)，以trie4為例，其平均訪問長度統(tǒng)計(jì)如表2所示. 各類trie索引樹的平均訪問長度統(tǒng)計(jì)方法與表2相同，限于篇幅，在此不再一一舉出.

表1 單字符樹詞庫平均訪問長度統(tǒng)計(jì)表

表2 前四字trie樹詞庫平均訪問長度統(tǒng)計(jì)表

2.3 整詞詞庫查詢長度分析

整詞詞庫的平均訪問長度直接受詞庫總詞條數(shù)量影響，假設(shè)詞庫總詞條數(shù)量為n，則它在順序查詢時(shí)，成功查詢的平均訪問長度為n/2，失敗查詢長度為n. 所以它的詞庫查詢的時(shí)間復(fù)雜度為O(n). 它的性能會(huì)隨著詞庫的增大而變慢. 本實(shí)驗(yàn)詞庫中它的平均訪問次數(shù)是139 548次，是字符樹平均訪問次數(shù)的41倍. 隨著詞庫條目的增大，兩者性能差距將越來越大.

2.4 各類詞庫查詢性能對比

現(xiàn)將本實(shí)驗(yàn)詞條集構(gòu)成的字符樹詞庫、各類trie索引樹詞庫以及整詞詞庫的平均訪問長度與余詞數(shù)量統(tǒng)計(jì)在表3中.

由表3可知，平均訪問長度是字符樹最短，它的平均訪問長度接近于一個(gè)常數(shù)(常用漢字?jǐn)?shù)6712的一半)，整詞詞庫最長，它接近于詞庫總數(shù)的一半，而trie索引樹則介于兩者之間，對前n字的trie索引樹來說，n越大，級數(shù)分的越多，余詞數(shù)越少，它的平均訪問長度就越短，trie索引樹就會(huì)向單字符樹演變; 當(dāng)n越小，它的級數(shù)越少，余詞表越大，它的平均訪問長度就越長，于是它將向整詞詞庫演變. 所以字符樹詞庫與整詞詞庫是trie索引樹詞庫的兩個(gè)極端，前者詞庫內(nèi)查詢時(shí)間復(fù)雜度為O(1)，它不隨詞庫規(guī)模增大而增大; 而后者詞庫內(nèi)查詢時(shí)間復(fù)雜度為O(m)，它隨詞庫的規(guī)模(詞條總數(shù)為m)增大而增大; 而trie索引樹性能在這兩者之間，當(dāng)詞庫增大時(shí)，隨著余詞數(shù)量增大，其性能就會(huì)降低，尤其在大規(guī)模詞庫中，trie索引樹詞庫的余詞大量存在，余詞表對性能影響將上升為主要矛盾. 而字符樹詞庫的查詢詞條的時(shí)間復(fù)雜度為O(1)，它不受詞庫總條數(shù)影響，且不存在余詞表，所以在大規(guī)模詞庫中將會(huì)突顯它的優(yōu)勢.

3 字符樹在掃瞄算法上的優(yōu)勢

基于詞庫的中文分詞是建立在“最大匹配算法”的思想上，要從待分詞的字符串中找出盡可能字?jǐn)?shù)多的詞，分詞時(shí)提取的詞長度越長越好，分詞結(jié)果中詞的個(gè)數(shù)越少越好.

表3 各類詞庫平均訪問長度統(tǒng)計(jì)表

3.1 整詞詞庫分詞掃瞄的缺陷

傳統(tǒng)整詞法存在大量的無效查詢，效率低下. 比如要找出字符串“ABCDEFGHIJKLM”中最長的詞. 如果詞庫中最長詞的長度是10個(gè)，則它必須先取長度是10的字符串A-J與詞庫中詞比較，查找是否有相同的，如果有則提取該字符串，如果沒有，則第二次取長度為9的字符串A-I來比較，依此類推，逐一縮短字符串長度進(jìn)行查詢. 在最壞的情況下，10次查詢有9次無效的，它的分詞時(shí)間復(fù)雜度為O(n×m)，(n為待分詞總字符數(shù)，m為詞庫最長字符數(shù)).

3.2 Trie索引樹分詞掃瞄的缺陷

Trie索引樹能夠?qū)⒃~長度小于樹深度的詞快速找到并確定，消除了它們的無效查詢問題. 所以對于詞長度小于樹深度的詞，它的時(shí)間復(fù)雜度與字符樹相同. 然而，對于詞長度大于或等于樹的深度時(shí)，依然與傳統(tǒng)方法一樣，存在無效查詢的問題，比如上例字符串中如果ABCD是一個(gè)詞，它從首字，次字，三字，四字都找到了，此時(shí)它卻無法確定ABCD就是最長的詞，因?yàn)樽铋L的詞有可能是ABCDE，也有可能是，ABCDEF…甚至是更長的字符串. 它既然無法確定ABCD是最長的詞，就只能逐個(gè)去查詢對比才能確定最長的詞. 所以它的性能只是介于兩者之間.

3.3 基于字符樹的分詞掃瞄算法時(shí)間復(fù)雜度

基于字符樹的分詞掃瞄能夠完全消除無效查詢問題. 無論要處理的字符串是多少長，它從字符串首字開始逐字與字符樹對比，一旦發(fā)現(xiàn)字符樹的路徑已經(jīng)是“盡頭”了，則查詢結(jié)束，然后提取現(xiàn)有的最長的詞. 它的時(shí)間復(fù)雜度取決于待分詞字符的總長度，與詞庫中最長詞的長度無關(guān). 所以，它的分詞算法的時(shí)間復(fù)雜度為O(n)，(n為待分詞總字符數(shù)). 采用字符樹詞庫進(jìn)行分詞不僅消除了無效查詢問題，而且它對于利用回溯法[13]進(jìn)行多種分詞方案的選擇時(shí)具有得天獨(dú)厚的優(yōu)勢.

4 實(shí)驗(yàn)結(jié)果比較

實(shí)驗(yàn)環(huán)境：操作系統(tǒng)是Win10，CPU 為Intel?CoreTMi5-6500 CPU @3.20 GHz;內(nèi)存大小為4 GB. 為了區(qū)別各類詞庫的查詢性能與內(nèi)存占用情況，本文編寫了6個(gè)詞庫類，如表4所示，它們分別依次對同一個(gè)詞庫文件進(jìn)行加載，對同一個(gè)文本文件進(jìn)行分詞，查看加載詞庫所用時(shí)間，占用內(nèi)存，以及分詞所花費(fèi)時(shí)間等數(shù)據(jù). 內(nèi)存占用量用加載詞庫前程序占用總內(nèi)存與加載詞庫后程序占用總內(nèi)存的差作為取值，內(nèi)存占用信息通過操作系統(tǒng)提供的GetProcessMemoryInfo函數(shù)獲取. 加載詞庫所需時(shí)間與對文件進(jìn)行分詞所需時(shí)間分別是在開始前用clock()函數(shù)獲取時(shí)間，結(jié)束后再次用該函數(shù)獲取時(shí)間，用它們的差值作為花費(fèi)時(shí)間，各trie索引樹法的散列表的裝載因子統(tǒng)一設(shè)為0.5. 實(shí)驗(yàn)取得數(shù)據(jù)分析表見表5所示.

表4 各詞庫類的數(shù)據(jù)結(jié)構(gòu)及實(shí)現(xiàn)技術(shù)

4.1 內(nèi)存占用情況

本文提出的單字符樹詞庫內(nèi)存占用最小，整詞二分法詞庫最大; 而對trie索引樹詞庫的內(nèi)存占用情況是級數(shù)越多，內(nèi)存占用卻越小. 原因是trie索引樹分的級數(shù)越多，就會(huì)有更多的共同的前綴字符被省略，而“余詞”數(shù)量也會(huì)大幅度減少，所以占用內(nèi)存會(huì)越少. 傳統(tǒng)的整詞詞庫占用內(nèi)存最大，最主要的原因是字符串對象的創(chuàng)建與排序會(huì)造成大量的“內(nèi)存碎片”，從而浪費(fèi)內(nèi)存. 而多字符樹與單字符樹相比，性能接近相同，但內(nèi)存占用卻是多字符樹更大，原因是多字符樹的每個(gè)節(jié)點(diǎn)多了一個(gè)指向字符數(shù)組的指針，而且各節(jié)點(diǎn)中除第一個(gè)字符保存在節(jié)點(diǎn)內(nèi)，其余的字符都是組合成數(shù)組“掛接”在節(jié)點(diǎn)上，需要另外的存儲(chǔ)空間. 所以它的內(nèi)存占用會(huì)比單字符樹大得多.

表5 實(shí)驗(yàn)數(shù)據(jù)統(tǒng)計(jì)表

通過軟件采集實(shí)驗(yàn)所用的詞庫文件獲得詞庫總條數(shù)為279 095，總字符數(shù)為：821 105. 平均每個(gè)詞含字符數(shù)為2.94個(gè). 而加載成單字符樹后產(chǎn)生的節(jié)點(diǎn)數(shù)為405 534，相當(dāng)于詞庫中的一半字符可以省略，平均一個(gè)詞僅占1.45個(gè)節(jié)點(diǎn)數(shù). 單字符樹一方面省略了共同前綴的字符; 另一方面，也是更重要的是由于它的節(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)單一，大小一致，在構(gòu)造字符樹完成后可以將所有字符節(jié)點(diǎn)從“分散”狀態(tài)“收集”到一張線性表中，釋放掉原來的所有節(jié)點(diǎn). 這一過程會(huì)釋放大量的“內(nèi)存空閑碎片”，從而減少內(nèi)存占用. 它的內(nèi)存占用只有整詞詞庫MySet的占用內(nèi)存的1/5.5.

4.2 分詞性能比較

分詞速度最快的是本文提出的字符樹分詞法，其次是trie索引樹分詞法，最差是整詞二分法. 字符樹的分詞速度大約是整詞折半法的35倍. 而對于trie索引樹詞庫的性能情況是級數(shù)越多，分詞速度越快.

原因分析：字符樹消除了分詞過程中的無效查詢的問題，它同時(shí)在掃瞄算法與詞庫查詢兩個(gè)方面都具有最突出的優(yōu)越性，所以總體分詞速度是最快的. 整詞分詞法由于在掃瞄算法上存在大量的無效查詢，而它的詞庫查詢時(shí)間復(fù)雜度又是最高的，所以它的分詞速度最慢. 而trie索引樹可以部分消除無效查詢，同時(shí)它的詞庫查詢訪問性能是介于字符樹與整詞法之間，所以它的分詞性能也處于兩者之間. 另一方面，不同級數(shù)的trie樹性能也不同，trie索引樹級數(shù)越多，也就是深度越深，它的分詞性能越好，越接近字符樹，而級數(shù)越少，則其性能越差，越接近整詞分詞法.

總之trie索引樹的分詞性能是介于單字符樹與整詞法兩者之間，當(dāng)它的級數(shù)增大則向字符樹方向演變，當(dāng)它級數(shù)減少則向整詞詞庫方法演變，整詞法與字符樹法是trie樹的兩個(gè)極端情況.

5 結(jié)束語

本文從基于詞庫的中文分詞思想出發(fā)，對現(xiàn)有分詞技術(shù)進(jìn)行分析對比，提出字符樹的分詞技術(shù)，解決了中文分詞中的無效查詢問題. 首先它改進(jìn)了詞庫查詢方式與分詞掃瞄方式，大大減少了運(yùn)算的復(fù)雜度，減少運(yùn)算量，尤其在大規(guī)模詞庫中顯示出具有的巨大優(yōu)勢;其次，單字符樹詞庫占用內(nèi)存小，大大降低了程序的空間復(fù)雜度. 無論在時(shí)間復(fù)雜度還是空間復(fù)雜度，單字符樹都是一種占據(jù)絕對優(yōu)勢的，在大數(shù)據(jù)處理中文信息時(shí)值得推廣的中文分詞技術(shù).