吳宏洲

摘要：該文主要論述一種快速分詞技術(shù)的實(shí)現(xiàn)。對于GBK編碼格式的原始文獻(xiàn)，利用GBK可見漢字，建立內(nèi)存常駐索引，按照最大匹配法查找外存分詞詞典庫，從而將文章例句進(jìn)行快速切分。理論上是目前最快的一種分詞方法。

關(guān)鍵詞：正向分詞；逆向分詞；GBK；字典索引

中圖分類號：TP18 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2015）06-0179-04

4A Quick Word Segmentation Technology Research and Application

WU Hong-zhou

（The China Patent Information Centre， Beijing 100088， China）

Abstract：This paper mainly discusses the realization of a fast segmentation technology.For GBK encoding format of the original literature， the use of visible GBK Chinese characters， establishing resident memory index， according to the maximum matching method to find the external storage word segmentation dictionary library， which will be fast segmentation articles sentences.In theory it is at present a word segmentation method is the fastest.

Key words：positive word segmentation；reverse participles；GBK；the dictionary index

在專利信息技術(shù)中，專利文獻(xiàn)信息檢索、機(jī)器翻譯、專利輔助自動文摘和CPC/IPC自動分類，都會用到一個基本的技術(shù)——分詞技術(shù)。所謂分詞，就是利用已有詞庫的詞，來切分文章中的詞的過程。切分的分詞，用來確定在文獻(xiàn)中的位置；用來統(tǒng)計(jì)特征詞的頻度；聚類、分類運(yùn)算；相似度計(jì)算等。目前有很多應(yīng)用場景已經(jīng)使用了已有的技術(shù)產(chǎn)品。帶來的好處是：引入語義分析、詞性分析、語法分析等成熟技術(shù)，性能穩(wěn)定，分詞正確率高；加快軟件產(chǎn)品開發(fā)使用，可移植性強(qiáng)。帶來的問題是：受著作版權(quán)保護(hù)，須繳納昂貴費(fèi)用，加大應(yīng)用軟件的制作成本；由于詞庫數(shù)據(jù)結(jié)構(gòu)的不公開，使維護(hù)變得困難；產(chǎn)品大多面向大眾化讀物，不能靈活地適應(yīng)專業(yè)技術(shù)性強(qiáng)的不同領(lǐng)域?qū)Ψ衷~的不同要求；詞庫中分詞需要標(biāo)注詞性，詞性對于專業(yè)技術(shù)文獻(xiàn)產(chǎn)生的作用并不明顯，更新分詞，須額外編輯詞性，并審校，費(fèi)時費(fèi)力，詞庫的更新周期比較長。為了降低應(yīng)用成本，迫使我們不得不自主研發(fā)一整套適合本領(lǐng)域的包括分詞在內(nèi)的相關(guān)基本技術(shù)。分詞技術(shù)屬于中國特色的信息處理技術(shù)之一。在西方語言中，拼音字母組合構(gòu)成的單詞，單詞與單詞之間有明顯空格分隔，詞是自然分隔的，無須分詞。對于相形文字（如中日韓語言）來說，字詞之間緊密連接，沒有明顯間隔。因此需要仿照西方語言來預(yù)先加工分詞，使之明顯分割。只有具備了分詞分割字詞的基礎(chǔ)，才能夠像西文那樣輕松地建立數(shù)學(xué)模型，利用數(shù)學(xué)方法，來對文獻(xiàn)進(jìn)行分析利用。因此本文將討論如何實(shí)現(xiàn)一種實(shí)用的快速分詞方法。

1 分詞技術(shù)的現(xiàn)狀

分詞技術(shù)目前已經(jīng)非常成熟。常見的有三種方法：

1） 字符串匹配的分詞方法；

2） 詞義分詞法；

3） 統(tǒng)計(jì)分詞法。

1.1 字符串匹配的分詞方法

這是一種常用的分詞法，它主要利用已有詞庫中的詞匹配文章句子中的詞，來切分句子。常見的方法又有四種方法：

1） 正向最大匹配法；

