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

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