基于雙字Hash機制的交通信息分詞算法研究

,,

(浙江工業(yè)大學 計算機科學與技術學院，浙江 杭州 310023)

目前，實時交通信息的采集與發(fā)布技術為交通管理部門和公眾提供了很大便利.浮動車、感應線圈等傳感器方式已經(jīng)成為我國各大城市實時交通信息采集與發(fā)布的主要技術手段.然而，采用浮動車、感應線圈和視頻監(jiān)控方式采集得到的交通信息，覆蓋范圍較小，對突發(fā)性點狀交通信息也難以獲取[1-2].同時，來源于社交網(wǎng)絡等互聯(lián)網(wǎng)文本形式的交通信息日益增多，但受制于自然語言理解[3-4]技術的限制，難以被現(xiàn)有計算機系統(tǒng)直接利用，不能滿足日益普及的高動態(tài)導航與位置服務需求.因此，開展互聯(lián)網(wǎng)文本蘊含交通信息的實時分詞技術[5-7]研究迫在眉睫，為文本蘊含交通信息語義理解提供技術支持，進而為高動態(tài)導航與位置服務提供重要的數(shù)據(jù)支撐，服務于公眾出行需求.

交通信息文本分詞主要采用正向逐字增加[8]的字符串匹配方式，但仍然是逐字匹配方法，所以其處理的效率不高.文獻[1]充分考慮了詞庫記錄長度的特點，提出了一種自然語言表達交通信息的跨階分詞算法，該算法通過對中文分詞階數(shù)進行設置，根據(jù)詞庫性質(zhì)變化將中文分詞的字符串指針設置為多階跨越，對可能成詞的中文字符串進行成詞處理.該算法在一定程度上提高了中文分詞效率，但仍然存在以下幾個方面問題：1)由于采用了一種多層模式的詞典結(jié)構(gòu)，且最大層數(shù)為詞庫中最大詞的單字數(shù)，所以，其匹配查詢效率并沒有得到最大限度的提高；2)對于長句或組合句表達的交通信息沒有進行有效的處理.針對以上問題，筆者重新設計了專業(yè)詞庫，建立了一種雙字Hash與List相結(jié)合的三層詞典數(shù)據(jù)結(jié)構(gòu)，基于該字典結(jié)構(gòu)，對最大匹配算法進行改進，提出了一種基于雙字Hash與List相結(jié)合的分詞算法.

1 基于雙字Hash和List的三層組合詞典結(jié)構(gòu)

詞典是中文分詞的基礎，分詞詞典機制設計的優(yōu)劣直接影響到中文分詞的速度和效率[9-10].如前所述，對交通信息的分詞有較特殊需求，因此其分詞詞典機制也具有一定的特殊性.

1.1 詞庫的設計

針對交通信息的特點，構(gòu)建詳細的交通信息專用詞庫，包括事件庫，地址庫，方向庫，附屬定位詞庫.地址庫包含某一特定區(qū)域中所有地理實體的名稱.如道路名、橋梁名及POI點名等；方向庫包含交通信息中各種表達的方向信息，如南北雙向、北向東、由南向北和以東等；事件庫包含交通信息中狀態(tài)信息的各種描述，如車多、交通管制和擁堵等；附屬定位詞庫包含不能獨立進行定位、與地址庫中的詞匯結(jié)合使用以及指向最終定位地址的詞匯，如東口、南側(cè)路等.每個詞庫記錄長度都具有一定的分布規(guī)律，以上海市為例，其中交通信息相關的地址庫記錄長度分布如表1所示.

表1 自然語言描述交通信息詞庫地址庫記錄長度分布

1.2 詞典數(shù)據(jù)結(jié)構(gòu)設計

