K叉樹地址的模糊匹配研究與實(shí)現(xiàn)

李新放，宋轉(zhuǎn)玲，陳學(xué)業(yè)，賀 彪，劉海行

(1. 國(guó)家海洋局第一海洋研究所，山東 青島 266061； 2. 青島海洋科學(xué)與技術(shù)國(guó)家實(shí)驗(yàn)室區(qū)域海洋動(dòng)力學(xué)與數(shù)值模擬功能實(shí)驗(yàn)室，山東 青島 266237； 3. 深圳市數(shù)字城市工程研究中心，廣東 深圳 518040)

數(shù)字城市是以空間信息為核心的城市信息系統(tǒng)體系，而在數(shù)字城市信息資源的集成和融合中，地名地址匹配是一項(xiàng)非常關(guān)鍵的技術(shù)[1]。地名地址匹配又稱為地理編碼，它是基于空間定位技術(shù)的一種編碼方式，提供一種把地名地址的地理位置信息轉(zhuǎn)換成可被用于GIS系統(tǒng)的地理坐標(biāo)方式[2]。應(yīng)用地名地址匹配技術(shù)可以地址數(shù)據(jù)為基礎(chǔ)紐帶，使分散的信息資源庫之間建立有機(jī)的聯(lián)系，實(shí)現(xiàn)不同數(shù)據(jù)類型、不同系統(tǒng)之間的互操作，滿足數(shù)據(jù)共享的要求[3-5]。

近年來，隨著地理信息技術(shù)的不斷發(fā)展和完善，地名地址匹配技術(shù)也在不斷改進(jìn)，國(guó)內(nèi)外專家進(jìn)行了很多深入的研究工作。文獻(xiàn)[6]提出了一種基于動(dòng)態(tài)生成矩陣的經(jīng)典算法解決字符串模糊匹配問題，許多研究人員基于該算法做了一系列的優(yōu)化改進(jìn)；文獻(xiàn)[7]提出了利用位向量法的BPM算法，但該方法需要的空間正比于字符集的大小，當(dāng)字符集很大時(shí)，需要很高的空間；文獻(xiàn)[8]提出了基于過濾方法和位向量法結(jié)合的模糊匹配算法，在一定程度上提高了模糊匹配的效率；馬照亭等提出了一種基于地址分詞的自動(dòng)地理編碼算法[9]；習(xí)明等提出了一種基于雙層哈希表的中文分詞優(yōu)化算法[10]；趙陽陽等提出了一種地址要素識(shí)別機(jī)制的地名地址分詞算法[11]；陳開渠等基于BPM算法和新的過濾方法，提出了BPM-BM算法，提高了字符集較大時(shí)模糊匹配的效率[12]；魏金明等利用分詞算法和置信度篩選的方法匹配數(shù)據(jù)，提出了一種基于置信度的地址匹配方法，提高了匹配的準(zhǔn)確性[13]；亢孟軍等提出了一種地址樹模型的中文地址提取方法,結(jié)合地址間拓?fù)潢P(guān)系可以從非標(biāo)準(zhǔn)地址中提取標(biāo)準(zhǔn)地址[14]。但目前快速高效準(zhǔn)確的地名地址匹配技術(shù)并不能完全滿足數(shù)字城市應(yīng)用需求，一方面沒有形成統(tǒng)一完善的標(biāo)準(zhǔn)，另一方面缺少精準(zhǔn)高效的服務(wù)，實(shí)際上已經(jīng)成為數(shù)字城市普及和推廣GIS相關(guān)應(yīng)用的瓶頸。

本文在分析中文地址特點(diǎn)及地址存放方式的基礎(chǔ)上，通過一種基于規(guī)則和統(tǒng)計(jì)組合的中文地址分詞方法實(shí)現(xiàn)分詞，并且以K叉樹的方式存儲(chǔ)構(gòu)建地址匹配模型，進(jìn)一步提高地址匹配的準(zhǔn)確度及效率。

1 中文地址分詞

中文地址分詞是地址匹配的基礎(chǔ)，本節(jié)詳細(xì)討論與中文地址分詞相關(guān)的問題，基于原始地址庫通過規(guī)則和統(tǒng)計(jì)的組合方法實(shí)現(xiàn)中文地址分詞。

1.1 中文地址定義

從GIS的角度看，一個(gè)中文地址是一個(gè)具有空間語義和地址模型結(jié)構(gòu)的連續(xù)文本字符串，可以定義如下

