王曉霞，孫德才

（渤海大學 遼寧 錦州 121013）

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

王曉霞，孫德才

（渤海大學 遼寧 錦州 121013）

近似串匹配是文本檢索、生物信息學和信號處理等領域的研究基礎。為提高近似串匹配速度，采用分塊的方法從匹配串中提取了新的q-gram命中特征，結合新特征提出了一種新的近似串匹配算法。實驗數(shù)據(jù)表明新算法消耗了少量的過濾時間就獲得了較高的過濾效率，結果顯示新算法在各種匹配錯誤率下的匹配速度一直比經(jīng)典的SWIFT算法快。

近似串匹配；過濾算法；q-gram過濾；q元語法

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

基于Off-line模式的過濾算法[3-4]是一種采用先過濾再驗證的二階段近似串匹配方法。過濾算法因采用過濾技術能在前期快速去除大量文本區(qū)域，適合Off-line模式下的大文本庫匹配。目前，過濾算法可歸為二類：精確匹配子串法和近似匹配子串法。精確匹配子串法通過定位無錯誤的模式串子串進行過濾，如文獻[5-11]。而近似匹配子串法通過定位允許有錯誤的模式串子串進行過濾，如文獻[12]。精確匹配子串法中因子串匹配過程簡單、過濾速度快而得到廣泛研究。如文獻[5]把模式串分成部分，在文本串中至少出現(xiàn)s部分且位置正確的文本區(qū)域才被驗證，這里稱為KS算法。Burkhardt對Jokinen和 Ukkonen[8]的工作進行了改進，提出一個近似串局部匹配算法QUASAR[7]。Rasmussen從基因檢索算法FASTA中受到了啟發(fā)提出一個近似串局部匹配算法SWIFT[9]。

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

1 基礎知識

KS算法的核心思想是把模式串分割成k+s個不重疊的子串，如果文本串中存在與模式串編輯距離不大于k的匹配串，那么文本串中一定存在至少s個完整匹配的模式串子串。該過濾準則最早由Wu和Manber提出，其算法中采用了s=1，這里稱為KS1算法，具體過濾定理參考文獻[5]。

Q-gram是長度為q的字符串，其位置用其首字符在模式串或文本串中的偏移量表示。Q-gram拆分方法是在串首放置一個長度為q的移動窗口，每次從窗口中提取一個qgram，根據(jù)窗口的移動距離d不同切分的方式也不同。Q-gram索引[13-14]主要包括2部分：詞匯表和倒排列表。詞匯表是q-gram項的集合，常采用哈希表或B*樹。每個q-gram項后連有一個存儲該索引項在文本中出現(xiàn)的地址集合，稱為倒排列表。

最早提出基于q-gram命中的過濾定理的是Jokinen和Ukkonen，該基礎過濾定理描述了一個存在匹配串的文本區(qū)域具有的最基本的q-gram命中特征，具體定理參考文獻[8]。

錯誤率描述一個字符串與模式串間的近似程度，定義為編輯距離與模式串長度的比值，。匹配錯誤率（Matching Error Ratio）是近似串匹配中界定哪些是匹配串的參數(shù)，匹配串是與模式串之間錯誤率不大于匹配錯誤率的字符串。

過濾效率（Filtration efficiency）是描述算法過濾階段拋棄無關片段的能力，定義為fe=（n-nf）/（n-nt），其中n表示整個文本庫的長度，即，nf表示過濾算法在本次匹配中未過濾掉的文本區(qū)域的總長度，而表示本次匹配文本庫中真實存在的所有匹配串的長度總和。

2 新過濾特征提取

提取新過濾特征時為便于表達，這里設q為q-gram索引中q-gram項的長度，e為過濾算法的匹配錯誤率，則匹配串與模式串P間的最大編輯距離k可通過計算。

