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

楊光豹 楊豐赫 毛貴軍

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

關(guān)鍵詞： 中文分詞; 正則表達(dá)式; 散列; 時間復(fù)雜度

中圖分類號：TP391? ? ? ? ? 文獻(xiàn)標(biāo)志碼：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 引言

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

1 主流中文分詞技術(shù)背景概述

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

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

再如姚興山提出的詞的首字，次字，三字，四字HASH表、詞索引表和詞典正文的詞典結(jié)構(gòu)[6]。以及劉勇等人提出的根據(jù)不同首字設(shè)置恰當(dāng)?shù)淖畲笤~長以提升算法效率的雙字哈希結(jié)構(gòu)等，最大匹配算法的改進(jìn)方法都是以減少無效匹配，提升分詞性能為目的的[7]。

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

⑴ 準(zhǔn)確度問題

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

⑵ 性能問題

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

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

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

2.1 變長最大匹配算法

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

2.2 詞庫分組hash優(yōu)化技術(shù)

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

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

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

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

3 分詞算法的執(zhí)行過程

3.1 初始字符串的截取

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

3.2 分詞的循環(huán)過程（見圖1）

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

3.3 變長掃瞄分詞技術(shù)的優(yōu)勢

首先，在取得的初始字符串較短時（小于詞庫中最長詞的長度）。外循環(huán)指針每次后移都使待處理的字符串越來越短，內(nèi)循環(huán)次數(shù)將隨之減小，直到減少到只需一次。它減少了循環(huán)后期的匹配查詢，但不會對分詞準(zhǔn)確性產(chǎn)生負(fù)面影響。處理一個長度不超過最大詞長的句子，最壞情況用傳統(tǒng)方法需要匹配n*n次，而采用變長初始字符串的分詞法只需要匹配n*（n+1）/2次。因?yàn)閭鹘y(tǒng)方法每次內(nèi)循環(huán)都要從最大詞長開始，而本方法只顧及尾指針前的字符，不管尾指針后的字符，因?yàn)槲仓羔樦蟮淖址麘?yīng)在處理后一個句子時該考慮。

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

第三，在進(jìn)行分詞時，對初始字符串截取的長短不會影響性能，因?yàn)樗鼘Τ^詞庫中最長詞的長度的字符串會忽略不查，而對長度小于或等于詞庫中最長詞的字符串，都是在各分詞庫中查詢。在順序查詢最壞情況下，它的查詢次數(shù)合計與在整個總詞庫中查詢一次相當(dāng)，換句話說就是采用分組詞庫時內(nèi)循環(huán)中各次查詢的累加與采用非分組詞庫的一次查詢相同。

3.4 步進(jìn)式雙重掃瞄方法

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

4 結(jié)論

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

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

參考文獻(xiàn)（References）：

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

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

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

[4] 孫茂松，左正平，黃昌寧.漢語自動分詞詞典機(jī)制的實(shí)驗(yàn)研究[J].中文信息學(xué)報，1999.14（1）：1-6

[5] 熊志斌，朱劍鋒.基于改進(jìn)Trie樹結(jié)構(gòu)的正向最大匹配算法[J].計算機(jī)應(yīng)用與軟件，2014.5：276-278

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

[7] 劉勇，魏光澤.基于雙字哈希結(jié)構(gòu)的最大匹配算法機(jī)制改進(jìn)[J].下電子設(shè)計工程，2017.25（16）：11-15