王 敏， 葉寬余， 薛 峰

（1.安徽工商職業(yè)學(xué)院 工商管理系，安徽 合肥 230041；2.合肥工業(yè)大學(xué) 計(jì)算機(jī)與信息學(xué)院，安徽 合肥 230009）

0 引 言

在電子商務(wù)領(lǐng)域，隨著在線商品數(shù)量、種類(lèi)的急劇增加，商品搜索顯得越來(lái)越重要，而要實(shí)現(xiàn)快速、精確的搜索，“分詞”是其中最為關(guān)鍵的一步。英文行文以詞為單位，詞與詞之間以空格作為自然分節(jié)符，而中文行文則是通過(guò)標(biāo)點(diǎn)、段落等明顯的分界符來(lái)簡(jiǎn)單劃界，沒(méi)有一個(gè)形式上的分界符對(duì)詞進(jìn)行有效、準(zhǔn)確的分割，因此對(duì)于中文字符串，需要經(jīng)過(guò)特殊的中文分詞處理才能進(jìn)行有效的檢索，這就需要研究一套真正適合電子商務(wù)網(wǎng)店商品搜索的中文分詞系統(tǒng)［1］。

中文分詞（Chinese Word Segmentation）指的是將一個(gè)漢字序列（如句子）切分成一個(gè)一個(gè)單獨(dú)的詞，是文本挖掘的基礎(chǔ)。近10余年來(lái)，中文自動(dòng)分詞研究取得了很大成就，如清華大學(xué)的SEGTAG系統(tǒng)、北京航空航天大學(xué)的CDWS系統(tǒng)等。主要的分詞算法有：基于字符串匹配的分詞方法、基于理解的分詞方法和基于統(tǒng)計(jì)的分詞方法［2］?；谧址ヅ涞姆衷~方法又叫機(jī)械分詞法，它是按照一定的策略將待分析的漢字串與一個(gè)“充分大的”機(jī)器詞典中的詞條進(jìn)行匹配，若在詞典中找到某個(gè)字符串，則匹配成功（識(shí)別出一個(gè)詞）。機(jī)械分詞從切分程度或切分策略上看，可以分為部分切分和全切分2種，部分切分只取得輸入序列的一種或幾種可接受的切分形式，全切分則要求獲得所有可接受的切分形式［3］。建立在全切分基礎(chǔ)上的分詞方法從根本上避免切分形式的遺漏，保證分詞結(jié)果的準(zhǔn)確性，但最終的分詞結(jié)果是否正確和完全，還要依賴于歧義處理方法的選擇與設(shè)計(jì)［4－5］。

“網(wǎng)店商品搜索”是網(wǎng)店為潛在買(mǎi)家開(kāi)放所有在線商品信息，展示網(wǎng)店數(shù)據(jù)價(jià)值的重要平臺(tái)。用戶可以根據(jù)輸入的關(guān)鍵詞，查詢到網(wǎng)店流行趨勢(shì)以及消費(fèi)趨勢(shì)。為了將用戶輸入的關(guān)鍵詞處理成真正體現(xiàn)用戶實(shí)際意圖的最佳商品CPV（類(lèi)目－屬性－屬性值）組合，本文結(jié)合全切分算法，研究一種面向網(wǎng)店商品搜索的中文分詞系統(tǒng)。

首先，設(shè)計(jì)一種數(shù)據(jù)結(jié)構(gòu)對(duì)網(wǎng)店商品原有的CPV樹(shù)信息進(jìn)行加工處理，構(gòu)成一個(gè)相對(duì)簡(jiǎn)潔的詞條字典供系統(tǒng)的分詞匹配使用。然后，結(jié)合全切分算法，實(shí)現(xiàn)對(duì)用戶輸入關(guān)鍵詞的完全切分，并通過(guò)和詞條字典匹配得到所有候選的詞條組合。同時(shí)，為了消除分詞過(guò)程中的歧義和不合理的詞條組合，保證搜索結(jié)果的準(zhǔn)確性和可靠性，系統(tǒng)結(jié)合商品類(lèi)目樹(shù)的存儲(chǔ)結(jié)構(gòu)，設(shè)計(jì)了3個(gè)過(guò)濾算法，并通過(guò)引入權(quán)值計(jì)算的方法對(duì)過(guò)濾后的詞條組合進(jìn)行排序，得到最佳搜索結(jié)果。實(shí)驗(yàn)表明利用該方法，比較好地處理了全切分算法中的歧義問(wèn)題，商品搜索中分詞匹配的準(zhǔn)確性和速度也明顯提高［6－7］。

