gis數(shù)據(jù)庫模式匹配技術(shù)研究

1、第 2 6卷 第 1 0 期 2 0 1 0年 5月甘肅科技 Ga n s uS c i e n c ea n dT e c h n o l o g yf ． 2 6Ma y ．No ． 1 02 0 1 0GI S數(shù) 據(jù) 庫 模 式 匹配技 術(shù)研 究 呂娜 ( 甘肅省地圖院 ， 甘肅 蘭州 7 3 0 0 0 0 )摘 要 ： 作為與傳統(tǒng)數(shù)據(jù)庫的顯著區(qū)別之一 ， G I S 數(shù)據(jù)庫不僅存儲(chǔ) 空間實(shí)體 的屬性信息 還 同時(shí)存儲(chǔ)其特有的

2、空 間信 息 。對(duì)于描述 同區(qū)域地物卻有不 同來 源或格式 的空間數(shù)據(jù) ， 可以利 用其空間與屬性 兩方面特征 ， 來確定兩個(gè)要素之 間的共同實(shí)體。詳細(xì)介紹了關(guān)于 G I S 數(shù)據(jù)庫模式匹配的實(shí)施框架、 給出了匹配方法的步驟、 算法及已所實(shí)現(xiàn)的模式 匹配詳細(xì)流程 ， 包括語 意與結(jié)構(gòu)相似度判斷 以及權(quán) 重的設(shè) 置 ， 最后 ， 對(duì) 匹配過程 中包 含 的不 確定 因素進(jìn)行 了分析與 討論 。關(guān)鍵詞 ： 模式匹配 ； 模式樹 ； 語 意與

3、結(jié) 構(gòu)相似度 ； 權(quán)重 中圖分類號(hào) ： P 2 0 8隨著空間信息技術(shù)的 日益發(fā)展與成熟 ， 越來 越 多的部門與單位紛紛建立起了面向各 自需求 的 G I S應(yīng)用系統(tǒng)。由于各個(gè)系統(tǒng)之間所承載的數(shù)據(jù)存在來 源與格式的差異 ， 導(dǎo)致 了地理信息交互與共享的困難。為了解決這一問題對(duì) G I S 研究與生產(chǎn)帶來的不 利影響， 在總結(jié)相關(guān)技術(shù)發(fā)展 的基礎(chǔ)上， 根據(jù) G I S 空 間數(shù)據(jù) 的特點(diǎn)和應(yīng)用背景 ， 提出一種便于實(shí)現(xiàn)的數(shù) 據(jù)模式匹配方

4、法， 詳細(xì)討論 了其 中關(guān)鍵步驟 的解決 途徑 ， 并證實(shí)了其有效性與可實(shí)施性。1實(shí)施框架 G I S 數(shù)據(jù)庫中對(duì)于空間實(shí)體的存儲(chǔ) ， 劃分為點(diǎn)、線 、 面三種遵循拓?fù)潢P(guān)系的要素類型。假設(shè)待匹配 的兩個(gè)空間數(shù)據(jù)中各有 M和 N個(gè)空間要素( 包括點(diǎn) 要素、 線要素與面要素 ) ， 如果直接采取兩兩 比較的 方式來判斷其中是否存在同名實(shí)體 ， 不僅需要極大 的比較次數(shù)( MN ) ， 而且對(duì)于不 同種類 的實(shí)體， 很 難設(shè)計(jì)它們之間的比較規(guī)

5、則。因此 ， 首先要對(duì)待匹 配空間數(shù)據(jù)進(jìn)行各 自獨(dú)立的要素分組 ， 將點(diǎn)、 線 、 面 要素分別歸類 ， 以減少算法時(shí)間消耗 ， 簡化對(duì)象匹配 規(guī)則。2 模式匹配與流程 所謂模式匹配 ， 即是通過指定的匹配算法 ， 對(duì)兩 個(gè)模式 中的每一個(gè)元素進(jìn)行一一對(duì)應(yīng) 的分析和 比較 ， 通過對(duì)元素間相似程度的判斷， 來確定 2 個(gè)模式 是否描述同一地理對(duì)象 ， 以達(dá)到方便數(shù)據(jù)流通與共 享等 目的。匹配流程大概可以分為下面幾個(gè)步驟 ：2 ． 1 模

