徐嘉康，張 晨，王柳靜，張貴軍

(浙江工業(yè)大學(xué) 信息工程學(xué)院，杭州 310023)

1 引 言

地址匹配是將待匹配的地址文本與對(duì)應(yīng)的地理坐標(biāo)及標(biāo)準(zhǔn)地址進(jìn)行匹配的過程，是地理編碼的核心部分，也是現(xiàn)代物流配送[1]、交通運(yùn)輸[2，3]中的重要環(huán)節(jié)之一.標(biāo)準(zhǔn)地址模型、搜索文本等諸多因素均會(huì)對(duì)中文地址匹配結(jié)果產(chǎn)生影響，使得此類問題的求解更為困難.隨著信息技術(shù)與計(jì)算機(jī)技術(shù)的快速發(fā)展，各行各業(yè)不同類型的地址不斷產(chǎn)生，當(dāng)前大多數(shù)中文地址匹配方法都是通過非結(jié)構(gòu)化、非空間化、非標(biāo)準(zhǔn)化且缺乏空間坐標(biāo)信息的地址直接匹配地理編碼數(shù)據(jù)庫(kù)，往往需要大量的分詞訓(xùn)練且造成算法對(duì)特定格式地址庫(kù)的依賴，導(dǎo)致算法在匹配信息不完整的情況下得到的結(jié)果不精確.因此，在重新構(gòu)建地址匹配模型的基礎(chǔ)上進(jìn)行地址匹配算法的再設(shè)計(jì)有著重要的現(xiàn)實(shí)意義.

隨著地理信息技術(shù)、計(jì)算機(jī)技術(shù)的發(fā)展，文本匹配技術(shù)越來越受到國(guó)內(nèi)外學(xué)者的重視，并進(jìn)行了許多富有意義的研究工作.Wang Xiaoli使用了基于文本序列距離的K最近鄰方法獲得最相似匹配序列[4]；Manish Patil使用編輯距離作為衡量標(biāo)準(zhǔn)提出了一種位置限制對(duì)齊方法[5]，提高了相似文本匹配效率.Qin Tian針對(duì)較為復(fù)雜的中文地址字符匹配問題，在優(yōu)化地址建模、地址標(biāo)準(zhǔn)化的基礎(chǔ)上，提出了一種中文地址分詞匹配方法[6]，在中文地址匹配中取得了良好的效果；Waterman提出的基于動(dòng)態(tài)規(guī)劃思想的局部序列匹配方法在生物信息領(lǐng)域中得到了廣泛應(yīng)用[7]，提高了序列匹配的精度與效率；Amihood Amir提出一種模板近似匹配方法，有效減少了匹配項(xiàng)中出現(xiàn)局部錯(cuò)誤的情況[8]；程昌秀建立了存儲(chǔ)標(biāo)準(zhǔn)地址數(shù)據(jù)集的標(biāo)準(zhǔn)地址庫(kù)和自定義的地址匹配規(guī)則庫(kù)，提出一種基于規(guī)則的模糊中文地址編碼方法[9]，提高了模糊地址文本的匹配成功率；王斌設(shè)計(jì)了一種支持移動(dòng)編輯距離的索引結(jié)構(gòu)，借助字母出現(xiàn)的頻率權(quán)重，提出一種優(yōu)化字母查詢算法[10]，通過增強(qiáng)索引的過濾能力，提高了地址文本查詢效率.

借鑒生物信息學(xué)序列比對(duì)思想，設(shè)計(jì)動(dòng)態(tài)地址匹配模型與非均權(quán)算子，不依賴于任何特定格式的地址庫(kù)，也無需對(duì)標(biāo)準(zhǔn)庫(kù)進(jìn)行標(biāo)注，避免大量分詞訓(xùn)練過程，從而使得算法在匹配信息不完整的情況下也可以得到較為精確的匹配結(jié)果.在杭州市標(biāo)準(zhǔn)地址數(shù)據(jù)上(1∶30萬)進(jìn)行了算法驗(yàn)證，實(shí)驗(yàn)結(jié)果證明了算法的有效性.

2 中文地址匹配模型

