非規范化中文地址的行政區劃提取算法

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

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

非規范化中文地址的行政區劃提取算法

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

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

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

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

0 引言

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

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

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

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

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

1 相關工作

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

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

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

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

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

2 非規范中文地址行政區劃提取算法

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

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

表1 行政區劃交運算示例

表1中D1和D2分別表示2個行政區劃。期望是指根據給出2個行政區劃的各個元素值推理出的一個合理行政區劃。可以看出示例2中，當兩個行政區劃中其中一個行政區劃缺失2級行政區時，交集運算得到的結果不是所期望的結果，期望的結果是D=D1∩D2={江蘇省，南京市，鼓樓區}。

根據以上的行政區劃一般的交集算法無法得出期望的結果，因此需要有一個能夠適應行政區劃交集運算方法使計算結果達到期望的行政區劃。為解決這個問題，本文在一般的集合運算的基礎上提出一種條件集合運算。

2.1 行政區劃集合運算

2.1.1 一般的集合運算

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

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

若有2個行政區劃D1={d11,d12,d13,d14,d15}和D2={d21,d22,d23,d24,d25}，則行政區劃的交為各級行政區劃元素的交，記為：DI，用式(1)表示。2個行政區劃元素的交記為：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)

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

①省級行政區劃元素的交。

(2)

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

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

(3)

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

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

(4)

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

(5)

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

②非省級區劃元素的交。

(6)

當區劃元素相等時，則交的結果為區劃元素；

當區劃元素不相等，且區劃元素都不為空，則結果為空；

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

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

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

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

(7)

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

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

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

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

(8)

2.1.2 條件集合運算

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

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

(9)

2.2 行政區劃可信度

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

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

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

(10)

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

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

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

2.3 “路”特征詞分組

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

2.4 非規范中文地址行政區劃提取算法

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

圖1 非規范中文地址的行政區劃提取算法流程

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

非規范中文地址的行政區劃提取算法步驟如下：

輸入：原始中文地址；

輸出：完整的行政區劃地址。

步驟1 讀入行政區劃表。

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

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

步驟4 判斷行政區劃集合個數，分為以下三種情況：

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

若DS是一個集合，則轉到步驟5。

若DS是多個行政區劃集合，則轉到步驟6。

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

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

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

步驟8 輸出行政區劃結果。

3 實驗設計與分析

3.1 實驗設計

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

準備一個行政區劃字典，該字典是規范的表達。

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

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

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

表2 行政區劃可信度

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

3.2 實驗分析

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

3.2.1 “路”特征詞分組處理

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

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

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

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

3.2.2 可信度計算

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

表4 可信度對比

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

3.2.3 算法對比

通過分析中文地址解析在各種算法中的應用，將采用基于分級地名庫的中文地理編碼[11]、基于分詞的地址匹配技術[12]、基于規則的中文地址要素解析方法[14]與本文算法進行對比。基于分級地名庫的中文地理編碼是通過TRIE樹詞典對地址要素字段創建索引,地址匹配的過程就是在每個級別的TRIE索引樹中查詢最大地址要素的過程。基于分詞的地址匹配技術是建立地址要素詞庫，采用基于“正向最大匹配分詞”的地址分詞算法對中文地址進行切分。基于規則的中文地址要素解析方法通過系統分析地址要素的構詞特征和句法模式，構建了各類地址要素的特征字庫，提出中文地址數字表達方法，設計了基于規則的中文地址要素解析方法。本文從解析的正確率與效率對四種算法進行了比較，算法對比表如表5。

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

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

由于用來實驗的中文地址數據來源于互聯網，大部分是特征字模糊、順序混亂的非規范地址。根據實驗結果可以看出基于規則的中文地址要素解析方法與基于分詞的地址匹配技術的正確率相差不大，原因是基于分詞的地址匹配技術是基于地址要素的詞典進行切分，而基于規則的地址要素解析方法是基于特征字庫設計的規則與算法，它們全部要求地址是完全匹配才能匹配準確，只對規范的特征字明顯的中文地址有作用，對非規范的中文地址解析的正確率不高。基于分級地名庫的地址匹配算法雖然可以同時進行模糊匹配和完全匹配，但是最終的匹配結果可能有多個，無法對最后得出的集合進行計算得出確定的地址，需要人工選擇準確的地址。本文算法不僅可以能夠對非規范的地址匹配查詢出完整的行政區劃集合，且當返回結果有多個時，可以利用集合運算計算出最準確的地址，增加了正確率。在效率方面，由于基于分級地名庫的地址匹配算法、基于分詞的地址匹配技術和本文算法都是利用中文地址具有層次結構特征構建的層級式詞典進行查詢匹配，所以效率高。通過實驗對比，可以看出，本文算法在正確率上具有極大優勢，且具有高效率，證明了本算法的有效性。

3.2.4 數據分析

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

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

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

4 結語

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

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

)

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

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

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

[4] 于光.中文分詞系統的設計與實現[D].成都:電子科技大學,2012:73.(YUG.DesignandimplementationofChinesewordsegmentationsystem[D].Chengdu:UniversityofElectronicScienceandTechnologyofChina, 2012: 73.)

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

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

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

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

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

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

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

[12] 孫亞夫,陳文斌.基于分詞的地址匹配技術[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] 程昌秀,于濱.一種基于規則的模糊中文地址分詞匹配方法[J].地理與地理信息科學,2011,27(3):26-29.(CHENGCX,YUB.Arule-basedsegmentingandmatchingmethodforfuzzyChineseaddresses[J].GeographyandGeo-InformationScience, 2011, 27(3): 26-29.)

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

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

[16] 段艷會,李曉林,黃爽.基于條件隨機場的中文地址行政區劃提取方法[J].武漢工程大學學報,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。

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

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

1001- 9081(2017)03- 0876- 07

10.11772/j.issn.1001- 9081.2017.03.876

TP391.1

A