李新放，宋轉玲，陳學業(yè)，賀 彪，劉海行

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

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

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

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

1 中文地址分詞

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

1.1 中文地址定義

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

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

(1)

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

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

(2)

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

圖1 中文地址定義

1.2 中文地址要素采樣

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

圖2 地址采樣過程

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

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

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

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

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”的重復頻率。通過字與字之間不同頻率的變化獲取中文地址不同字段的邊界，基于統(tǒng)計結果可以很明顯得出具有正確語義關系的地址要素之間的邊界，實現(xiàn)優(yōu)化的中文地址分詞,如圖4所示。

圖4 地址語料庫的AF

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

2 基于K叉樹的地址匹配

2.1 中文地址K叉樹原理

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

2.2 基于原始地址分詞庫的K叉樹構建

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

圖5 空間目標體系與K叉樹

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

2.3 搜索匹配方法

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

(1) 對待匹配地址進行數(shù)據(jù)清洗及預處理，主要包括去除地址中字母、標點及特殊符號等。

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

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

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

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

3 試驗與驗證

3.1 數(shù)據(jù)準備

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

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

3.2 系統(tǒng)原型

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

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

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

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

4 結 語

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