李曉林，黃 爽，盧 濤，李 霖

(1.武漢工程大學(xué) 計算機科學(xué)與工程學(xué)院，武漢 430205； 2.智能機器人湖北省重點實驗室(武漢工程大學(xué))，武漢 430205； 3.武漢大學(xué) 資源與環(huán)境科學(xué)學(xué)院，武漢 430079) (*通信作者電子郵箱13986287758@163.com)

非規(guī)范化中文地址的行政區(qū)劃提取算法

李曉林1,2，黃 爽1,2*，盧 濤1,2，李 霖3

(1.武漢工程大學(xué) 計算機科學(xué)與工程學(xué)院，武漢 430205； 2.智能機器人湖北省重點實驗室(武漢工程大學(xué))，武漢 430205； 3.武漢大學(xué) 資源與環(huán)境科學(xué)學(xué)院，武漢 430079) (*通信作者電子郵箱13986287758@163.com)

由于互聯(lián)網(wǎng)上中文地址的非規(guī)范化表達(dá)，導(dǎo)致互聯(lián)網(wǎng)中的中文地址信息在地理位置服務(wù)中難以直接應(yīng)用。針對此問題，提出一種非規(guī)范中文地址的行政區(qū)劃提取算法。首先,對原始數(shù)據(jù)進行“路”特征詞分組預(yù)處理；再利用行政區(qū)劃字典和移動窗口最大匹配算法，從中文地址中提取所有可能的行政區(qū)劃數(shù)據(jù)集；然后，利用中文地址行政區(qū)劃元素之間具有層次關(guān)系的特點，建立行政區(qū)劃條件集合運算規(guī)則，對獲取的數(shù)據(jù)集進行集合運算；再利用行政區(qū)劃匹配度建立一種行政區(qū)劃集合解析規(guī)則，來計算行政區(qū)劃可信度;最后，得到可信度最大信息量最完整的中文地址的行政區(qū)劃。利用從互聯(lián)網(wǎng)中提取的約25萬條中文地址數(shù)據(jù)進行是否采用“路”特征詞分組處理以及是否進行可信度計算處理,對算法的可用性進行了驗證，并與目前的地址匹配技術(shù)進行對比，準(zhǔn)確率達(dá)到93.51%。

集合運算；行政區(qū)劃；中文地址；移動窗口；匹配度；解析規(guī)則

0 引言

自然語言處理(Natural Language Processing, NLP)是人工智能領(lǐng)域的一個重要組成部分，它能實現(xiàn)人與計算機之間用自然語言進行有效通信的各種理論和方法[1]。隨著互聯(lián)網(wǎng)技術(shù)的飛速發(fā)展，網(wǎng)絡(luò)上的信息量更是大得驚人，漢語是世界上使用人數(shù)最多的一門語言，那么中文信息處理自然也是NLP的重要分支，而中文分詞又是中文信息處理的基礎(chǔ)，是中文信息處理的第一步，只有做好中文分詞，后面對信息處理的步驟才會精確，因此高效準(zhǔn)確的中文分詞意義重大。就自然語言處理這方面來說，西方由于其語言的天然便利性等因素，其處理發(fā)展得比較好，形成了不少成熟的技術(shù)[2]，但是這些理論與方法常常都不能直接作用于漢語之上，原因是漢語自身的語言結(jié)構(gòu)和西文差別較大，漢語不像其他外文如英語，沒有天然的詞匯分隔符，所以要對中文信息進行處理就必須首先完成中文分詞[3]。

目前常見的中文分詞算法主要分為三類[4]：基于詞庫的分詞算法、基于統(tǒng)計的分詞算法、基于理解的分詞算法。

在基于互聯(lián)網(wǎng)位置服務(wù)的領(lǐng)域中，中文分詞也發(fā)揮了極大的作用?；诨ヂ?lián)網(wǎng)位置服務(wù)是即時定位的位置服務(wù)，實時為用戶提供準(zhǔn)確的地理位置信息，實現(xiàn)各種與位置相關(guān)的業(yè)務(wù)。在基于互聯(lián)網(wǎng)位置服務(wù)中，地理位置可以有多種表達(dá)形式，中文文本表達(dá)是其中之一，用戶可以通過中文地址信息獲取他們所需的精確地址，更好地提高服務(wù)質(zhì)量。隨著地理信息系統(tǒng)在人們生活中的作用越來越重要，對于根據(jù)中文文本地址信息快速、準(zhǔn)確查找其地理坐標(biāo)的需求日益明顯[5]。地址匹配技術(shù)能夠在地理編碼庫中比對出相應(yīng)的地理坐標(biāo)，滿足人們的需求。在地址匹配方面，采用分詞的地址匹配技術(shù)，可以解決大多數(shù)非空間坐標(biāo)地址的匹配問題。地址分詞是地址匹配的基礎(chǔ)，直接影響地址匹配的準(zhǔn)確性，地址分詞就是根據(jù)輸入地址字符串、地址詞典、地址模型，將地址切分轉(zhuǎn)換為計算機能夠理解的、結(jié)構(gòu)化的詞組。西文地址分解可以按照空格、標(biāo)點等進行單詞分割，中文地址分詞需要借助地名語料庫(地址詞典)和中文分詞算法進行中文地址分詞。

一個規(guī)范的中文地址應(yīng)包含完整的行政區(qū)劃，并按照行政區(qū)劃(省/市/縣/鄉(xiāng)/村)、路街、牌號、建筑、戶室的次序來表達(dá)[6]，特征字明顯，利用中文地址分詞算法好切分，從而可以準(zhǔn)確地與該地址的地理位置對應(yīng)。然而，在互聯(lián)網(wǎng)上，中文地址經(jīng)常用非規(guī)范行政區(qū)劃方式來描述，表述混亂與模糊，難以確定該地址所表達(dá)的地理位置，作為位置服務(wù)是無效的[7]，因此，普通的中文地址分詞算法無法很好地解決非規(guī)范的中文地址問題，需要在中文地址分詞算法上研究一種優(yōu)化的中文地址解析算法來解析非規(guī)范的中文地址。中文地址中與行政區(qū)劃相關(guān)的不規(guī)范的表達(dá)方式有：省略行政區(qū)劃特征詞、省略部分行政區(qū)劃、無行政區(qū)劃、行政區(qū)劃信息層次雜亂。此外，地址的非行政區(qū)劃部分存在與行政區(qū)劃同名的情況，主要表現(xiàn)在：路街的名稱常用行政區(qū)劃名稱命名、建筑(或企業(yè))名稱中包含行政區(qū)劃名稱、地名與行政區(qū)劃同名等。在互聯(lián)網(wǎng)中紛雜的非規(guī)范信息中，辨別出相對于用戶需要的信任度比較高的信息，在當(dāng)今地理信息位置服務(wù)方面變得十分必要[8]。