1 系統(tǒng)主流程設(shè)計(jì)

分詞算法分為4個(gè)功能模塊，如圖1所示。

（1）詞表初始化模塊。為提高全切分算法的匹配效率，設(shè)計(jì)詞條數(shù)據(jù)結(jié)構(gòu)對(duì)原CPV樹(shù)進(jìn)行簡(jiǎn)化處理，形成詞條字典；設(shè)計(jì)類(lèi)目節(jié)點(diǎn)和屬性／屬性值節(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)保存原CPV樹(shù)的節(jié)點(diǎn)信息，為系統(tǒng)的過(guò)濾算法和權(quán)值計(jì)算提供有效數(shù)據(jù)。

（2）全切分模塊。應(yīng)用全切分算法對(duì)用戶輸入的字符串進(jìn)行完全切分，再和詞條字典進(jìn)行匹配，留下匹配成功的詞條組合。

（3）Filter模塊。根據(jù)CPV樹(shù)中類(lèi)目、屬性和屬性值的邏輯關(guān)系，設(shè)計(jì)3個(gè)過(guò)濾方法去掉商品類(lèi)目樹(shù)中歧義和不合理的詞條組合。

（4）權(quán)值計(jì)算模塊。根據(jù)分詞匹配的準(zhǔn)確度以及詞條中類(lèi)目和屬性的權(quán)重計(jì)算出詞條組合的權(quán)值，選出最佳詞條組合，分詞成功。

圖1 系統(tǒng)主流程圖

1.1 詞表初始化模塊

1.1.1 網(wǎng)店商品的類(lèi)目管理

一個(gè)大型電子商務(wù)網(wǎng)店的在線商品數(shù)有時(shí)會(huì)達(dá)到億以上，類(lèi)目管理相當(dāng)巨大。這時(shí)，為了便于快速查詢和合理利用存儲(chǔ)空間，通常將其類(lèi)目體系分為3個(gè)層次：類(lèi)目（C），商品分類(lèi)；屬性（P），描述特征含義的名字；屬性值（V），具體的一個(gè)特征值。所有類(lèi)目采用具有樹(shù)形關(guān)系的存儲(chǔ)結(jié)構(gòu)，簡(jiǎn)稱CPV樹(shù)，CPV樹(shù)可通過(guò)某些自動(dòng)化算法生成，也可基于人工方法生成，它們的關(guān)系如圖2所示。根節(jié)點(diǎn)Root將所有一級(jí)類(lèi)目關(guān)聯(lián)到一起，前幾層為類(lèi)目，上下級(jí)類(lèi)目是繼承關(guān)系，類(lèi)目和屬性值都可以擁有屬性，每個(gè)屬性總屬于某個(gè)類(lèi)目，一個(gè)類(lèi)目可具有多個(gè)屬性，但規(guī)定只有葉子類(lèi)目才可以擁有屬性，一個(gè)屬性可以有多個(gè)屬性值，但屬性P與屬性值V總是成對(duì)出現(xiàn)。

圖2 CPV樹(shù)示意圖

1.1.2 詞條數(shù)據(jù)結(jié)構(gòu)

網(wǎng)店中的CPV樹(shù)以文本形式存儲(chǔ)，每一行的數(shù)據(jù)從左往右分別表示節(jié)點(diǎn)ID、節(jié)點(diǎn)類(lèi)型、節(jié)點(diǎn)級(jí)別、父節(jié)點(diǎn)ID、子節(jié)點(diǎn)ID、類(lèi)目ID、類(lèi)目名稱、屬性ID、屬性名稱、屬性值ID、屬性值名稱、類(lèi)目屬性級(jí)別、狀態(tài)標(biāo)記串。

CPV樹(shù)存儲(chǔ)了所有商品信息，是全切分詞進(jìn)行匹配的原始數(shù)據(jù)，但這種存儲(chǔ)形式中含有很多冗余數(shù)據(jù)，加上該文件含有上百萬(wàn)條的數(shù)據(jù)，匹配效率會(huì)很低。因此，需要重新設(shè)計(jì)一個(gè)精簡(jiǎn)的表1所列的數(shù)據(jù)結(jié)構(gòu)來(lái)存儲(chǔ)各個(gè)詞條信息，所有的詞條信息構(gòu)成一個(gè)新的數(shù)據(jù)詞典。