2） 逆向最大匹配法；

3） 最短路徑分詞法；

4） 雙向最大匹配法。

1.2 詞義分詞方法

一種機(jī)器語音判斷的分詞方法。在進(jìn)行句法、語義分析時，利用句法信息和語義信息來處理歧義現(xiàn)象從而得到分詞，這種分詞方法，現(xiàn)在還不成熟，處在實(shí)驗(yàn)階段。

引入詞性協(xié)助分析詞性在語法位置上的可能性，對詞進(jìn)行合理切分，目前國內(nèi)產(chǎn)品出現(xiàn)的比較多。如中國科學(xué)院計(jì)算所的ICTCLAS產(chǎn)品。

1.3 統(tǒng)計(jì)分詞法

根據(jù)詞組的統(tǒng)計(jì)，就會發(fā)現(xiàn)兩個相鄰字出現(xiàn)的頻率最多，那么這個詞就很重要。就可以作為用戶提供字符串中的分隔符來分詞。

2 分詞技術(shù)的實(shí)現(xiàn)

本文討論的是屬于字符串匹配的分詞方法。而且主要著重討論正向最大匹配法和逆向最大匹配法。雙向最大匹配法是前兩種方法的結(jié)合，用于判斷切分產(chǎn)生歧義時，是否需要人工干預(yù)來決定選擇哪一種結(jié)果，或者，通過最佳路徑分詞法來自動選擇一種。因此，設(shè)計(jì)好正向/逆向分詞技術(shù)是分詞技術(shù)實(shí)現(xiàn)的基礎(chǔ)，也是本文主旨。本文重點(diǎn)是要實(shí)現(xiàn)一種高效的分詞技術(shù)。由于分詞技術(shù)是一種純粹底層的引擎，因此提出的高效目標(biāo)，既要保證分詞的效率和效果，還要兼顧系統(tǒng)資源開銷，將節(jié)省的資源盡可能多地用于其他方面，例如響應(yīng)更多的客戶端的服務(wù)請求。筆者利用內(nèi)存和外存相結(jié)合的方法建立了一個駐留內(nèi)存的字典索引和一對存放于外存的正向分詞和逆向分詞詞庫來實(shí)現(xiàn)高效分詞技術(shù)。

2.1 分詞庫的構(gòu)建

在外存建立詞庫，要對詞庫中詞語的開頭漢字、詞語的漢字字?jǐn)?shù)和結(jié)尾漢字這三項(xiàng)進(jìn)行標(biāo)注。將分詞數(shù)據(jù)結(jié)構(gòu)定義為定長記錄：{分詞char（30），首字char（2），首字編碼char（4），尾字char（2），尾字編碼char（4），分詞漢字?jǐn)?shù)int，位置號int}。

詞庫設(shè)計(jì)需要考慮在詞庫檢索效率與詞長選擇之間求得平衡。如果詞長過長，檢索效率必然下降；如果詞長過短，就會丟失正確的長詞，使分詞正確性得不到滿足?？紤]到化學(xué)、藥物、微生物等領(lǐng)域的技術(shù)術(shù)語可能會有大量長詞出現(xiàn)，因此，犧牲部分分詞的訪問效率，換來長詞的滿足也是不得已的，通常認(rèn)為一個長詞最長不超過15個漢字。

實(shí)驗(yàn)中我們建立了大約120萬條分詞的詞典庫，用以模擬專利文獻(xiàn)詞典的真實(shí)數(shù)據(jù)規(guī)模。

2.1.1 正向分詞詞庫的構(gòu)建

將詞庫文件按照{(diào)首字編碼（正序）+詞語的漢字字?jǐn)?shù)（逆序）+尾字編碼（正序）+分詞（正序）}來排序，并得到一個正向分詞庫文件。每個記錄行號填入“位置號”字段。樣例參見表1。

2.1.2 逆向分詞詞庫的構(gòu)建

將詞庫文件按照{(diào)尾字編碼（正序）+詞語的漢字字?jǐn)?shù)（逆序）+首字編碼（正序）+分詞（正序）}來排序，并得到逆向分詞庫文件。每個記錄行號填入“位置號”字段。樣例參見表2

