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

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

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

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

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

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