定理1對字符串S進行任意分區(qū)，并任選一個編輯不動點（任二字符間），如圖1。如在字符串S上任意位置施加k次編輯操作后（分區(qū)邊界不隨字符移動），則任意分區(qū)內(nèi)原來的q-gram數(shù)量減少的數(shù)目都不超過kq。

圖1 字符串分區(qū)示意

證明以下分2種情況進行討論：

1）包含不動點的分區(qū)si：si分區(qū)內(nèi)不論在不動點的左或右，一個修改操作最多改變個q-gram；一個刪除操作最多改變q個q-gram，如編輯發(fā)生在不動點左側則左側有新的qgram被移入，如在右側則右側有新的移入，但新的移入不會影響原來的q-gram；一個插入操作最多改變個q-gram，同時引起q-1個q-gram外移（編輯發(fā)生在不動點左側則左移出，在右側則右移出），即至多影響q個q-gram。因此，si分區(qū)內(nèi)k個編輯操作最多影響kq個q-gram。

2）不包含不動點的分區(qū)sj：sj設分區(qū)在不動點的左側，如此影響sj區(qū)q-gram數(shù)的編輯操作或發(fā)生在sj區(qū)內(nèi)，或發(fā)生在sj區(qū)的右側與不動點之間。如全發(fā)生在sj區(qū)內(nèi)則與1）情況類似，最多影響kq個q-gram；如編輯發(fā)生在sj區(qū)的右側與不動點之間，修改操作不影響sj區(qū)內(nèi)的q-gram，一個插入操作最多使得原sj區(qū)內(nèi)的一個q-gram左移出，一個刪除操作最多使得區(qū)sj內(nèi)的一個q-gram右移出。綜上所述，影響最多的是編輯操作發(fā)生在區(qū)內(nèi)，因此原sj區(qū)經(jīng)過編輯操作后最多影響kq個q-gram。分區(qū)的位置在不動點右側情況類似，這里不再討論。

結合情況1）和2）可知，定理1證畢。

定義1對模式串P進行連續(xù)但不重疊的等大小分割，把P分割成k+1個模式塊，分別稱為P0，P1，…Pk，則前k塊的長度，這里稱為完整模式塊，最后一個pk塊的長度為l，l≥b，稱為尾模式塊。Pi+1塊為Pi塊的右連續(xù)塊，對Pi+1塊向左擴展 q-1個字符得到 P（i+1）塊，稱 P（i+1）塊為Pi+1塊的模式修正塊。稱 P0，P1，…，Pi，P（i+1），…Pk為模式塊序列，如圖2。如模式串P中一個q-gram項Q的首字符落在模式塊Pj中，則稱為Q在模式塊Pj內(nèi)。， 0≤j＜i。從串向右進行k-i次擴展則得到，，…，塊，且

圖2 模式串分割與文本塊序列

定義2設Pi，0≤i≤k是模式串P根據(jù)定義1進行分塊后的第i個模式塊，設是文本串的一個子串，且串和Pi完全匹配（相等），則稱塊為Pi塊的一個命中文本塊。在T中從向左進行i次擴展則得到，，…，塊，且 。則從塊首字符向左拓展k個字符位置開始到塊尾字符向右擴展k個字符位置結束的區(qū)域稱為模式串P的一個潛在匹配區(qū)域。塊為塊的右連續(xù)串，把串向左擴展q-1個字符得到塊（對應 P（j+1）），稱為塊的文本修正塊。稱為模式串P的P0，P1，…，Pi，P（i+1），…，Pk的一個對應文本塊序列，如圖2。文本串T中一個q-gram項Q的首字符落在模式塊Tj中，則稱為Q在文本塊內(nèi)。

情況a）：當，1）且j=i時，Tji塊內(nèi)與Pj塊內(nèi)共享的q-gram項數(shù)等于b-q+1；2）且0≤j＜i或j=（i+1）或i+1＜j＜k時，塊內(nèi)Pj塊內(nèi)共享的q-gram項數(shù)不小于且j=k時，塊內(nèi)與Pj塊內(nèi)共享的q-gram項數(shù)不小于t，如k≠i+1則t=l+1-（k+1）q，如則t=l-kq。