2.2常駐內(nèi)存字典索引表的構(gòu)建

在內(nèi)存建立一個字典索引表。由于分詞庫，對于正向分詞是按照單詞首字集中有序存放的，對于逆向分詞也是按照單詞尾字集中有序存放的。因此，字典索引，對于正向分詞庫來說，需要知道單詞首字的起、止位置；同樣，對于逆向分詞庫來說，需要知道單詞尾字的起、止位置。

接下來選擇什么樣的字典作為索引就是一個關(guān)鍵。

通過考查GBK編碼特征，GBK編碼是雙字節(jié)定長漢字編碼。其編碼與漢字區(qū)位相對應(yīng)。筆者在GBK編碼中篩選出21002個可見漢字建立字典索引碼表。這是目前國內(nèi)漢字編碼比較多的，且與《漢語大字典》相一致?！稘h語大字典》1993年版和1998年版，收錄了21000個字頭。字典索引碼表中的字，對于專利文獻(xiàn)領(lǐng)域的應(yīng)用，我們認(rèn)為也已經(jīng)足夠。如果要應(yīng)用于其他方面，例如涉及古籍出版物的文獻(xiàn)，這一方案還是不足以滿足所需。例如《康熙字典》中的字頭收錄了多達(dá)47043個字頭。其中大多是異形字和非常用字。

21002個可見漢字是如何從GBK編碼表篩選的？

首先來看GBK編碼分布圖（參見圖1）。

圖1 GBK編碼分布圖

根據(jù)GBK編碼分布圖，我們將編碼劃分為兩類編碼：

1） 由漢字一區(qū)、漢字二區(qū)、擴(kuò)展三區(qū)和擴(kuò)展四區(qū)組成的字模漢字編碼表，去掉其中不可見漢字字模編碼，共收錄21002個漢字。作為漢字編碼。

2） 符號區(qū)字模編碼和不可見漢字字模編碼，作為非漢字編碼。

另外除GBK編碼外，還有一類西文ASCII編碼。作為西文編碼。

以可見漢字編碼作為字典構(gòu)建正向和逆向分詞索引，其最大記錄數(shù)約21002個。將數(shù)據(jù)結(jié)構(gòu)定義為定長記錄：{GBK編碼char（4），漢字char（2），首字串字?jǐn)?shù)int，尾字串字?jǐn)?shù)int，首字開始int，首字結(jié)尾int，尾字開始int，尾字結(jié)尾int}。其記錄格式參見表3。

表3 內(nèi)存字典索引格式

1） 首先，對于停用字詞要做特殊預(yù)處理，要么過濾掉，要么視同分隔符作用，進(jìn)行特殊預(yù)切分，停用字詞前后要添加空格分隔符。

2） 對于ascii編碼的西文字母數(shù)字及其特殊符號，視同分隔符作用，不進(jìn)行切分。原樣輸出。

3） 對于GBK編碼的符號區(qū)和不屬于字典索引表中識別漢字的編碼，視同分隔符作用，不進(jìn)行切分。原樣輸出。

4） 對于GBK編碼屬于字典索引表中可識別的漢字的連續(xù)字串，視同中文例句，要進(jìn)行分詞切分，切分分詞前后要添加空格分隔符。切分的句子按照最大正向匹配法或最大逆向匹配法進(jìn)行分詞切分，切分出的分詞或單字之間要以空格分隔符分隔。

分詞切分算法包含：

正文切分句子算法、句子切分分詞（分為最大正向分詞匹配和最大逆向分詞匹配）算法。

2.4.1 將正文切分成句子

正文切分句子，主要是對原始文件中的正文信息進(jìn)行解析最粗的過程，首先要讀入一個字，這里的字，是文字串中最小的邏輯單元，對于ASCII編碼的字是單字節(jié)，而對于GBK編碼的字是一個雙字節(jié)。

要確定字的類型。主要有3種：

