[發明專利]一種基于改進BM算法與后綴數組的冗余字段過濾方法

有效

• 申請號: 201811318116.4
• 申請日: 2018-11-07
• 公開（公告）號: CN109460495B
• 公開（公告）日: 2022-05-10
• 發明（設計）人: 朱丹;張坤;邢蘇霄;章東潤;張熠;徐曉麗
• 申請（專利權）人: 南京烽火星空通信發展有限公司
• 主分類號: G06F16/9032
• 分類號: G06F16/9032
• 代理公司: 南京經緯專利商標代理有限公司 32200
• 代理人: 楊海軍

本發明涉及一種基于改進BM算法與后綴數組的冗余字段過濾方法，針對現有技術的不足，設計引入改進型BM算法，通過增大模式串的移動距離，減少移動匹配的次數，由此提高匹配效率，極大地提高冗余字段的過濾效率，尤其針對中文環境的字符冗余過濾處理上，能夠大大提高冗余字段過濾效率。

技術領域

本發明涉及一種基于改進BM算法與后綴數組的冗余字段過濾方法，屬于模式識別與數據清洗技術領域。

背景技術

隨著大數據時代的到來以及互聯網的普及，網絡上每天都會產生海量的數據。這其中，文本數據占據很大的一個比重。因為缺少格式化的規約以及用戶自我輸入的隨意性，造成網絡上的文本數據質量往往不高，這類數據一般被稱為“臟數據”，這在數據采集過程中是很常見的現象。為了得到較高質量的數據，可以通過數據清洗技術對“臟數據”進行清洗，本發明主要針對“冗余字段”的清洗工作提出一種高效快速的過濾方法。

為了實現上述功能，需要兩個步驟：1)確定最大冗余字段；2)定位最大冗余字段。以上步驟分別涉及到字符串的處理與模式匹配兩個技術。

最大冗余字段其實就是不可重疊的最長重復子串，一般有三個方法可以用來計算最大冗余字段：蠻力法、后綴樹與后綴數組。蠻力法因為效率問題不予考慮，而后綴樹因為代碼實現復雜度高也不推薦。后綴數組是后綴樹的一個非常精巧的替代品，它比后綴樹更加容易編程實現，能夠實現后綴樹的很多功能而時間復雜度也并不遜色，而且它比后綴樹所占用的內存空間小很多。所以本發明采用后綴數組來確定最大冗余字段。

現有的模式匹配算法主要有前綴匹配算法KMP(Kunth-Morris-Pratt)和BM(Boyer-Moore) 算法。KMP算法采用從左至右的匹配方式，通過一個輔助函數跳過失配串，以實現優化。在字符失配時，取消機械的從頭比對的方式，而是依據之前的檢測信息進行計算，直接跳過不必要的檢測，從而減少冗余。BM算法在進行模式串比對時，采用從右至左的方式，當發現不匹配時，將模式串向右移動。BM算法不需要對文本串中的字符進行逐一比較，而會跳過其中的某些部分，對于每一次匹配失敗，BM算法都能使用失敗信息來排除盡可能多的無法匹配的位置。BM算法與KMP算法相比，匹配效率明顯提高，但其仍有缺陷。BM算法需要做壞字符和好后綴的預處理。其中，好后綴的預處理開銷較大，當模式串很長時，會影響匹配的性能。

發明內容

本發明所要解決的技術問題是提供一種基于改進BM算法與后綴數組的冗余字段過濾方法，通過增大模式串的移動距離以提高BM算法的匹配效率，進而提高字符串冗余字段過濾的應用效率。

本發明為了解決上述技術問題采用以下技術方案：本發明設計了一種基于改進BM算法與后綴數組的冗余字段過濾方法，用于實現對目標文本的過濾，包括如下步驟：

步驟A.獲得目標文本所對應的字符串S，然后進入步驟B；

步驟B.根據字符串S的長度I，獲得字符串S所對應的各個后綴Suffix(i)，其中，1≤i≤I， i表示字符串S中各字符的序號，Suffix(i)表示字符串S中、由第i個字符至末尾字符所構的后綴，然后進入步驟C；

步驟C.針對I個后綴Suffix(i)進行大小比較，并從小至大進行排序，獲得各后綴的排序，然后進入步驟D；

步驟D.針對排序各后綴，依序獲得兩兩后綴之間的最長公共前綴，然后進入步驟E；

步驟E.針對排序各后綴，基于依序、相鄰兩后綴不屬于同一字符串后綴，獲得各個最長公共前綴中的最小值，即為目標文本中最大冗余字符子串，然后進入步驟F；

步驟F.以目標文本所對應字符串S作為主串，目標文本中最大冗余字符子串作為模式串，查找主串中與模式串相匹配的第一個子串，并從主串中刪除該子串，更新獲得主串，即為目標文本過濾結果；

上述步驟F包括如下步驟：