情況a）：當0≤i＜k，表明命中文本塊不是尾文本塊，即i≠k，此時，

2）且0≤j＜i或j=（i+1）或i+1＜j＜k時，因命中文本塊非尾文本塊，所以滿足條件的模式塊Pj除第i+1塊進行了左擴q-1字符外其他長度都為b，長度用表示，塊內(nèi)共有個 q-gram。又據(jù)基礎過濾定理可知，Tji塊內(nèi)和Pj塊內(nèi)共享的qgram項數(shù)不小于個。

3）且j=k時，表示命中文本塊非尾文本塊，要計算qgram數(shù)目的為尾文本塊。因尾文本塊不能進行右擴展，如k≠i+1時，塊長為l，內(nèi)含l-q+1個q-gram。根據(jù)基礎過濾定理可知塊內(nèi)與Pk塊內(nèi)共享的q-gram項數(shù)不小于l+1-（k+1）q。如k≠i+1時，則尾文本塊剛好也是第i+1塊，串長為l+q-1，內(nèi)含l個q-gram。根據(jù)基礎過濾定理可知塊內(nèi)與Pk塊內(nèi)共享的q-gram項數(shù)不小于l-kq。

情況b）：當i=k，表明命中文本塊為尾文本塊，且不存在第i+1塊，此時，

結合情況a）和b）可知定理2成立，證畢。

3 用q-gram命中特征改進的KS1算法

定理2描述了一個含有匹配串的文本區(qū)域具有的qgram命中特征，包括：1）包含至少一個完全匹配的模式塊；2）模式塊與對應文本塊間共享的q-gram數(shù)目滿足一定的閾值；3）文本塊序列構成的文本區(qū)域與模式串間總共享q-gram數(shù)目也滿足一定的閾值。反過來說，一個滿足上述特征的文本區(qū)域內(nèi)包含匹配串的概率也非常高。本節(jié)將介紹一個用定理2新特征優(yōu)化的KS1算法 （Counter KS，CKS），簡稱CKS算法，用于解決大文本庫的近似串全局匹配問題。該算法包括文本庫預處理、輸入、過濾、驗證和輸出5部分。文本庫預處理中采用q-gram索引結構。輸入階段需要給定模式串和匹配錯誤率。過濾階段包括KS1過濾和q-gram命中過濾，是本文算法的核心，將進行詳細介紹。驗證階段采用Smith-Waterman算法[15]進行驗證。輸出階段則輸出匹配結果。

過濾階段的主要任務是盡可能地用過濾條件剔除那些一定不包含匹配串的文本區(qū)域。好的過濾器能在較短的過濾時間內(nèi)拋棄大量的無關文本區(qū)域。本文的CKS算法過濾器包含KS1過濾器和q-gram命中數(shù)過濾器，二個過濾器的過濾過程是互相交叉的。CKS算法過濾階段的主要思路是：首先采用KS1過濾器拋棄那些不含命中文本塊的文本區(qū)域，然后用q-gram命中數(shù)除去那些雖然存在命中文本塊但命中數(shù)目不滿足要求的文本區(qū)域。這里分配一個長度為的一位數(shù)組H來存儲這些命中位置信息。如數(shù)組中H[i]=1則代表P中存在q-gram命中T中第i個位置，相反值為0時代表無命中。數(shù)組H中每個元素因只需存儲1或0，所以可用一個二進制位存儲，且每32個二進制位為一組。CKS過濾器的過濾過程如下：

步驟2）處理q-gram項Qj，從q-gram索引中取出Qj的倒排列表，并依次讀取倒排列表中的q-gram項地址，同時置H數(shù)組。例如，t是倒排列表中一個q-gram地址，即Qj命中了文本的位置t，即置H[t]=1。當Qj的倒排列表處理完畢后，j=j+ 1，轉2）處理下一個q-gram。直到模式串的所有q-gram都處理完畢時，轉3）。