因此，本文提出一種非規(guī)范中文地址的行政區(qū)劃提取算法，對數(shù)據(jù)進行“路”特征詞分組預(yù)處理，并根據(jù)中文地址具有層級關(guān)系的特點建立了條件集合運算規(guī)則，對通過移動窗口最大匹配算法中的提取的行政區(qū)劃集合進行集合運算，并利用行政區(qū)劃匹配度建立一種行政區(qū)劃集合解析規(guī)則，計算行政區(qū)劃可信度，從非規(guī)范的中文地址中提取出最完整準(zhǔn)確的行政區(qū)劃，可以有效地提高地址數(shù)據(jù)查找的速度和準(zhǔn)確性，從而提高網(wǎng)絡(luò)地圖在線服務(wù)質(zhì)量，為用戶更好的定位。

1 相關(guān)工作

根據(jù)地址匹配算法的特征分類，迄今為止現(xiàn)有的中文地址匹配算法主要有三類[9]：

1)以地址要素層級模型為核心的地址匹配算法。此類算法以地址具有級別屬性的特點來構(gòu)建模型，這類算法的匹配率依賴于地址表述的規(guī)范性。文獻[10]地址要素識別機制的地名地址分詞算法,提出基于地址要素識別機制的地名地址分詞算法，采用最大正向匹配算法，增加了基于地址要素的識別機制，提高了地址分詞的準(zhǔn)確度，但匹配速率卻下降了。文獻[11]基于分級地名庫的層級結(jié)構(gòu)，按照地址要素的等級進行迭代處理，匹配過程是逐級匹配。

2)以全文檢索模型為核心的地址匹配算法。此類算法是將地址庫作為文本庫，將待匹配的地址作為檢索條件，這類算法只考慮關(guān)鍵詞匹配，匹配速率高，但是準(zhǔn)確率不高。文獻[12]建立了地址要素詞庫，利用正向最大匹配算法進行地址分詞。文獻[13]通過建立存儲標(biāo)準(zhǔn)地址數(shù)據(jù)集的標(biāo)準(zhǔn)地址庫和自定義的地址匹配規(guī)則庫，提出了一種基于規(guī)則的模糊中文地址分詞匹配方法，但是對于大規(guī)模或大范圍的地名地址數(shù)據(jù)，該算法不僅查找的速度慢，而且沒有顧及地址的語義信息，導(dǎo)致查找的準(zhǔn)確性較低，查找結(jié)果多樣且往往不是用戶所需要的結(jié)果。

3)以正則表達(dá)式匹配為核心的地址匹配算法。此類算法是以特征字為分界線使用正則表達(dá)式匹配的方法在地址庫中進行查找，這類算法匹配速度慢，匹配率高，但準(zhǔn)確率低。文獻[14]通過系統(tǒng)分析地址要素的構(gòu)詞特征和句法模式，構(gòu)建了各類地址要素的特征字庫，提出了中文地址的數(shù)字表達(dá)方法，設(shè)計了基于規(guī)則的中文地址要素解析方法。但是部分解析規(guī)則存在沖突現(xiàn)象，導(dǎo)致部分信息無法正確解析，且對于不具備特征字的地址要素，只能解析出部分信息。文獻[15]在中文地址編碼研究中采用分段、組合、優(yōu)先規(guī)則，對中文地址進行分段匹配，這些規(guī)則雖然減少了地址要素匹配次數(shù)，但是由于采用數(shù)據(jù)庫查詢的方式，算法總體匹配速率不高。

但這些算法大部分依賴于中文地址規(guī)范性、特征字以及地址詞典，對規(guī)范的中文地址能夠取得不錯的成效，但對于非規(guī)范中文地址，成效不佳，因此為解決上述依賴規(guī)范中文地址、匹配速率、匹配準(zhǔn)確度問題，同作者的文獻[16]，提出基于條件隨機場的中文地址行政區(qū)劃提取方法。該方法根據(jù)中文地址中行政區(qū)劃的表達(dá)特點和特征，采用判別式概率模型，在觀測序列已知的基礎(chǔ)上對目標(biāo)序列建模，通過構(gòu)建語料訓(xùn)練集和建立相應(yīng)的特征模板，得到行政區(qū)劃的表達(dá)模型。對非規(guī)范中文地址的行政區(qū)劃提取取得一定效果，但是此方法依賴于訓(xùn)練語料，需要進行人工標(biāo)注，是有監(jiān)督學(xué)習(xí)方法，因此在此研究基礎(chǔ)上，本文提出一種非規(guī)范中文地址的行政區(qū)劃提取算法，運用“路”特征詞分組、行政區(qū)劃集合運算以及可信度計算等方法，對原地址數(shù)據(jù)進行處理運算，避免人工預(yù)處理，提高了整個算法的運算速率，并且也提高了地址匹配的準(zhǔn)確率。

2 非規(guī)范中文地址行政區(qū)劃提取算法

互聯(lián)網(wǎng)上的地址信息紛繁復(fù)雜，且由于人為書寫原因以及各方面別的原因造成中文地址信息錯誤或者遺漏，所以本文先利用移動窗口匹配算法匹配行政區(qū)劃得出所有可能行政區(qū)劃結(jié)果集，再進行可信度計算得出可信度最大的中文地址，那么如何從匹配到的所有可能的行政區(qū)劃集合中提取準(zhǔn)確的中文地址信息是要解決的問題。一般是運用集合的交集運算對行政區(qū)劃集合中的行政區(qū)劃進行計算，來提取準(zhǔn)確的行政區(qū)劃結(jié)果。一般的交集運算是指按照行政區(qū)劃中每一級行政區(qū)劃所對應(yīng)的行政區(qū)劃元素是否相等，如果相等則取行政區(qū)劃元素的值，如果不等，則該行政區(qū)劃元素交的結(jié)果為空，但是在兩個行政區(qū)劃進行交集運算時，不能簡單地按照各級元素是否相等來確定行政區(qū)劃相交的結(jié)果，否則行政區(qū)劃交運算的結(jié)果不是期望的結(jié)果。例如表1(3級行政區(qū)劃，省、市、縣)。

