嵌入式平臺(tái)上的地址搜索.doc

-專業(yè)文檔，值得下載!-專業(yè)文檔，值得珍藏！-嵌入式平臺(tái)上的地址搜索李勇陳文斌（北京靈圖軟件技術(shù)有限公司，北京100094,，）摘要：地址匹配技術(shù)是地理信息系統(tǒng)中的一項(xiàng)重要技術(shù)。本文在借鑒各種地址模型的基礎(chǔ)上，提出了一種可以應(yīng)用于嵌入式中的簡化層次地址模型，建立了一個(gè)嵌入式中的搜索模式的地址匹配服務(wù)框架，并最終實(shí)現(xiàn)了嵌入式平臺(tái)上的地址匹配搜索服務(wù)程序。結(jié)果顯示這種方法具有很高的效率，很好的滿足了用戶的地址匹配查詢需求。關(guān)鍵詞：地址模型，地址要素，地址搜索，倒排索引前言在現(xiàn)實(shí)世界中，人們通過地址來描述城市中的目標(biāo)地理位置。這種現(xiàn)實(shí)世界的定位方式是通過一段文字來表示目標(biāo)位置的。如，我們用“北京市海淀區(qū)東北旺西路8號”來表示中關(guān)村軟件園的位置。在地理信息系統(tǒng)中，計(jì)算機(jī)無法通過諸如以上的文字信息來直接定位目標(biāo)位置。目標(biāo)位置是由其所在地的地理空間坐標(biāo)確定的，常用的如該地的經(jīng)緯度等。這就需要將能被人們記住的文字地址信息和地理信息系統(tǒng)中的地理空間坐標(biāo)建立起一一對應(yīng)的聯(lián)系，從而實(shí)現(xiàn)人們與地理信息系統(tǒng)的交互。地址匹配技術(shù)（GEOCODING，也稱地址編碼）正是在這種背景中發(fā)展起來的。地址匹配是將地理坐標(biāo)（例如經(jīng)緯度）賦予街道地址還有其他點(diǎn)位和地理特征的過程1。有了地理坐標(biāo)，地理特征就可以被顯示到地圖上或運(yùn)用到地理信息系統(tǒng)中。美國是地址匹配技術(shù)應(yīng)用最早，最廣泛的國家。從二十世紀(jì)六十年代開始，美國就開始了地址信息的收集以及標(biāo)準(zhǔn)的建立工作，在1976年研究發(fā)展了“雙重獨(dú)立地圖編碼系統(tǒng)”（DualIndependentMapEncoding，DIME），于1990年前后發(fā)布了與人口數(shù)據(jù)相關(guān)的全國人口地址編碼系統(tǒng)：TopologicallyIntegratedGeographicEncodingandReferencingSystem，即“圖形整合地理編碼參照系統(tǒng)”，簡稱TIGER。另外，國外的很多商用地理信息系統(tǒng)軟件中都有相關(guān)的地址匹配模塊，如ArcInfo的GeoCoding和MapInfo的MapMaker等，都實(shí)現(xiàn)了基本的地址編碼框架和匹配引擎2。而對于我國，由于國情不一樣，地址地名等信息缺少統(tǒng)一的標(biāo)準(zhǔn)，又缺乏有效的服務(wù)體系，使得國外的地理編碼軟件在我國并不適用。從八十年代開始，一部分城市的規(guī)劃、測繪及管理部門對城市地址編碼問題相繼開展了研究工作。由于地理信息應(yīng)用的社會(huì)化，基于位置的服務(wù)需求強(qiáng)烈，地理編碼和地址定位技術(shù)也得到越來越多的重視。國內(nèi)也有一些公司開發(fā)了相應(yīng)的地理編碼軟件和應(yīng)用，如北京長地計(jì)算機(jī)公司的“導(dǎo)址神”，北京靈圖軟件公司的地址匹配引擎等。上述的各種系統(tǒng)都是基于服務(wù)器或者個(gè)人計(jì)算機(jī)的地址匹配服務(wù)程序。而近些年，隨著嵌入式系統(tǒng)軟硬件的發(fā)展，各種帶有導(dǎo)航等地理服務(wù)系統(tǒng)的智能終端獲得了廣泛的應(yīng)用。在這些系統(tǒng)中，需要相應(yīng)的地址匹配服務(wù)功能。由于嵌入式系統(tǒng)的各種限制（主要是CPU的處理速度、內(nèi)存的大小、IO的速度、外存的大小等），使得嵌入式系統(tǒng)中的地址匹配技術(shù)和基于服務(wù)器和個(gè)人計(jì)算機(jī)的地址匹配技術(shù)有著很大的差別?；诜?wù)器和個(gè)人計(jì)算機(jī)的地址匹配技術(shù)并不能直接簡單地移植到嵌入式系統(tǒng)中來使用。本文在借鑒基于服務(wù)器和個(gè)人計(jì)算機(jī)的地址匹配技術(shù)的基礎(chǔ)上，通過分析中文地址的特征，提出一種嵌入式上的地址匹配服務(wù)框架，并在嵌入式系統(tǒng)中實(shí)現(xiàn)地址匹配的功能。這種地址匹配技術(shù)應(yīng)用了當(dāng)代搜索引擎的一些技術(shù)，更像是一種地址搜索功能，具有高效的特征，非常適合嵌入式系統(tǒng)中的應(yīng)用。1地址數(shù)據(jù)的分析和地址模型地址是對具體地點(diǎn)的規(guī)范文字描述，主要是指由地名地址主管部門正式認(rèn)可或命名的對確定地點(diǎn)的完整文字描述，通常以地址標(biāo)牌的形式確立。地址通常是由一個(gè)或多個(gè)地址要素組成，每一個(gè)地址要素為地址串中的一個(gè)相對獨(dú)立的部分。地址要素包含行政區(qū)劃、道路名、自然地理名、門牌號、樓牌號等。這些要素按大的地址要素在前，小的地址要素在后的方式組合形成的地址名稱。關(guān)于中文地址國內(nèi)進(jìn)行了許多卓有成效的研究1、2、3，4，5，下面簡單介紹一下比較通用的兩種模型。-專業(yè)文檔，值得下載!-專業(yè)文檔，值得珍藏！-文獻(xiàn)2主要介紹了一種層次地址模型，其認(rèn)為各個(gè)地址要素存在著一對一或者是一對多的包含關(guān)系，比如一個(gè)省包含若干個(gè)市，一個(gè)小區(qū)對應(yīng)著某條道路的某個(gè)門牌號等等，并且總結(jié)出了大約40種地址層次模式。這種地址模型的特點(diǎn)在于具有良好的可擴(kuò)充性，對于新的地址模式可以方便的添加，并且可以針對不同城市采用不同的模式，缺點(diǎn)在于，有時(shí)候地址并不存在嚴(yán)格的包含關(guān)系，這時(shí)候用這種模型來描述就存在誤差。針對上述模型的缺點(diǎn)，文獻(xiàn)1提出了一種網(wǎng)狀模型，其認(rèn)為地址要素之間是一種帶有固定包含指向的網(wǎng)狀結(jié)構(gòu)，并且用有限狀態(tài)自動(dòng)機(jī)來描述和解析各種地址。這種地址模型的缺點(diǎn)在于擴(kuò)充性不好，修改地址模式比較復(fù)雜。在本文中，由于針對的是嵌入式中的地址匹配，考慮到效率的要求，不可能采用特別復(fù)雜的地址模型，因而采用較為簡單的層次地址模型。并且，考慮到嵌入式系統(tǒng)的特殊需求，對地址要素之間的包含等關(guān)系并沒有建立嚴(yán)格的聯(lián)系。下面重點(diǎn)介紹本文中的地址模型。1.1行政區(qū)劃級別地址要素的處理由于行政區(qū)劃級別的數(shù)據(jù)在長時(shí)間內(nèi)相對比較穩(wěn)定，所以對行政區(qū)劃級別的地址要素，建立嚴(yán)格的包含關(guān)系，并且對所有的地址要素只建立3級包含關(guān)系：省-市-其他地址要素（對北京這樣的直轄市，3級關(guān)系為：直轄市-區(qū)-其他地址要素）。比如，某個(gè)市必定屬于某個(gè)省，某個(gè)區(qū)必定屬于某個(gè)市，某個(gè)鎮(zhèn)、小區(qū)或者村必定屬于某個(gè)市。特殊的，對于跨區(qū)的道路，將道路按照所屬的區(qū)數(shù)分成若干段，每一段屬于某個(gè)區(qū)。如圖1所示。圖1行政區(qū)劃級別地址要素的包含關(guān)系1.2門牌號以及樓牌號的處理門牌號是相對于道路來設(shè)定的，而樓牌號是相對于小區(qū)來設(shè)定的，這也是兩種存在嚴(yán)格包含關(guān)系的地址要素聯(lián)系。由于一條道路包含的門牌號數(shù)量比較大，一個(gè)小區(qū)包含的樓牌號也比較多，考慮到數(shù)據(jù)存儲(chǔ)以及最后地址搜索的效率，需要對這種存在嚴(yán)格包含關(guān)系且子級別數(shù)據(jù)比較大的地址要素進(jìn)行特殊的處理。在本文中，門牌號以及樓牌號和其他地址要素分開存儲(chǔ)，包含這些門牌號或者樓牌號的道路或小區(qū)通過一個(gè)指針來獲得這些信息。這種數(shù)據(jù)處理方式有效的減少了數(shù)據(jù)冗余，并且提高了地址搜索過程中地址初步檢索的效率。1.3其它地址要素的處理對于上面提到的省名、市名以及門牌號、樓牌號之外的地址要素，本文將這些地址要素當(dāng)作一個(gè)獨(dú)立的實(shí)體來處理。對于這些地址要素，按照中文地址模型的各種習(xí)慣，盡可能地將其拆分成最小有效地址要素單元，這樣做可以提高最終用戶經(jīng)行地址搜索的準(zhǔn)確性。值得說明的是，在某個(gè)市內(nèi)，如果按照最小單元來拆分地址要素，有可能存在重名的地址要素名稱，但實(shí)際上這兩個(gè)名稱并不是同一個(gè)地址，這時(shí)候就不能對這些地址要素經(jīng)行進(jìn)一步的拆分，而盡可能地保持其完整性。2嵌入式上的地址搜索框架用戶在嵌入式設(shè)備上進(jìn)行地址匹配查詢時(shí)，通常是針對某個(gè)省的某個(gè)市的，因此本文設(shè)定用戶在嵌入式設(shè)備上進(jìn)行地址匹配查詢時(shí)必須首先選擇省份和城市?？紤]到用戶在嵌入式設(shè)備上進(jìn)行信息錄入時(shí)非常不便捷，本文重點(diǎn)考慮拼音首字母的用戶輸入模式，這種模式可以很好緩解用戶信息錄入的負(fù)擔(dān)。其次再考慮漢字輸入的查詢。再者，由于嵌入式系統(tǒng)的處理能力有限，為了提高查詢的效率，應(yīng)盡可能將數(shù)據(jù)處-專業(yè)文檔，值得下載!-專業(yè)文檔，值得珍藏！-理等功能提前到數(shù)據(jù)預(yù)處理階段，充分運(yùn)用PC的強(qiáng)大處理功能。借鑒當(dāng)前流行的搜索引擎技術(shù)6，7，采用對地址要素名稱進(jìn)行建立倒排索引的技術(shù)來提高嵌入式上的地址匹配查詢效率?；谝陨峡紤]，嵌入式上的地址搜索框架如圖2所示。圖2嵌入式地址搜索框架圖2中，PC端主要完成數(shù)據(jù)的預(yù)處理功能。按照文中的地址模型，原始地址數(shù)據(jù)經(jīng)過地址要素拆分工具拆分成符合要求的地址要素，然后這些地址通過索引建立工具生成各種順排數(shù)據(jù)以及倒排索引數(shù)據(jù)，包含有：行政區(qū)劃數(shù)據(jù)、地址要素?cái)?shù)據(jù)（不包含省名、市名等行政區(qū)劃數(shù)據(jù)以及門牌樓牌等數(shù)據(jù)）、門牌樓牌數(shù)據(jù)、索引數(shù)據(jù)。在嵌入式端，地址匹配查詢服務(wù)根據(jù)用戶的輸入調(diào)用查詢匹配邏輯，查詢匹配模塊通過數(shù)據(jù)讀取和緩存模塊高效獲得所需要的各種數(shù)據(jù)，進(jìn)一步處理完成用戶的請求。3地址數(shù)據(jù)的預(yù)處理地址數(shù)據(jù)的預(yù)處理分為兩步：地址要素的拆分以及索引的建立。其中地址要素的拆分決定了最終呈現(xiàn)給用戶的地址信息，而且地址要素拆分的好壞會(huì)影響最終查詢的效率，因?yàn)闇?zhǔn)確的拆分可以大量減少重復(fù)的地址要素信息。本文中地址拆分的策略是：首先拆分已經(jīng)確定的地址要素，比如省名市名，然后再拆分其他地址要素。由于中文地址的復(fù)雜性，地址要素的拆分需要大量經(jīng)驗(yàn)數(shù)據(jù)的支持，并沒有一個(gè)完美的方法，在此不再贅述。下面重點(diǎn)介紹一下本文中地址要素?cái)?shù)據(jù)的索引方法。本文對地址要素建立拼音首字母索引，采用二元索引，直接支持拼音首字母的輸入查詢，當(dāng)用戶需要進(jìn)行漢字輸入查詢時(shí)，先將漢字拼音首字母取出來做拼音首字母查詢?nèi)缓笞鰸h字過濾操作，從而完成漢字的查詢。索引的建立過程如圖3所示。圖3地址要素索引文件的建立過程4嵌入式上的查詢實(shí)現(xiàn)為了提高用戶的體驗(yàn)，在嵌入式上實(shí)現(xiàn)地址匹配查詢時(shí)，在用戶輸入的同時(shí)立即顯示候選的地址信息（由于是二元索引，當(dāng)用戶輸入超過兩個(gè)字母或者兩個(gè)漢字時(shí)才有提示）。為了到達(dá)這種效果，并且保證合理的響應(yīng)時(shí)間，運(yùn)用了多種緩存技術(shù)：倒排索引的緩存以及查詢結(jié)果的緩存。倒排索引的緩存減少了系-專業(yè)文檔，值得下載!-專業(yè)文檔，值得珍藏！-統(tǒng)外存的IO操作，而查詢結(jié)果的緩存則可以大量縮短用戶連貫輸入過程中的匹配操作，從而縮短了用戶響應(yīng)時(shí)間。由于本文的索引是地址要素的拼音首字母索引，索引在進(jìn)行漢字輸入查詢時(shí)，需要特殊的處理，其過程如圖4所示。圖4漢字查詢的處理過程由圖4可以看出，漢字的查詢是建立在拼音首字母查詢的基礎(chǔ)上的，因而漢字查詢的效率會(huì)略低于拼音首字母查詢的效率。5結(jié)束語本文中介紹的地址搜索服務(wù)已經(jīng)在嵌入式系統(tǒng)中實(shí)現(xiàn)。對北京十幾萬的地址數(shù)據(jù)（其中包含道路級別數(shù)據(jù)三萬多條），在普通的PDA上，拼音首字母地址匹配查詢響應(yīng)時(shí)間在100毫秒以內(nèi)，漢字地址匹配查詢響應(yīng)時(shí)間基本在1秒以內(nèi)，效率還是很高的，完全可以滿足用戶的需求。本文中所述的方法還有很多需要完善的地方。例如，目前只能實(shí)現(xiàn)精確匹配，并不支持模糊匹配，但在現(xiàn)實(shí)中人們經(jīng)常會(huì)存在記憶錯(cuò)誤或者是輸入錯(cuò)誤，在查詢時(shí)需要一定的模糊性。還有就是地址數(shù)據(jù)的處理并沒有做到完全自動(dòng)化，需要大量人工干預(yù)。在后面的工作中，可以嘗試建立一個(gè)更加完善的系統(tǒng)，盡量減少人工的干預(yù)，并且在用戶體驗(yàn)度上爭取獲得更好的效果。參考文獻(xiàn)1徐錫珍.城市地址編碼與地址匹配的設(shè)計(jì)和應(yīng)用.太原理工大學(xué)畢業(yè)設(shè)計(jì)（論文）.2006年6月.2李娜.城市地理編碼技術(shù)的研究.武漢大學(xué)碩士學(xué)位論文.2006年5月.3張作華，孫凌宇.基于城市地址編碼技術(shù)的探討.井岡山師范學(xué)院學(xué)報(bào)（自然科學(xué)）.Vol.26No.320