空間數據模式匹配應用范文

本站小編為你精心準備了空間數據模式匹配應用參考范文，愿這些范文能點燃您思維的火花，激發您的寫作靈感。歡迎深入閱讀并收藏。

《地理與地理信息科學雜志》2014年第四期

1模式匹配的主要應用領域

1．1更新信息傳播空間數據現勢性是GIS的“生命”，直接影響著其使用價值與可持續發展。伴隨著GIS空間數據更新理論研究和工程實踐的不斷深入，更新信息傳播問題已成為生產單位、應用部門及學術界共同面臨的新問題。由于數據庫間在數據模式和數據實例之間存在多種潛在的語義差異，當利用一個新版GIS數據庫中的更新變化要素及其相關信息對另一個GIS數據庫中的對應要素進行更新（即更新信息傳播）時，必須首先在兩個數據庫間進行模式匹配操作建立模式映射關系，以引導和簡化變化發現、實體識別、更新集成等操作，從而在保證更新傳播實施效率的同時，最大限度地維護目標數據庫的自治性、完整性、正確性和一致性［6，7］。

1．2語義查詢處理目前使用的空間數據查詢方式大都是基于關鍵字匹配技術，如果用戶輸入的查詢關鍵字與被查數據模式元素的名稱不盡相同或有所偏差，則不能返回真正需要的信息或者會返回很多無用的信息。為解決傳統查詢方式的不足，提出了語義查詢技術［8］。語義查詢又稱語義檢索、概念匹配，是指在相關技術（如本體等）的支持下，首先使用戶的查詢請求和被檢索的內容在語義上都是可被計算機理解、處理的，在此基礎上對用戶查詢語句（如Select語句）和被查數據模式元素進行匹配，然后重寫查詢語句中的關鍵字使其與被查數據模式名稱相一致，從而返回準確的查詢數據。

1．3地理服務發現網絡地理服務是利用地理數據和相關的功能實現諸如地址匹配、地圖繪制、路程安排等基本地理操作任務的Internet應用，它允許開發者將GIS功能集成到自己的Web應用中，而不用自己在本地實現該GIS功能［9］。隨著越來越多的網絡地理信息服務的出現，快速準確找到用戶需要的地理信息服務顯得尤為重要［10］。在服務發現過程中，一旦服務請求者和提供者使用不同的術語表示同一個概念或者是同樣的詞表示不同的涵義，就會發生找不到匹配的服務和找到的服務不能完全滿足需求的情況。另外，地理服務版本差異造成的語義異構也將增加服務發現的難度。與語義查詢類似，通過模式匹配也可以有效解決這類問題。

2模式匹配相關研究內容綜述

近些年來，模式匹配作為數據管理與應用中的基礎性問題受到了全球的普遍關注，在數據庫、人工智能、信息檢索、知識管理、語義Web等眾多領域引起了廣泛的討論和研究。概括而言，當前對模式匹配問題的研究主要集中在匹配實施方法、匹配效率優化、匹配結果表達、匹配質量評價4個方面。

