一種面向網店商品搜索的中文分詞系統設計

王 敏， 葉寬余， 薛 峰

（1.安徽工商職業學院 工商管理系，安徽 合肥 230041；2.合肥工業大學 計算機與信息學院，安徽 合肥 230009）

0 引 言

在電子商務領域，隨著在線商品數量、種類的急劇增加，商品搜索顯得越來越重要，而要實現快速、精確的搜索，“分詞”是其中最為關鍵的一步。英文行文以詞為單位，詞與詞之間以空格作為自然分節符，而中文行文則是通過標點、段落等明顯的分界符來簡單劃界，沒有一個形式上的分界符對詞進行有效、準確的分割，因此對于中文字符串，需要經過特殊的中文分詞處理才能進行有效的檢索，這就需要研究一套真正適合電子商務網店商品搜索的中文分詞系統［1］。

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

“網店商品搜索”是網店為潛在買家開放所有在線商品信息，展示網店數據價值的重要平臺。用戶可以根據輸入的關鍵詞，查詢到網店流行趨勢以及消費趨勢。為了將用戶輸入的關鍵詞處理成真正體現用戶實際意圖的最佳商品CPV（類目－屬性－屬性值）組合，本文結合全切分算法，研究一種面向網店商品搜索的中文分詞系統。

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

1 系統主流程設計

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

（1）詞表初始化模塊。為提高全切分算法的匹配效率，設計詞條數據結構對原CPV樹進行簡化處理，形成詞條字典；設計類目節點和屬性／屬性值節點數據結構保存原CPV樹的節點信息，為系統的過濾算法和權值計算提供有效數據。

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

（3）Filter模塊。根據CPV樹中類目、屬性和屬性值的邏輯關系，設計3個過濾方法去掉商品類目樹中歧義和不合理的詞條組合。

（4）權值計算模塊。根據分詞匹配的準確度以及詞條中類目和屬性的權重計算出詞條組合的權值，選出最佳詞條組合，分詞成功。

圖1 系統主流程圖

1.1 詞表初始化模塊

1.1.1 網店商品的類目管理

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

圖2 CPV樹示意圖

1.1.2 詞條數據結構

網店中的CPV樹以文本形式存儲，每一行的數據從左往右分別表示節點ID、節點類型、節點級別、父節點ID、子節點ID、類目ID、類目名稱、屬性ID、屬性名稱、屬性值ID、屬性值名稱、類目屬性級別、狀態標記串。

CPV樹存儲了所有商品信息，是全切分詞進行匹配的原始數據，但這種存儲形式中含有很多冗余數據，加上該文件含有上百萬條的數據，匹配效率會很低。因此，需要重新設計一個精簡的表1所列的數據結構來存儲各個詞條信息，所有的詞條信息構成一個新的數據詞典。

表1 詞條lexeme的成員變量

1.1.3 CPV樹節點數據結構

系統在成功匹配后會存留一些有歧義的詞條組合需要剔除，為了判斷這點，需要設計一個數據結構來保存CPV樹的所有節點信息。首先，利用一個HashMap〈long，List〉來存儲所有類目節點的信息，long為類目ID（cid），List中存儲了類目節點的具體信息。List的第1個元素為一個String，保存類目的名稱cname；第2個元素為一個HashSet，記錄了這個類目所有的上級類目；最后一個元素long則記錄了該類目擁有多少個屬性，用于計算節點的權重。

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

1.1.4 詞表初始化

詞表的構造是本文分詞算法的前提，構造詞表的過程為：

（1）讀入含冗余信息的CPV樹信息。

（2）對CPV樹信息進行精簡處理，將其轉換成一個個詞條（lexeme）。

（3）在創建詞條的同時，更新并保存CPV樹中所有節點的信息，采用1.1.3中類目節點和屬性／屬性值節點設置的數據結構。

（4）計算一個類目下最多掛有多少屬性／屬性值節點，同時計算一個屬性／屬性值節點最多能被多少個類目擁有，按一定的規則預先設定權值并更新詞條（lexeme）的權重信息。

1.2 全切分模塊

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

（1）計算字符串長度，假設長度為n，則一個與該字符串長度相同的二進制串的取值范圍為0～（2n－1）。

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

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

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

圖3 全切分流程圖

1.3 Filter模塊的設計

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

（1）Filter＿MoreThanOneC（）：用于去除有多個cid的詞條組合。在CPV的組合中，不能存在多個cid，否則該組合就是無效的。

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

（3）Filter－NotleafNotPutin（）：判斷組合的詞條在CPV樹上是否存在父子關系，如果一個葉子類目和另一個葉子類目下的屬性組合了，也需要過濾掉。

1.4 權重計算模塊

詞條組合經過過濾，大大提高了搜索結果的準確性，但過濾后的詞條可能數目較多，排列混亂，不利于用戶的直接應用。因此，為了進一步優化分詞結果，選出最佳的詞條組合，設計了權值計算的方法，權重信息分可為3個方面。

（1）分出詞的匹配度。記Pn＝當前組合分出詞的個數／分出最多詞的個數。

（2）分詞中字的匹配度。記Pm＝匹配出來詞的字數／用戶輸入的字數。

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

最后，設定總權重W ＝PnaPmbPic，其中引入3個參數a、b、c，是為了能靈活調整Pn、Pm、Pi3個值所占的比重。為了確定a、b、c這3個參數的最佳值，設計了一個評估函數，該函數利用一個設計好的評估測試集，動態地調整a、b、c三者的值，記錄下分詞效果最佳時各個參數的值。該評估函數在判斷分詞效果優劣的時候考慮了2點：一是分詞結果和測試集中結果完全符合的個數；二是如果不符合，它們之間的相近程度有多少。

2 實驗結果與分析

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

（2）系統實驗中可以查看分詞過程中的處理數據。例如，當輸入“紅色手機”，由全切分算法將其切分成“紅色／手機”和“紅／手機”這2種情況，計算詞匹配度、字匹配度和每個詞條自身的權值，根據公式計算出總權值，并按總權值進行排序，處理結果見表2～表4所列。

全切分后的分詞結果：① 紅色／手機；② 紅／手機。所有匹配情況和對應的總權值為：

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

表2 情況1處理結果

表3 情況2處理結果

表4 情況3處理結果

3 結束語

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

［1］王顯芳，杜利民.一種能夠檢測所有交叉歧義的漢語分詞算法［J］.電子學報，2004，32（1）：50－54.

［2］萬建成，楊春花.書面漢語的全切分分詞算法模型［J］.小型微型計算機系統，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］曹勇剛，曹羽中.面向信息檢索的自適應中文分詞系統［J］.軟件工程，2006，17（3）：356－363.

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

［6］Manning C，Schütze H.統計自然語言處理基礎［M］.苑春法，李 偉，李慶中，譯.北京：電子工業出版社，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］歐陽一鳴，周 強，胡學鋼，等.數據挖掘中動態改變樣本域提高預測精度 ［J］.合肥工業大學學報：自然科學版，2006，29（4）：395－398.