A= {Xi∈A|R(Xi,Xj)≠Ф，Xi≠Xj}

(1)

式中，A為一個(gè)中文地址；Xi為中文地址要素，可以被看作是指示地理實(shí)體的最小空間語義單元；R(Xi,Xj)為地址要素Xi、Xj之間的空間約束關(guān)系；Ф為空值。定義式(1)中的地址要素Xi為

Xi={WNWF|WN∈CN，WF∈CF}

(2)

式中，WN為地址實(shí)體名稱的字符串；WF為地址模型特征的字符串；CN為語料庫中的地址實(shí)體名稱集合；CF為語料庫中地址模型特征的集合。中文地址定義如圖1所示。

圖1 中文地址定義

1.2 中文地址要素采樣

中文地址中的最小語義單元是地址要素，它不僅僅是一個(gè)單詞，而是由地址實(shí)體名稱和地址模型特征共同組成的，在采樣過程中必須考慮語料庫中所有可能長(zhǎng)度的單詞，基本的遍歷采樣方式會(huì)產(chǎn)生大量具有不正確空間語義的字段，正確字段的數(shù)量與n(即地址長(zhǎng)度)成正比，不正確字段的數(shù)量與2n成比例,如圖2所示。

圖2 地址采樣過程

本文在研究中文地址命名規(guī)范和特點(diǎn)基礎(chǔ)上，基于中文地址語言模型通過新的優(yōu)化采樣方法進(jìn)行采樣，基本采樣過程如圖3所示。優(yōu)化的采樣方法基于地址中的地址要素之間存在的空間約束關(guān)系，保證被采樣的所有字段具有正確的空間語義，優(yōu)化采樣方法計(jì)算一個(gè)地址中所有字段的計(jì)算時(shí)間與n成正比，提高了分詞效率,可以采樣具有正確語義關(guān)系的地址段。

圖3 單一地址的優(yōu)化采樣模型

1.3 基于規(guī)則和統(tǒng)計(jì)的組合分詞

基于優(yōu)化的采樣模型，通過抽取語料庫中的地址計(jì)算單詞的重復(fù)地址頻率為

AF(Si|S1S2…Si-1,Corpus)=Frequency(Si|S1S2…

Si-1,Corpus)

(3)

式中，Si為地址中位置i處的字符；Corpus為地址語料庫；Frequency(Si|S1S2…Si-1,Corpus)為語料庫中字符序列“S1S2…Si-1”的重復(fù)頻率。通過字與字之間不同頻率的變化獲取中文地址不同字段的邊界，基于統(tǒng)計(jì)結(jié)果可以很明顯得出具有正確語義關(guān)系的地址要素之間的邊界，實(shí)現(xiàn)優(yōu)化的中文地址分詞,如圖4所示。

圖4 地址語料庫的AF

分詞方法主要包括以下具體步驟：①通過統(tǒng)計(jì)學(xué)方法提取詞的特征值，選取一個(gè)或多個(gè)特征值作為分詞參考；②針對(duì)每一個(gè)特征值分別設(shè)計(jì)分詞算法，根據(jù)算法對(duì)地址進(jìn)行分詞處理，得到地址分詞結(jié)果集合；③對(duì)于多個(gè)分詞結(jié)果集合的情況，設(shè)計(jì)合并算法求解最優(yōu)分詞結(jié)果；④提取分詞結(jié)果，利用地址要素完善初步分詞結(jié)果，得到最終分詞結(jié)果。

2 基于K叉樹的地址匹配

2.1 中文地址K叉樹原理

中文地址的模型特點(diǎn)決定了它具有一定的層級(jí)關(guān)系，標(biāo)準(zhǔn)地址模型的層次關(guān)系一般為：省(直轄市)—市(地級(jí)市)—區(qū)(縣、縣級(jí)市)—鎮(zhèn)(鄉(xiāng)、街道)—村(路)—門牌號(hào)。參考標(biāo)準(zhǔn)地址模型的層次關(guān)系，數(shù)字城市中中文地址樹體系的構(gòu)建過程可以表述為構(gòu)建一棵邏輯意義上層次結(jié)構(gòu)的地址樹，樹的節(jié)點(diǎn)對(duì)應(yīng)實(shí)際地理空間中的地理實(shí)體，節(jié)點(diǎn)之間的關(guān)系表述空間實(shí)體之間的關(guān)系。地址樹的上層節(jié)點(diǎn)表示城市的行政區(qū)劃單位，中層節(jié)點(diǎn)表示城市的各個(gè)功能單元，最下層節(jié)點(diǎn)具體對(duì)應(yīng)數(shù)字城市空間目標(biāo)體系中的一棟建筑等目標(biāo)點(diǎn)?；贙叉樹的特殊結(jié)構(gòu)，建立不同層次之間的節(jié)點(diǎn)關(guān)聯(lián)，抽取地址樹主干索引表優(yōu)先完成地址模型上層節(jié)點(diǎn)的搜索匹配，可以最大效率地提高搜索匹配的效率，如圖5所示。