中文地址中的一個行政區(qū)劃是一組有序的行政區(qū)劃元素組成，行政區(qū)劃元素是指中文地址中的詞可以與行政區(qū)劃字典成功匹配出一個或多個行政區(qū)劃的詞。行政區(qū)劃包含有省、市、縣、鄉(xiāng)、村5級，可表示為：行政區(qū)劃={省,市,縣,鄉(xiāng),村}，用D表示行政區(qū)劃，di(i=1,2,3,4,5)表示行政區(qū)劃中的每個元素，則行政區(qū)劃D表示為：D={d1,d2,d3,d4,d5}。

表1 行政區(qū)劃交運算示例

表1中D1和D2分別表示2個行政區(qū)劃。期望是指根據(jù)給出2個行政區(qū)劃的各個元素值推理出的一個合理行政區(qū)劃?？梢钥闯鍪纠?中，當(dāng)兩個行政區(qū)劃中其中一個行政區(qū)劃缺失2級行政區(qū)時，交集運算得到的結(jié)果不是所期望的結(jié)果，期望的結(jié)果是D=D1∩D2={江蘇省，南京市，鼓樓區(qū)}。

根據(jù)以上的行政區(qū)劃一般的交集算法無法得出期望的結(jié)果，因此需要有一個能夠適應(yīng)行政區(qū)劃交集運算方法使計算結(jié)果達(dá)到期望的行政區(qū)劃。為解決這個問題，本文在一般的集合運算的基礎(chǔ)上提出一種條件集合運算。

2.1 行政區(qū)劃集合運算

2.1.1 一般的集合運算

常見的行政區(qū)劃區(qū)劃集合運算是以下幾種：

1)2個行政區(qū)劃的交集運算。

若有2個行政區(qū)劃D1={d11,d12,d13,d14,d15}和D2={d21,d22,d23,d24,d25}，則行政區(qū)劃的交為各級行政區(qū)劃元素的交，記為：DI，用式(1)表示。2個行政區(qū)劃元素的交記為：dIi(i=1,2,3,4,5)。

DI(D1,D2)=D1∩D2={d11,d12,d13,d14,d15}∩ {d21,d22,d23,d24,d25}={dI1,dI2,dI3,dI4,dI5}

(1)

由于行政區(qū)劃元素之間存在包含關(guān)系，即除了省級區(qū)劃外，其他各級區(qū)劃都屬于1個或n個上級行政區(qū)劃，所以行政區(qū)劃交集運算時先計算省級行政區(qū)化元素的交，再計算非省級區(qū)劃元素的交。

①省級行政區(qū)劃元素的交。

(2)

其中：∧為與運算符，∨為或運算符。省級區(qū)劃元素交的結(jié)果為ρ時，ρ表示不確定，即2個行政區(qū)劃中存在一個行政區(qū)劃的省級區(qū)劃元素為空?。此時需要對省級區(qū)劃元素為空的行政區(qū)劃利用行政區(qū)劃字典查詢得到省級區(qū)劃元素非空的行政區(qū)劃。

假設(shè)，兩個相交的行政區(qū)劃D1和D2中，其中一個行政區(qū)劃Di(i=1,2)中的省級區(qū)劃元素di1(i=1,2)為空，即di1=?,?dik≠?(i=1,2,k=2,3，…,5)，選取一個區(qū)劃元素dik，此行政區(qū)劃元素dik是此行政區(qū)劃元素中等級最小的一個，用式(3)表示：

(3)

則用行政區(qū)劃字典查詢dik得到m個包含行政區(qū)劃元素dik的行政區(qū)劃的集合：

query(dik)=DS(dik)={Di1,Di2,…,Dim}= {{di11,di12,…,di1k},{di21,di22,…,di2k},…, {dim1,dim2,…,dimk}}；i=1,2

(4)

此時兩個行政區(qū)劃D1和D2省級區(qū)劃元素交的計算應(yīng)為省級行政區(qū)劃元素為空的行政區(qū)劃求得集合DS(dik)中每一個省級行政區(qū)劃元素與另一個省級行政區(qū)劃元素不為空行政區(qū)劃的省級行政區(qū)劃元素進行依次交運算，求并集：

(5)

其中：d11=?表示D1的省級區(qū)劃元素為空，d21=?表示D2的省級區(qū)劃元素為空。

②非省級區(qū)劃元素的交。

(6)

當(dāng)區(qū)劃元素相等時，則交的結(jié)果為區(qū)劃元素；

當(dāng)區(qū)劃元素不相等，且區(qū)劃元素都不為空，則結(jié)果為空；

當(dāng)區(qū)劃元素不相等，且區(qū)劃元素有一個為空時，如果存在非空的交父元素(?dIj≠?)，結(jié)果為非空區(qū)劃元素值。

2)1個行政區(qū)劃集合的交集運算。

一個行政區(qū)劃集合DS=(D1,D2,…,Dm)，并且D1,D2,…,Dm的省級區(qū)劃元素都不為空，則行政區(qū)劃集合DS的交集為D1,D2,…,Dm相交，記為DI(D1,D2,…,Dm)，用式(7)表示：

DI(D1,D2,…,Dm)=∩DS=∩(D1,D2,…,Dm)=D1∩D2∩…∩Dm

(7)

其中：∩DS表示集合DS里面的元素相交。

3)多個行政區(qū)劃集合的交集運算。

多個行政區(qū)劃集合的交為多個行政區(qū)劃集合分別兩兩相交結(jié)果的交，記為DSI，用式(8)表示：

DSI=(DS1,DS2,…,DSn)={{DS1∩DS2},{DS1∩DS3},…,{DS1∩DSn},{DS2∩DS3},…,{DS2∩DSn},…,{DSn-1∩DSn}}