1：ASCII編碼單字節(jié)表示的字，如西文字母數(shù)字及符號；

2：GBK編碼雙字節(jié)表示的字，不屬于字典索引表中（21002個漢字）的部分，如符號區(qū)全角符號和一至四區(qū)不可見漢字編碼；

3：GBK編碼雙字節(jié)表示的字，屬于字典索引表中（21002個漢字）的部分，作為漢字編碼。

讀入的字的類型如果連續(xù)相同，則字的流構(gòu)成同類字串，亦即短語，直至讀到一個不同類型的字為止。如果屬于1類或2類的短語，不處理，原樣輸出；如果屬于3類的短語，要將短語句子作切分分詞的細(xì)加工處理，處理后的分詞流結(jié)果輸出。重新繼續(xù)構(gòu)造新的類型的字串，直至全部讀入的字串處理完為止。

算法：

T00； //首先確定已讀類型T0為空

Y=X “”； // 句子樣板串Y和已讀字串X也清空

While（（T1getword（fdi，&C） ） > 0） {

T1getword（fdi，&C）； // 讀入字C，類型T1

If（T1 ！= T0）{ //當(dāng)讀字節(jié)的類型T1與已讀類型T0不一致時

If （ T1 == 3） // 句子是漢字串

X segment （X，direct） // 句子切分分詞 ；direct正向/逆向

// 第一次，相當(dāng)于只輸出一個空，分詞

Else If（T==2）

X X+ “ ”；

YY+X+ “ ”； // 句子樣板串Y添加已讀串S和空格（即Y=Y+X+ ）

X “”； //然后清空已讀串X

T0T1； //重置新類型，T0取新類型T1

} else { //否則，T1與T0一致，拼接字串

XX+C； // 讀入字C添加到已讀字串X

}

}

2.4.2 句子切分分詞

句子切分分詞，主要有最大正向分詞法和最大逆向分詞法兩種方法。

兩種方法同時對句子進(jìn)行切分分詞，是一種混合方法，主要用來對句子切分分詞結(jié)果進(jìn)行互校時同時使用。如果兩種切分句子結(jié)果出現(xiàn)歧義，則會引入另外一種，最短路徑的方法，即計(jì)算切分分詞數(shù)量最少優(yōu)先自動判斷方法。后兩種方法在這里，就不進(jìn)一步介紹。

算法：

If （Direct==1） { // 正向分詞

// 進(jìn)入最大正向分詞處理

}else{ // 否則 ， 逆向分詞

// 進(jìn)入最大逆向分詞處理

}

2.4.2.1 最大正向分詞匹配

由于正向分詞庫的記錄是按照字頭（正序）、詞長字?jǐn)?shù)（逆序）、字尾（正序）排序，字典索引表中記錄了正向分詞庫中字頭和最大詞長字?jǐn)?shù)。切分例句時，通過字頭、可能的最大詞長來優(yōu)先查找分詞?？赡艿淖畲笤~長，是實(shí)際句子長度和字典字頭對應(yīng)的正向分詞的最大長度兩者中最小的長度，最小不能小于2，否則不成其為詞，而為單字。例如：例句S：“最大正向分詞法”，其句長SL：7。

最大正向分詞匹配法，首先取字頭“最”字。全程折半查找字典索引表，找到“最”字索引?！白睢弊謱?yīng)正向分詞庫的局部起止范圍[begin，end]，最大詞長度WL=11。沿著起止范圍[begin，end]對分詞詞庫進(jìn)行折半查找。查找分詞“最大逆向分詞法”，如果沒有找到，則將查找詞去掉一個漢字“法”，繼續(xù)找“最大正向分詞”，如果還沒有找到，則繼續(xù)去掉后面的字，直至“最大”，還沒有找到，將“最”字，作為非分詞字，輸出。繼續(xù)以“大正向分詞法”為新句子，繼續(xù)切分分詞。如果找到分詞，例如：找到“最大正向分詞”，則輸出“最大正向分詞”，截?cái)喾衷~后的句子“法”作為新句子繼續(xù)切分分詞。直至，句子切分完畢。