2.2 基于原始地址分詞庫的K叉樹構(gòu)建

應(yīng)用原始地址數(shù)據(jù)經(jīng)分詞后得到的分詞庫作為基本詞典，對(duì)原始地址庫中每個(gè)地址進(jìn)行分詞建樹，將其構(gòu)建成以層次化樹形結(jié)構(gòu)存儲(chǔ)的地址樹。該樹的節(jié)點(diǎn)代表實(shí)際地址數(shù)據(jù)中具有實(shí)際地理意義的實(shí)體，節(jié)點(diǎn)的父子關(guān)系表達(dá)了地理空間實(shí)體在空間中的上下級(jí)關(guān)系(大小關(guān)系)。地址樹構(gòu)建技術(shù)方法可以快速根據(jù)分詞地址要素的約束關(guān)系自動(dòng)構(gòu)建帶有空間層次關(guān)系的地址要素結(jié)構(gòu)樹，可用于生成標(biāo)準(zhǔn)地址庫，進(jìn)而避免人為構(gòu)建標(biāo)準(zhǔn)地址庫，具有快速、準(zhǔn)確的特點(diǎn)，可服務(wù)于地址編碼技術(shù)。

圖5 空間目標(biāo)體系與K叉樹

中文地址層次結(jié)構(gòu)樹構(gòu)建技術(shù)主要包括以下步驟：①根據(jù)原始地址數(shù)據(jù)構(gòu)建初始地址樹；②將樹每層節(jié)點(diǎn)按照節(jié)點(diǎn)名稱的第一個(gè)字符的英文字母進(jìn)行升序排列；③利用正向最大字?jǐn)?shù)匹配方法提取層次節(jié)點(diǎn)共名的部分，作為新的節(jié)點(diǎn)更新樹結(jié)構(gòu)；④遍歷樹，統(tǒng)計(jì)地理實(shí)體要素之間的層次關(guān)系，生成地址要素關(guān)系表；⑤構(gòu)建地址樹節(jié)點(diǎn)名稱索引；⑥根據(jù)地址要素關(guān)系表矯正地址要素層次關(guān)系錯(cuò)誤情況；⑦處理重名節(jié)點(diǎn)之間錯(cuò)誤的上下層次關(guān)系。

2.3 搜索匹配方法

基于字典的查詢匹配規(guī)則有很多種，根據(jù)掃描方向的不同，可以分為正向匹配和逆向匹配，按照不同長(zhǎng)度優(yōu)先匹配的情況，可以分為最大最長(zhǎng)匹配和最小最短匹配。目前最常用的是最大匹配法，有正向和逆向兩種方式。由于漢語單字成詞的特點(diǎn)，最小匹配法一般很少使用。試驗(yàn)表明，逆向匹配的切分精度相對(duì)于正向匹配要略高，而且歧義現(xiàn)象也較少，本文在初步分詞基礎(chǔ)上，應(yīng)用逆向匹配方式將地址要素對(duì)應(yīng)到地址樹節(jié)點(diǎn)中，實(shí)現(xiàn)地址匹配查詢并最優(yōu)地址樹路徑。將待匹配地址與已構(gòu)建的地址樹進(jìn)行比較匹配，獲取正確的匹配節(jié)點(diǎn)，對(duì)于不存在匹配節(jié)點(diǎn)的中文地址創(chuàng)建新的樹節(jié)點(diǎn)，作為樹結(jié)構(gòu)更新參考。對(duì)于模糊匹配的地址，引入置信度作為權(quán)重參考，參考權(quán)重值大的作為地址匹配的優(yōu)選路徑構(gòu)建樹節(jié)點(diǎn)。具體算法流程包括以下步驟：

(1) 對(duì)待匹配地址進(jìn)行數(shù)據(jù)清洗及預(yù)處理，主要包括去除地址中字母、標(biāo)點(diǎn)及特殊符號(hào)等。