表1 詞條lexeme的成員變量

1.1.3 CPV樹(shù)節(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)

系統(tǒng)在成功匹配后會(huì)存留一些有歧義的詞條組合需要剔除，為了判斷這點(diǎn)，需要設(shè)計(jì)一個(gè)數(shù)據(jù)結(jié)構(gòu)來(lái)保存CPV樹(shù)的所有節(jié)點(diǎn)信息。首先，利用一個(gè)HashMap〈long，List〉來(lái)存儲(chǔ)所有類(lèi)目節(jié)點(diǎn)的信息，long為類(lèi)目ID（cid），List中存儲(chǔ)了類(lèi)目節(jié)點(diǎn)的具體信息。List的第1個(gè)元素為一個(gè)String，保存類(lèi)目的名稱cname；第2個(gè)元素為一個(gè)HashSet，記錄了這個(gè)類(lèi)目所有的上級(jí)類(lèi)目；最后一個(gè)元素long則記錄了該類(lèi)目擁有多少個(gè)屬性，用于計(jì)算節(jié)點(diǎn)的權(quán)重。

同理，再利用一個(gè) HashMap〈long，List〉來(lái)存儲(chǔ)所有屬性／屬性值節(jié)點(diǎn)的信息，long為屬性ID（pid），List中存儲(chǔ)了該屬性節(jié)點(diǎn)的具體信息。List的第1個(gè)元素是一個(gè)String，保存了屬性的名稱pname；第3個(gè)元素記錄了該節(jié)點(diǎn)可以掛在多少個(gè)類(lèi)目下，同樣是用于計(jì)算節(jié)點(diǎn)的權(quán)重；第2個(gè)元素又是一個(gè) HashMap〈long，List〉，用來(lái)保存該屬性節(jié)點(diǎn)所擁有的所有屬性值節(jié)點(diǎn)的信息，long為該屬性值的ID，List中保存了該屬性值名稱vname以及該屬性／屬性值組合所屬的葉子類(lèi)目的ID。

1.1.4 詞表初始化

詞表的構(gòu)造是本文分詞算法的前提，構(gòu)造詞表的過(guò)程為：

（1）讀入含冗余信息的CPV樹(shù)信息。

（2）對(duì)CPV樹(shù)信息進(jìn)行精簡(jiǎn)處理，將其轉(zhuǎn)換成一個(gè)個(gè)詞條（lexeme）。

（3）在創(chuàng)建詞條的同時(shí)，更新并保存CPV樹(shù)中所有節(jié)點(diǎn)的信息，采用1.1.3中類(lèi)目節(jié)點(diǎn)和屬性／屬性值節(jié)點(diǎn)設(shè)置的數(shù)據(jù)結(jié)構(gòu)。

（4）計(jì)算一個(gè)類(lèi)目下最多掛有多少屬性／屬性值節(jié)點(diǎn)，同時(shí)計(jì)算一個(gè)屬性／屬性值節(jié)點(diǎn)最多能被多少個(gè)類(lèi)目擁有，按一定的規(guī)則預(yù)先設(shè)定權(quán)值并更新詞條（lexeme）的權(quán)重信息。

1.2 全切分模塊

全切分模塊的過(guò)程如圖3所示，首先接收用戶輸入字符串，然后選擇切分點(diǎn)切分字符串，再進(jìn)行詞典匹配，匹配成功，保留切分結(jié)果，匹配不成功，不保留切分結(jié)果，繼續(xù)進(jìn)行下一次切分，直至完成切分。全切分過(guò)程的關(guān)鍵是切分點(diǎn)的選擇，該過(guò)程的核心算法如下：

（1）計(jì)算字符串長(zhǎng)度，假設(shè)長(zhǎng)度為n，則一個(gè)與該字符串長(zhǎng)度相同的二進(jìn)制串的取值范圍為0～（2n－1）。

（2）記切分點(diǎn)個(gè)數(shù)為x（起始為0），計(jì)算0～（2n－1）之間所有數(shù)字長(zhǎng)度為n的二進(jìn)制串形式，判斷每個(gè)二進(jìn)制串中“1”的個(gè)數(shù)是否為x，是則保留該二進(jìn)制串。

（3）判斷所保留的二進(jìn)制串中“1”所在的位置，以該位置作為切分點(diǎn)對(duì)字符串進(jìn)行切分。