6、式樹的生成 G I S 空間數(shù)據(jù)庫 中， 描述相 同地理對(duì)象 的數(shù)據(jù) 文件在形式組織上可能千差萬別 ， 但是其模式結(jié)構(gòu) 卻相互類似 ： 包含與被包含是兩個(gè)層次間元素基本 的關(guān)系 ， 于是將模式結(jié)構(gòu)轉(zhuǎn)化成一個(gè)清晰元異意的 模式樹 ， 以方便各個(gè)元素的遍歷 ， 進(jìn)一步進(jìn)行 2 個(gè)模 式相應(yīng)元素之間的匹配。：模式樹通過算法生成 ， 具體描述如下 ：， ’’ t r e e=b u i l d t r e e()B u i l d t r e

7、e ( S t r i n gs c h e m a L o c a t i o n ) ／ ／ 根據(jù)模式文 件的目錄建立模式樹 {r o o tg e t S c ： h e m a R o o t ( s c h e m a L o e a -t i o n ) ； ／ ／ 通過解析函數(shù)解析模式文件并得到該模式 的根結(jié)點(diǎn) t r e e R o o t= r o o t ． g e t T r e e R o o t ( ) ； ／

8、 ／ 得到模 式樹的邏輯根結(jié)點(diǎn)元素 t = n e wt r e e ( t r e e R o o t ) ； ／ ／ 建立模式樹根結(jié) 、 一點(diǎn) 。e l m e n ts t e p t h r o n g h ( r o o t ) ； ／ ／ ~ t 歷模式文件 并取出 模式中 所有元素， 如果元素類型為 基本類型，則將該元素直接看成時(shí)結(jié)點(diǎn)。一．．{’● -i f ( e l e m e n t 是前一個(gè)元素的孩子)a d d

9、 A sC h i l d ( ) ； ／ ／ 將該元素做為前一個(gè) 元素的孩子 i f ( e l m e n t 是前一個(gè)元素的兄弟)a d d A s S i b l i n g ( ) ； ／ ／ 將該元素作為前一個(gè) 元素的 兄弟 }3 2甘 肅 科 技 第 2 6 卷 值 V ， 權(quán)值用 w 表示 。則有 ：V=W。 。 。 ‘ D + ( 1 一 W)T匹配者可以根據(jù) 自己的需要決定在進(jìn)行匹配時(shí) 更注重哪一方面的相似性。權(quán)

10、 值 w 是 匹配者根據(jù) 自己需要定義的， 具有很大的靈活性。2 ． 4 集成數(shù)據(jù)模式 ．兩個(gè)數(shù)據(jù)模式進(jìn)行匹配后 ， 用戶可以根據(jù)需要 選取其中的任意一個(gè)模式文件來作為它們 的集成模 式文件， 也可以通過運(yùn)用 以上匹配算法生成的映射，生成集成模式 。算法輸人是模式匹配算法 中生成 的映射 ， 根據(jù)映射關(guān)系， 算法 自 動(dòng)生成包含樹 中的葉節(jié) 點(diǎn)層次 ， 并在各個(gè)映射中生成存在映射關(guān)系的元素。這些生成的元素被包含在一個(gè)用戶 自定義的新的

11、數(shù) 據(jù)模式中， 作為匹配結(jié)果輸 出。經(jīng)過 以上步驟的具體實(shí)現(xiàn) ， 匹配得以基本完成。具體匹配流程 ， 如圖 1 所示。模式lL 一式 數(shù) 兒 樹 掘 泰的 解 遍 l啦 析- I 塑成模式的牛成j 輸H {橫2 卜 _ ．成 與與橫 廷 配 圖 1 數(shù)據(jù)模式 匹配流程 3匹配不確定性因素分析 模式匹配的關(guān)鍵 ， 在于對(duì)兩個(gè)模式元素之間相 似程度的判斷。具體在操作 中， 與判斷法則密切相 關(guān) 。就 目前可行 的匹配算法與匹配器

12、中， 面向空間 信息集成的模式匹配還并不完善 ， 基于其他數(shù)據(jù)集 成領(lǐng)域的模式匹配算法仍有一定的參考的價(jià)值。對(duì)于語意相似度的判斷 ， 一般會(huì)有一個(gè) 比較 明確的結(jié)果。無論是對(duì)元素命名或元素?cái)?shù)據(jù)類型的相 似度判斷 ， 都可以得到一個(gè)明確的取值 ， 假設(shè)定義為 T ，= l 時(shí)， 代表相似 ， T= 0時(shí) ， 則代表不相似。加 入條件之間的權(quán)重 ， 可 以簡單的得 到語意相似度的 取值。對(duì)于結(jié)構(gòu)相似度 ， 判斷條件則非 常復(fù)雜， 并且 ，隨

