王曉霞，孫德才

（渤海大學(xué) 遼寧 錦州 121013）

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

王曉霞，孫德才

（渤海大學(xué) 遼寧 錦州 121013）

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

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

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

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

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

1 基礎(chǔ)知識(shí)

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

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

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

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

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

2 新過濾特征提取

提取新過濾特征時(shí)為便于表達(dá)，這里設(shè)q為q-gram索引中q-gram項(xiàng)的長度，e為過濾算法的匹配錯(cuò)誤率，則匹配串與模式串P間的最大編輯距離k可通過計(jì)算。

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

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

證明以下分2種情況進(jìn)行討論：

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

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

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

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

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

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

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

情況a）：當(dāng)0≤i＜k，表明命中文本塊不是尾文本塊，即i≠k，此時(shí)，

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

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

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

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

3 用q-gram命中特征改進(jìn)的KS1算法

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

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

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

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

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

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

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

步驟8）i=i+1，轉(zhuǎn)4）處理下一個(gè)模式分塊，直到所有模式塊都被處理完畢時(shí)，算法結(jié)束。

4 實(shí)驗(yàn)

4.1 實(shí)驗(yàn)環(huán)境

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

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

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

圖3 算法性能對(duì)比

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

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

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

5 結(jié)論

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

雖然新算法提高了算法的過濾效率，但算法還存在精確匹配效果不好、隨匹配錯(cuò)誤率逐漸升高逐步退化等問題。文中下一步的工作將繼續(xù)研究減少過濾時(shí)間，提高過濾效率等相關(guān)方法和技術(shù)，并進(jìn)一步優(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所對(duì)應(yīng)的摻鉺光纖光源可靠度曲線

4 結(jié)論

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

參考文獻(xiàn)：

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

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

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

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

[5]馬靜，王大海，晁代宏，陳淑英.基于關(guān)鍵器件的光纖陀螺可靠性評(píng)估[J].中國慣性技術(shù)學(xué)報(bào)，2009（5）:618-621.

[6]姚淼，宋家友，張俊麗.基于貝葉斯理論的ATS測量不確定度評(píng)定[J].計(jì)算機(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 稿件編號(hào)：201601127

教育部人文社會(huì)科學(xué)研究青年基金項(xiàng)目（15YJC870021；15YJC870028）；遼寧省博士科研啟動(dòng)基金計(jì)劃項(xiàng)目（201411 38）；遼寧省教育廳科學(xué)研究項(xiàng)目（L2015010；L2014451）；遼寧省自然科學(xué)基金（2015020009）。

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