[發(fā)明專利]一種基于改進(jìn)BM算法與后綴數(shù)組的冗余字段過濾方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201811318116.4
• 申請(qǐng)日: 2018-11-07
• 公開（公告）號(hào): CN109460495B
• 公開（公告）日: 2022-05-10
• 發(fā)明（設(shè)計(jì)）人: 朱丹;張坤;邢蘇霄;章東潤(rùn);張熠;徐曉麗
• 申請(qǐng)（專利權(quán)）人: 南京烽火星空通信發(fā)展有限公司
• 主分類號(hào): G06F16/9032
• 分類號(hào): G06F16/9032
• 代理公司: 南京經(jīng)緯專利商標(biāo)代理有限公司 32200
• 代理人: 楊海軍

1.一種基于改進(jìn)BM算法與后綴數(shù)組的冗余字段過濾方法，用于實(shí)現(xiàn)對(duì)目標(biāo)文本的過濾，其特征在于，包括如下步驟：

步驟A.獲得目標(biāo)文本所對(duì)應(yīng)的字符串S，然后進(jìn)入步驟B；

步驟B.根據(jù)字符串S的長(zhǎng)度I，獲得字符串S所對(duì)應(yīng)的各個(gè)后綴Suffix(i)，其中，1≤i≤I，i表示字符串S中各字符的序號(hào)，Suffix(i)表示字符串S中、由第i個(gè)字符至末尾字符所構(gòu)的后綴，然后進(jìn)入步驟C；

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

步驟D.針對(duì)排序各后綴，依序獲得兩兩后綴之間的最長(zhǎng)公共前綴，然后進(jìn)入步驟E；

步驟E.針對(duì)排序各后綴，基于依序、相鄰兩后綴不屬于同一字符串后綴，獲得各個(gè)最長(zhǎng)公共前綴中的最小值，即為目標(biāo)文本中最大冗余字符子串，然后進(jìn)入步驟F；

步驟F.以目標(biāo)文本所對(duì)應(yīng)字符串S作為主串，目標(biāo)文本中最大冗余字符子串作為模式串，查找主串中與模式串相匹配的第一個(gè)子串，并從主串中刪除該子串，更新獲得主串，即為目標(biāo)文本過濾結(jié)果；

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

步驟F1.以目標(biāo)文本所對(duì)應(yīng)字符串S作為主串，目標(biāo)文本中最大冗余字符子串作為模式串，初始化參數(shù)k'＝0，將主串中第一個(gè)字符的位置與模式串中第一個(gè)字符的位置相對(duì)齊，然后進(jìn)入步驟F2；

步驟F2.針對(duì)主串與模式串，判斷模式串中第K-k'位置的字符與主串中對(duì)應(yīng)位置的字符是否相同，是則進(jìn)入步驟F3；否則主串中該位置的字符即為當(dāng)前壞字符，當(dāng)前壞字符所對(duì)應(yīng)模式串中的位置，即為模式串當(dāng)前失配位置，并進(jìn)入步驟F4；其中，K為模式串的長(zhǎng)度；

步驟F3.判斷K-k'是否等于1，是則進(jìn)入步驟F9；否則針對(duì)k'的值進(jìn)行加1更新，然后返回步驟F2；

步驟F4.提取主串中對(duì)應(yīng)模式串最右邊界位置的下一個(gè)位置的字符，作為比對(duì)末字符，并判斷比對(duì)末字符是否位于模式串中，是則進(jìn)入步驟F5；否則針對(duì)模式串右移K+1位，并更新k'＝0，再返回步驟F2；

步驟F5.根據(jù)模式串當(dāng)前失配位置，減去當(dāng)前壞字符在模式串中最右出現(xiàn)的位置，即減去模式串中當(dāng)前失配位置左側(cè)、當(dāng)前壞字符中最右的位置，獲得模式串對(duì)應(yīng)當(dāng)前壞字符的右移位數(shù)，然后進(jìn)入步驟F6；其中，若模式串中當(dāng)前失配位置的左側(cè)不存在當(dāng)前壞字符，則定義當(dāng)前壞字符在模式串中最右出現(xiàn)的位置為-1；

步驟F6.判斷當(dāng)前壞字符獲得之前、主串與模式串從右至左同位置字符比對(duì)中，是否存在比對(duì)相同的后綴，是則提取該后綴，作為當(dāng)前好后綴，并進(jìn)入步驟F7；否則按模式串對(duì)應(yīng)當(dāng)前壞字符的右移位數(shù)，針對(duì)模式串進(jìn)行右移，并更新k'＝0，再返回步驟F2；

步驟F7.若當(dāng)前好后綴同時(shí)存在于模式串中、相對(duì)模式串當(dāng)前失配位置的左側(cè)，則根據(jù)當(dāng)前好后綴中最后一個(gè)字符所對(duì)應(yīng)模式串中的位置，減去當(dāng)前好后綴在模式串中上一次所出現(xiàn)位置段中最后一字符的位置，獲得模式串對(duì)應(yīng)當(dāng)前好后綴的右移位數(shù)，然后進(jìn)入步驟F8；

若當(dāng)前好后綴中存在位于模式串當(dāng)前失配位置左側(cè)的后綴，且模式串以該后綴開頭，則根據(jù)當(dāng)前好后綴中位于模式串當(dāng)前失配位置左側(cè)、最長(zhǎng)長(zhǎng)度后綴最后一字符在模式串中的位置，減去該后綴在模式串中上一次所出現(xiàn)位置段中最后一字符的位置，獲得模式串對(duì)應(yīng)當(dāng)前好后綴的右移位數(shù)，然后進(jìn)入步驟F8；

否則將K+1位作為模式串對(duì)應(yīng)當(dāng)前好后綴的右移位數(shù)，然后進(jìn)入步驟F8；

步驟F8.按模式串對(duì)應(yīng)當(dāng)前壞字符的右移位數(shù)與模式串對(duì)應(yīng)當(dāng)前好后綴的右移位數(shù)之間的最大值，針對(duì)模式串進(jìn)行右移，并更新k'＝0，再返回步驟F2；

步驟F9.刪除主串中與模式串相對(duì)應(yīng)各位置的字符，更新主串，即為目標(biāo)文本過濾結(jié)果。