支持帶有通配符的字符串匹配算法.pdf

1、帶有通配符的字符串匹配問題已成為諸多領(lǐng)域的研究熱點(diǎn)，例如生物信息學(xué)、數(shù)據(jù)庫系統(tǒng)中的SQL查詢、搜索引擎的文本索引、文件名查找、網(wǎng)絡(luò)入侵檢測等領(lǐng)域。然而，帶有通配符的查詢模式在更好的滿足用戶查詢需求的同時(shí)，也使得查詢處理過程變得更加復(fù)雜，如何高效地支持帶有通配符的字符串匹配問題面臨著很大的挑戰(zhàn)。
　　目前，關(guān)于通配符的匹配問題大多都是針對在線數(shù)據(jù)搜索，基于索引的離線查詢方法較少，并且這些算法中索引占用的存儲空間較大，對于通配符的定義

2、也有所限制，不具有普遍性。本文主要研究查詢模式串中含有可代表任意長度字符串的通配符“*”以及可代表任意一個(gè)字符的通配符“？”時(shí)的字符串匹配問題，包括精確字符串匹配問題以及近似字符串匹配問題。由于gram索引結(jié)構(gòu)在空間大小以及查詢效率上的優(yōu)勢，本文首次將gram索引結(jié)構(gòu)用于帶通配符的字符串匹配問題。
　　首先，本文對現(xiàn)有的支持帶有通配符的字符串匹配技術(shù)進(jìn)行了概述。通過對現(xiàn)存算法的對比分析，本文提出了基于gram索引結(jié)構(gòu)的支持通配符的

3、精確字符串匹配算法。通過將帶有通配符的查詢模式串分解為若干不含通配符的查詢片段，成功的將帶有通配符的復(fù)雜查詢問題轉(zhuǎn)化為不含通配符的精確子串查詢問題，并且在片段查詢的過程中運(yùn)用了長度過濾、位置過濾以及計(jì)數(shù)過濾等過濾方法，提高了查詢速度。然后，本文對精確匹配算法進(jìn)行了擴(kuò)展，使其能夠適用于近似匹配問題。在查詢片段中利用近似匹配常用的鴿巢原理過濾法，可以排除部分不是查詢結(jié)果的字符串。但是此方法只適用于編輯距離閾值k較小的情況，并且在帶有通配符的