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

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

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

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

(1.武漢工程大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，武漢 430205； 2.智能機(jī)器人湖北省重點(diǎn)實(shí)驗(yàn)室(武漢工程大學(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)用。針對(duì)此問(wèn)題，提出一種非規(guī)范中文地址的行政區(qū)劃提取算法。首先,對(duì)原始數(shù)據(jù)進(jìn)行“路”特征詞分組預(yù)處理；再利用行政區(qū)劃字典和移動(dòng)窗口最大匹配算法，從中文地址中提取所有可能的行政區(qū)劃數(shù)據(jù)集；然后，利用中文地址行政區(qū)劃元素之間具有層次關(guān)系的特點(diǎn)，建立行政區(qū)劃條件集合運(yùn)算規(guī)則，對(duì)獲取的數(shù)據(jù)集進(jìn)行集合運(yùn)算；再利用行政區(qū)劃匹配度建立一種行政區(qū)劃集合解析規(guī)則，來(lái)計(jì)算行政區(qū)劃可信度;最后，得到可信度最大信息量最完整的中文地址的行政區(qū)劃。利用從互聯(lián)網(wǎng)中提取的約25萬(wàn)條中文地址數(shù)據(jù)進(jìn)行是否采用“路”特征詞分組處理以及是否進(jìn)行可信度計(jì)算處理,對(duì)算法的可用性進(jìn)行了驗(yàn)證，并與目前的地址匹配技術(shù)進(jìn)行對(duì)比，準(zhǔn)確率達(dá)到93.51%。

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

0 引言

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

目前常見(jiàn)的中文分詞算法主要分為三類(lèi)[4]：基于詞庫(kù)的分詞算法、基于統(tǒng)計(jì)的分詞算法、基于理解的分詞算法。

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

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

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

1 相關(guān)工作

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

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

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

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

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

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

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

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

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

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

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

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

2.1.1 一般的集合運(yùn)算

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

1)2個(gè)行政區(qū)劃的交集運(yùn)算。

若有2個(gè)行政區(qū)劃D1={d11,d12,d13,d14,d15}和D2={d21,d22,d23,d24,d25}，則行政區(qū)劃的交為各級(jí)行政區(qū)劃元素的交，記為：DI，用式(1)表示。2個(gè)行政區(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)系，即除了省級(jí)區(qū)劃外，其他各級(jí)區(qū)劃都屬于1個(gè)或n個(gè)上級(jí)行政區(qū)劃，所以行政區(qū)劃交集運(yùn)算時(shí)先計(jì)算省級(jí)行政區(qū)化元素的交，再計(jì)算非省級(jí)區(qū)劃元素的交。

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

(2)

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

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

(3)

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

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

(4)

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

(5)

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

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

(6)

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

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

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

2)1個(gè)行政區(qū)劃集合的交集運(yùn)算。

一個(gè)行政區(qū)劃集合DS=(D1,D2,…,Dm)，并且D1,D2,…,Dm的省級(jí)區(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)多個(gè)行政區(qū)劃集合的交集運(yùn)算。

多個(gè)行政區(qū)劃集合的交為多個(gè)行政區(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 條件集合運(yùn)算

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

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

(9)

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

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

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

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

(10)

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

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

通過(guò)可信度比較規(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 “路”特征詞分組

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

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

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

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

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

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

輸入：原始中文地址；

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

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

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

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

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

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

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

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

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

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

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

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

3 實(shí)驗(yàn)設(shè)計(jì)與分析

3.1 實(shí)驗(yàn)設(shè)計(jì)

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

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

給定一個(gè)中文地址，該地址沒(méi)有其他參考信息，如郵編、電話(huà)區(qū)號(hào)等。

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

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

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

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

3.2 實(shí)驗(yàn)分析

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

3.2.1 “路”特征詞分組處理

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

根據(jù)上述實(shí)驗(yàn)數(shù)據(jù)，從兩個(gè)方面進(jìn)行分析，首先從選擇完全區(qū)劃匹配以及選擇完全+部分行政區(qū)劃匹配方面分析。在正確率方面，由表3可以看出，對(duì)原始數(shù)據(jù)，選擇完全區(qū)劃匹配的正確率高于選擇完全+部分區(qū)劃匹配，是因?yàn)橥耆?部分查詢(xún)匹配是可以對(duì)關(guān)鍵字進(jìn)行匹配，例如“南京鼓樓區(qū)上海路”，直接進(jìn)行完全+部分查詢(xún)匹配，會(huì)將“上?！逼ヅ涑伞吧虾Ｊ小保瑢⒁孕姓^(qū)劃命名的道路匹配成行政區(qū)劃，導(dǎo)致結(jié)果錯(cuò)誤，從而降低正確率。在時(shí)間消耗方面，選擇完全區(qū)劃匹配查詢(xún)的時(shí)效要遠(yuǎn)高于選擇完全+部分區(qū)劃匹配，是由于完全+部分匹配查詢(xún)對(duì)關(guān)鍵字匹配，查詢(xún)次數(shù)比選擇完全匹配查詢(xún)次數(shù)多，導(dǎo)致消耗的時(shí)間多。

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

表3 “路”特征詞分組對(duì)比

3.2.2 可信度計(jì)算

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

表4 可信度對(duì)比

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

3.2.3 算法對(duì)比

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

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

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

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

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

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

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

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

4 結(jié)語(yǔ)

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

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

)

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

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

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

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

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

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

[7] 徐娟,曹曄,張奇.面向自由文本的中文地址規(guī)范化[J].計(jì)算機(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].計(jì)算機(jī)工程,2004,30(23):50-52.(CHENXQ,CHIZX,JINN.Applicationandstudyofcitygeocodingsystem[J].ComputerEngineering, 2004, 30(23): 50-52.)

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

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

[11] 孫存群,周順平,楊林.基于分級(jí)地名庫(kù)的中文地理編碼[J].計(jì)算機(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ó)年,李伯秋,等.基于規(guī)則的中文地址要素解析方法[J].地球信息科學(xué)學(xué)報(bào),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] 段艷會(huì),李曉林,黃爽.基于條件隨機(jī)場(chǎng)的中文地址行政區(qū)劃提取方法[J].武漢工程大學(xué)學(xué)報(bào),2015,37(11):47-51.(DUANYH,LIXL,HUANGS.ExtractionofadministrativedivisionofChineseaddressbasedonconditionalrandomfields[J].JournalofWuhanInstituteofTechnology, 2015, 37(11): 47-51.)

[17] 馬照亭,李志剛,孫偉,等.一種基于地址分詞的自動(dòng)地理編碼算法[J].測(cè)繪通報(bào),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。

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

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

1001- 9081(2017)03- 0876- 07

10.11772/j.issn.1001- 9081.2017.03.876

TP391.1

A