一種基於過濾型的字符串快速匹配方法
2023-06-11 17:28:41 1
專利名稱：一種基於過濾型的字符串快速匹配方法
技術領域：
本發明涉及字符串匹配技術領域，特別是涉及一種基於過濾型的字符串快速匹配方法，屬於信息檢索領域和計算生物學領域。
背景技術：
字符串匹配問題可以界定為從給定的符號序列中找出一個具有某種屬性的模式，最簡單的例子是從給定的字符序列中找出一個給定的字符串。「近似匹配」一般是指在允許模式和文本字符串之間存在某些細微的差異。「匹配」一般是指「近似匹配」。字符串匹配是計算機科學中最古老、研究最廣泛的問題之一，並且，字符串匹配的應用也隨處可見。近年來，學術界對字符串匹配的研究興趣與日俱增，特別是在發展迅猛的信息檢索領域和計算生物學領域。同時，近似匹配的應用也越來越廣泛。例如，信息檢索中對拼寫錯誤的糾正，在計算生物學中的序列比對，在信號處理中對傳輸錯誤的糾正，等等。之所以有上述現象，不僅因為在這兩個研究領域中需要處理的文本規模越來越大，而且由於需要在文本中進行越來越複雜的搜索。現在對近似匹配的研究主要基於距離模型，在該模型中需要一個可以度量兩個字符串相似度的距離函數。在近似匹配中，通常給出模式串和一個對應的閥值k，其中，k指定了模式串和匹配結果之間允許的最大距離。近似匹配的定義如下在編輯距離模型下，給定一個整數k和兩個字符串分別為Pattern[l-m]、Text[l-n]，找出文本串Text中的所有子串P，使得編輯距離edit (Pattern，p)彡k。在實際應用中，很多問題是用了編輯距離模型或者使用其變體。已有的近似匹配方法分為四類第一類是基於動態規劃方法；第二類是基於NFA搜索；第三類是基於位並行技術，這是當前應用最成功的一類方法。最後一類是基於過濾的方法，它用一個快速的過濾算法跳過文本中那些不可能存在成功匹配的大塊區域，然後再利用一個非過濾算法來驗證剩下的區域是否存在成功匹配。這類方法也是最快的算法之
o提出的算法就是利用過濾的思想，使得算法的效率大為提高。
發明內容
本發明的目的在於提供快速近似模式匹配的一種方法，尤其是克服機器字長的限制，提供一種適用於長模式串近似匹配的算法。對於給定的文本串和模式串，本發明一種基於過濾型的字符串快速匹配方法是在文本串中尋找與模式串具有一定相似度的子串。字符串匹配問題就是在一個大的文本串中搜索某個模式串的所有出現位置。本發明用過濾思想過濾掉了文本串中那些不能產生成功匹配的區域，從而提高了算法在平均情況下的效率。為實現上述目的，本發明採用如下技術方案一種基於過濾型的字符串快速匹配方法，包括如下步驟
(I)對模式串進行預處理記模式串長度為(k+s)h的前綴為Ptl，將Ptl切分成k+s個長度為h的模式串子塊，將每一個模式串子塊的長度延長k+q-1，則兩個連續模式串子塊之間存在長度為k+q-1的重疊部分；這k+s個延長之後的模式串子塊分別記為Qp Q2、…、
Qk+S;其中h= — q + 1咖為模式串字符的個數；k為把模式串轉變成文本串某個子串所 _ k + s _
需要的最少操作次數簡稱編輯距離，0 ^ k < m ;s為在匹配過程中文本串索引(文本串索引的說明在步驟2中)與模式串子塊的因子精確匹配的最少個數，I ^ s < m;q是文本串索引的長度，q ^ h ；(2)創建文本串索引從文本串起始位置開始，每隔h長度依次讀取文本串的q個字符作為文本串索引，文本串索引分別標記為屯、d2,；q ^ h ；
(3)創建匹配數組B [d，j]:如果某一個文本串索引Cli屬於Qj,則B [ClijJl=I;否則BWi, j]=0 ;為每個文本串創建長度為m』的數組M,用於記錄文本串索引的匹配個數,記Cli對應的數組為Mdi [I…m』 ]，Mdi[l-m，]初始化為0 ;其中m』 =k+s ；(4)計算k+s個連續的文本串索引與模式串子塊的匹配個數將文本串索引與模式串子塊進行匹配；在記錄匹配情況的過程中，若出現Mdi[j] k)的情況，則停止構建該數組，轉而繼續構建下一個索引的數組Mdi+1 ;若元素Mdi[m』] ^ s，則需要進一步檢測近似匹配，繼續下一步；(5)檢測近似匹配若存在近似匹配，則待檢測的區域位於文本串的j_ (k+s)h-2k-q+2至j+m-(k+s-l)h+k-q部分，並用動態規划算法檢測該區域，如果檢測出近似匹配，則給出近似匹配的所有出現位置，否則報告該區域不存在近似匹配。字符串是定義在有限字母表上的字符序列。文本串是一個字符串，模式串也是一個字符串。字符串匹配問題就是在一個大的文本串中搜索某個模式串的所有出現位置。給定字符串x，y和z，稱X是xy的一個前綴，x是yx的一個後綴，x是yxz的一個因子。本發明的原理如果把文本串分成k+s片，那麼對於任意一個成功的近似匹配，至少有s片在文本串中是精確匹配的。利用上述思想,本發明通過構造q-gram索引計算文本串中已精確匹配的子串個數，確定在該g-gram索引某段區域是否有存在近似匹配的可能。g-gram索引指的是在建立索引時對文本Text切分時採用長度為q、滑動距離為d的滑動窗口，切分得到長度為q的子串。為了計算q-gram與模式串的匹配個數，引入匹配數組B[d，j]，如果某一個q-gram d屬於Qj,則B[d, j]=l;否則B [d, j] =0。這樣,對於每一個q-gramd,B[d，*]給出了每一塊d的匹配信息。在確定了某段區域有存在近似匹配的可能之後，就需要對該段區域進行驗證。應用比較廣泛的驗證算法是基於位並行技術的，比如BPM算法。但是該方法適用於完成模式串長度比較短時的近似匹配驗證。本發明選取的驗證算法是基於動態規劃矩陣的DP算法。該算法的思想是通常模式串在文本中成功匹配的數目是很少的，因此，在編輯距離矩陣M中，每一列的值從上往下計算很快就達到k+1 (即不匹配了)，如果某個矩陣元素的值大於k+1,那麼搜索結果就不會依賴於這個元素。如果一個矩陣元素的值小於或等於k，那麼這個元素就稱為活動的。該方法只計算到每一列的最後一個活動元素，不需要再對後面的元素進行計算。本發明與現有的近似匹配算法相比，具有以下顯著優點
(I)近似捜索中大量使用位並行方法，很多很好的結果都是使用位並行方法得到。然而位並行算法適用於模式串較短的情況，但是現實需求中很多搜索都是對長模式串進行。如果模式串的長度超過了計算機的字長，那麼匹配的效果將變得非常的糟糕。而本近似捜索算法非常適合長模式串的近似匹配，當模式串的長度m和閥值k的比值增加時，其效率也相應的提高。(2)在未増加新的過濾策略之前，近似匹配算法的時間開銷主要是計算數組M以及用DP算法驗證可能的匹配區域。通過增加過濾策略，簡化了匹配時計算每個q-gram索引與模式串中每個塊的匹配時間，從而大大縮短了計算數組M的時間。在最好情況下，本算法能比原算法能縮短一半的匹配時間。(3)過濾算法只能提高算法在平均情況下的效率，它的優勢在於可能不需要檢查文本中的每個字符。過濾算法的效率和它能過濾掉的文本大小有關，並且對錯誤水平非常的敏感。大多數過濾算法在錯誤水平較低時工作得很好，否則就很差。而本過濾算法在錯誤水平較高時，依然保持了良好的性能。實驗顯示，當錯誤水平較高時，本算法比同類算法 所需的匹配時間能減少一半。
圖I是構造索引對文本串的處通不意圖；圖2是模式串的處理示意圖。
具體實施例方式為了更好地理解本發明，下面結合實施例對本發明作進ー步說明，但本發明要求保護的範圍並不局限於實施例表示的範圍。實施案例I :手機簡訊分類近些年，我國加快了社會信息化和數位化的發展步伐，人們每天要處理的信息越來越多。各應用服務商為了提醒或者讓客戶儘快了解相關信息會以簡訊的方式通知客戶，如電子商務網商品推薦、網上銀行信息回饋、各種扣費通知還有用戶本身的聊天信息等。但隨著人們接觸的業務越來越多，這些信息變得繁雜難以管理。大家需要ー種很方便、鬆散、有效的方式分類簡訊，擺脫直接打開收件箱應對各類信息的窘況。應用本發明「ー種基於過濾型的字符串快速匹配方法」能夠實現用模版來分類短息的功能。當用戶需要劃分ー個新的信息類別，只需要提供一條或者多條該類型的信息，系統就能利用近似匹配的辦法自動分類將來收到的簡訊，應用步驟如下(I)用戶建立一個新的信息類，提供一條或若干條簡訊作為該類的樣本，這些樣本就是該類的模式串。而新的簡訊內容則作為目標文本串，如果某類模式串與該文本串相匹配則該文本串屬於該類。(2)假設簡訊樣本的長度是m=32，簡訊文本串索引的長度q=2 ;用戶設定相似度是k=4，在匹配過程中簡訊索引與模式串子塊的因子精確匹配的最少個數s=2 ;則其中
h= m f — g + 1 =4;如圖2所示，對模式串進行預處理記模式串長度為(k+s)h=24的前 _ k + s J
綴為Po，將Po切分成k+s=6個長度為h=4的模式串子塊，將每一個模式串子塊的長度延長k+q-1 = 5,則兩個連續模式串子塊之間存在長度為k+q-Ι = 5的重疊部分；這k+s=6個延長之後的模式串子塊分別記為Q1, Q2,…，Q6 ;(3)如圖I所示，對於新的簡訊，假設其長度是128 ;創建簡訊的索引從簡訊起始位置開始，每隔h=4長度依次讀取簡訊的q=2個字符作為新簡訊索引，簡訊索引分別標記為
Cll、^2) ... d32 ；(4)創建匹配數組B[d，j]，如果某ー個簡訊索引Cli屬於Qj,則Β[『 j]=l;否則B[di； j]=0;為每個簡訊創建長度為m』的數組M，用於記錄簡訊索引的匹配個數，記も對應的數組為Mdi [6]，Mdi [6]初始化為O ；(5)計算k+s=6個連續的簡訊索引與模式串子塊的匹配個數將簡訊索引與模式串子塊進行匹配；在記錄匹配情況的過程中，若出現Mdi[b]彡b-4(這裡有b>4)的情況，則停止構建該數組，轉而繼續構建下ー個索引的數組唚1+1 ;若元素Mdi[6]彡2，則需要進ー步 檢測近似匹配，繼續下一歩；(6)檢測近似匹配若存在近似匹配，則待檢測的區域位於簡訊的j-32至j+14部分(j是某一次匹配中連續6個索引最後ー個索引的在日記文檔的結束位置)，並用動態規划算法檢測該區域，如果檢測出近似匹配，則給出近似匹配的所有出現位置，否則報告該區域不存在近似匹配。ー個簡訊可以屬於多個類，只要匹配成功就證明該簡訊的部分內容符合某類的模版要求。實施案例2 日記文檔模糊捜索隨著計算機技術的迅速發展和生活速度的加快，相對於以往用紙筆寫日記、完成工作文檔的情況，人們現在更偏向於用計算機完成文本工作。主要有三個原因1)計算機技術使人們完成文本工作更容易和快捷；2)計算機日記更具有娛樂色彩，如編輯心情；3)滿足人們隨手記錄的要求。相比於一天結束後完成一篇日記或者工作報告，即時記錄更符合人們的需求，隨著手機硬體技術、手寫字識別和語音識別技術的發展，我們更方便更直接地記錄日常信息，通過計算機識別技木，這些多媒體信息將會轉化為文本進行存儲。對於這些比較隨意散亂、文學性不強的文檔，應用本發明「一種過濾型快速近似模式匹配方法」可以滿足用戶模糊捜索日誌的需求，應用步驟如下( I)用戶指定日記文檔作為本實施例中的文本串，輸入查詢語句作為本發明中的模式串；(2)查詢語句的長度記為m=16，用戶設定查詢相似度k=2，在匹配過程中日記文檔索引與查詢語句子塊的因子精確匹配的最少個數s為1，日記文檔索引的長度q=3;則
h= W ^ q + l =4;對查詢語句進行預處理記查詢語句的長度為(k+s)h=12的前綴為Pci,
將Ptl切分成k+s=3個長度為4的查詢語句子塊，將每一個查詢語句子塊的長度延長k+q-1=4，則兩個連續查詢語句子塊之間存在長度為4的重疊部分；這3個延長之後的查詢語句子塊分別記為Q1, Q2, Q3;(3)創建日記文檔索引假設日記的長度是1000。從日記文檔起始位置開始，每隔4個字符依次讀取日記文檔的3個字符作為日記文檔索引，日記文檔索引分別標記為も、
^2) · · · d250 ;(4)創建匹配數組B[d，j]，如果某ー個日記文檔索引Cli屬於Qj.，則Β[『」]=1;否則B Wi，j] =O ;為每個日記文檔創建長度為3的數組M，用於記錄日記文檔索引的匹配個數，記Cli對應的數組為Mdi [3]，Mdi [3]初始化為O ；(5)計算3個連續的日記文檔索引與查詢語句子塊的匹配個數將日記文檔索引與查詢語句子塊進行匹配；在記錄匹配情況的過程中，若出現Mdi[b]彡b-2(這裡有b>2)的情況，則停止構建該數組，轉而繼續構建下ー個索引的數組唚1+1 ;若元素Mdi [m』 ]彡S=I，則需要進ー步檢測近似匹配，繼續下一歩；(6)檢測近似匹配若存在近似匹配，則待檢測的區域位於日記文檔的j-17至j+7 (j是某一次匹配中連續3個索引最後ー個索引的在日記文檔的結束位置)部分，並用動態規划算法檢測該區域，如果檢測出近似匹配，則給出近似匹配的所有出現位置，否則報告 該區域不存在近似匹配。只要存在某處匹配成功的文檔作為候選文檔提供用戶詳細查看。
權利要求
1.一種基於過濾型的字符串快速匹配方法，其特徵在於包括如下步驟 (1)對模式串進行預處理記模式串長度為(k+S)h的前綴為P。，將P。切分成k+s個長度為h的模式串子塊，將每一個模式串子塊的長度延長k+q-l，則兩個連續模式串子塊之間存在長度為k+q-l的重疊部分；這k+s個延長之後的模式串子塊分別記為Q1' Q2>…、Qk+S ；其中
2.根據權利要求I所述的基於過濾型的字符串快速匹配方法，其特徵在於所述文本串為字符串，模式串為字符串；所述字符串是定義在有限字母表上的字符序列。
3.根據權利要求I所述的基於過濾型的字符串快速匹配方法，其特徵在於給定字符串x，y和z，稱X是xy的一個前綴，x是yx的一個後綴，x是yxz的一個因子。
全文摘要
本發明公開了一種基於過濾型的字符串快速匹配方法，該方法先對模式串進行預處理將模式串前綴P0切分成k+s個長度為h的模式串子塊，將每一個模式串子塊的長度延長k+q-1，分別記為Q1、Q2、…、Qk+s；然後從文本串起始位置開始，每隔h長度依次讀取文本串的q個字符作為文本串索引，文本串索引分別標記為d1、d2，...dn/h；再創建匹配數組B[d，j]如果某一個文本串索引di屬於Qj,則匹配數組B[di，j]=1;計算k+s個連續的文本串索引與模式串子塊的匹配個數，最後檢測近似匹配。本方法結合了動態規划算法與過濾算法，並且增加了新的過濾策略，縮短近似匹配的平均時間，使得匹配性能有了較大的提高。
文檔編號G06F17/30GK102750379SQ201210211829
公開日2012年10月24日 申請日期2012年6月25日 優先權日2012年6月25日
發明者李擁軍, 林浩, 謝豪, 鄒少聰, 黃格仕 申請人:華南理工大學