,,

(浙江工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，浙江 杭州 310023)

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

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

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

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

1.1 詞庫(kù)的設(shè)計(jì)

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

表1 自然語(yǔ)言描述交通信息詞庫(kù)地址庫(kù)記錄長(zhǎng)度分布

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

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

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

2 改進(jìn)的最大匹配算法

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

2.1 算法描述

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

目標(biāo)：對(duì)一個(gè)句子C1C2C3…Cn，進(jìn)行分詞處理.

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

2) 取第一個(gè)短句進(jìn)行分詞處，取句子的第一個(gè)字C1作為當(dāng)前字串.

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

4) 則切分C1，標(biāo)記C1為非詞匯，從C2開(kāi)始下一次分詞.

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

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

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

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

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

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

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

2.2 示例描述

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖2 自然語(yǔ)言描述的實(shí)時(shí)交通信息

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

表3 分詞性能分析

4 結(jié) 論

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

參考文獻(xiàn)：

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

[2] 陳傳彬，陸鋒，勵(lì)惠國(guó)，等．自然語(yǔ)言表達(dá)實(shí)時(shí)路況信息的路網(wǎng)匹配融合技術(shù)[J]．中國(guó)圖象圖形學(xué)報(bào)，2009，14(8)：1669-1676．

[3] 王秋．淺析自然語(yǔ)言理解及其應(yīng)用[D]．西安：陜西師范大學(xué)，2008．

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

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

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

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

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

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

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

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

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

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

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