基于編輯距離的字符串模式匹配算法研究

《基于編輯距離的字符串模式匹配算法研究》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫(kù)。

1、基于編輯距離的字符串模式匹配算法研究第1章緒論1.1研究背景及其意義隨著人類社會(huì)的不斷快速發(fā)展，科學(xué)信息技術(shù)同樣產(chǎn)生了翻天覆地的變化，大量的大規(guī)模數(shù)據(jù)產(chǎn)生于人類社會(huì)中的各種不同的應(yīng)用領(lǐng)域。然而，由于大規(guī)模數(shù)據(jù)都具有高度自治性，從而導(dǎo)致了不同應(yīng)用領(lǐng)域之間的數(shù)據(jù)異構(gòu)性。因此，大規(guī)模數(shù)據(jù)間的相互轉(zhuǎn)換操作就顯得尤為重要。而隨著Inter的不斷迅速發(fā)展，就更加需要緊密聯(lián)系不同應(yīng)用領(lǐng)域中的大規(guī)模數(shù)據(jù)，而數(shù)據(jù)集成作為核心的方法，能夠?qū)崿F(xiàn)不同應(yīng)用領(lǐng)域中大規(guī)模數(shù)據(jù)的共享。模式匹配起源于對(duì)模式集問題的研究，早期模式匹配工作就是為了給模式

2、集成提供服務(wù)。模式集成是從給定的一組獨(dú)立開發(fā)的模式中構(gòu)造一個(gè)全局視圖的過程。由于模式是單獨(dú)開發(fā)的，因此不同的模式使用不同的結(jié)構(gòu)和術(shù)語(yǔ)。因此，模式集成的第一步就是確認(rèn)這些模式間的關(guān)系，這就需要模式匹配操作。當(dāng)這些關(guān)系被確認(rèn)后，匹配的元素就可以統(tǒng)一的出現(xiàn)在集成模式中。隨著模式集成問題的不斷研究和發(fā)展變化，模式匹配的應(yīng)用已經(jīng)開始轉(zhuǎn)變到數(shù)據(jù)倉(cāng)庫(kù)領(lǐng)域中。數(shù)據(jù)倉(cāng)庫(kù)是一種支持決策的數(shù)據(jù)庫(kù)，它的數(shù)據(jù)是通過提取一組數(shù)據(jù)源中的數(shù)據(jù)。而在這個(gè)提取過程，就是要將數(shù)據(jù)源的數(shù)據(jù)按照一定標(biāo)準(zhǔn)轉(zhuǎn)換為數(shù)據(jù)倉(cāng)庫(kù)的數(shù)據(jù)。近些年來(lái)，電子商務(wù)[1]的出現(xiàn)，對(duì)

3、于模式匹配的研究更進(jìn)了一步。模式匹配進(jìn)一步應(yīng)用到電子商務(wù)的信息轉(zhuǎn)換過程中。在電子商務(wù)過程中，交易雙方要頻繁交換描述商務(wù)交易的信息。任何一個(gè)交易方都使用自己的信息模式。不同的信息模式可能包含不同的名稱、不同的數(shù)據(jù)類型，允許值的范圍也不同。信息轉(zhuǎn)換問題實(shí)際上是不同消息模式轉(zhuǎn)換的問題，而不同消息模式轉(zhuǎn)換問題實(shí)際上就是一個(gè)模式匹配問題。模式匹配(Schemamatching)就是找出兩種模式成員之間上的語(yǔ)義關(guān)系而進(jìn)行的操作。在模式匹配中，輸入?yún)?shù)是兩個(gè)模式，輸出參數(shù)是匹配結(jié)果，即兩種模式中元素之間的某種映射關(guān)系，而每一種匹配

4、結(jié)果都表示在兩種模式中的某些元素存在邏輯上的對(duì)應(yīng)關(guān)系。......1.2國(guó)內(nèi)外研究現(xiàn)狀近些年來(lái)，模式匹配作為大規(guī)模數(shù)據(jù)處理中的基礎(chǔ)性問題受到了全球的普遍關(guān)注。匹配是對(duì)模式進(jìn)行處理的一個(gè)基本操作，該操作將模式中的每一個(gè)元素找出與另一個(gè)模式存在語(yǔ)義對(duì)應(yīng)關(guān)，即映射。因此，模式匹配工作仍然是以人工的為主的方式進(jìn)行匹配。因此需要找出一種可以應(yīng)用于不同的數(shù)據(jù)模型和應(yīng)用領(lǐng)域，通用范圍廣、自動(dòng)化程度高的一種綜合模式匹配方法。模式匹配系統(tǒng)應(yīng)用在很多領(lǐng)域中，這是模式匹配原型系統(tǒng)一大特點(diǎn)，例如XML文檔的轉(zhuǎn)換和XML模式聚類等領(lǐng)域。如XM