中文地址匹配模型可以表示為：輸入地址字符串S={s0s1s2s3…sm}，m為S的長(zhǎng)度；地址庫(kù)字符串T={t0t1t2t3…tn}，n為T的長(zhǎng)度.其中sm表示輸入地址字符串S第m+1位的字符，tn同理.S與T匹配評(píng)分得到打分矩陣C，cij表示字符si與字符tj的相似性得分.本文假設(shè)輸入地址和地址庫(kù)各地址相互獨(dú)立，在滿足約束條件的情況下，最大化匹配得分.匹配問題的數(shù)學(xué)模型可以用公式(1)描述：

(1)

其中R表示根據(jù)單字在地址庫(kù)中的重要性差異生成的權(quán)重矩陣，R(si，tj)表示字符si與tj的權(quán)重匹配得分；Wk表示輸入地址字符串上k個(gè)空位的懲罰分，Wl則表示地址庫(kù)字符串l個(gè)空位的懲罰分.

3 模型求解

Smith-waterman算法是生物信息領(lǐng)域的重要算法[7]，其優(yōu)勢(shì)在于可以在給定的打分評(píng)估準(zhǔn)則下找出兩個(gè)序列的最優(yōu)比對(duì)塊，使得局部匹配成為可能.本文改進(jìn)Smith-waterman算法，在動(dòng)態(tài)打分匹配的基礎(chǔ)上引入空位罰分策略，通過地址單字檢索求權(quán)算法(Word Frequency-InverseTable Frequency，WF-ITF)構(gòu)建了置換矩陣，可以有效解決中文地址匹配問題.

3.1 空位罰分策略

動(dòng)態(tài)規(guī)劃算法使用的矩陣可以用公式(2)表示，其中cij為文本匹配過程中對(duì)應(yīng)位置字符的比對(duì)得分.本方法進(jìn)行局部匹配時(shí)需要進(jìn)行回溯最高分的操作，因此將初始打分矩陣的第1行和第1列都置0.

兩文本之間一般存在著錯(cuò)位相似的情況，空位的引入能夠很好的解決錯(cuò)位匹配的問題.但是沒有代價(jià)的空位也會(huì)導(dǎo)致算法傾向于大量使用空位來匹配兩文本中的字符，造成過

(2)

度匹配的現(xiàn)象出現(xiàn).因此空位模型會(huì)對(duì)文本匹配產(chǎn)生巨大影響.這里認(rèn)為連續(xù)的長(zhǎng)空位比分散的空位更可靠.使用空位罰分避免算法過度匹配文本，用公式(3)表示：

Wk=u(k-1)+v

(3)

其中Wk是空位的懲罰得分；k表示當(dāng)前匹配添加的空位數(shù)，k為1時(shí)就只是起始空位罰分v，當(dāng)k大于1時(shí)，會(huì)由常系數(shù)u給出額外的連續(xù)空位懲罰.

3.2 基于WF-ITF置換矩陣的字符權(quán)重

字符對(duì)匹配或錯(cuò)配的分?jǐn)?shù)用置換矩陣表示，若匹配則加分，錯(cuò)配則扣分，具體見公式(4)：

(4)

其中P表示在匹配時(shí)的得分，為正常數(shù)；N表示在錯(cuò)配時(shí)的得分，為負(fù)常數(shù).

常值置換矩陣在所有的字符匹配情況下給出的分值沒有差別，考慮到不同的字符在地址庫(kù)中的重要性差異，引入字符出現(xiàn)頻率來改進(jìn)分值.單純的字符出現(xiàn)頻率無法很好地反應(yīng)字符的重要性，因此使用TF-IDF方法來優(yōu)化字符權(quán)重[11].TF-IDF是由Jones提出的一種統(tǒng)計(jì)方法，用以評(píng)估單一字詞對(duì)于一個(gè)文件集或一個(gè)語(yǔ)料庫(kù)中的其中一份文件的重要程度.字詞的重要性隨著它在文件中出現(xiàn)的次數(shù)成正比增加，但同時(shí)會(huì)隨著它在語(yǔ)料庫(kù)中出現(xiàn)的頻率成反比降低，用公式(5)、公式(6)表示：