（4）若x＜n，則令x＝x＋1，繼續(xù)步驟（2）。

圖3 全切分流程圖

1.3 Filter模塊的設(shè)計(jì)

對(duì)用戶輸入的字符串進(jìn)行切分，并在詞條詞典中匹配會(huì)得到若干類(lèi)目詞條和屬性詞條，將這些詞條相互組合后，會(huì)有一些歧義和不合理的組合，需要將其排除。為此，系統(tǒng)設(shè)計(jì)了3個(gè)Filter模塊，用于過(guò)濾那些完全不合理的組合，以提高分詞系統(tǒng)的準(zhǔn)確率。

（1）Filter＿M(jìn)oreThanOneC（）：用于去除有多個(gè)cid的詞條組合。在CPV的組合中，不能存在多個(gè)cid，否則該組合就是無(wú)效的。

（2）Filter－SameP－Different－V（）：CPV 中屬性和屬性值總是成對(duì)出現(xiàn)的，因此，對(duì)于某個(gè)屬性，如果包含多個(gè)屬性值，也是不合理的，這樣的組合也要過(guò)濾掉。

（3）Filter－NotleafNotPutin（）：判斷組合的詞條在CPV樹(shù)上是否存在父子關(guān)系，如果一個(gè)葉子類(lèi)目和另一個(gè)葉子類(lèi)目下的屬性組合了，也需要過(guò)濾掉。

1.4 權(quán)重計(jì)算模塊

詞條組合經(jīng)過(guò)過(guò)濾，大大提高了搜索結(jié)果的準(zhǔn)確性，但過(guò)濾后的詞條可能數(shù)目較多，排列混亂，不利于用戶的直接應(yīng)用。因此，為了進(jìn)一步優(yōu)化分詞結(jié)果，選出最佳的詞條組合，設(shè)計(jì)了權(quán)值計(jì)算的方法，權(quán)重信息分可為3個(gè)方面。

（1）分出詞的匹配度。記Pn＝當(dāng)前組合分出詞的個(gè)數(shù)／分出最多詞的個(gè)數(shù)。

（2）分詞中字的匹配度。記Pm＝匹配出來(lái)詞的字?jǐn)?shù)／用戶輸入的字?jǐn)?shù)。

（3）詞條權(quán)重。在1.1初始化詞表的時(shí)候，每個(gè)詞條都賦予了一個(gè)權(quán)重，記該組合中每個(gè)詞條的權(quán)重分別為：P1，P2，…，PN，詞條權(quán)值是它們的平均值，即Pi＝ （P1＋P2＋…＋PN）／N。

最后，設(shè)定總權(quán)重W ＝PnaPmbPic，其中引入3個(gè)參數(shù)a、b、c，是為了能靈活調(diào)整Pn、Pm、Pi3個(gè)值所占的比重。為了確定a、b、c這3個(gè)參數(shù)的最佳值，設(shè)計(jì)了一個(gè)評(píng)估函數(shù)，該函數(shù)利用一個(gè)設(shè)計(jì)好的評(píng)估測(cè)試集，動(dòng)態(tài)地調(diào)整a、b、c三者的值，記錄下分詞效果最佳時(shí)各個(gè)參數(shù)的值。該評(píng)估函數(shù)在判斷分詞效果優(yōu)劣的時(shí)候考慮了2點(diǎn)：一是分詞結(jié)果和測(cè)試集中結(jié)果完全符合的個(gè)數(shù)；二是如果不符合，它們之間的相近程度有多少。

2 實(shí)驗(yàn)結(jié)果與分析

（1）用戶輸入字符串，算法提交后，返回分詞后的結(jié)果。例如用戶輸入“紅色手機(jī)”，返回的結(jié)果是：｛“cate”：｛“id”：1512，“name”：“手機(jī)”｝，“value”：｛“1”：｛“id”：28326，“name”；“紅色”｝｝，“property”：｛“1”：｛“id”：16270207，“name”：“顏色分類(lèi)”｝｝｝。cate中包含類(lèi)目id和類(lèi)目名稱，只允許存在一個(gè)類(lèi)目；value中為屬性值id和屬性值名稱；property中是屬性id和屬性名稱，屬性／屬性值可以存在多個(gè)，但必須成對(duì)出現(xiàn)。