(8)

2.1.2 條件集合運算

由于中文地址的混亂和無序性，會有多個集合運算中行政區(qū)劃得出的結(jié)果集沒有任何關(guān)聯(lián)的可能，導(dǎo)致集合運算的結(jié)果為空集。如果式(8)中多個行政區(qū)劃集合的交集運算結(jié)果為空，即DSI(DS1,DS2,…,DSn)=?，則會造成地址的行政區(qū)劃信息的丟失。為了避免行政區(qū)劃信息的丟失，本文提出一種條件集合運算。

當(dāng)DSI(DS1,DS2,…,DSn)=?時，將行政區(qū)劃的交運算變成并運算，即DSI(DS1,DS2,…,DSn)→DSU(DS1,DS2,…,DSn)，用式(9)表示：

(9)

2.2 行政區(qū)劃可信度

當(dāng)集合運算的結(jié)果依然是一個集合時，為提取出這個集合中最正確最完整并與原中文地址最為匹配的行政區(qū)劃，本文提出行政區(qū)劃可信度計算。行政區(qū)劃可信度是根據(jù)移動窗口算法中完全匹配與部分匹配規(guī)則與行政區(qū)劃的層次關(guān)系建立一個規(guī)則，計算集合中每個行政區(qū)劃的可信度，選取可信度最大的行政區(qū)劃作為最終提取結(jié)果。

完全匹配就是將中文地址中的行政區(qū)劃字符串與得出的行政區(qū)劃集合中的行政區(qū)劃進行匹配，每個字符都全部匹配。部分匹配是指中文地址中的行政區(qū)字符串與得出的行政區(qū)劃集合中的行政區(qū)劃進行匹配，只能匹配出除去“省”“市”“區(qū)”“縣”“鄉(xiāng)”“村”特征詞外的部分。

完全匹配度用a表示，部分匹配度用p表示，完全匹配的概率大于部分匹配的概率，且均為正數(shù)，即0

(10)

1)行政區(qū)劃中全部是完全匹配的行政區(qū)劃的可信度最大；全部是部分匹配的行政區(qū)劃可信度最小；

2)兩個行政區(qū)劃中級數(shù)大的是完全匹配的行政區(qū)劃可信度大；

通過可信度比較規(guī)則，可得出a,p,x的關(guān)系為x>a/p，由于完全匹配是指字符串全部匹配，不妨設(shè)完全匹配概率為1，部分匹配概率為0.6，即a=1，p=0.6，則x>5/3，取x=2。

2.3 “路”特征詞分組

由于中文地址中路街名稱大量使用行政區(qū)劃的名稱來命名，比如“洪山園路，“洪山”是“洪山區(qū)”的簡稱，在對行政區(qū)劃進行移動窗口匹配時容易把街道匹配成行政區(qū)劃，從而對下一步可信度計算造成干擾。為了提高行政區(qū)劃的準(zhǔn)確率，本文對地址中的路街名稱過濾。路街名稱的一般命名規(guī)則是“名稱+路街特征詞”。常用的特征詞有“路”“街”“大街”“道”“大道”等。地址中的行政區(qū)劃一般位于路街名稱的前面，將中文地址以路街特征為參照分組，取第一個分組。然后截取第一個分組前半部分作為計算地址行政區(qū)劃的地址字符串，匹配行政區(qū)劃元素詞。

2.4 非規(guī)范中文地址行政區(qū)劃提取算法

對于輸入的中文地址，本算法先對原數(shù)據(jù)進行“路”特征詞分組預(yù)處理，再根據(jù)基于移動窗口算法的地址匹配對地址進行匹配，返回中文地址中所有可能的行政區(qū)劃結(jié)果集，然后進行集合運算，最后對集合運算出的結(jié)果進行可信度計算，解析出可信度最大的中文地址的行政區(qū)劃。非規(guī)范中文地址的行政區(qū)劃提取算法的流程如圖1。

圖1 非規(guī)范中文地址的行政區(qū)劃提取算法流程

基于移動窗口匹配算法的地址匹配方法，首先建立用于行政區(qū)劃匹配字典，然后根據(jù)地址數(shù)據(jù)表達(dá)的語義特點，建立行政區(qū)劃的匹配規(guī)則，將字符串中的字符比作一個可滑動的滑動窗口對行政區(qū)劃表進行匹配查詢，返回對應(yīng)的行政區(qū)劃結(jié)果集，包含與該行政區(qū)劃匹配父行政區(qū)劃，直到省級，從而得到所有可能的行政區(qū)劃。

非規(guī)范中文地址的行政區(qū)劃提取算法步驟如下：

輸入：原始中文地址；

輸出：完整的行政區(qū)劃地址。

步驟1 讀入行政區(qū)劃表。

步驟2 對原始數(shù)據(jù)進行“路”詞分組預(yù)處理，取第一個分組，若0個匹配，則置結(jié)果為空，直接輸出。

步驟3 利用移動窗口算法對行政區(qū)劃表進行匹配查詢，根據(jù)分組后地址中文地址中包含的行政區(qū)劃元素詞匹配出這個地址字符串所包含的可能行政區(qū)劃結(jié)果集DS。

步驟4 判斷行政區(qū)劃集合個數(shù)，分為以下三種情況：

若DS僅僅是一個行政區(qū)劃，則直接輸出。

若DS是一個集合，則轉(zhuǎn)到步驟5。

若DS是多個行政區(qū)劃集合，則轉(zhuǎn)到步驟6。

步驟5 利用式(1)～(7)進行1個行政區(qū)劃集合的交集運算得到DI，轉(zhuǎn)到步驟7。

步驟6 利用式(8)進行多個行政區(qū)劃集合的交集運算得到DSI，當(dāng)DSI=?時，利用式(9)進行多個行政區(qū)劃結(jié)合的條件交集運算得到新的DSI。

步驟7 利用式(10)對集合運算的結(jié)果進行可信度計算，選擇可信度大的行政區(qū)劃。

步驟8 輸出行政區(qū)劃結(jié)果。

3 實驗設(shè)計與分析

3.1 實驗設(shè)計

為了驗證本算法的有效性，本文做了以下準(zhǔn)備工作：