(5)

(6)

其中m代表指定詞語(yǔ)在單一文本中出現(xiàn)的次數(shù)；M代表文本中所有詞語(yǔ)出現(xiàn)總數(shù)；N為文本庫(kù)中文本總數(shù)；n為含有指定詞語(yǔ)的文本數(shù)量.歸一化后的傳統(tǒng)TF-IDF公式如公式(7)所示：

(7)

其中Wij代表指定詞語(yǔ)i在文本j中的重要程度權(quán)重；tfij表示詞語(yǔ)i在文本j中的出現(xiàn)頻率；N代表本文總數(shù)；ni代表存在詞語(yǔ)i的文本數(shù)量.

由于地址的長(zhǎng)度相對(duì)于通常文件來說短的多.傳統(tǒng)的歸一化TF-IDF算法無法適用于本文的單字權(quán)重計(jì)算，因此需要將TF-IDF方法進(jìn)行改造[12]，算法具體步驟如算法1所示.

算法1中N表示地址庫(kù)中地址總條數(shù)，perWordRow表示地址庫(kù)中出現(xiàn)單字w的條數(shù)，perWordSum表示單字w在地址庫(kù)中出現(xiàn)總次數(shù).itf-w和wf-w分別為單字w的頻率權(quán)重值和逆頻率權(quán)重值，由公式(8)與公式(9)得到，將兩值相乘得到單字最終權(quán)重.

(8)

(9)

得到單字權(quán)重之后，將結(jié)果更新到置換矩陣中，更新方式如公式(10)所示：

(10)

其中E為固定的縮放因子常數(shù)；res為計(jì)算得到的單字權(quán)重，N為原置換矩陣中的負(fù)常數(shù).

算法1. 地址單字檢索求權(quán)：

輸入：待統(tǒng)計(jì)的地址庫(kù)T(dn)

第n條地址信息dn

輸出：R(φn)：經(jīng)過統(tǒng)計(jì)計(jì)算地址的權(quán)重表；

φn：表中第n條的權(quán)重結(jié)果

1. initialization；

2.whileaddress-unvisited=?do

3. next-address：j←selectAdd(i)；

4.ifaddress-unvisited≠?then

5.break；

6.else

7. next-address：w← selectAdd(0，1…Len)；

8. perWordRow：w ← perWordRow+1；

9.end

10.end

11.Perform：

12. itf-w ←getItf(perWordRow，perWordSum)；

13. wf-w ←getWf(perWordRow.perWordSum)；

14.res← getRes(itf-w，wf-w)；

15.Returnres

3.3 基于動(dòng)態(tài)匹配的相似度打分

相似度計(jì)算是地址匹配過程中非常重要的環(huán)節(jié)，是提升匹配精度的重要方法.本文將連續(xù)的數(shù)字以及單個(gè)的中文字符作為字符單元，以此將地址文本轉(zhuǎn)化為離散的字符單元的順序排列，數(shù)字0-9以及字母a-z、A-Z因?yàn)楸旧硖厥庑?，使用所有單字?quán)重的均值[13，14]代替.記輸入地址文本序列為S，比對(duì)地址序列為T，相似度計(jì)算的數(shù)學(xué)表達(dá)如公式(11)所示，結(jié)合置換矩陣、空位罰分策略和打分矩陣得到：

(11)

其中si為文本序列S的第i位字符，tj為文本序列T的第j位字符.k為文本序列S插入的空位數(shù)，l為文本序列T插入的空位數(shù).

在計(jì)算矩陣C的過程中，矩陣元素Ci，j取3種計(jì)算方式得到的相似度的最大值作為該矩陣元素Ci，j的值，在序列S和序列T的空位插入會(huì)在匹配過程中出現(xiàn)，加入空位操作也會(huì)使對(duì)應(yīng)參數(shù)加一.當(dāng)完成C矩陣全部元素的計(jì)算后，遍歷矩陣找到相似度最高的點(diǎn)即為匹配結(jié)果.從最優(yōu)點(diǎn)出發(fā)往左上方回溯得到次大值即可得到最相似片段，輸入地址文本S繼續(xù)匹配，記錄匹配得分，直至完成地址庫(kù)中所有地址T的比對(duì).