(2) 利用地址模型的特征名稱對(duì)待匹配地址進(jìn)行初步地址分詞處理。

(3) 根據(jù)地址模型的關(guān)系，對(duì)分割后的待匹配數(shù)據(jù)進(jìn)行驗(yàn)證，糾正地址要素的模型關(guān)系問題。

(4) 采用逆向匹配算法，優(yōu)先從分割出來的地址要素集合的右側(cè)開始，依次將地址要素名稱與地址樹進(jìn)行全局的精確查找，將每一個(gè)地址要素對(duì)應(yīng)查找到的地址樹節(jié)點(diǎn)組成一個(gè)節(jié)點(diǎn)名稱的集合，然后根據(jù)驗(yàn)證節(jié)點(diǎn)之間的層次關(guān)系，得到一條與原始待匹配地址符合度最高的地址路徑。

(5) 若步驟(4)未找到符合條件的地址，根據(jù)原始地址樹的統(tǒng)計(jì)特征值，推測(cè)待匹配地址可能的分詞組合，根據(jù)節(jié)點(diǎn)間層次關(guān)系及單詞匹配率進(jìn)行置信度計(jì)算，重復(fù)步驟(4)計(jì)算合適的模糊匹配地址返回最佳匹配路徑。

3 試驗(yàn)與驗(yàn)證

3.1 數(shù)據(jù)準(zhǔn)備

利用深圳市2015年人口普查數(shù)據(jù)，共獲得40余萬個(gè)地址。原始數(shù)據(jù)都屬于深圳轄區(qū)，但不是標(biāo)準(zhǔn)的地址格式，測(cè)試數(shù)據(jù)使用過濾器進(jìn)行預(yù)處理，主要預(yù)處理工作如下：①刪除重復(fù)的地址；②從地址中刪除所有的符號(hào)和標(biāo)點(diǎn)；③刪除太短的地址。其中試驗(yàn)數(shù)據(jù)是從預(yù)處理后的地址數(shù)據(jù)中隨機(jī)選擇了10 000個(gè)地址數(shù)據(jù)，部分地址數(shù)據(jù)及分段例子見表1。

表1 地址數(shù)據(jù)及分段示例

3.2 系統(tǒng)原型

原型系統(tǒng)開發(fā)硬件環(huán)境為：PC臺(tái)式機(jī)電腦(CPU i7-4790k，8 GB內(nèi)存，1T硬盤)；軟件環(huán)境：Windows 7 專業(yè)版，開發(fā)平臺(tái)VS2012，C#編程語言。

本文開發(fā)了基本的原型系統(tǒng)并基于預(yù)處理后的地址數(shù)據(jù)進(jìn)行地址匹配查詢，試驗(yàn)結(jié)果根據(jù)待匹配地址不同均可在5 s內(nèi)給出優(yōu)化匹配結(jié)果，原型系統(tǒng)如圖6所示。

利用文中所提出的方法能夠?qū)崿F(xiàn)較好的分詞并具有較高的準(zhǔn)確性，但是測(cè)試過程中同時(shí)發(fā)現(xiàn)在處理測(cè)試地址時(shí)仍然存在一些缺陷，對(duì)于同音字、錯(cuò)別字等的匹配效率和準(zhǔn)確度有待進(jìn)一步完善。

圖6 基于K叉樹的模糊地址匹配

4 結(jié) 語

地名地址匹配是數(shù)字城市系統(tǒng)建設(shè)中一項(xiàng)非常關(guān)鍵的技術(shù)，中文語義和地名地址描述的復(fù)雜性對(duì)地名地址編碼匹配均提出了更高的要求。本文應(yīng)用基于規(guī)則和統(tǒng)計(jì)的組合方法進(jìn)行中文地址分詞，保證了主體地理空間要素、地址特征名稱分割正確，應(yīng)用K叉樹的方式實(shí)現(xiàn)地址存儲(chǔ)和匹配查詢，地址匹配算法具有較好的匹配度。但是地址匹配的準(zhǔn)確度和效率尚待進(jìn)一步研究提高，可以進(jìn)一步改進(jìn)相關(guān)匹配算法，如引入神經(jīng)網(wǎng)絡(luò)等機(jī)器學(xué)習(xí)方法，在中文地址匹配中加入拼音模型、查詢次數(shù)統(tǒng)計(jì)等提高匹配準(zhǔn)確度，對(duì)于匹配速度方面引入Hadoop等大數(shù)據(jù)分布式架構(gòu)，以提升匹配的效率。