基于字符樹結構的高性能中文詞庫技術①

楊光豹， 楊豐赫， 鄭慧錦

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

2(東南大學 網絡空間安全學院，南京 211189)

3(浙江青田縣職業技術學校，青田 323900)

引言

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

1 字符樹分詞原理

1.1 單字符樹原理

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

單字符樹的各個節點都采用同樣的數據結構，每個節點中都有一個詞串標記isword，如果其值為true則表示從根到該節點為止的路徑構成一個詞，否則僅僅是詞的中間節點. 其數據結構如圖2所示.

圖1 單字符樹詞庫構造舉例

圖2 單字符樹詞庫節點數據結構

查詢一個詞只需要從根節點開始，例如查詢“中國”這個詞，只需要從根節點開始先找“中”，找到后再在“中”的子節點中找“國”找到后再看這個“國”的節點中的詞串標記是否是true，如果是true，則說明詞庫中存在“中國”. 否則就不存在. 這樣構造起來的字符樹最大的好處是不會出現無效查詢，當查詢詞庫中存在的詞，比如想查詢“千方百計”，它從樹根逐級查詢會有一條路徑存在，最后依據路徑末端節點的詞串標記來判斷.查詢詞庫中不存在的字符串時，要么路徑不存在，要么路徑末端節點的標記是false.

1.2 多字符樹原理

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

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

圖3 多字符樹詞庫構造舉例

圖4 多字符樹詞庫節點數據結構

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

2 各詞庫查詢性能分析

無論是單字符樹還是多字符樹，它們都不是索引樹. 因為它們沒有所謂的“余詞正文”，所有的詞都已經在這棵樹上，它只是把詞庫的存儲方式從“表”變成“樹”，它不需要索引.

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

2.1 字符樹詞庫查詢長度統計分析

由于單字符樹與多字符樹在查詢原理上相同，所以查詢性能相同，在性能比較時以單字符樹為代表參與. 之所以引用兩種結構的字符樹是為了研究它們占用的內存區別.

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

2.2 trie索引樹詞庫查詢長度統計分析

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

表1 單字符樹詞庫平均訪問長度統計表

表2 前四字trie樹詞庫平均訪問長度統計表

2.3 整詞詞庫查詢長度分析

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

2.4 各類詞庫查詢性能對比

現將本實驗詞條集構成的字符樹詞庫、各類trie索引樹詞庫以及整詞詞庫的平均訪問長度與余詞數量統計在表3中.

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

3 字符樹在掃瞄算法上的優勢

基于詞庫的中文分詞是建立在“最大匹配算法”的思想上，要從待分詞的字符串中找出盡可能字數多的詞，分詞時提取的詞長度越長越好，分詞結果中詞的個數越少越好.

表3 各類詞庫平均訪問長度統計表

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

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

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

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

3.3 基于字符樹的分詞掃瞄算法時間復雜度

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

4 實驗結果比較

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

表4 各詞庫類的數據結構及實現技術

4.1 內存占用情況

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

表5 實驗數據統計表

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

4.2 分詞性能比較

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

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

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

5 結束語

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