一種適用于移動(dòng)搜索的中文分詞算法

賀菲菲， 賀 炎， 齊靜娜

(1.中興通訊股份有限公司 西安研發(fā)中心，陜西 西安 710114；2.西安郵電大學(xué) 計(jì)算機(jī)學(xué)院, 陜西 西安 710121)

一種適用于移動(dòng)搜索的中文分詞算法

賀菲菲1， 賀 炎2， 齊靜娜2

(1.中興通訊股份有限公司 西安研發(fā)中心，陜西 西安 710114；2.西安郵電大學(xué) 計(jì)算機(jī)學(xué)院, 陜西 西安 710121)

針對現(xiàn)有中文分詞算法無法為移動(dòng)搜索提供用戶興趣偏好信息的現(xiàn)狀，提出一種改進(jìn)的正向最大匹配中文分詞算法。該算法基于逐字二分的分詞詞典機(jī)制，添加詞分類信息，在詞典中存儲了每個(gè)詞條的分類信息，分詞時(shí)采用改進(jìn)的次字區(qū)位碼哈希非均勻分段機(jī)制進(jìn)行正向最大匹配分詞。實(shí)驗(yàn)結(jié)果表明，與逐字二分法相比，改進(jìn)的分詞算法其存儲空間增加了13%，但時(shí)間效率提高了20%左右，且分詞后可同時(shí)提取出詞條的分類信息。

中文分詞；詞典機(jī)制；詞分類信息

隨著網(wǎng)絡(luò)信息資源的飛速增長以及移動(dòng)設(shè)備的普及，越來越多的用戶習(xí)慣使用移動(dòng)設(shè)備隨時(shí)隨地進(jìn)行搜索。由于用戶常常不能準(zhǔn)確表達(dá)自己的查詢意圖，以及網(wǎng)絡(luò)資源過于豐富導(dǎo)致信息迷失等原因，移動(dòng)搜索給用戶反饋了過多無用的信息。如何找出用戶真實(shí)的查詢意圖，使用移動(dòng)設(shè)備快捷地從海量網(wǎng)絡(luò)資源中篩選出真正滿足用戶需求的信息，即個(gè)性化信息服務(wù)成為當(dāng)代移動(dòng)搜索引擎的主要發(fā)展方向[1-3]。

移動(dòng)搜索引擎的首要任務(wù)就是進(jìn)行中文分詞，分詞精確度對搜索引擎的查詢結(jié)果將產(chǎn)生很大影響[4]。中文分詞算法種類眾多，大致可分為3大類。(1)基于字符串匹配的分詞方法[5-8]：采用正向最大匹配、逆向最大匹配等策略將漢字字符串與詞典中的詞條進(jìn)行機(jī)械式匹配，如果找到該字符串，則識別出一個(gè)詞條。該分詞法對詞典的依賴性很強(qiáng)，詞典中未登錄詞條和新詞都無法被切分出來，且無法根據(jù)文檔的上下文語義來分詞。(2)基于理解的分詞方法[6]：通過機(jī)器學(xué)習(xí)方法訓(xùn)練計(jì)算機(jī)的思維能力，模擬人腦對句子的理解過程，在大量句法信息、語法信息的基礎(chǔ)上對句子進(jìn)行句法、語法分析，處理歧義現(xiàn)象并理解句子。由于中文的復(fù)雜性與模糊性，現(xiàn)有技術(shù)很難把海量知識準(zhǔn)確轉(zhuǎn)化成機(jī)器可識別的表達(dá)形式，分詞準(zhǔn)確率不高。(3)基于統(tǒng)計(jì)的分詞方法[9]：不需要詞典等先驗(yàn)知識，通過統(tǒng)計(jì)字與字同時(shí)出現(xiàn)的概率來判斷是否構(gòu)成詞?；诟怕式y(tǒng)計(jì)的分詞系統(tǒng)在評測中優(yōu)于基于字符串匹配和基于理解的分詞系統(tǒng)。但這種方法經(jīng)常將一些高頻度、但并不是詞的常用字組合為詞條，導(dǎo)致分詞錯(cuò)誤，且計(jì)算開銷較大，分詞效率較低。

