模式匹配的泛代數(shù)描述及算法研究.pdf

1、模式是數(shù)據(jù)庫應(yīng)用中的一類特定的元數(shù)據(jù)模型，是實現(xiàn)異構(gòu)數(shù)據(jù)和應(yīng)用系統(tǒng)互操作中不可缺少的基本元素。對于模式，最基本的操作就是匹配，其目的在于獲得模式元素之間的對應(yīng)。模式匹配在許多數(shù)據(jù)庫應(yīng)用中起到關(guān)鍵性的作用，例如電子商務(wù)、數(shù)據(jù)倉庫、科學(xué)數(shù)據(jù)共享、元模型／數(shù)據(jù)管理、XML消息交換等。 對于模式匹配問題，建立相應(yīng)的形式化匹配框架是非常重要的，它有助于分析模式匹配問題的結(jié)構(gòu)，建立模式匹配的算法模型和評價模式匹配算法。然而，目前對于模式匹配

2、研究的工作主要集中在基于特定應(yīng)用領(lǐng)域的匹配算法研究，而沒有對模式匹配問題的代數(shù)學(xué)基礎(chǔ)進(jìn)行過深入研究。因此，論文研究工作首先著重于建立一個模式匹配的泛代數(shù)描述框架： 1．基于泛代數(shù)的觀點，本文將模式定義為一類特定的有限結(jié)構(gòu)(代數(shù))，稱之為多標(biāo)記模式，其最顯著的特點就是可以形式化地描述任何類型的模式，并將這些模式轉(zhuǎn)換為基于特定基調(diào)的有限結(jié)構(gòu)，基調(diào)中包含各種可以用于匹配操作的信息。基于多標(biāo)記模式，運用泛代數(shù)學(xué)研究方法，可以對模式這類有

3、限結(jié)構(gòu)的映射操作進(jìn)行深入分析和研究。 2．為了刻畫多對多的匹配，基于多標(biāo)記模式，提出了個體匹配和多價匹配的概念。利用多價匹配，可以形式化地描述多對多的模式匹配。 3．基于多標(biāo)記模式，提出了模式同態(tài)的概念，它可以用數(shù)學(xué)的方法來描述模式的多價匹配。 4．基于多價匹配和模式同態(tài)，證明了模式匹配問題與模式同態(tài)的等價性：模式匹配問題等價于尋找兩個模式之間最強的模式同態(tài)。這樣，就建立了模式匹配問題的泛代數(shù)描述框架：模式同態(tài)。

4、 由于同態(tài)是一個典型的組合優(yōu)化問題，基于模式同態(tài)，論文首次將模式匹配問題形式化為一個組合優(yōu)化問題，得到模式匹配的算法模型?；谀Ｊ狡ヅ涞乃惴Ｐ?，論文進(jìn)行了模式匹配算法的研究： 1．將多標(biāo)記模式實例化為一種描述異構(gòu)模式的元模型，稱之為多標(biāo)記圖模型，它可以很好地描述模式中元素的語義性質(zhì)，以及元素之間的各種關(guān)系。多標(biāo)記圖模型實質(zhì)上是一種基于圖模型的語義數(shù)據(jù)模型。 2．由于使用多標(biāo)記圖模型來表示各種異構(gòu)的模式，因此，自

5、然而然地將模式匹配問題歸約為多標(biāo)記圖同態(tài)，即多標(biāo)記圖匹配的問題，它是經(jīng)典的組合優(yōu)化問題。 3．基于對比模型，研究了多標(biāo)記圖相似性計算方法，建立了基于對比模型的多標(biāo)記圖匹配的優(yōu)化目標(biāo)函數(shù)。由此，綜合已有的模式相似性度量方法，可以設(shè)計各種優(yōu)化搜索算法來求解模式匹配問題。 4．多空間搜索是解決NP難解問題的有效的算法設(shè)計思想，論文采用貪婪策略和局部搜索技術(shù)，設(shè)計了基于多空間搜索的多空間匹配算法。使用若干模式樣本對多空間匹配算法