編輯距離下具有間隙約束的近似模式匹配.pdf

1、模式匹配問(wèn)題在計(jì)算機(jī)科學(xué)中出現(xiàn)的最早且人們對(duì)它的研究也最廣泛，隨著需要處理的文本規(guī)模越來(lái)越大，在文本中進(jìn)行的搜索越來(lái)越復(fù)雜，模式和文本之間可以有某些細(xì)小不同的近似模式匹配問(wèn)題得到了廣泛的應(yīng)用。但對(duì)具有間隙約束的近似模式匹配問(wèn)題的研究目前尚未成熟，因此，論文針對(duì)此問(wèn)題展開(kāi)研究和實(shí)現(xiàn)。
　　論文將目標(biāo)問(wèn)題分成兩個(gè)方面進(jìn)行具體的研究以及方法實(shí)現(xiàn)。一是字符串的近似匹配問(wèn)題，二是模式之間存在間隙約束的匹配問(wèn)題。在字符串的近似匹配方面，論文首

2、先對(duì)基本字符串匹配的一些相關(guān)知識(shí)進(jìn)行了介紹，包括字符串匹配的概念以及傳統(tǒng)字符串匹配的方法。接著對(duì)近似串的匹配方法進(jìn)行了研究，包括：動(dòng)態(tài)規(guī)劃方法、基于自動(dòng)機(jī)的方法、位并行方法以及基于文本過(guò)濾的方法。通過(guò)對(duì)這四種方法進(jìn)行研究和對(duì)比，本文將動(dòng)態(tài)規(guī)劃方法作為近似串匹配的主要方法，將編輯距離模型作為衡量字符串相似度的模型，并對(duì)編輯距離矩陣的建立以及字符串之間編輯距離的計(jì)算進(jìn)行了方法實(shí)現(xiàn)。在具有間隙約束的模式匹配方面，本文首先對(duì)文本串進(jìn)行了預(yù)處理，

3、將文本串保存為純文本文檔的形式，利用Lucene對(duì)純文本文檔建立倒排索引的方式為文本串中的每個(gè)字符串建立索引，這種索引包含了該字符串所有的出現(xiàn)位置及出現(xiàn)次數(shù)，然后在索引基礎(chǔ)上通過(guò)Lucene中SpanNearQuery的搜索機(jī)制對(duì)具有間隙約束的模式串進(jìn)行搜索。此方法摒棄了普通順序方法因文本過(guò)大而造成的匹配時(shí)間代價(jià)高的缺陷，大大提高了匹配效率。
　　最后，論文將此方法和普通的順序匹配算法進(jìn)行了對(duì)比，在保證相同文本、相同模式和相同匹配