應用Q-gram命中特征優(yōu)化的近似串匹配算法

　　近似串匹配（ Approximate String Matching）是允許有“錯誤”發(fā)生的字符串匹配，它在文本串中查找所有與模式串之間錯誤數(shù)不大于一定閾值的所有匹配串。字符串間的錯誤數(shù)可采用編輯距離、漢明距離、最長公共子串等表示。編輯距離是指把一個字符串經(jīng)過插入、修改或刪除3種編輯操作轉(zhuǎn)變成字符串所要進行的最小操作次數(shù)，常用表示。近似串匹配技術(shù)在眾多研究領(lǐng)域都有廣泛的應用，如文本檢索、生物信息學、信號處理和模式識別等。

　　基于Off-Iine模式的過濾算法是一種采用先過濾冉驗證的二階段近似串匹配方法。過濾算法因采用過濾技術(shù)能在前期快速去除大量文本區(qū)域，適合Off-line模式下的大文本庫匹配。目前，過濾算法可歸為二類：精確匹配子串法和近似匹配子串法。精確匹配子串法通過定位無錯誤的模式串子串進行過濾。

　　本研究主要解決的是在大文本庫中快速查找與模式串間錯誤率不大于的所有匹配串的問題。文中將結(jié)合KS算法和q-gram命中特征，設(shè)計一個新的無損過濾算法，擬通過犧牲一定過濾時間來換取較大過濾效率的提升，最終達到提高算法整體匹配速度的目的。
?