豐富的專業(yè)詞庫保證了交通信息分詞的正確性，而合理的詞庫數(shù)據(jù)結(jié)構(gòu)保證了交通信息分詞的速度與效率.基于雙字哈希分詞詞典機制[11-12]結(jié)合基于整詞二分詞典機制[13]與基于逐字二分的詞典機制[14]兩者的優(yōu)點，在匹配的時間效率和空間效率上，達到了較好的效果.從表1可以看出：自然語言描述的實時交通信息所發(fā)生的地址具有一定的分布規(guī)律.因此，筆者從詞典數(shù)據(jù)結(jié)構(gòu)設計出發(fā)，在雙字Hash分詞詞典機制的基礎之上，充分考慮交通信息詞庫記錄長度的分布規(guī)律，設計了一種基于雙字Hash和List相結(jié)合的三層詞典數(shù)據(jù)結(jié)構(gòu).該結(jié)構(gòu)先對首字使用Hash定位，再對次字使用Hash定位，經(jīng)過兩次Hash定位后剩余字分配到List列表.各個詞庫中的內(nèi)容在程序運行時加載到內(nèi)存，以提高運行速度.其詞典的數(shù)據(jù)結(jié)構(gòu)設計如下：采用三層結(jié)構(gòu)，外層Hash表的鍵為詞條記錄中首字，其值不能重復，而對應的值為一個內(nèi)層的Hash表，內(nèi)層Hash表鍵為詞條記錄中第二個字，其值為一個List列表，該列表保存了詞條記錄剩下字串的值，并依次排列，若為空，則表示前兩個字是一個完整的詞.基于表1統(tǒng)計的詞庫分布規(guī)律，采用這種結(jié)構(gòu)，減少了與List列表的匹配次數(shù)，從而提高分詞的效率.詞典的部分記錄的數(shù)據(jù)結(jié)構(gòu)如表2所示.

表2 詞典的數(shù)據(jù)結(jié)構(gòu)

2 改進的最大匹配算法

根據(jù)面向交通信息的自然語言理解過程中的分詞算法的改進需求，對最大匹配算法進行了改進.結(jié)合上述所提出的基于雙字Hash與List相結(jié)合的詞典數(shù)據(jù)結(jié)構(gòu)，筆者改進了最大匹配算法，由傳統(tǒng)的逐字減一的方式改變?yōu)檎蛑鹱旨右坏姆绞竭M行匹配；對長句或組合句采用分治的方法，將長句或組合句劃分為多個短句，先對短句進行分詞，最后歸并其結(jié)果，從而實現(xiàn)長句或組合句的有效處理；同時，在切分過程中增加了對關鍵詞匯的詞庫歸屬性判斷，保存了根據(jù)各個詞庫切分出來的關鍵詞匯的個數(shù)與順序，使其能夠滿足基于模板規(guī)則自然語言語義理解的需求.

2.1 算法描述

改進的最大匹配算法的流程如圖1所示.具體算法描述如下.

目標：對一個句子C1C2C3…Cn，進行分詞處理.

1) 預處理階段.依次判斷C1C2C3…Cn是否為非中文漢字，如果是非中文漢字，按這些非中文字符把語句切分成多個短句，分別對這些短句進行分詞處理，轉(zhuǎn)到步驟2)；如果全是中文漢字，取句子的第一個字C1作為當前字串，轉(zhuǎn)到步驟3).

2) 取第一個短句進行分詞處，取句子的第一個字C1作為當前字串.

3) 分別在地址庫，方向庫，事件庫等的首字Hash表中查找是否存在；若都不存在，轉(zhuǎn)到步驟4)；若C1在地址庫、方向庫、事件庫等某一個庫中的首字Hash表中存在，則轉(zhuǎn)到步驟5).

4) 則切分C1，標記C1為非詞匯，從C2開始下一次分詞.

5) 判斷次字Hash表是否為空.若為空，轉(zhuǎn)到步驟6)；若不為空，轉(zhuǎn)到步驟7).

6) 則C1成詞，保存C1，記錄C1所隸屬詞庫及順序標志，取下一個字作為當前字串，轉(zhuǎn)到步驟3).

7) 取下一個字C2，在次字Hash表中查找是否存在.若不存在，轉(zhuǎn)到步驟4)；若存在，轉(zhuǎn)到步驟8).