目前，移動(dòng)搜索引擎大多采用上述中文分詞算法。但這些算法往往不能滿足移動(dòng)搜索輕量級、執(zhí)行速度快、分詞精確性較高等要求，也不能提供可以反映用戶真實(shí)搜索意圖或興趣偏好的個(gè)性化信息。為了提高分詞效率，并在分詞的同時(shí)提取能在一定程度上反映用戶真實(shí)搜索意圖的信息，便于從中提取用戶的興趣偏好，本文提出一種改進(jìn)的正向最大匹配分詞算法，通過改進(jìn)逐字二分法分詞詞典機(jī)制，為每個(gè)詞條添加了分類信息，并采用次字區(qū)位碼哈希非均勻分段機(jī)制，進(jìn)行正向最大匹配分詞處理。

1 逐字二分的分詞詞典機(jī)制

逐字二分的分詞詞典[10]由首字哈希表、詞索引表和詞典正文3部分組成。通過首字哈希表的定位，結(jié)合詞索引表，可以很方便地指定詞在詞典正文中可能的位置范圍，進(jìn)而采用逐字二分法在詞典正文中進(jìn)行定位。其基本結(jié)構(gòu)[10]如圖1所示。

圖1 逐字二分法的基本結(jié)構(gòu)

2 改進(jìn)的分詞詞典機(jī)制和分詞算法

為了提高分詞效率，并在分詞的同時(shí)提供詞分類信息，方便從中提取用戶的興趣偏好，對逐字二分的分詞詞典機(jī)制和正向最大匹配分詞算法進(jìn)行改進(jìn)。

2.1 基于詞分類信息的詞典機(jī)制

主要從兩個(gè)方面對逐字二分的分詞詞典機(jī)制進(jìn)行改進(jìn)。

(1)詞條分類設(shè)計(jì)，添加分類信息

在改進(jìn)的分詞詞典中，詞條根據(jù)內(nèi)容進(jìn)行三級分類，按照由上而下的順序給各類別名分配兩位十進(jìn)制數(shù)進(jìn)行編碼，并按照“主類在前子類在后”的方式將代表詞條分類信息的編碼以及詞頻等信息作為詞條的屬性存入詞典中。

(2) 增加次字區(qū)位碼分段哈希索引表

為了提高次字查詢效率，可直接使用次字哈希方法或多字哈希機(jī)制[11-12]，但這種方法會使次字哈希表的長度過長，或造成次字哈希表難于構(gòu)建，導(dǎo)致詞典的存儲結(jié)構(gòu)復(fù)雜。

在逐字二分的分詞詞典中增加一張次字區(qū)位碼分段哈希索引表。對原始詞庫中所有詞條的次字分布范圍進(jìn)行統(tǒng)計(jì)，根據(jù)統(tǒng)計(jì)結(jié)果對次字進(jìn)行非均勻分段，將首字相同的詞條按照次字的區(qū)位碼進(jìn)行哈希運(yùn)算，分別映射到不同的分段內(nèi)(段號為：1-20)，使各段內(nèi)詞條數(shù)目大致相同，從而通過增加少量存儲空間達(dá)到縮小次字查找范圍的目的。

改進(jìn)的詞典結(jié)構(gòu)包括首字哈希表F_hash、次字區(qū)位碼非均勻分段哈希索引表S_hash、次字索引表S_index和詞典正文Last_table 4個(gè)部分，其邏輯結(jié)構(gòu)如圖2所示。

圖2 詞典邏輯結(jié)構(gòu)

2.2 改進(jìn)的正向最大匹配法

基于改進(jìn)的詞典結(jié)構(gòu)，采用與之相適應(yīng)的改進(jìn)的正向最大匹配分詞法，其分詞過程如圖3所示。

改進(jìn)的分詞算法主要在以下兩個(gè)方面對正向最大匹配分詞算法進(jìn)行改進(jìn)。