3.4 排序歸一化

排序可以顯著減少結(jié)果集合的冗余，提升匹配精度.結(jié)合歸一化打分，能夠兼顧全局和局部匹配能力的提升[15].排序歸一化可以保留低分高相似地址，也能防止結(jié)果集重復(fù)冗余.

首先進(jìn)行得分歸一化.在計(jì)算出輸入地址序列S和地址庫(kù)中地址T之間的相似度k的基礎(chǔ)上，除以兩條序列較長(zhǎng)者的長(zhǎng)度，均衡長(zhǎng)短序列的分值差異，即：m=length(S)，n=length(T)，max(m，n)=g，S和T的歸一化計(jì)算公式如公式(12)所示：

(12)

i(S，T)的值代表相似得分與長(zhǎng)度的比值，歸一值越大，相似部分占序列本身的比例就越大.

在完成相似度計(jì)算與排序歸一化之后，考慮到地址匹配結(jié)果多樣性的要求，本文引入了小頂堆模型[16].小頂堆是一種特殊的樹形數(shù)據(jù)結(jié)構(gòu)，其特點(diǎn)能保證堆頂?shù)闹凳钦麄€(gè)堆中的最小值.小頂堆保證了每個(gè)節(jié)點(diǎn)的值都小于或等于左右子樹的值.每次地址匹配的結(jié)果都根據(jù)其歸一值i(S，T)，更新到小頂堆地址樹.小頂堆地址樹的容量即為需要保留的地址數(shù)量.地址樹的更新為兩個(gè)階段：地址樹容量未滿時(shí)進(jìn)行地址樹構(gòu)建操作、地址樹容量已滿時(shí)進(jìn)行地址樹更新操作，具體情況見圖1，其中字母代表地址元素，數(shù)字代表地址元素對(duì)應(yīng)歸一值.

圖1 地址樹更新Fig.1 Address tree update

地址樹構(gòu)建：當(dāng)?shù)刂窐湓匚礉M時(shí)，計(jì)算歸一值，根據(jù)小頂堆的性質(zhì)添加的合適的位置即可.

地址樹更新：當(dāng)?shù)刂窐湓匾褲M時(shí)，則對(duì)比新元素與堆頂元素歸一值的大小，若新元素值小于堆頂元素值，放棄該元素，反之則彈出堆頂元素，放入新元素.小頂堆會(huì)將新放入的元素從堆頂交換到合適的位置，保證堆頂始終是堆中的最小值.小頂堆的最小值對(duì)應(yīng)最差地址匹配結(jié)果，通過每次更新淘汰最差元素，保證了最后留在堆中的元素一定是所有匹配結(jié)果中歸一值最靠前的.

3.5 算法流程

算法的基本思想是：首先，完成打分矩陣、置換矩陣以及空位罰分策略的初始化；統(tǒng)計(jì)地址庫(kù)根據(jù)字符重要程度；其次，基于動(dòng)態(tài)規(guī)劃完成打分矩陣得到相似度，歸一化得到最后分值；最后，匹配結(jié)果更新到小頂堆，保證結(jié)果集的精度以及多樣性.算法流程見圖2.具體步驟如下：

1)參數(shù)設(shè)置(空位延長(zhǎng)單位罰分u，空位起始罰分v，單字權(quán)重縮放因子E)；

2)初始化打分矩陣C；

3)初始化空位罰分Wk；

4)初始化置換矩陣R；

5)完成地址庫(kù)字符出現(xiàn)次數(shù)統(tǒng)計(jì)，得到單字權(quán)重；

6)選中一條地址，結(jié)合單字權(quán)重，空位罰分完成打分矩陣計(jì)算，遍歷得到最高分值，歸一化之后更新到地址結(jié)果集；

7)判斷是否完成全地址庫(kù)比對(duì)，完成則輸出地址結(jié)果集，否則回到步驟6).

