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

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

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

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