準(zhǔn)備一個行政區(qū)劃字典，該字典是規(guī)范的表達(dá)。

給定一個中文地址，該地址沒有其他參考信息，如郵編、電話區(qū)號等。

以地址“福州鼓樓洪山園路”為例，該地址存在以下幾方面問題：1)該地址的行政區(qū)劃部分不完整且沒有規(guī)律；2)該地址中的地址要素殘缺，無法推出完整地址；3)該地址不是按照省、市、縣的規(guī)則形成的，無法使用一般的中文地址匹配方法進行匹配；4)該地址的路名中包含行政區(qū)劃名稱。由此可見，該地址存在要素殘缺和語義模糊等問題，具有代表性。

首先對該地址進行“路”特征詞分組得到“福州鼓樓”，在通過移動窗口匹配查詢得到所有可能的行政區(qū)劃集合，然后進行集合運算，再進行利用可信度公式進行可信度計算，提取出可信度最大的行政區(qū)劃，集合運算結(jié)果及可信度如表2。

表2 行政區(qū)劃可信度

可以看出，“福建省，福州市，鼓樓區(qū)”的可信度最大，因此選取此地址作為行政區(qū)劃結(jié)果。

3.2 實驗分析

本文利用網(wǎng)絡(luò)爬蟲從互聯(lián)網(wǎng)上提取約25萬條地址數(shù)據(jù)進行中文地址行政區(qū)劃匹配實驗。從三個方面驗證實驗：1)通過對本文算法的數(shù)據(jù)的預(yù)處理過程，比較不同處理方法對實驗結(jié)果的影響，從而選取最佳方案。2)通過加入可信度計算，比較加入可信度對實驗結(jié)果的影響。3)通過對比分析不同的算法來驗證本文算法的有效性。

3.2.1 “路”特征詞分組處理

本文實驗對于中文地址的預(yù)處理計算分為直接地址處理和“路”特征詞分組地址處理2種。直接地址是將原始地址作為計算的字符串直接用于匹配計算。分組地址是依據(jù)中文地址中行政區(qū)劃表示的特點選取路街前面的地址部分進行“路”特征分組處理后作為行政區(qū)劃匹配計算的字符串。本文將直接地址、分組地址與完全匹配查詢(F)、完全匹配查詢+部分匹配查詢(P)進行組合，進行實驗，實驗結(jié)果如表3。

根據(jù)上述實驗數(shù)據(jù)，從兩個方面進行分析，首先從選擇完全區(qū)劃匹配以及選擇完全+部分行政區(qū)劃匹配方面分析。在正確率方面，由表3可以看出，對原始數(shù)據(jù)，選擇完全區(qū)劃匹配的正確率高于選擇完全+部分區(qū)劃匹配，是因為完全+部分查詢匹配是可以對關(guān)鍵字進行匹配，例如“南京鼓樓區(qū)上海路”，直接進行完全+部分查詢匹配，會將“上海”匹配成“上海市”，將以行政區(qū)劃命名的道路匹配成行政區(qū)劃，導(dǎo)致結(jié)果錯誤，從而降低正確率。在時間消耗方面，選擇完全區(qū)劃匹配查詢的時效要遠(yuǎn)高于選擇完全+部分區(qū)劃匹配，是由于完全+部分匹配查詢對關(guān)鍵字匹配，查詢次數(shù)比選擇完全匹配查詢次數(shù)多，導(dǎo)致消耗的時間多。

從選擇“路”特征詞分組處理以及不選擇“路”特征詞分組處理方面分析，由表3可以看出，采用完全行政區(qū)劃匹配方法時正確率和時效不受“路”特征詞分組處理的影響基本維持不變，因為行政區(qū)劃完全匹配方法已經(jīng)把所有用行政區(qū)劃命名的路街全都過濾掉了，但對于一些中文地址中行政區(qū)劃區(qū)劃省略了特征詞“省市縣”的也過濾了。所以，無論是否對原始地址進行“路”特征詞分組，對計算結(jié)果沒有太大的影響。而選擇完全匹配查詢+部分匹配查詢測試的地址字符串進行“路”特征詞分組處理后正確率有明顯的提升，大約提升了20%，達(dá)到93.51%，是因為省略了地址中的道路、街道等，匹配時只需要匹配行政區(qū)劃，避免了將道路、街道名匹配成行政區(qū)劃，所以時效和正確率都有明顯的提升，但是有些以“道”“街”等特征詞命名的行政區(qū)劃經(jīng)過“路”特征詞分組處理后也被過濾掉了，導(dǎo)致解析正確率無法到達(dá)100%。

表3 “路”特征詞分組對比

3.2.2 可信度計算

由于行政區(qū)劃集合運算得到的結(jié)果有可能是集合形式，無法得到確切的行政區(qū)劃，本節(jié)實驗從兩個方面進行:一方面選擇最后求得的集合中最大非空行政區(qū)劃元素作為計算結(jié)果，一方面對集合運算的結(jié)果作可信度計算，選擇可信度最大的行政區(qū)劃，實驗結(jié)果如表4。

表4 可信度對比

由表4可以看出，在正確率方面，選擇完全區(qū)劃匹配查詢時，對數(shù)據(jù)進行“路”特征詞分組處理與不進行處理后，選擇最大非空區(qū)劃元素或者選擇可信度最大的行政區(qū)劃元素作為結(jié)果的正確率并沒有發(fā)生變化，因為完全區(qū)劃匹配就是對行政區(qū)中的最大元素進行匹配，所以選擇可信度最大的或者選擇最大非空行政區(qū)劃元素得到的結(jié)果相同，因此對結(jié)果無影響;同時可以看出，選擇完全+部分區(qū)劃匹配查詢，對結(jié)果進行可信度處理的正確率是要高于選擇最大非空行政區(qū)劃元素處理的正確率，對原始數(shù)據(jù)而言，由于完全+部分匹配查詢是對關(guān)鍵字進行匹配查詢，會匹配出干擾行政區(qū)劃，比如“上海路”會匹配成“上海市”，對結(jié)果的選擇造成影響，而選擇可信度最大的行政區(qū)劃作為結(jié)果是對完全匹配以及部分匹配以及行政區(qū)劃層次結(jié)構(gòu)等因素進行考慮后得出的結(jié)果，所以得出的結(jié)果正確率高于單純選擇最大行政區(qū)劃的結(jié)果，并且選擇“路”特征詞分組處理+完全+部分匹配查詢+可信度處理，能夠使正確率提高到93.51%，是由于“路”特征詞分組處理省略了地址中的道路、街道等，匹配時只需要匹配行政區(qū)劃，避免了將道路、街道名匹配成行政區(qū)劃。時間消耗是受完全匹配查詢或者完全+部分匹配查詢以及是否進行“路”特征詞分組的影響，上一節(jié)已進行分析。