圖2 地址動(dòng)態(tài)匹配算法流程圖Fig.2 Address dynamic matching algorithm

4 實(shí)驗(yàn)結(jié)果與分析

地理數(shù)據(jù)集使用杭州市的矢量數(shù)據(jù)(1：30萬)，基于網(wǎng)絡(luò)連通性構(gòu)建了杭州市實(shí)際道路的路網(wǎng)模型.用以檢驗(yàn)本文算法的有效性.

完全精準(zhǔn)的地址匹配容易實(shí)現(xiàn)，但是現(xiàn)實(shí)生活經(jīng)常有人會(huì)對(duì)地址進(jìn)行錯(cuò)誤描述.本文考慮到日常語(yǔ)言使用習(xí)慣，整理了3類錯(cuò)誤類型：錯(cuò)別字，如注意力不集中導(dǎo)致的輸入錯(cuò)誤，或者認(rèn)知中對(duì)同音字和形近字的誤判；詞義轉(zhuǎn)化，意義相同，僅僅命名習(xí)慣存在區(qū)別，比如幢、棟、號(hào)、樓等等[17]；去除地址非相關(guān)信息的簡(jiǎn)寫.針對(duì)以上錯(cuò)誤建立了測(cè)試集如表1所示，地址庫(kù)中各區(qū)地址字段總數(shù)為Count，測(cè)試集地址字段總數(shù)Test為2000，對(duì)應(yīng)區(qū)域所含待匹配地址字段總數(shù)為Test×Scale，如：測(cè)試集含蕭山區(qū)地址字段總數(shù)為419.

表1 測(cè)試數(shù)據(jù)集Table 1 Test data set

4.1 算法性能分析

為了驗(yàn)證本文算法的有效性，實(shí)驗(yàn)測(cè)試平臺(tái)使用8核CPU(R7-4800H)，主頻2.9GHz，16G內(nèi)存筆記本；操作系統(tǒng)Windows10家庭版，基于Java的JDK1.8版本，進(jìn)行算法驗(yàn)證.算法代碼使用IntelliJ IDEA 2019.1編寫.算法初始化參數(shù)設(shè)置空位延長(zhǎng)單位罰分u為-1，空位起始罰分v為-1，空位初始個(gè)數(shù)k為0；單字權(quán)重初始值E為10，單字錯(cuò)配常數(shù)N為-1；小頂堆模型容量為10.

在測(cè)試集上完成算法的運(yùn)行，統(tǒng)計(jì)得到本算法在不同錯(cuò)誤類型上的表現(xiàn).具體結(jié)果如圖3所示，通過圖3看出，本算法在應(yīng)對(duì)不同錯(cuò)誤類型時(shí)表現(xiàn)出明顯差異：詞義轉(zhuǎn)換類結(jié)果最好，正確率達(dá)到了100%.錯(cuò)別字類也得到了較好的結(jié)果，平均正確率89.46%，而且效果并沒有隨著錯(cuò)別字的增加而變差，證明了本算法能夠較好的應(yīng)對(duì)錯(cuò)字.刪除非相關(guān)字符類別的錯(cuò)誤結(jié)果較差，正確率為51%，考慮到文本過度精簡(jiǎn)容易丟失關(guān)鍵信息[18]，地址庫(kù)層面的匹配難以判斷，故正確率仍在可接受的范圍內(nèi).

圖3 地址測(cè)試集多組別類型結(jié)果Fig.3 Address test set multi-group type result

為了更好的衡量算法的性能，這里將實(shí)驗(yàn)結(jié)果進(jìn)行細(xì)分統(tǒng)計(jì)，使用了召回率R、查準(zhǔn)率P以及F值作為評(píng)價(jià)指標(biāo).

假定在測(cè)試數(shù)據(jù)的分類結(jié)果中，X代表錯(cuò)誤地址的匹配結(jié)果集里存在對(duì)應(yīng)的標(biāo)準(zhǔn)地址且排名第一位為該標(biāo)準(zhǔn)地址的地址數(shù)；Y代表錯(cuò)誤地址的匹配結(jié)果集里存在對(duì)應(yīng)的標(biāo)準(zhǔn)地址但該標(biāo)準(zhǔn)地址不為排名第一位的地址數(shù)；Z代表錯(cuò)誤地址的匹配結(jié)果集里不存在對(duì)應(yīng)的標(biāo)準(zhǔn)地址的地址數(shù).具體的公式表示為：