步驟3）按定義1和定義2在邏輯上把模式串在分割成k+1個連續(xù)但不重疊的模式塊P0，P1，…，Pk。從0到k依次處理每個模式塊Pi，0≤i≤k，一個模式塊的處理過程如4）。

步驟4）處理模式塊Pi，首先從模式串中提取出Pi塊的內(nèi)容，對其進行滑動距離為q的q-gram拆分。最后可能剩余不足長度q的剩余串，此時從Pi塊后向前取q個字符構成一個q-gram項，最后得到模式塊Pi的所有q-gram項，轉5）。

步驟5）為確定模式塊Pi在文本串T中所有的命中文本塊，首先按順序依次從q-gram索引中提取出各q-gram的倒排列表；然后按倒排列表長度從小到大進行排序；接著從長度小到大順序依次對倒排列表進行地址交運算（以第一個qgram項為基地址）。如運算過程中列表出現(xiàn)空集，則可確定模式塊Pi在文本串中無命中文本塊，i=i+1轉步驟4），否則將得到模式塊Pi在文本串T中的命中文本塊集合。最后依次處理集合中的每一個命中文本塊，處理過程如6）。

步驟6）處理模式塊Pi命中的文本塊，首先按定義1和定義 2進行擴展，得到對應的文本塊序列；然后訪問q-gram命中數(shù)組H統(tǒng)計各個文本塊中的q-gram命中數(shù)目。由于H中每32個二進制位為一組，每個二進制位代表一個q-gram是否命中，所以只需統(tǒng)計文本塊范圍內(nèi)二進制位中1的個數(shù)。CKS采用快速算法處理文本塊的組，時間復雜度與1個數(shù)有關，而與二進制位數(shù)無關。對于完整的組直接處理，而不完整的組則要輔以移位和取低位等運算。如某個文本塊內(nèi)的q-gram命中數(shù)目不滿足定理2條件，則該命中無效，轉6）處理下一個命中。如每個文本塊內(nèi)q-gram命中都符合要求則轉8）。

步驟8）i=i+1，轉4）處理下一個模式分塊，直到所有模式塊都被處理完畢時，算法結束。

4 實驗

4.1 實驗環(huán)境

文中實驗數(shù)據(jù)來源于美國國家生物技術信息中心NCBI的人類不同完整基因序列 （ftp.ncbi.nih.gov//repository/Uni-Gene/Homo_sapiens/Hs.seq.uniq.gz），共約164 MB基因序列文本，共123，252個完整人類不同基因序列。因SWIFT，QUASAR中的值都為11，這里也取11。文中實驗中參加對比的算法有 KS1[5]、QUASAR[7]、SWIFT[9]以及本文的 CKS。QUASAR算法中的塊大小設置為，SWIFT算法中的Bin大小設置為。本實驗的模式串集合為500個長度為2，000基因子序列。文中所有實驗都在同一硬件和軟件環(huán)境下進行的，實驗硬件環(huán)境是：處理器AMD X4 630和主存4 GB；實驗軟件環(huán)境是：WINDOWS XP SP3和VISUAL C++6.0。

4.2 CKS算法性能表現(xiàn)

為對比分析各個算法在不同匹配錯誤率下的性能差異，實驗中對模式串集分別采用KS1、QUASAR、SWIFT和CKS算法進行批量匹配實驗，匹配錯誤率分別采用 0，0.005，0.01，0.02，0.03，0.04。實驗中統(tǒng)計了不同匹配錯誤率下各算法的過濾時間、過濾效率、驗證時間和匹配時間的平均值，如圖3所示。

圖3 算法性能對比