8) 取C1C2為詞首的剩下漢字的列表.若列表為空，C1C2成詞，切分C1C2，記錄C1C2所隸屬詞庫及順序標志，一次分詞結(jié)束，取下一個字作為當前字串，轉(zhuǎn)到步驟3).若列表不為空，則二分查找C3…Ci(i≥3)是否存在列表中.若存在列表中，記錄最后成詞i值，在i處切分，一次分詞結(jié)束，保存C1…Ci，切分C1…Ci，記錄C1…Ci所隸屬詞庫及順序標志，一次分詞結(jié)束，取下一個字作為當前字串，轉(zhuǎn)到步驟3)；若不存在列表中，則直接切分C1…Ci，一次分詞結(jié)束，取下一個字作為當前字串，轉(zhuǎn)到步驟3).

9) 不斷循環(huán)取下一個短句，按步驟2)進行分詞，直到句子結(jié)束的最后一個字Cn.

然而，交通信息中可能會存在一些數(shù)字型偏移量.偏移量是動態(tài)估算的，其數(shù)值是不斷變化的，在詞庫中無法逐一列舉出來，這也給基于字符串匹配的分詞帶來了新的問題.針對這一問題，筆者算法采用數(shù)字型偏移量與字符串表示的中文進行分開處理.先按照圖1的步驟對輸入的交通信息進行分詞，然后再對輸入的交通信息中無法匹配的剩余字符串進一步的處理，從中一次性提取中數(shù)字型信息，作為數(shù)字偏移量，以此來解決數(shù)字型偏移量問題.

按照上述步驟，切分出來的關鍵詞匯包含了該詞匯的隸屬詞庫，然后以關鍵詞匯、個數(shù)和順序為條件，進行基于模板規(guī)則的自然語言理解，成功匹配的詞匯認為已達到自然語言理解目的，否則予以排除，盡而完成面向自然語言描述的交通信息的自然語言理解.

2.2 示例描述

目標：對“浙江中路以東300 m，發(fā)生一起交通事故”進行分詞為例.

1) 逐次判斷是否包含非中文字符和數(shù)字，以包含的非中文字符為界將字串分為兩個短字串，“浙江中路以東300 m南京路”和“發(fā)生一起交通事故”，分別對這兩部分短句進行分詞.

2) 取字串“浙”，作為關鍵字在地址庫，方向庫，事件庫等的首字Hash表進行匹配，在地址庫的首字Hash表中匹配成功得到以“浙”為鍵的Hash表.

3) 取字串“江”，作為關鍵字在2)中得到的Hash表中進行匹配，匹配成功，得到以“浙江”為前綴，由剩下字串組成的列表.

4) 取字串“中”，作為關鍵字在3)中得到的列表中進行二分查找，匹配失敗.

5) 取字串“中路”，作為關鍵字在3)中得到的列表中進行二分查找，匹配成功，記錄“浙江中路”.

6) 取字串“中路以”，作為關鍵字在3)中得到的列表中進行二分查找，直到短句結(jié)束，匹配失敗.

7) 保存最后匹配成功的字串“浙江中路”，切分，記錄所隸屬詞庫及順序，一次分詞結(jié)束.

8) 取成詞的下一字“以”，按步驟2)操作在地址庫，方向庫，事件庫等的首字Hash表進行匹配進行Hash匹配，依次順序進行，直到短句結(jié)束.

9) 取下一個短句，同理切分出詞“事故”，直到整個句子結(jié)束.

10) 分詞處理完成后，在無法匹配的字串中一次性提取出數(shù)字信息，將此作為數(shù)字型偏移量.

11) 最后切分出的結(jié)果：“浙江中路”是第一個地址詞，“以東”是方向詞，“交通事故”是事件詞，“300米”是數(shù)字型偏移量.

3 實驗結(jié)果

基于上述算法設計，使用Java平臺來實現(xiàn)交通信息分詞測試.實驗數(shù)據(jù)來源于上海出行網(wǎng)發(fā)布的實時交通信息，共計400條，如圖2所示.測試環(huán)境操作系統(tǒng)：win7系統(tǒng)，處理器：IntelI5，內(nèi)存：4 G.采用Oracle 10 g數(shù)據(jù)庫管理系統(tǒng)完成所有數(shù)據(jù)的管理工作.

圖2 自然語言描述的實時交通信息