2．1匹配實施方法研究目前，大多數系統的模式匹配任務是在圖形界面支持下靠操作員手動完成的，該方式不僅要求操作員充分了解模式元素的語義內涵，而且隨著待匹配模式元素數據的增加，其費時、費力、易出錯的缺陷也將變得更加突出。另外，用戶需求的變化、數據源的變化等都可能造成模式的變化，從而導致這些模式間的匹配關系發生變化。顯然，如果僅僅依靠手工匹配無法適應這種復雜動態的匹配需求。為了盡量減少模式匹配過程中用戶的參與，提出了多種自動（或半自動）的匹配方法及系統。Rahm等根據匹配所依據的信息類型及其結合方式對各種模式匹配方法進行了層次式劃分（圖2），結合圖2的分類體系又對2001年以前的典型匹配方法及系統進行了比較權威的總結和評述［13］。在此分類體系基礎上，Shvaiko等根據所用技術的特征（Heu－risticorformal，Implicitorexplicit）對其中基于模式的匹配方法做了更為詳細的劃分［14］。潘超等則進一步總結了2010年之前的主要方法及系統［15］。本文依據圖2所示的分類結果，對模式匹配方法的基本策略和問題做簡要評述。（1）單匹配，主要利用某一種類型的信息識別語義相關模式元素，可進一步劃分為基于模式的匹配和基于實例的匹配兩類。1）基于模式的匹配方法，主要通過對比模式元素本身所包含的信息（如名稱標簽、描述性元數據、數據類型、數據長度、結構關聯關系等）判斷元素是否匹配。由于數據模式設計本身是一項靈活性很大的主觀活動，不同的設計者可能采用不同的機制和元素來抽象和模擬相同的現實事物或現象，并且所形成的模式結構的語義信息大部分隱含在設計者的大腦中，而模式元素本身所承載的一部分外在顯式信息對模式匹配而言是不明確、不完整、易混淆的。因此，該類方法往往產生錯配、漏配等情況，質量和效果不高。針對這一情況，文獻［16］提出了基于信息論的模式匹配模型，嘗試解決模式信息丟失或者不完整情況下的模式匹配問題。2）基于實例的匹配方法，主要依據屬性字段數據值的統計概括信息（如最大值、最小值、平均值、方差）或部分重疊對應實體的屬性值，來匹配識別兩個數據集（如關系表）之間語義相關的屬性字段，一般不能確定數據集之間的匹配關系。由于概括信息是確定屬性是否匹配的必要但不充分信息，因此如果單獨用其進行匹配常常會產生一些錯配或漏配現象。針對這種情況有兩種改進途徑：一是將概括信息與其他類型的信息結合構成混合匹配；二是通過進一步分析比較數據集之間部分對應實體（或重復記錄）的屬性值來確定相關的屬性，但這種方式目前通常以預先手動建立實體對應關系為基礎，自動化程度低，屬性相關性對比分析和度量模型較單一，尚沒有充分考慮語義相關屬性在具體屬性值上的各種表達差異，仍有很大的擴展改進空間。（2）多匹配，主要利用多種類型的信息或方法識別語義相關模式元素，可以進一步劃分為混合匹配與復合匹配兩大類。1）混合匹配主要通過綜合使用多種匹配指標或信息源（如名稱信息、元數據描述信息、數據約束信息、實例概括統計信息、屬性依賴關系等）來確定匹配元素?；旌掀ヅ湓诖_定一對模式元素是否匹配時，同時考慮了多種匹配標準，對于不符合標準的候選成員能夠較早地被刪除。因此，這種方法與單獨執行多種匹配方法相比，可以減少比較模式信息的遍歷次數，不僅能取得較好的匹配性能和效果，而且匹配效率也得到了提高。但由于多種來源的信息具有不同的表達形式，一般并不能被直接應用于混合匹配，常常需要制定高效的策略和規則對其進行規范化處理?；旌掀ヅ渌罁钠ヅ湫畔⒑鸵巹t往往由設計者事先規定，一般不易進行調整和修改，靈活性較低。2）復合匹配主要通過對多個獨立匹配方法（如基于模式的匹配、基于實例的匹配、混合匹配等）所取得結果的組合分析來確定匹配元素。復合匹配允許用戶根據應用需要，靈活地選擇現有方法并按不同的順序（如并行順序、串行順序、混合順序）加以執行。在串行執行時，前面匹配方法所取得的匹配結果，可以用作后面匹配方法的輸入，從而達到反復修改匹配結果的目的。復合匹配是以單個匹配方法為基礎的，為保證其效率和效果，不僅要盡可能地提高每個成員匹配方法的效率和效果，而且應該選擇正確的執行順序、制定合理的結果重用和組合策略［19］。靜態組合的匹配算法和人工調節的匹配參數難以適應自動匹配的要求，如何對現有的匹配算法進行動態選擇、搭配、組合、重用以及對匹配參數進行自動調節是復合匹配面臨的一個有待深入研究的重要問題。每種匹配技術都各有其優點和適用范圍，綜合使用多種匹配信息或方法能夠充分發揮不同技術間的互補性優勢，有效提高匹配系統的匹配質量和通用性。但隨著匹配信息或方法的增加，系統的復雜性也將隨之增加。