(1)基于改進(jìn)的詞典結(jié)構(gòu)，次字 W2 采用次字區(qū)位碼哈希非均勻分段機(jī)制進(jìn)行查找。首先，根據(jù)W2的區(qū)位碼進(jìn)行哈希處理，得到其分段號wordIndex；然后，根據(jù)wordIndex的值在首字 W1 對應(yīng)的S_hash表內(nèi)進(jìn)行次字區(qū)間regionIndex的定位，進(jìn)而實(shí)現(xiàn)在regionIndex對應(yīng)的S_index表內(nèi)對次字的查找。

(2)在次字定位后，可得到 W1W2 對應(yīng)的Last_table表。改進(jìn)的分詞算法根據(jù)Last_table表中存儲的詞條長度動(dòng)態(tài)截取當(dāng)前中文字符串，將截取到的字符串與Last_table表中相應(yīng)的詞條進(jìn)行匹配，并綜合考慮切分詞長及詞頻選取最優(yōu)的切分結(jié)果。在該分詞過程中，詞的切分長度由待匹配詞長動(dòng)態(tài)決定，避免了傳統(tǒng)最大匹配法中匹配詞長固定所造成的效率低下或錯(cuò)誤切分。

圖3 分詞過程

3 實(shí)驗(yàn)結(jié)果及分析

(1)實(shí)驗(yàn)環(huán)境

系統(tǒng)服務(wù)器端操作系統(tǒng)為Windows Server 2008，開發(fā)語言采用Java ，開發(fā)工具采用JDK 6.0，MyEclipse 8.5，Tomcat 6.0，數(shù)據(jù)庫系統(tǒng)采用MySQL5.5。

(2)實(shí)驗(yàn)內(nèi)容

為了驗(yàn)證改進(jìn)的分詞詞典機(jī)制和分詞算法的有效性，分別使用逐字二分法和改進(jìn)的分詞算法對測試文本(總大小為31KB)進(jìn)行分詞處理，并從時(shí)間、空間復(fù)雜度和分詞后所能顯示的詞分類信息這兩個(gè)方面進(jìn)行對比。

(3)實(shí)驗(yàn)結(jié)果及分析

在分詞過程中，逐字二分法占用的空間大小為3 553 068 字節(jié)，分詞時(shí)間為156ms，而改進(jìn)的分詞算法占用的空間大小為4 014 108字節(jié)，分詞時(shí)間為125ms。可以看出，由于在詞典中存儲了詞分類信息，改進(jìn)的算法比逐字二分法增加了13%的存儲空間；同時(shí)，改進(jìn)的分詞算法采用次字區(qū)位碼哈希非均勻分段機(jī)制，縮小了次字的查找范圍，使得測試文本分詞的時(shí)間效率提高了20%左右，且分詞后可同時(shí)提取出詞分類信息。舉例如下：輸入以下待分詞的字符串“計(jì)算機(jī)網(wǎng)絡(luò)是計(jì)算機(jī)技術(shù)與通信技術(shù)結(jié)合的產(chǎn)物”，其輸出結(jié)果如圖4所示。

圖4 分詞結(jié)果測試

圖4中切分出來的第一個(gè)詞是“計(jì)算機(jī)網(wǎng)絡(luò)”，其所屬分類為“031 402,031 404,032 001”，表明該詞屬于“工程應(yīng)用類”下的“計(jì)算機(jī)技術(shù)”子類。

4 結(jié)束語

改進(jìn)的最大匹配分詞算法結(jié)合次字區(qū)位碼哈希非均勻分段機(jī)制，將首字相同的詞條根據(jù)次字區(qū)位碼進(jìn)行非均勻分段，縮小了分詞過程中次字的查找范圍，提高了分詞速度。隨著詞典中詞條數(shù)目的增加，該方法的優(yōu)越性會更為顯著。同時(shí)，該分詞詞典中添加了詞條的分類信息，分詞后可同時(shí)獲取所有詞條的分類信息。實(shí)驗(yàn)結(jié)果表明，與逐字二分法相比，改進(jìn)的分詞算法在存儲空間上雖然有所增加，但時(shí)間效率卻提高了20%左右。分詞后提取出的詞條分類信息可用于進(jìn)行查詢的擴(kuò)展，實(shí)現(xiàn)個(gè)性化的搜索查詢。通過分析用戶歷史查詢詞條的分類信息，可以提取出用戶在一段時(shí)間內(nèi)的興趣偏好，為搜索結(jié)果的個(gè)性化推薦提供一種有效方法。