(13)

(14)

(15)

圖4 地址測(cè)試相關(guān)統(tǒng)計(jì)結(jié)果Fig.4 Address test set multi-group type result

通過表2與圖4可以得出，在測(cè)試結(jié)果集里各錯(cuò)誤類型地址的查準(zhǔn)率表現(xiàn)均為良好，在錯(cuò)別字與詞義轉(zhuǎn)換類型上更是高達(dá)94%.召回率R可看作算法的魯棒性，可表征結(jié)果集中包含標(biāo)準(zhǔn)地址的概率，其值越大說明算法魯棒性越強(qiáng)，能給使用者提供較為合理的結(jié)果.F值綜合考慮了查準(zhǔn)率P與召回率R，數(shù)值上表現(xiàn)良好，說明該算法比較穩(wěn)定.

表2 測(cè)試數(shù)據(jù)相關(guān)統(tǒng)計(jì)參數(shù)
Table 2 Related statistical parameters of test set results

TYPEXYZ錯(cuò)別字1425018錯(cuò)別字22572246錯(cuò)別字3281020刪除非相關(guān)36898256詞義轉(zhuǎn)換20900總計(jì)1540120340

為了驗(yàn)證匹配結(jié)果的地理分布情況，根據(jù)3.4節(jié)的歸一化值i(S，T)，我們將每組測(cè)試數(shù)據(jù)中i值最大的地址作為基準(zhǔn)點(diǎn)，分別與其余次優(yōu)點(diǎn)作距離計(jì)算，求得平均置信距離.置信距離計(jì)算公式[19]具體如下：

(16)

(17)

(18)

f3=cosφ2cosφ1

(19)

其中d為各組的基準(zhǔn)點(diǎn)與次優(yōu)點(diǎn)之間的地理距離，r為地球赤道半徑，φ2為基準(zhǔn)點(diǎn)的經(jīng)度弧度，φ1為次優(yōu)點(diǎn)的經(jīng)度弧度，λ2為基準(zhǔn)點(diǎn)的緯度弧度，λ1為次優(yōu)點(diǎn)的緯度弧度.

由圖5可以看出來，置信距離小于20千米的測(cè)試案例占72%，其中置信距離小于10千米占測(cè)試案例的48%.考慮到此計(jì)算思路非計(jì)算各地址點(diǎn)的平均絕對(duì)距離而是通過確定一個(gè)基準(zhǔn)點(diǎn)算其兩者的平均相對(duì)距離.說明該算法匹配結(jié)果聚散情況良好，可滿足于實(shí)際的地理聚散程度要求.

圖5 組間平均置信距離Fig.5 Average confidence distance between groups

最后將該算法運(yùn)用于實(shí)際路網(wǎng)系中測(cè)試，從圖6中可以看出次優(yōu)地址(如圖6中圓形所示)分布在最優(yōu)地址(如圖6中五角星所示)附近，說明在滿足多樣性的要求下，匹配結(jié)果的各地址之間相距良好，說明可適用于實(shí)際模糊搜索場(chǎng)景.

圖6 匹配結(jié)果Fig.6 Result of matching

5 結(jié) 論

本文針對(duì)常見的中文地址錯(cuò)誤類型，提出了一種基于動(dòng)態(tài)規(guī)劃的地址匹配方法.參考生物信息學(xué)的序列比對(duì)思想，引入非均值權(quán)重與空位罰分策略增加了動(dòng)態(tài)匹配算法的性能，提升了匹配精度.使用排序均一化策略提升了匹配的效率，提升了結(jié)果的多樣性.最后在杭州市實(shí)際路網(wǎng)上驗(yàn)證了算法的有效性最后將算法應(yīng)用到杭州市實(shí)際中文地址匹配問題上，實(shí)驗(yàn)結(jié)果證明了本文算法是可行且有效的.