（2）系統(tǒng)實(shí)驗(yàn)中可以查看分詞過(guò)程中的處理數(shù)據(jù)。例如，當(dāng)輸入“紅色手機(jī)”，由全切分算法將其切分成“紅色／手機(jī)”和“紅／手機(jī)”這2種情況，計(jì)算詞匹配度、字匹配度和每個(gè)詞條自身的權(quán)值，根據(jù)公式計(jì)算出總權(quán)值，并按總權(quán)值進(jìn)行排序，處理結(jié)果見(jiàn)表2～表4所列。

全切分后的分詞結(jié)果：① 紅色／手機(jī)；② 紅／手機(jī)。所有匹配情況和對(duì)應(yīng)的總權(quán)值為：

情況1：詞匹配度2／2＝1.0，字匹配度4／4＝1.0，總權(quán)值0.9；情況2：詞匹配度2／2＝1.0，字匹配度4／4＝1.0，總權(quán)值0.55；情況3：詞匹配度2／2＝1.0，字匹配度4／4＝1.0，總權(quán)值0.55。

表2 情況1處理結(jié)果

表3 情況2處理結(jié)果

表4 情況3處理結(jié)果

3 結(jié)束語(yǔ)

全切分算法是一種常用的分詞算法，其核心問(wèn)題是歧義的識(shí)別與處理，本文為了消除分詞結(jié)果中的歧義和不合理詞條組合，保證搜索結(jié)果的準(zhǔn)確性和可靠性，在重新設(shè)計(jì)網(wǎng)店商品數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)上，進(jìn)行詞條字典匹配，并設(shè)計(jì)了3個(gè)過(guò)濾算法，有效地解決了全切分算法中的缺點(diǎn)和不足。此外，為了使得搜索結(jié)果更符合用戶意圖，系統(tǒng)引入了權(quán)值計(jì)算的方法對(duì)搜索結(jié)果進(jìn)行排序，獲取最佳結(jié)果。實(shí)驗(yàn)表明利用該方法，網(wǎng)店商品搜索中分詞匹配的準(zhǔn)確性和速度明顯提高，實(shí)用性更強(qiáng)。雖然本系統(tǒng)中對(duì)分詞算法的改進(jìn)已經(jīng)達(dá)到了一定效果，但還有很大的提升空間，比如可以對(duì)詞表進(jìn)行一定的處理，用一定的規(guī)則將一些無(wú)關(guān)緊要的詞條排除掉，以提高分詞的準(zhǔn)確性和速度；此外，當(dāng)前處理同義詞和一些特殊情況的方法還不夠豐富，有待進(jìn)一步的研究［8］。

［1］王顯芳，杜利民.一種能夠檢測(cè)所有交叉歧義的漢語(yǔ)分詞算法［J］.電子學(xué)報(bào)，2004，32（1）：50－54.

［2］萬(wàn)建成，楊春花.書(shū)面漢語(yǔ)的全切分分詞算法模型［J］.小型微型計(jì)算機(jī)系統(tǒng)，2006，24（7）：1247－1251.

［3］Zhang Maoyuan，Lu Zhengding.A Chinese word segmentation based on language situation in processing ambiguous words［J］.Inf Sci，2004，162（3／4）：275－285.

［4］曹勇剛，曹羽中.面向信息檢索的自適應(yīng)中文分詞系統(tǒng)［J］.軟件工程，2006，17（3）：356－363.

［5］許高建，胡學(xué)鋼，路 遙，等.一種改進(jìn)的中文分詞歧義消除算法研究［J］.合肥工業(yè)大學(xué)學(xué)報(bào)：自然科學(xué)版，2008，31（10）：1622－1625.

［6］Manning C，Schütze H.統(tǒng)計(jì)自然語(yǔ)言處理基礎(chǔ)［M］.苑春法，李 偉，李慶中，譯.北京：電子工業(yè)出版社，2005：45－50.

［7］Luo Zhengqing，Chen Zengwu，Hu Shangxw.A revised MMalgorithMof Chinese automatic words segmentation ［J］.Journal of Chinese Information Processing，1996，10（3）：30－36.

［8］歐陽(yáng)一鳴，周 強(qiáng)，胡學(xué)鋼，等.數(shù)據(jù)挖掘中動(dòng)態(tài)改變樣本域提高預(yù)測(cè)精度 ［J］.合肥工業(yè)大學(xué)學(xué)報(bào)：自然科學(xué)版，2006，29（4）：395－398.