算法：

Y “”； // 清空結(jié)果

// S=例句，傳入?yún)?shù)

SLlength（S）； // 取例句長度

While（SL>0） { // 從例句首字開始切分分詞

Hget（S，0，1）； // 取字頭

Pbinary_search_gbk（0，GBKNUM-1，H）； // 折半查找字頭

WLgbk[P].hml； // 取字典正向分詞最大長度

begin gbk[P].hmb； // 分詞庫局部開始位置

end gbk[P].hme； // 分詞庫局部結(jié)尾位置

Lmin（WL，SL）； // 字典正向分詞最大長度和句長較小者，作為最大試探長度

For（l=L；i>1；l--） { // 以最大試探長度依次縮小，

// 來截?cái)嗑渥釉囂绞欠翊嬖谧畲蠓衷~

Csubstr（S，0，l）； //截取句子，取待查找分詞

// 局部折半查找分詞

If（（rcfinddict（C，begin，end，fid））>0） { // fid指定分詞庫句柄

Break； // 找到分詞

}

}

Csubstr（S，0，l）； //截取句子分詞

YY+C+ “ ”； // 輸出分詞 ，或 ，非分詞單字

S substr（S，l，SL）； //截?cái)喾衷~后新句子

SL length（S）； // 取新句長度，繼續(xù)

}

output（Y）//返回 輸出結(jié)果

2.4.2.2 最大逆向分詞匹配

由于逆向分詞庫的記錄是按照字尾（正序）、詞長字?jǐn)?shù)（逆序）、字頭（正序）排序，字典索引表中記錄了逆向分詞庫中字尾和最大詞長字?jǐn)?shù)。切分例句時，通過字尾、可能的最大詞長來優(yōu)先查找分詞?？赡艿淖畲笤~長，是實(shí)際句子長度和字典字尾對應(yīng)的逆向分詞的最大長度兩者中最小的長度，最小不能小于2，否則不成其為詞，而為單字。例如：例句S：“最大逆向分詞法”，其句長SL：7。

最大逆向分詞匹配法，首先取字尾“法”字，全程折半查找字典索引表，找到“法”字索引?！胺ā弊謱?yīng)正向分詞庫的局部起止范圍[begin，end]，最大詞長度WL=14。沿著起止范圍[begin，end]對分詞詞庫進(jìn)行折半查找。查找分詞“最大逆向分詞法”，如果沒有找到，則將查找詞去掉一個漢字“最”，繼續(xù)找“大逆向分詞法”，如果還沒有找到，則繼續(xù)去掉后面的字，直至“詞法”，還沒有找到，將“法”字，作為非分詞字，輸出。繼續(xù)以“最大逆向分詞”為新句子，繼續(xù)切分分詞。如果找到分詞，例如：找到“逆向分詞法”，則輸出“ 逆向分詞法”，截?cái)喾衷~后句子“最大”，以新句子繼續(xù)切分分詞。直至，句子切分完畢。結(jié)果為“最大 逆向分詞法”

算法：

Y””； // 清空結(jié)果

// S=例句，傳入?yún)?shù)

SLlength（S）； // 取例句長度

While（SL>0） { // 從例句首字開始切分分詞

T substr （S，SL-1，1）； // 取尾字

Pbinary_search_gbk（0，GBKNUM-1，T）； // 折半查找字尾

WLgbk[P].tml； // 取字典逆向分詞最大長度

begin gbk[P].tmb； // 分詞庫局部開始位置

end gbk[P].tme； // 分詞庫局部結(jié)尾位置

Lmin（WL，SL）； // 字典逆向分詞最大長度和句長較小者，作為最大試探長度

For（lL；i>1；l--） { // 以最大試探長度依次縮小，

// 來截?cái)嗑渥釉囂绞欠翊嬖谧畲蠓衷~

C substr（S，SL-l，l）； //截取句子，取待查找分詞

// 局部折半查找分詞

If（（rcfinddict（C，begin，end，fid））>0） { // fid指定分詞庫句柄

Break // 找到

}

}

C substr（S，SL-l，l）； //截取句子分詞

Y “ “+C+Y； // 輸出分詞 ，或 ，非分詞單字，逆向粘接分詞

S substr（S，SL-1，l）； //截?cái)喾衷~后新句子

SL length（S）； // 取新句長度，繼續(xù)

}

