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

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

1、基于編輯距離的字符串模式匹配算法研究第1章緒論1.1研究背景及其意義隨著人類社會的不斷快速發(fā)展，科學信息技術(shù)同樣產(chǎn)生了翻天覆地的變化，大量的大規(guī)模數(shù)據(jù)產(chǎn)生于人類社會中的各種不同的應(yīng)用領(lǐng)域。然而，由于大規(guī)模數(shù)據(jù)都具有高度自治性，從而導致了不同應(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ù)的共享。模式匹配起源于對模式集問題的研究，早期模式匹配工作就是為了給模式

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

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

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

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

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

7、集成、異構(gòu)數(shù)據(jù)源集成、語義查詢處理、數(shù)據(jù)倉庫、電子商務(wù)等領(lǐng)域都有著廣泛的研究。2.1模式匹配概述模式匹配[22]是在作為輸入的模式中有對應(yīng)語義關(guān)系的元素間產(chǎn)生一個映射。模式匹配的目標是尋找兩個或多個模式的元素之間語義上的對應(yīng)關(guān)系。而匹配結(jié)果元素包含有以下幾種情況，即是空、是一個匹配元素、多個匹配元素或者多個模式元素可能會對應(yīng)于一個或多個匹配元素，模式元素匹配結(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ù)來進行的。......2.2模式匹配的分類基于模式的匹配又被分為元素匹配和結(jié)構(gòu)匹配。再往下，元素匹配可分為基于語言學特征的匹配(Linguisticmatch)和基于約束的匹配(Constraintbased)，則結(jié)構(gòu)匹配下面只有一個基于約束的匹配?；趯嵗钠ヅ浔粍潪樵仄ヅ?，