基于分組hash與變長匹配的中文分詞技術

楊光豹 楊豐赫 毛貴軍

摘 要： 中文分詞是海量中文信息處理的基礎任務，分詞的準確性與分詞速度是最為重要的。但是現有技術在分詞時，準確性與分詞速度卻是無法調和的。為了提高中文分詞的速度，同時又不因縮短初始字符串長度造成準確性降低，提出使用正則表達式進行變長字符串的截取與對詞庫進行分組散列的技術。通過理論分析，該技術在時間復雜度上從原來的o（n*n）下降到o（n），在精確度上又以句子長度作為動態變化的初始字符串長度，從而避免長詞的丟失，保證了分詞的準確性不受損失。

關鍵詞： 中文分詞; 正則表達式; 散列; 時間復雜度

中圖分類號：TP391? ? ? ? ? 文獻標志碼：A? ? ?文章編號：1006-8228（2019）04-52-04

Abstract： Chinese word segmentation is the basic task of mass Chinese information processing. The accuracy and speed of word segmentation are the most important. However， the accuracy and the speed of word segmentation cannot be reconciled with in the existing technologies. In order to improve the speed of Chinese word segmentation without the accuracy reduction caused by reducing the initial string length， this paper proposes the use of regular expressions to intercept variable-length strings and to hash word libraries. Through theoretical analysis， this technology reduces from the original O（n*n） to O（n） in terms of time complexity， and takes the sentence length as the dynamic initial string length in terms of accuracy， so as to avoid the loss of long words and ensure that the accuracy of word segmentation is not damaged.

Key words： Chinese word segmentation; regular expression; hash; time complexity

0 引言

中文分詞技術是中文文本信息處理的基礎，它的準確性與分詞性能直接影響到后續的信息處理。在大數據與人工智能強勁發展的今天，中文分詞技術在中文信息處理中起著至關重要的作用，尤其是在分詞性能要求較高的海量中文信息處理系統中，比如搜索引擎等。現有的主流分詞技術基本上都是基于“最大匹配算法”的思想。但其技術在設計與實現中一直存在分詞準確性與分詞性能相互制約的矛盾。兩者不能兼顧。本文在中文分詞技術上提出采用變長最大匹配與分組hash算法，能有效解除兩者的矛盾關系，使分詞準確性與分詞處理性能都得到很大提高。

1 主流中文分詞技術背景概述

現有的分詞算法可分為三大類：基于字符串匹配的分詞方法、基于理解的分詞方法和基于統計的分詞方法[1]。主流中文分詞以字符串匹配為主，它的核心思想就是“最大匹配算法”，該算法的設計與實現技術包含兩個核心內容：分詞算法與詞典結構[2]。在分詞算法上出現各種流派：有正向最大匹配算法，逆向最大匹配算法，雙向匹配算法，以及它們的各類改進型觀點。比如雙向匹配算法就是對正向最大匹配算法與逆向最大匹配算法的一個改進，其針對一個字符串，分別從兩個方向進行處理 [3]。

而針對正（逆）向最大匹配算法的改進方向主要是優化詞典結構，提升分詞匹配效率。孫茂松設計并考察了三種典型的分詞詞典機制：整詞二分、TRIE索引樹及逐字二分，并且對它們的時間、空間效率進行了比較[4]。熊志斌等人后來提出了一種改進的TRIE樹詞典結構，根據詞典中詞語的長度調整字符串的相應長度，其目的就是為了減少匹配次數，提高中文分詞速度[5]。

再如姚興山提出的詞的首字，次字，三字，四字HASH表、詞索引表和詞典正文的詞典結構[6]。以及劉勇等人提出的根據不同首字設置恰當的最大詞長以提升算法效率的雙字哈希結構等，最大匹配算法的改進方法都是以減少無效匹配，提升分詞性能為目的的[7]。

到目前為止，現有的分詞技術均不可避免地存在一些共同的缺陷：

⑴ 準確度問題

所有的現有技術中都有一個共同特點就是它們在進行分詞之前必須取一個初始字符串長度作為待處理的字符串進行分詞。這將產生一個不可避免的缺陷就是常會將一個完整的長詞分割掉。比如：假設確定初始字符串長度為8，則對字符串：“恰似一江春水向東流”這個詞來說，它們將會被拆散了。而如果初始字符串取詞庫中最長的詞長，則將出現大量的無效查詢，從而會大大影響分詞性能。

⑵ 性能問題

因為初始字符串長度越長，越能符合“最大匹配算法”思想，分詞會越準確，但它卻讓分詞過程的性能快速下降。由于對這個字符串進行分詞要用雙重循環對詞庫進行查詢，假設這個字符串長度為n，詞庫記錄數為m，在最壞情況，傳統順序查詢的時間復雜度為O（n*n*m）;對按折半查詢法來說，它的時間復雜度是O（n*n*log2n）。而對查詢性能相對較好的hash表法來說，比如像姚興山提出的技術，它對四字以內的詞通過hash表間的級連進行查詢，假如字典中四字以上的詞數量是s個，則它的時間復雜度為O（n*n*（4+log2s））。從時間復雜度來看，這些技術都沒有解決截取的初始字符串越長分詞性能越低，初始字符串長度增加將使分詞效率快速下降的問題。而且字符越長，無效的匹配運算將越多。