5、L文檔自動(dòng)轉(zhuǎn)換系統(tǒng)[15]是應(yīng)用在E-Business領(lǐng)域的一個(gè)典型系統(tǒng)是的Xtra[16]系統(tǒng)。Xtra系統(tǒng)中在進(jìn)行文檔轉(zhuǎn)換過程，定義了一系列模式轉(zhuǎn)換操作集合、一個(gè)評(píng)價(jià)這些操作集合的代價(jià)模型、一個(gè)記錄算法來(lái)記錄兩個(gè)模式轉(zhuǎn)換中的有效操作順序集合。然后，使用XSLTGenerator將腳本轉(zhuǎn)換成XSLT，再使用一個(gè)XSLTExecutor,將源XML文檔和與生成的XSLT合成起來(lái)，最終生成目標(biāo)XML文檔。在Cupid、A、S-Match[17,18]、XClust、ARTEMIS[19]等模式匹配系統(tǒng)中，采用了多種匹配

6、策略，如名稱匹配、結(jié)構(gòu)匹配和上下文匹配等，同時(shí)也考慮到了其它方面的模式和實(shí)例信息，以此期望得到更優(yōu)的匹配結(jié)果。其中，最具有代表性的是Cupid模式匹配算法。Cupid系統(tǒng)是基于名稱、數(shù)據(jù)類型和與約束的語(yǔ)言學(xué)匹配。在匹配過程中，將轉(zhuǎn)換成為一顆標(biāo)記樹進(jìn)行有底到頂?shù)谋闅v匹配，對(duì)成員之間的結(jié)構(gòu)相似度后加權(quán)得到結(jié)構(gòu)相似系數(shù)ssim；最后，通過加權(quán)值公式(1-1)來(lái)進(jìn)行模式匹配。.......第2章模式匹配技術(shù)的描述與分類近年來(lái)，模式匹配己成為數(shù)據(jù)庫(kù)研究的一個(gè)熱點(diǎn)的，它的目標(biāo)是尋找兩個(gè)或多個(gè)模式的元素之間語(yǔ)義上的對(duì)應(yīng)關(guān)系。在模式

7、集成、異構(gòu)數(shù)據(jù)源集成、語(yǔ)義查詢處理、數(shù)據(jù)倉(cāng)庫(kù)、電子商務(wù)等領(lǐng)域都有著廣泛的研究。2.1模式匹配概述模式匹配[22]是在作為輸入的模式中有對(duì)應(yīng)語(yǔ)義關(guān)系的元素間產(chǎn)生一個(gè)映射。模式匹配的目標(biāo)是尋找兩個(gè)或多個(gè)模式的元素之間語(yǔ)義上的對(duì)應(yīng)關(guān)系。而匹配結(jié)果元素包含有以下幾種情況，即是空、是一個(gè)匹配元素、多個(gè)匹配元素或者多個(gè)模式元素可能會(huì)對(duì)應(yīng)于一個(gè)或多個(gè)匹配元素，模式元素匹配結(jié)果并不是唯一的。而通常情況下的模式匹配關(guān)系的基數(shù)的情況也并不是唯一的，其包含有1:1，1:N，N:1，N:M四種匹配關(guān)系基數(shù)，而元素匹配的結(jié)果是1:1，1:N，

8、N:1這三種情況。目前，大多的匹配研究工作都是圍繞1:1的關(guān)系基數(shù)來(lái)進(jìn)行的。......2.2模式匹配的分類基于模式的匹配又被分為元素匹配和結(jié)構(gòu)匹配。再往下，元素匹配可分為基于語(yǔ)言學(xué)特征的匹配(Linguisticmatch)和基于約束的匹配(Constraintbased)，則結(jié)構(gòu)匹配下面只有一個(gè)基于約束的匹配。基于實(shí)例的匹配被劃為元素匹配，