13、著匹配的進(jìn)行， 受到不同匹配模型的影響， 一個(gè)模 式 中的某一元素的父子節(jié)點(diǎn)和另一個(gè)模式中的某特 定元素的父子節(jié)點(diǎn)的結(jié)構(gòu)相似度可能會(huì)隨匹配進(jìn)程 發(fā)生變化 ， 使相似判斷成為一個(gè)動(dòng)態(tài)的過程。為此 ，提出這樣的假設(shè) ： 將 葉節(jié)點(diǎn)元素的語意相似度判斷 引入結(jié)構(gòu)相似度判斷： 對(duì)于兩棵樹中的葉節(jié)點(diǎn) ， 如果 它們的語意高度相似， 則可認(rèn)為它們在結(jié)構(gòu)上相似；對(duì)于兩棵樹中的非葉節(jié)點(diǎn) ； 如果它們的孩子節(jié)點(diǎn)全 部或部分高度相似( 取決于匹配精確程度要

14、求 ) ， 也 認(rèn)為他們結(jié)構(gòu)相似 。在實(shí)際匹配過程 中， 結(jié)構(gòu)相似度是一個(gè)需要慎 重考慮的問題。因?yàn)橥诓煌哪Ｊ剑?， 由于用戶 操作 、 習(xí)慣 的不 同， 對(duì)元素 的語意命 名產(chǎn)生 的隨機(jī) 性 ， 對(duì)語意相似度的判斷所產(chǎn)生的負(fù)面影響， 可以通 過字庫詞庫 的不斷完善而逐漸減小 ； 但是 由于兩個(gè) 模式之間的空間關(guān)系 ， 空間信息組織方式等條件的 不 同， 對(duì)結(jié)構(gòu)匹配效果產(chǎn)生的影響， 則很難完全通過 算法進(jìn)行完美的解決。這一點(diǎn) ，

15、正是匹配存在不確 定性因素的根本原因。：一 對(duì)于此 ， 語意相似度和結(jié)構(gòu)相似度反差很大的 情況下 ， 權(quán)重的取值就非常重要。兩個(gè)模式需要?dú)v 經(jīng)二次匹配乃至多次匹配， 調(diào)整不同的權(quán)重與闞值 設(shè)置， 才可能得到理想的匹配結(jié)果。} ．4 結(jié)束語 。利用模式匹配技術(shù)， 可以基本準(zhǔn)確 的判斷兩個(gè) 模式文件是否定義的是 同一個(gè)地理對(duì)象 并在匹配 通過的基礎(chǔ)上生成它們 的集成模式文件， 有利于模 式文件的流通與共享。但是 ， 由于現(xiàn)實(shí)世界地物特

16、征的高復(fù)雜程度而造成的復(fù)雜描述 ， 以及人們在描 述 同一特征時(shí)的主觀性差異 ， 對(duì)模式匹配 的精確程 度仍然會(huì)產(chǎn)生一定的影響， 因此 ， 有關(guān)空間數(shù)據(jù)模式 匹配還有大量的工作有待于進(jìn)一步的研究。參考文獻(xiàn)：[ 1 ] 李俊 ， 關(guān)佶紅 ， 李 玉珍 ． G M L 空 間數(shù)據(jù)存儲(chǔ) 映射模型研 究[ J ] ． 武漢 大學(xué) 學(xué) 報(bào) ( 信息 科學(xué) 版 ) ， 2 0 0 4 ， 2 9 ( 1 2 ) ：1 0 71 ． 1 0 7 4

17、．[ 2 ] 關(guān)估 紅 ， 虞為 ， 安揚(yáng)． G M L 模式匹配算法 [ J ] ． 武漢 大學(xué) 學(xué)報(bào)( 信息科學(xué)版) ， 2 0 0 4 ， 2 9 ( 2 ) ： 1 6 9 - 1 7 4 ．[ 3 ]李由 ， 劉東 波． 基 于數(shù)據(jù) 實(shí)例分 布特征 的 自動(dòng)模式 匹 配方法 [ J ] ． 計(jì)算機(jī)科學(xué) ， 2 0 0 5 ， 3 2 ( 7 ) ： 1 1 - 1 5 ．[ 4 ]簡睿， 俞勇． 基于形式化概念分析的X M L