3.2.3 算法對比

通過分析中文地址解析在各種算法中的應(yīng)用，將采用基于分級地名庫的中文地理編碼[11]、基于分詞的地址匹配技術(shù)[12]、基于規(guī)則的中文地址要素解析方法[14]與本文算法進行對比?；诜旨壍孛麕斓闹形牡乩砭幋a是通過TRIE樹詞典對地址要素字段創(chuàng)建索引,地址匹配的過程就是在每個級別的TRIE索引樹中查詢最大地址要素的過程?；诜衷~的地址匹配技術(shù)是建立地址要素詞庫，采用基于“正向最大匹配分詞”的地址分詞算法對中文地址進行切分?；谝?guī)則的中文地址要素解析方法通過系統(tǒng)分析地址要素的構(gòu)詞特征和句法模式，構(gòu)建了各類地址要素的特征字庫，提出中文地址數(shù)字表達(dá)方法，設(shè)計了基于規(guī)則的中文地址要素解析方法。本文從解析的正確率與效率對四種算法進行了比較，算法對比表如表5。

表5 不同算法的處理效率與正確率比較

表5 不同算法的處理效率與正確率比較

由于用來實驗的中文地址數(shù)據(jù)來源于互聯(lián)網(wǎng)，大部分是特征字模糊、順序混亂的非規(guī)范地址。根據(jù)實驗結(jié)果可以看出基于規(guī)則的中文地址要素解析方法與基于分詞的地址匹配技術(shù)的正確率相差不大，原因是基于分詞的地址匹配技術(shù)是基于地址要素的詞典進行切分，而基于規(guī)則的地址要素解析方法是基于特征字庫設(shè)計的規(guī)則與算法，它們?nèi)恳蟮刂肥峭耆ヅ洳拍芷ヅ錅?zhǔn)確，只對規(guī)范的特征字明顯的中文地址有作用，對非規(guī)范的中文地址解析的正確率不高?；诜旨壍孛麕斓牡刂菲ヅ渌惴m然可以同時進行模糊匹配和完全匹配，但是最終的匹配結(jié)果可能有多個，無法對最后得出的集合進行計算得出確定的地址，需要人工選擇準(zhǔn)確的地址。本文算法不僅可以能夠?qū)Ψ且?guī)范的地址匹配查詢出完整的行政區(qū)劃集合，且當(dāng)返回結(jié)果有多個時，可以利用集合運算計算出最準(zhǔn)確的地址，增加了正確率。在效率方面，由于基于分級地名庫的地址匹配算法、基于分詞的地址匹配技術(shù)和本文算法都是利用中文地址具有層次結(jié)構(gòu)特征構(gòu)建的層級式詞典進行查詢匹配，所以效率高。通過實驗對比，可以看出，本文算法在正確率上具有極大優(yōu)勢，且具有高效率，證明了本算法的有效性。

3.2.4 數(shù)據(jù)分析

根據(jù)上述“路”特征詞分組處理實驗，以及算法對比分析實驗，可以看出，在中文地址行政區(qū)劃解析方面，影響中文地址解析效率的方面有以下三點：“路”特征詞、尾特征詞、詞典結(jié)構(gòu)以及可信度計算。

在時效上，影響速率的第一個因素是“路”特征詞。根據(jù)本文在對原始地址進行“路”特征詞處理的實驗中，由表3可以看出將地址進行了“路”特征詞處理之后，解析速度明顯提高，因為對地址進行“路”特征詞處理后，過濾掉了地址中的道路、街道等信息，只對行政區(qū)劃進行解析，大幅度提高了中文地址行政區(qū)劃的解析速率。而在本文方法與基于分級地名庫的中文地理編碼、基于分詞的地址匹配技術(shù)以及基于規(guī)則的中文地址要素解析方法的對比實驗中可以看出，影響速率的第二個因素是詞典結(jié)構(gòu)，在本文方法與其他三個算法的對比實驗中，利用中文地址的層次結(jié)構(gòu)特征，對有從屬關(guān)系的地址建立逐級的父子關(guān)系，從而建立起層級式詞典，減少了查詢次數(shù)，加快了地址的查詢匹配速率。

在正確率上，第一個影響因素是“路”特征詞。在表3中，雖然進行“路”特征詞分組處理后，由于省略了道路、街道等信息，去掉了干擾項，正確率有一定提升，但是由于一些行政區(qū)劃是以“路”特征詞命名，導(dǎo)致有用信息被省略，從而導(dǎo)致正確率無法達(dá)到100%。第二個影響因素是尾特征詞。同樣在表3中可以看出，進行完全匹配查詢+部分匹配查詢的正確率高于只采用完全匹配查詢，由于實驗數(shù)據(jù)來源于互聯(lián)網(wǎng)，大多數(shù)是非規(guī)范的中文地址，很多地址缺乏關(guān)鍵字，而完全匹配查詢是依賴于中文地址的規(guī)范性，依賴于關(guān)鍵字全部匹配，而部分匹配查詢，可以有效避免缺乏尾特征詞的非規(guī)范地址匹配不上，因此增大了正確率。而在表5中，同樣可以看出依賴于尾特征詞的基于規(guī)則的中文地址要素解析方法正確率較低，對非規(guī)范中文地址的解析準(zhǔn)確率不高。第三個因素是可信度計算，從表4可以看出，在行政區(qū)劃集合運算得出的結(jié)果是一個集合時，選擇可信度大的計算結(jié)果的正確率比選擇最大非空行政區(qū)劃元素的結(jié)果正確率高。

4 結(jié)語