2．2匹配效率優化研究當前模式匹配的難點，不僅在于缺乏切實可行的判別模式元素是否匹配相關的策略和規則，更在于依據判別規則執行模式匹配的代價偏高，必須進行大量的計算比較才能確定獲取潛在的匹配元素。模式匹配中最常用的兩兩比較法，也稱嵌套循環法或笛卡爾法，是將兩個待匹配模式元素集合做笛卡爾乘積，根據用戶所定義的規則和策略，對結果集中的每對元素進行比較，如果比較結果滿足所定義的規則條件，則認為它們是匹配元素。該方法簡單，能夠最大限度地保證匹配結果的質量和精度，但是隨著待匹配元素數量的不斷增加，所需的處理時間和系統資源的消耗將呈指數級增長，在實際應用中的可行性和使用價值并不高。因此，必須加強模式匹配效率優化模型及算法的研究。目前，只有少數幾個系統考慮處理了模式匹配的執行效率問題，根據模式匹配策略的不同，提出了不同的模式匹配執行效率優化技術。概括而言，現有模式匹配執行效率優化所采取的基本策略主要有如下5種［20］：1）分而治之，先將待匹配的模式元素集劃分為不同的塊（Blocks）、區（Partitions）或簇（Clusters），然后在塊（區或簇）之間執行模式匹配。該策略降低了匹配比較的搜索空間，效率較高，但可能降低匹配質量。2）模式過濾，依據相關的上下文信息或通過問卷調查預先排除掉一些模式元素，從而降低比對次數，提升匹配效率。3）避免重復，在模式匹配執行過程避免一些相同子任務的重復執行。4）改善數據結構，利用諸如索引、Hash表等特殊類型的數據結構，減少待匹配模式元素間的比較次數，從而提高執行效率。5）優化模式元素相關性度量模型（如編輯距離等）的計算效率等。隨著大數據時代的到來，勢必出現大模式的匹配問題。大模式的“大”不僅意味著數量的大，還代表著模式種類多、結構雜、差別大、變化快等。由于目前尚沒有對大模式匹配問題給予充分的考慮和有效的處理，若采用現有策略執行匹配將會因時間復雜度過高而得不到理想的匹配結果。針對大模式匹配執行效率問題，可通過大模式聚類分割技術加以解決［21］。目前這一技術仍需攻克3個核心問題：如何分割模式；如何選擇需要進行匹配的模式片斷；如何避免模式分割可能造成的結果遺漏。

2．3匹配結果表達研究匹配結果（模式映射）表達的主要任務是存儲和組織通過匹配識別發現的相關模式元素及其映射關系，并構建相應的存取和檢索方法，以引導和簡化各種應用處理中的其他操作。目前，有一些匹配工具把模式映射保存在純文本文件中，而且不同工具定義的模式映射文件格式不同，缺乏足夠的語義表現力和處理能力，使得模式映射的讀取過程較煩瑣，造成不同系統間難于共享模式映射，通用性不強；還有一些匹配工具使用關系數據庫存儲和管理模式映射，但由于模式映射的半結構化特征，往往導致數據表中出現很多值為NULL的字段，從而造成非常大的冗余，使得很多復雜的匹配關系（如條件匹配、部分匹配、計算匹配等［22］）無法得到有效的表達，且每當待匹配元素數目發生變化時，將可能導致整個數據表的結構重構，不便于模式映射的管理和維護。針對上述模型及方法的不足，一些學者開始嘗試利用基于邏輯的語言（如一階邏輯、描述邏輯、Datalog等）或半結構化模型（如XML、RDF等）來表達和存儲模式映射。例如，文獻［23］利用一階邏輯表達XML模式與OWL本體間的語義映射；為評價對比現有基于邏輯的映射語言的共性與差別，文獻［24］采用分布式一階邏輯來統一現有的各種映射語言；文獻［25］采用巴克斯范式（Backus－NaurForm，BNF）來表達語義映射；文獻［26］提出了一種新的映射語言———RDFMappingSchema來表達XML數據和RDF數據之間的語義映射；文獻［27］在BRICKS系統中采用XML來存儲和管理模式映射。目前大部分模式匹配研究的重點仍集中在如何發現和找到語義相關元素匹配對，有關匹配結果表達的研究才剛剛起步［28］，有些表達語言或模型的提出尚處于思想萌芽階段，也只是僅僅給出了一些示例性的表達結果，仍缺乏系統性的研究，更沒有形成統一的表達語言或模型。即使是同一種語言或模型，表達映射的方式也不盡相同，所支持的功能和算子差別較大［29］。匹配結果表達的研究仍然面臨著許多開放性問題，如表達模型能夠支持的映射關系類型及語義轉換函數種類、匹配結果的檢索與編輯、匹配結果的有效性檢驗、匹配結果的可視化等。