從圖3（a）的平均過濾時間對比可知，CKS算法的過濾時間消耗要少于SWIFT算法，接近QUASAR，但要多于KS1算法。KS1算法的過濾時間最短，因其過濾過程最簡單。從圖3（b）的平均過濾效率對比可知，CKS算法在匹配錯誤率較低時與SWIFT、KS1等算法的過濾效率接近。當匹配錯誤率較高時，CKS算法的過濾效率最高，這是因為其過濾條件的選擇更能體現(xiàn)匹配區(qū)域特征。從圖3（c）的平均驗證時間對比可知，KS1、SWIFT和CKS算法在匹配錯誤率較低時都較好，且當匹配錯誤率升高時，CKS、SWIFT逐漸占據(jù)優(yōu)勢。從總體而言，CKS算法因其過濾效率較高而使其驗證時間都較短。從圖3（d）的平均匹配時間對比可知，QUASAR算法的匹配時間一直都較長；KS1算法當匹配錯誤率為0時匹配速度最快，而當匹配錯誤率較高時效果變差；SWIF算法當匹配錯誤率較低時因過濾時間較長而總時間較長，而當匹配錯誤率較高時速度逐漸變快。CKS算法的匹配時間都較穩(wěn)定性，算法除精確匹配要比KS1算法差一點外，在其他匹配錯誤率下都較快，這主要源于CKS算法的過濾時間較短而驗證時間又不太長。根據(jù)以上分析可得出如下結論：

1）CKS算法的整體性能穩(wěn)定，對匹配錯誤率的改變不敏感，相對于其他算法更具通用性。

2）CKS算法除進行精確匹配外，相對于其他算法其匹配速度一直都最快。

5 結論

文中為解決從大文本庫中查找模式串的所有匹配串問題，提出了一種用q-gram命中特征優(yōu)化的近似串匹配算法。文中給出了q-gram命中特征的提取過程和新算法的匹配詳細流程。最后實驗數(shù)據(jù)表明改進算法通過使用新過濾特征在較短的過濾時間內(nèi)就獲得了較高的過濾效率，加快了總的匹配速度。理論分析和實驗結果顯示，新算法的整體性能較好，穩(wěn)定性高，適合各種匹配錯誤率下的近似匹配。

雖然新算法提高了算法的過濾效率，但算法還存在精確匹配效果不好、隨匹配錯誤率逐漸升高逐步退化等問題。文中下一步的工作將繼續(xù)研究減少過濾時間，提高過濾效率等相關方法和技術，并進一步優(yōu)化本文算法。

[1]Navarro G.A guided tour to approximate string matching[J].ACM Computing Surveys，2001，33（1）:31-88.

[2]Levenshtein V.Binary codes capable of correcting deletions，insertions，and reversals[J].Soviet Physics Doklady，1966，10（8）:707-710.

[3]Burkhardt S.Filter algorithms for approximate string matching:[D].Saarland:Department of Computer Science，Saarland University，2002.

[4]Hu HJ，Zheng K，Wang XL，et al.GFilter:A General Gram Filter for String Similarity Search[J].IEEE Transactions on Knowledge and Data Engineering，2015，27（4）:1005-1018.

[5]Wu S，Manber U.Fast text searching allowing errors[J].Communications of the ACM，1992，35（10）:83-91.

[6]Chang YI，Chen JR，Hsu MT.A hash trie filter method for approximate string matching in genomic databases[J].Applied Intelligence，2010，33（1）:21-38.

[7]Burkhardt S，Crauser A，F(xiàn)erragina P，et al.Q-gram based database searching using a suffix array[C].//Proceedings of the AnnualInternationalConference on Computational Molecular Biology，RECOMB 99.New York，USA:ACM，1999:77-83.

[8]Jokinen P，Ukkonen E.Two algorithms for approximate string matching in static texts[C].//16th International Symposium Proceedings on Mathematical Foundations of Computer Science.Berlin，Germany:Springer-Verlag，1991: 240-248.

[9]Rasmussen KR，Stoye J，Myers EW.Efficient q-gram filters for finding all epsilon-matches over a given length[J].Journal of Computational Biology，2006，13（2）:296-308.