在目前無法用一般分詞匹配算法匹配出正確的行政區(qū)劃的情況下，本文提出了一種非規(guī)范中文地址的行政區(qū)劃提取算法，本算法利用基于移動窗口算法的地址匹配算法，并顧及中文地址的語義，根據(jù)中文地址的表達(dá)特點，建立行政區(qū)劃集合運算規(guī)則和可信度計算規(guī)則，提高了對中文地址行政區(qū)劃解析的正確率和時效。本算法提出了一種對中文地址數(shù)據(jù)進行預(yù)處理的方法——“路”特征詞分組處理，能夠過濾掉干擾中文地址行政區(qū)劃解析的路街信息，使中文地址行政區(qū)劃解析的效率得到很大的提高。本算法還提出的行政區(qū)劃條件集合運算和可信度計算，能夠便捷地處理多個行政區(qū)劃集合并解析出最完整、最準(zhǔn)確的行政區(qū)劃信息，不造成地址信息丟失，本算法不依賴于地址來源，對非規(guī)范的中文地址也能進行行政區(qū)劃信息的提取，在性能上具有明顯的優(yōu)越性，因此，本算法在地理位置服務(wù)中具有實用性。

但是該算法還有一定的缺陷，在進行“路”特征詞分組處理時，由于中文地址中有一部分行政區(qū)劃以“道”“路”等特征詞命名，如“哈爾濱道里區(qū)”，按照“路”特征詞分組后會將“道里區(qū)”過濾掉，導(dǎo)致解析結(jié)果錯誤。還有中文地址中一些鄉(xiāng)鎮(zhèn)的名稱與行政區(qū)劃名稱相同也會產(chǎn)生錯誤的結(jié)果，因此在未來的工作中，將處理更加復(fù)雜的、辨別度不高的非規(guī)范中文地址，改進算法，從而設(shè)計出適應(yīng)各種不同類型地址的算法。

)

[1] 李生.自然語言處理的研究與發(fā)展[J].燕山大學(xué)學(xué)報,2013,37(5):377-384.(LIS.Researchanddevelopmentofnaturallanguageprocessing[J].JournalofYanshanUniversity, 2013, 37(5): 377-384.)

[2] 呂雅娟,趙鐵軍,楊沐昀,等.基于分解與動態(tài)規(guī)劃策略的漢語未登錄詞識別[J].中文信息學(xué)報,2001,15(1):28-33.(LYUYJ,ZHAOTJ,YANGMJ,etal.LeveledunknownChinesewordsresolutionbydynamicprograming[J].JournalofChineseInformationProcessing, 2001, 15(1): 28-33.)

[3] 李慶虎,陳玉健,孫家廣.一種中文分詞詞典新機制——雙字哈希機制[J].中文信息學(xué)報,2003,17(4):13-18.(LIQH,CHENYJ,SUNJG.AnewdictionarymechanismforChinesewordsegmentation[J].JournalofChineseInformationProcessing, 2003, 17(4): 13-18.)

[4] 于光.中文分詞系統(tǒng)的設(shè)計與實現(xiàn)[D].成都:電子科技大學(xué),2012:73.(YUG.DesignandimplementationofChinesewordsegmentationsystem[D].Chengdu:UniversityofElectronicScienceandTechnologyofChina, 2012: 73.)

[5] 郭會,宋關(guān)福,馬柳青,等.地理編碼系統(tǒng)設(shè)計與實現(xiàn)[J].計算機工程,2009,35(1):250-252.(GUOH,SONGGF,MALQ,etal.Designandimplementationofaddressgeocodingsystem[J].ComputerEngineering, 2009, 35(1): 250-252.)

[6] 郭文龍.基于SNM算法的大數(shù)據(jù)量中文地址清洗方法[J].計算機工程與應(yīng)用,2014,50(5):108-111.(GUOWL.CleaningapproachtolargeamountsofChineseaddressbasedonSNMalgorithm[J].ComputerEngineeringandApplications, 2014, 50(5): 108-111.)

[7] 徐娟,曹曄,張奇.面向自由文本的中文地址規(guī)范化[J].計算機應(yīng)用與軟件,2015,32(8):22-24.(XUJ,CAOY,ZHANGQ.Chineseaddressstandardisationforplaintext[J].ComputerApplicationsandSoftware, 2015, 32(8): 22-24.)

[8] 陳細(xì)謙,遲忠先,金妮.城市地理編碼系統(tǒng)應(yīng)用與研究[J].計算機工程,2004,30(23):50-52.(CHENXQ,CHIZX,JINN.Applicationandstudyofcitygeocodingsystem[J].ComputerEngineering, 2004, 30(23): 50-52.)

[9] 宋子輝.自然語言理解的中文地址匹配算法[J].遙感學(xué)報,2013,17(4):788-801.(SONGZH.AddressmatchingalgorithmbasedonChinesenaturallanguageunderstanding[J].JournalofRemoteSensing, 2013, 17(4): 788-801.)

[10] 趙陽陽,王亮,仇阿根.地址要素識別機制的地名地址分詞算法[J].測繪科學(xué),2013,38(5):74-76.(ZHAOYY,WANGL,QIUAG.Animprovedalgorithmforaddresssegmentation[J].ScienceofSurveyingandMapping, 2013, 38(5): 74-76.)

[11] 孫存群,周順平,楊林.基于分級地名庫的中文地理編碼[J].計算機應(yīng)用,2010,30(7):1953-1955.(SUNCQ,ZHOUSP,YANGL.Chinesegeo-codingbasedonclassificationdatabaseofgeographicalnames[J].JournalofComputerApplications, 2010, 30(7): 1953-1955.)

[12] 孫亞夫,陳文斌.基于分詞的地址匹配技術(shù)[EB/OL]. [2016- 01- 05].http://xueshu.baidu.com/s?wd=paperuri%3A%284105a7e9cf9ea8588730d99199975503%29&filter=sc_long_sign&tn=SE_xueshusource_2kduw22v&sc_vurl=http%3A%2F%2Fcpfd.cnki.com.cn%2FArticle%2FCPFDTOTAL-DLXX200711001019.htm&ie=utf-8&sc_us=16495669320387933132.(SUNYF,CHENWB.Addressmatchingtechnologybasedonsegmentation[EB/OL]. [2016- 01- 05].http://xueshu.baidu.com/s?wd=paperuri%3A%284105a7e9cf9ea8588730d99199975503%29&filter=sc_long_sign&tn=SE_xueshusource_2kduw22v&sc_vurl=http%3A%2F%2Fcpfd.cnki.com.cn%2FArticle%2FCPFDTOTAL-DLXX200711001019.htm&ie=utf-8&sc_us=16495669320387933132.)

