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

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

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

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