2 一種基于數組詞庫與變長匹配的中文分詞技術

要提高分詞的準確性與運算性能，在算法設計與實現上可從以下兩方面展開：①改進詞典結構與內容;②改進掃描方式。為了解決現有分詞處理技術中的第一個缺陷，避免將一個詞拆散掉，同時不錯過任何一個長詞，本文提出了變長最大匹配算法的設計思想。

2.1 變長最大匹配算法

這種方法的初始處理字符串的長度不再是一個固定長度的字符串，而是可變的，它是取一個處于標點符號之間的字符串。我們知道在標點符號之間取字符串，多數情況是一個完整的句子，由于中文的任何一個詞都存在標點符號一側，不可能將一個詞分在標點符號的兩側，所以截取標點符號之間的字符串作為初始字符串，可以保證不會將一個詞拆散掉。它不錯過任何一個詞庫中有的長詞！從而避免了把一個詞拆散的可能性，能夠最大程度地符合“最大匹配算法”的思想。

2.2 詞庫分組hash優化技術

通過變長最大匹配算法的設計思想從文章中截取字符串能保證詞的完整性，也盡最大程度地符合中文分詞的“最大匹配算法”的思想。但這種方法有可能會使分詞處理的初始字符串很長（一個長句子）。如果采用傳統的方法進行查詢的話，在性能上有可能將是災難性的后果！為此本文對詞庫采用了分組hash法進行優化。在理論上，該技術能將分詞處理的內循環查詢過程的時間復雜度降為O（1），總的時間復雜度降為O（n）。這樣可以保證初始字符串無論取多大都不影響分詞運算的總性能。因為時間復雜度為O（n）時，字符串的運算量是隨字符串長度而線性增長，總運算量不會增加。詞庫結構設計方法如下（見圖1）。

首先，以詞的長度為分類依據對詞庫進行分類，將整個詞庫的所有詞串分成多組記錄，每組詞的長度相同。加載詞庫時先以詞庫中最長詞的長度作為數組的長度建立一個關聯集合的數組，數組的各元素（分詞庫）分別存放詞庫中同組的記錄;數組元素的下標=詞庫中的詞的長度-1。依據這樣的原則將詞庫中的記錄按其包含中文字的個數分組加載到相應的數組分詞庫中去。結果是：詞長度為1的詞加載到數組下標為0的分詞庫中，長度為2的詞加載到下標為1的分詞庫中……依次類推，將詞庫中長度為10的詞加載到下標為9的詞庫中。這樣就把每一個詞的字符串的長度與數組的下標進行了一一映射。

如此一來，要查詢字符串就變得非常直接簡單，根據字符串的長度確定數組元素下標（分詞庫的外部索引），比如要查詢長度為10的字符串，只需要去下標為9的分詞庫中查詢，而不去其它分詞庫中去找，假設初始掃瞄的字符串長的長度為n，詞庫總詞匯數為m，內循環一次，就是從最長的詞查詢到最短的一個字，如果詞庫內都采用最原始的順序查詢法，最壞情況下，用傳統方法需要查詢內循環就需要n*m次，而用分組詞庫法只需查詢m次。

在詞庫加載時，各個分詞庫中的詞都采用hash算法進行存儲與查詢。查詢字符串時，字符串的長度決定外部索引，字符串hash值決定內部索引。這就是查詢字符串的分組hash算法。

3 分詞算法的執行過程

3.1 初始字符串的截取

截取字符串的方法可以通過正則表達式在循環處理分詞之前進行。具體方法是：①設定待處理文章首字符指針;②設定一個正則表達式用于查詢標點符號的位置;③將文章中出現在首指針后的第一個標點符號位置設定為尾指針;④將循環指針設定在首指針+數組長度的后一位置（初始字符串長度小于數組長度時設在尾指針）。這樣在首指針與尾環指針之間就是我們要截取的初始字符串（見圖1）。而在首指針與循環指針之間的字符串就是每一次內循環要查詢的字符串。由于分詞時應該是詞越長越好，但并非初始字符串越長越好，有時候一個句子也只有四、五個字，如果采用固定長度的方法將會造成很多無效的匹配運算。而采用這種以標點符號為分隔標志的變長方法可以有效提升準確度，同時減少無效匹配。

3.2 分詞的循環過程（見圖1）