[1] 梁琛，王忠民，范琳. 移動(dòng)搜索終端用戶行為調(diào)查研究[J].西安郵電大學(xué)學(xué)報(bào)，2014，19(2):108-112.

[2] 賀炎，楊爽，王忠民. 我國移動(dòng)搜索產(chǎn)業(yè)共贏合作模式探討[J].西安郵電大學(xué)學(xué)報(bào)，2013，18(6):95-99.

[3] 王忠民，史育蘭，張榮，等. 一種移動(dòng)智能搜索個(gè)性化客戶端[J].西安郵電大學(xué)學(xué)報(bào)，2013，18(3):71-75.

[4] 趙川，杜玲，岳鵬，等.基于中文的自然語言理解初探[J].現(xiàn)代電子技術(shù)，2007(6):82-85.

[5] 梁喜濤，顧磊 .中文分詞與詞性標(biāo)注研究[J].計(jì)算機(jī)技術(shù)與發(fā)展，2015,25(2):175-180.

[6] 林冬盛.中文分詞算法的研究與實(shí)現(xiàn)[D].西安：西北大學(xué)，2011:7-16,19-22.

[7] 楊毅，王禹橋. 中文分詞詞典機(jī)制：次字拼音首字母哈希機(jī)制[J].計(jì)算機(jī)工程與設(shè)計(jì)，2010,31(6):1369-1375.

[8] 焦嬌. 基于二次哈希并逐字二分匹配的中文分詞改進(jìn)算法[J]. 信息與電腦，2010(9):113.

[9] 李惠. 組合型中文分詞方法的研究[D].廣州：廣東工業(yè)大學(xué)，2014:7-12.

[10]吳晶晶，荊繼武，聶曉峰，等. 一種快速中文分詞詞典機(jī)制[J].中國科學(xué)院研究生院學(xué)報(bào)，2009,26(5):703-711.

[11]羅洋.一種基于雙哈希二叉樹的中文分詞詞典機(jī)制[J].計(jì)算機(jī)應(yīng)用與軟件，2013，30(5):251-253.

[12]周俊，鄭中華，張煒. 基于改進(jìn)最大匹配算法的中文分詞粗分方法[J].計(jì)算機(jī)工程與應(yīng)用，2014，50(2):124-128.

[責(zé)任編輯：祝劍]

A chinese word segmentation algorithm for mobile search

HE Feifei1, HE Yan2, QI Jingna2

(1. ZTE Corporation, Xi’an R & D Center, Xi’an 710114, China; 2.School of Computer Science and Technology, Xi’an University of Posts and Telecommunications, Xi’an 710121, China)

As existing Chinese word segmentation algorithm can’t provide user interest information for mobile search, an improved FMM segmentation algorithm is proposed. Based on a new dictionary mechanism which contains words’ classified information, the algorithm performs Forward Maximum Matching by the improved second word area code hash non-uniform segmentation mechanism. Experimental results show that compared with the Verbatim dichotomy, the storage space of the improved algorithm is increased by 13%, but the time efficiency is improved by about 20%, and the words’ classified information is extracted simultaneously.

chinese word segmentation, dictionary mechanism, words’ classified information

10.13682/j.issn.2095-6533.2015.04.013

2015-03-20

國家自然科學(xué)基金資助項(xiàng)目(61373116)；西安郵電大學(xué)青年基金資助項(xiàng)目(ZL2014-27)

賀菲菲(1980-)，女，碩士，工程師，從事移動(dòng)終端軟件開發(fā)、數(shù)據(jù)業(yè)務(wù)等研究。E-mail：he.feifeixa@zte.com.cn 賀炎(1980-)，女，碩士，講師，從事機(jī)器學(xué)習(xí)、移動(dòng)搜索等研究。E-mail：heyan0220@xupt.edu.cn

TP391.1

A

2095-6533(2015)04-0062-04