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

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

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

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