變長最大匹配算法也是按先查詢最長的詞，然后是次長的詞這樣的順序進行匹配查詢的， 所以分詞循環查詢的內循環是使循環指針從后向首指針方向移動，而外循環是跳過已提取的詞，使首指針向尾指針方向移動。剛開始循環指針從首指針+數組長度的后一位置開始循環，因為比這更長的字符串在詞庫中肯定是沒有的，所以循環指針沒有必要從尾指針開始循環。查詢過程是：首次取首指針與循環指針之間的字符串（10個字），該字符串長度決定詞庫的外部索引（就是數組下標），該字符的hash值決定詞庫的內部索引。所以根據這個字符串可以直接到下標為9的詞庫中查詢結果，它無需進行遍歷查詢。如果詞庫中沒有查到，則將循環指針前移一個字符，取此前面的字符串（9個字），到下標為8的分詞庫中查詢……依此類推。如果查詢到詞庫中該字符串，則提取該詞，之后將首指針往后跳到循環指針的位置，然后循環指針重置在首指針+數組長度的后一位置，但不超過尾指針。如果超過尾指針，則循環指針設定在尾指針位置即可。等內外循環都完成了，則該句子分詞結束，然后再根據正則表達式截取下一個句子進行分詞。

3.3 變長掃瞄分詞技術的優勢

首先，在取得的初始字符串較短時（小于詞庫中最長詞的長度）。外循環指針每次后移都使待處理的字符串越來越短，內循環次數將隨之減小，直到減少到只需一次。它減少了循環后期的匹配查詢，但不會對分詞準確性產生負面影響。處理一個長度不超過最大詞長的句子，最壞情況用傳統方法需要匹配n*n次，而采用變長初始字符串的分詞法只需要匹配n*（n+1）/2次。因為傳統方法每次內循環都要從最大詞長開始，而本方法只顧及尾指針前的字符，不管尾指針后的字符，因為尾指針之后的字符應在處理后一個句子時該考慮。

其次，在取得的初始字符串很長時。由于超過數組長度，就意味著超長的字符串不在詞庫中，所以循環指針可以忽略掉這些字符串，而直接定位在與數組同長度的后一位置上（圖1中的10的后一位置）。略去了超長詞的無效匹配。

第三，在進行分詞時，對初始字符串截取的長短不會影響性能，因為它對超過詞庫中最長詞的長度的字符串會忽略不查，而對長度小于或等于詞庫中最長詞的字符串，都是在各分詞庫中查詢。在順序查詢最壞情況下，它的查詢次數合計與在整個總詞庫中查詢一次相當，換句話說就是采用分組詞庫時內循環中各次查詢的累加與采用非分組詞庫的一次查詢相同。

3.4 步進式雙重掃瞄方法

由于單一的掃瞄方式不可避免會發生切分錯誤。為了減少分詞的切分錯誤或歧義，本文采用“步進式”多次掃瞄的方式。方法是將分詞過程進行兩次循環：比如“當中華人民共和國成立的時候”這句話，第一次循環之后，切分結果是：（“當中”，“華人”，“民”，“共和國”，“成立”，“的”，“時候”），將結果存放到臨時變量中;然后將首指針向后移動一個漢字進行第二次掃瞄分詞，結果是（“當”，“中華人民共和國”，“成立”，“的”，時候），將結果存放到另一變量中，然后將兩次分詞的結果進行比較。依據最大匹配算法的思想，結果中長度越長，詞的數量越少，則切分越科學，本文按長度優先，數量兼顧的原則來選擇。由于最大長度第一次是3個字，而第二次是7個字，所以選擇第二次掃瞄作為分詞結果。通過步進式雙重掃瞄的方式可以大大減少分詞中的錯誤切割，提高分詞的科學性。

4 結論

本文提出的將詞庫進行分組hash算法，同時通過正則表達式進行初始字符串的截取，以及采用步進式多重掃瞄技術。一方面可以將字符串長度和字符串hash值直接與詞的索引地址映射，讓分詞循環運算的總的時間復雜度降低到O（n）。另一方面，可以提高分詞的準確度，避免將詞從中間拆散，減少詞的歧義。這是本文在中文分詞技術中的創新點。

本文存在的問題是采用hash表存儲詞庫不可避免帶來這樣的問題：字符串的hash值的計算是通過hash函數計算獲得的，這個過程需要時間，hash函數的性能會直接影響查詢的性能;同時hash沖突的處理也會降低查詢性能，所以實際的時間復雜將是大小o（n）。

參考文獻（References）：

[1] 孫鐵利，劉延吉.中文分詞技術的研究現狀與困難[J].信息技術，2009.7：187-189

[2] 奉國和，鄭偉.國內中文自動分詞技術研究綜述[J].圖書情報工作，2011.2：41-45

[3] 陳之彥，李曉杰，朱淑華，付丹龍，邢詒海等.基于Hash結構詞典的雙向最大匹配分詞法[J].計算機科學，2015.42（s2）：49-54

[4] 孫茂松，左正平，黃昌寧.漢語自動分詞詞典機制的實驗研究[J].中文信息學報，1999.14（1）：1-6

[5] 熊志斌，朱劍鋒.基于改進Trie樹結構的正向最大匹配算法[J].計算機應用與軟件，2014.5：276-278

[6] 姚興山.基于Hash算法的中文分詞研究[J].現代圖書情報技術，2008.3：78-81

[7] 劉勇，魏光澤.基于雙字哈希結構的最大匹配算法機制改進[J].下電子設計工程，2017.25（16）：11-15