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ù)庫不僅存儲 空間實體 的屬性信息 還 同時存儲其特有的

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

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

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

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

6、式樹的生成 G I S 空間數(shù)據(jù)庫 中， 描述相 同地理對象 的數(shù)據(jù) 文件在形式組織上可能千差萬別 ， 但是其模式結(jié)構(gòu) 卻相互類似 ： 包含與被包含是兩個層次間元素基本 的關(guān)系 ， 于是將模式結(jié)構(gòu)轉(zhuǎn)化成一個清晰元異意的 模式樹 ， 以方便各個元素的遍歷 ， 進一步進行 2 個模 式相應(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é)點 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é)點元素 t = n e wt r e e ( t r e e R o o t ) ； ／ ／ 建立模式樹根結(jié) 、 一點 。e l m e n ts t e p t h r o n g h ( r o o t ) ； ／ ／ ~ t 歷模式文件 并取出 模式中 所有元素， 如果元素類型為 基本類型，則將該元素直接看成時結(jié)點。一．．{’● -i f ( e l e m e n t 是前一個元素的孩子)a d d

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

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

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

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

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

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

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

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

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