output（Y）//返回輸出 結(jié)果

2.5 分詞切分試驗(yàn)效果

本文采用C語言實(shí)現(xiàn)，在lenovo T61，Intel（R）Core（TM）2 Duo CPU T7500 @2.20GHz2.17GHz，1.96GB內(nèi)存。安裝WindowsXP，同時安裝SUSE linux server11。在SUSE下運(yùn)行。

通過對正文文件的整個文件的單線程切分，測試實(shí)際切分效果，將國際專利分類號索引電子文檔正文文件，分成八個大部的8個文件，分別切分。其效果由表4不難看出，逆向分詞比正向分詞平均快10%。

3 結(jié)論

本文給出分詞算法的技術(shù)實(shí)現(xiàn)，在于推薦一種快速分詞技術(shù)方案。該方案采用內(nèi)外存相結(jié)合，通過內(nèi)存構(gòu)建GBK編碼字典，快速查找到外存分詞庫的局部起止位置，通過縮小范圍的局部折半查找來快速確定分詞是否存在。通過提供的最大正向分詞匹配法和或最大逆向分詞匹配法，來對文章切分句子，對句子短語再進(jìn)一步分線程雙向切分，通過比對短語切分結(jié)果，當(dāng)切分結(jié)果出現(xiàn)歧義時，采用分詞數(shù)最少策略取其一種，記錄歧義語句日志。雙向匹配法產(chǎn)生的歧義的改進(jìn)算法不在本文討論之內(nèi)。由于在本專利信息領(lǐng)域使用，考慮到一篇專利標(biāo)題和文摘平均大約在5000字節(jié)以內(nèi)，專利說明書和權(quán)利要求書等文獻(xiàn)，在1萬字之間，即便直接單線程切分文摘或全文也不足1秒，如果采用多線程并行多結(jié)點(diǎn)切分，其速度還可以進(jìn)一步加快?？蓪⒎衷~效率提高到足以使分詞服務(wù)響應(yīng)擁塞現(xiàn)象能夠消除為止，其性能是可控的。使得節(jié)省的時間能更多地用于其他方面。例如：統(tǒng)計(jì)詞頻、相似度比對運(yùn)算等。由于最大正向分詞匹配法和或最大逆向分詞匹配法同屬于機(jī)械分詞法，兩種方法切分的結(jié)果都會產(chǎn)生錯誤率，而且同時出現(xiàn)錯誤的情況也在所難免。但是這并不影響該方法的使用。分詞庫與字典索引表是一個相互關(guān)聯(lián)的數(shù)據(jù)結(jié)構(gòu)，在運(yùn)行期間需要相對穩(wěn)定和保持靜態(tài)不變?？焖俜衷~方法由于不涉及詞性問題，新分詞的增加，可通過獲取新詞的自動方法獲得。自動獲取新詞并定期更新分詞庫及字典索引表，由于完全自主定義，而使得維護(hù)變得非常容易。技術(shù)實(shí)現(xiàn)通過socket提供的接口服務(wù)，可與Java、C#等語言通信，或者重新用其他語言編寫，算法簡約，不會存在移植性障礙。

參考文獻(xiàn)：

[1] 莊新妍. 計(jì)算機(jī)中文分詞技術(shù)的應(yīng)用[J]. 呼倫貝爾學(xué)院學(xué)報(bào)，2010（3）.

[2] 李淑英. 中文分詞技術(shù)[J]. 科技信息，2007（36） .

[3] 余戰(zhàn)秋. 中文分詞技術(shù)及其應(yīng)用初探[J]. 電腦知識與技術(shù)，2004（32）.

[4] 劉紅芝. 中文分詞技術(shù)的研究[J]. 電腦開發(fā)與應(yīng)用，2010（3）.