[10]Lu，CW，Lu CL，and Lee，RCT.A new filtration method and a hybrid strategy for approximate string matching[J].Theoretical Computer Science，2013，481（0）:9-17.

[11]Egidi L，Manzini G.Better spaced seeds using Quadratic Residues[J].Journal of Computer and System Sciences，2013，79（7）:1144-1155.

[12]Baeza-YatesR， Navarro G.Fasterapproximate string matching[J].Algorithmica，1999，23（2）:127-158.

[13]Navarro G，Baeza-Yates R，Sutineny E，et al.Indexing methods for approximate string matching[J].IEEE Data Engineering Bulletin，2001，24（4）:19-27.

[14]Navarro G，Baeza-yates R.A practical q-gram index for text retrieval allowing errors[J].CLEI Electronic Journal，1998，1（2）:1-16.

[15]Smith TF， Waterman MS， Identification ofcommon molecular subsequences[J].Journal of Molecular Biology，1981，147（1）:195-197.

圖4 不同的λk所對應的摻鉺光纖光源可靠度曲線

4 結論

文中針對光纖陀螺用摻鉺光纖光源高可靠性、長壽命的特點提出了無失效數(shù)據(jù)下基于貝葉斯理論的可靠性評估方法，通過分析摻鉺光纖光源失效模式給出了威布爾分布作為其壽命分布，結合先驗信息和少量的試驗數(shù)據(jù)估計出了可靠性模型參數(shù)，并通過仿真分析說明所得摻鉺光纖光源可靠性模型是合理的，且算法具有較好的穩(wěn)健性。為實際應用中光纖陀螺及慣導系統(tǒng)的可靠性評估提供了依據(jù)。但處理先驗信息相對保守，有待進一步研究得出更精確的可靠性模型。

參考文獻：

[1]王瑞.應用于高精度光纖陀螺的摻鉺光纖光源研究[D].哈爾濱：哈爾濱工程大學，2008.

[2]金少華.電工產(chǎn)品可靠性評估方法與貝葉斯理論的應用[D].天津：河北工業(yè)大學，2002.

[3]劉海濤，張志華.威布爾分布無失效數(shù)據(jù)的貝葉斯可靠性分析[J].系統(tǒng)工程理論與實踐，2008（11）:103-108.

[4]李承劍，慕曉冬，張華鵬.基于貝葉斯理論的航空電子設備可靠性評估[J].火力與指揮控制，2009（1）:139-140.

[5]馬靜，王大海，晁代宏，陳淑英.基于關鍵器件的光纖陀螺可靠性評估[J].中國慣性技術學報，2009（5）:618-621.

[6]姚淼，宋家友，張俊麗.基于貝葉斯理論的ATS測量不確定度評定[J].計算機測量與控制，2015，23（6）：2053-2055.

Approximate string matching algorithm optimized with q-gram hit features

WANG Xiao-xia，SUN De-cai
（Bohai University，Jinzhou 121013，China）

Approximate string matching is a widely used in Text Retrieval，Computational Biology and Signal Processing，etc.To enhance the performance of approximate string matching，some new features based on q-gram hit are extracted from true match by using partition and a new approximate string matching algorithm based these features is proposed.The experimental results demonstrate that the proposed algorithm achieves high filtration efficiency in a short filtration time by using new features and the new algorithm's matching speed is always faster than that of SWIFT on condition of various matching error ratio.

Approximate string matching；filter algorithm；q-gram filter；q-gram

TN91

A

1674－6236（2016）15-0149-05

2016-01-16 稿件編號：201601127

教育部人文社會科學研究青年基金項目（15YJC870021；15YJC870028）；遼寧省博士科研啟動基金計劃項目（201411 38）；遼寧省教育廳科學研究項目（L2015010；L2014451）；遼寧省自然科學基金（2015020009）。

王曉霞（1977—），女，遼寧葫蘆島人，碩士，講師。研究方向：近似串匹配、近似重復檢測、入侵檢測等。