實時交通信息是對交通狀況的即時反映，具有很強的時效性，因此，實時交通信息的分詞對指導公眾實時出行和智能導航具有重要意義.分別采用跨階分詞算法和筆者算法對400條實時交通信息實驗數(shù)據(jù)進行中文分詞，排除無關的通用詞條記錄，筆者分詞算法將專業(yè)交通信息詞庫加載到內(nèi)存，以提高運行效率.由表3可以看出：筆者算法和跨階分詞算法理解成功率均為98%，容錯性也完全相同.筆者算法在分詞匹配時，由于采用的兩層的Hash結(jié)構(gòu)，每次都將查詢固定在一定的范圍內(nèi)，所以其分詞的效率較高.同時，跨階分詞算法對長句或組合句沒有進行有效處理.實驗結(jié)果表明：筆者的算法對于長句或組合句的分詞成功率為96%.實際應用表明：筆者算法執(zhí)行簡單，不需要詞法、句法及語義等知識的支持，數(shù)據(jù)結(jié)構(gòu)也較為簡單，較符合實時交通信息分詞應用需求.

表3 分詞性能分析

4 結(jié) 論

自然語言表達的交通信息的中文分詞，具有一定的特殊性.通過對基于詞典的中文分詞算法進行研究，并充分考慮專用詞庫中詞條記錄的長度分布特點，提出了一種基于雙字Hash與List結(jié)合的詞典機制的改進的最大匹配算法，在切分過程中增加了對關鍵詞匯的詞庫歸屬性判斷，保存了根據(jù)各個詞庫切分出來的關鍵詞匯的個數(shù)與順序，使其能夠有效地為面向交通信息的自然語義理解提供技術支持，提高了自然語言表達的交通信息分詞效率.并且，對于長句或組合多句表達的交通信息，也能夠很好地進行處理，經(jīng)測試取得了較好的效果.由于未登錄詞的識別難度較大，容易造成錯分、誤分的情況，因此，如何進一步提高未登錄詞的辨識度也是后續(xù)自然語言描述的交通信息分詞研究的關鍵.另外，對算法的容錯性需要進一步提高，使其能在更加復雜的組合句描述的交通信息處理上取得更好的效果.

參考文獻：

[1] 陸鋒，劉煥煥，陳傳彬．一種中文自然語言表達交通信息的跨階分詞算法[J]．武漢大學學報：信息科學版，2009，34(8)：943-947．

[2] 陳傳彬，陸鋒，勵惠國，等．自然語言表達實時路況信息的路網(wǎng)匹配融合技術[J]．中國圖象圖形學報，2009，14(8)：1669-1676．

[3] 王秋．淺析自然語言理解及其應用[D]．西安：陜西師范大學，2008．

[4] 陳周娟，續(xù)海峰，鈕王杰．基于靜態(tài)知識庫的領域內(nèi)自然語言理解的語義處理研究[J]．機床與液壓，2007，35(7)：37-39．

[5] 張黎，徐蔚然．中文分詞研究[J]．軟件，2012，33(12)：103-108．

[6] 黃昌寧，趙海．中文分詞十年回顧[J]．中文信息學報，2007，21(3)：8-19．

[7] 龍樹全，趙正文，唐華．中文分詞算法概述[J]．電腦知識與技術，2009，5(10)：2605-2607．

[8] 邵星星．基于Lucene的中文分詞技術研究[D]．西安：西安電子科技大學，2012．

[9] 張林曼，吳升．地理編碼系統(tǒng)中地名地址分詞算法研究[J]．測繪科學，2010，35(2)：46-48．

[10] 郭瞳康．基于詞典的中文分詞技術研究[D]．哈爾濱：哈爾濱理工大學，2010．

[11] 楊安生．二次Hash+二分最大匹配快速分詞算法[J]．情報探索，2009(8)：90-92．

[12] 李慶虎，陳玉健，孫家廣．一種中文分詞詞典新機制——雙字哈希機制[J]．中文信息學報，2003，17(4)：13-18．

[13] 葉繼平，張桂珠．中文分詞詞典結(jié)構(gòu)的研究與改進[J]．計算機工程與應用，2012，48(23)：139-142．

[14] 譚駿珊，吳惠雄．一種改進整詞二分法的中文分詞詞典設計[J]．信息技術，2009(5)：40-42．