2．4匹配質量評價研究雖然人們對模式匹配問題進行了廣泛研究，但大部分的自動匹配方法還停留在高度實驗階段，而得不到廣泛的實際性應用。其中也有一些較為實用的系統出現，而這些系統卻依舊需要大量的人機交互或后處理工作，還遠遠滿足不了實際需要。當前有關自動匹配質量的研究主要集中在質量評價模型和策略上，概括而言，各種自動匹配方法及系統的匹配質量可以從有效性（Effectiveness）、效率（Efficiency）、通用性（Genericity）和易用性（Ease－of－use）4個方面加以評價［30］：1）有效性：主要考慮匹配結果的正確性和召回率，通常用Precision和Recall兩個單項指標及F－Measure（a）、F－Measure、Overall等幾個綜合指標加以衡量。2）效率：主要考慮系統執行匹配時所消耗的資源，如時間、內存等，通常情況下只采用時間指標來評價匹配效率。3）通用性：主要考慮系統的應用領域、所支持的數據模型或類型及系統是否可以支持在線匹配或離線匹配。目前還沒有評價匹配系統通用性的定量指標或模型。4）易用性：不論全自動匹配能否實現，用戶的參與及交互總是需要的，易用性主要考慮通過自動匹配能夠節省多少人力，一般應綜合考慮匹配執行的預處理與后處理兩個階段。然而，現有的評價策略常常將預處理階段的人力參與忽略掉，只考慮后處理階段用于添加遺漏匹配、移除或修改錯誤匹配的人力參與。上述的有效性指標可在一定程度上反映模式匹配后處理階段的人力參與情況，但由于這些指標的取值介于0～1，直接用其評價人力參與情況還不太恰當。針對這種情況，Bogdan等提出了簡單可用性（SimpleUsability）模型和簡單成本（SimpleCost）模型，這兩個模型分別根據人機交互過程中拖拽、單擊、雙擊3種不同的鼠標行動及其執行成本來評價人力參與情況。以上單因素評價模型彼此間是相互矛盾的，僅利用其中的任何一種都不能全面客觀地評價匹配系統，因此，需要將這些指標綜合起來考慮，對匹配系統進行總體上的質量評價，這實際上是一個多目標模糊決策難題。文獻從有效性和效率兩方面討論分析了匹配系統的總體評價方法，但卻忽略了通用性和易用性兩方面的因素。總體而言，目前人們雖然認為自動匹配的質量評價與控制是一個很重要的問題，卻沒有高度重視它，自動匹配質量問題的研究還沒有全面深入地展開。

3結語

經過近30年的不懈努力，模式匹配問題研究已取得了較為豐富的學術成果，從最初的利用元素自身的各種信息進行模式匹配，到后來集成各種類型的結構信息、數據實例信息來輔助匹配，再到近年來為模式匹配方法尋找理論支持，提供人性化的用戶干預工具等。但由于模式匹配本身的主觀性與復雜性，目前仍然存在著一些問題和不足?，F有大多數研究主要集中在匹配方法上，一般只專注于不同模式之間的簡單匹配（即1∶1匹配），不能有效識別復雜匹配（即1∶N、M∶l和M∶N匹配），應用往往局限于特定領域或特定模式，通用性有待提高。對模式匹配的不確定性、模式通用表達模型、匹配方法的質量評價、模式結果的后處理分析、匹配結果的存儲管理及可視化維護等問題尚缺乏整體系統的分析和全面深入的研究。從文獻資料上看，目前針對空間數據模式匹配的研究仍比較薄弱，有關空間數據模式匹配問題的闡述大多是一些附帶的概念性解釋，缺乏針對性的深入分析，僅有少數研究側重于具體方法的設計及原型系統的實現。與空間數據模式種類多、規模大、結構復雜的特點相比，現有研究尚不能滿足一個理想模式匹配系統在通用性、強壯性、靈活性、交互性和擴展性等方面的要求。因此，很有必要進一步積極開展針對空間數據模式匹配的系統性研究工作，從而為空間數據資源的高效共享與靈性服務提供理論支持與技術保障。

作者：王育紅景海濤薛華柱單位：河南理工大學測繪與國土信息工程學院