[13] 程昌秀,于濱.一種基于規(guī)則的模糊中文地址分詞匹配方法[J].地理與地理信息科學(xué),2011,27(3):26-29.(CHENGCX,YUB.Arule-basedsegmentingandmatchingmethodforfuzzyChineseaddresses[J].GeographyandGeo-InformationScience, 2011, 27(3): 26-29.)

[14] 張雪英,閭國年,李伯秋,等.基于規(guī)則的中文地址要素解析方法[J].地球信息科學(xué)學(xué)報,2010,12(1):9-16.(ZHANGXY,LYUGN,LIBQ,etal.Rule-basedapproachtosemanticresolutionofChineseaddresses[J].JournalofGeo-InformationScience, 2010, 12(1): 9-16.)

[15] 唐靜.城市地名地址的編碼匹配研究[D].昆明：昆明理工大學(xué),2011:76.(TANGJ.Studyoncitynamesaddressmatchestheencoding[D].Kunming:KunmingUniversityofScienceandTechnology, 2011: 76.)

[16] 段艷會,李曉林,黃爽.基于條件隨機場的中文地址行政區(qū)劃提取方法[J].武漢工程大學(xué)學(xué)報,2015,37(11):47-51.(DUANYH,LIXL,HUANGS.ExtractionofadministrativedivisionofChineseaddressbasedonconditionalrandomfields[J].JournalofWuhanInstituteofTechnology, 2015, 37(11): 47-51.)

[17] 馬照亭,李志剛,孫偉,等.一種基于地址分詞的自動地理編碼算法[J].測繪通報,2011(2):59-62.(MAZT,LIZG,SUNW,etal.Anautomaticgeocodingalgorithmbasedonaddresssegmentation[J].BulletinofSurveyingandMapping, 2011(2): 59-62.)

[18]GUOH,ZHUH,GUOZ,etal.Addressstandardizationwithlatentsemanticassociation[C]//Proceedingsofthe15thACMSIGKDDInternationalConferenceonKnowledgeDiscoveryandDataMining.NewYork:ACM, 2009: 1155-1164.

[19]COLDBERGDW,WILSONJP,KNOBLOCKCA.Fromtexttogeographiccoordinates:thecurrentstateofgeocoding[J].UrbanandRegionalInformationSystemsAssociation, 2007, 19(1): 33-46.

ThisworkispartiallysupportedbySpecialPlanofSurveyingandMappingGeographicInformationPublicWelfareScientificResearchSpecialIndustry(201412014),theNationalHighTechnologyResearchandDevelopmentProgram(863Program) (2013AA12A202),theNaturalScienceFoundationofHubeiProvince(2013CFA125),the7thGraduateStudentInnovationFundProjectsofWuhanInstituteofTechnology(CX2015053).

LI Xiaolin, born in 1962, M. S., associate professor. His research interests include data mining, machine learning, artificial intelligence.

HUANG Shuang, born in 1992, M. S. candidate. Her research interests include data mining, machine learning, artificial intelligence.

LU Tao, born in 1980, Ph. D., associate professor. His research interests include image/visual processing, computer vision, artificial intelligence.

LI Lin, born in 1960, Ph. D., professor. His research interests include geo-semantics and ontology, three-dimensional modeling and visualization.

Administrative division extracting algorithm for non-normalized Chinese addresses

LI Xiaolin1,2, HUANG Shuang1,2*, LU Tao1,2，LI Lin3

(1.SchoolofComputerScienceandEngineering,WuhanInstituteofTechnology,WuhanHubei430205,China; 2.HubeiProvincialKeyLaboratoryofIntelligentRobot(WuhanInstituteofTechnology),WuhanHubei430205,China; 3.SchoolofResourceandEnvironmentalSciences,WuhanUniversity,WuhanHubei430079,China)

Chinese addresses on the Internet are always non-normalized, which cannot be used directly in location-based services. To solve the problem, an algorithm to extract administrative divisions from non-normalized Chinese addresses was proposed. Firstly, preprocessing “road” feature word grouping for original data; using administrative division dictionary and moving window maximum matching algorithm, extract all possible administrative region data sets from Chinese address. Then, using the Chinese administrative divisions between the elements of the hierarchical relationship between the characteristics, the administrative set conditional set operation rule was established and the acquired data set was aggregated. using the administrative division of matching, a set of administrative division set rules were established to calculate the credibility of the administrative division. Finally, the credibility of the maximum amount of information the most complete Chinese address of the administrative divisions were obtained. By using the extracted from the Internet about 250 000 Chinese address data whether the use of “road” feature word packet processing and whether to carry on the credibility calculation process was verified for the availability of the algorithm, and with the current address matching technology for comparison, the accuracy rate of 93.51%.

set operation; administrative division; Chinese address; moving window; matching degree; analytical rule

2016- 08- 26;

2016- 10- 18。

測繪地理信息公益性行業(yè)科研專項(201412014)；國家863計劃項目(2013AA12A202);湖北省自然科學(xué)基金資助項目(2013CFA125);武漢工程大學(xué)第七屆研究生創(chuàng)新基金資助項目(CX2015053)。

李曉林(1962—)，男，湖北孝感人，副教授，碩士，主要研究方向：數(shù)據(jù)挖掘、機器學(xué)習(xí)、人工智能； 黃爽(1992—)，女，湖北武漢人，碩士研究生，主要研究方向：數(shù)據(jù)挖掘、機器學(xué)習(xí)、人工智能； 盧濤(1980—)，男，湖北武漢人，副教授，博士，主要研究方向：圖像/視覺處理、計算機視覺、人工智能； 李霖(1960—)，男，湖北孝感人，教授，博士生導(dǎo)師，博士，主要研究方向：地理語義及本體、三維建模及可視化。

1001- 9081(2017)03- 0876- 07

10.11772/j.issn.1001- 9081.2017.03.876

TP391.1

A