[發(fā)明專利]一種基于Sunday算法的字符搜索方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201710375615.6
• 申請(qǐng)日: 2017-05-24
• 公開(kāi)（公告）號(hào): CN107220333B
• 公開(kāi)（公告）日: 2020-01-31
• 發(fā)明（設(shè)計(jì)）人: 劉小壘;張小松;牛偉納;胡斌;王中晴
• 申請(qǐng)（專利權(quán)）人: 電子科技大學(xué)
• 主分類號(hào): G06F16/903
• 分類號(hào): G06F16/903
• 代理公司: 51230 成都弘毅天承知識(shí)產(chǎn)權(quán)代理有限公司
• 代理人: 徐金瓊;劉東

1.一種基于Sunday算法的字符搜索方法，其特征在于：包括以下步驟：

步驟1：利用模式串中相鄰兩字符的信息構(gòu)建輔助數(shù)組，所述模式串為待匹配的字符串；

步驟2：文本窗口與文本字符串左對(duì)齊，所述文本字符串為待搜索文本，所述文本窗口在所述文本字符串上滑動(dòng)；利用所述輔助數(shù)組判斷所述文本窗口內(nèi)最后兩個(gè)字符是否在模式串中出現(xiàn)；若未出現(xiàn)，跳轉(zhuǎn)到步驟4；若出現(xiàn)，則將模式串中出現(xiàn)的字符與所述最后兩個(gè)字符對(duì)齊，判斷模式串與文本字符串對(duì)應(yīng)位置上的字符是否匹配，若匹配，則匹配成功程序結(jié)束；若不匹配，則跳轉(zhuǎn)到步驟3；

步驟3：采用Sunday算法進(jìn)行下一次的匹配和跳轉(zhuǎn)，若采用Sunday算法匹配成功，則程序結(jié)束；若采用Sunday算法匹配失敗，則判斷Sunday算法跳轉(zhuǎn)的長(zhǎng)度是否超過(guò)文本窗口的長(zhǎng)度，若超過(guò)文本窗口長(zhǎng)度，則跳轉(zhuǎn)到步驟4；若未超過(guò)文本窗口長(zhǎng)度，則重復(fù)步驟3；

步驟4：文本窗口向右移動(dòng)J個(gè)字符長(zhǎng)度，將文本窗口中的末位字符和文本窗外與所述末位字符相鄰的字符作為組合字符，利用輔助數(shù)組判斷所述組合字符是否在模式串中出現(xiàn)；若出現(xiàn)，跳轉(zhuǎn)到步驟5；若未出現(xiàn)，判斷文本窗口是否超出文本字符串，若超出，則匹配失敗程序結(jié)束；若未超出，重復(fù)步驟4的內(nèi)容；其中模式串的長(zhǎng)度和文本窗口的長(zhǎng)度均為J個(gè)字符長(zhǎng)度；

步驟5：模式串中出現(xiàn)的字符與所述組合字符對(duì)齊，判斷模式串與文本字符串對(duì)應(yīng)位置上的字符是否匹配；若匹配則匹配成功程序結(jié)束；若不匹配，跳轉(zhuǎn)到步驟3。

2.根據(jù)權(quán)利要求1所述的一種基于Sunday算法的字符搜索方法，其特征在于：步驟1中輔助數(shù)組構(gòu)建方式如下：

S201：利用模式串中字符的ASCII碼值和設(shè)定的index值，計(jì)算模式串中相鄰兩字符的哈希值，采用如下公式：

H[i]＝A[i]×index+A[i+1]×(index+1)

其中，i表示模式串中字符的位置序號(hào)；H[i]表示模式串中相鄰兩字符的哈希值；A[i]表示第i個(gè)字符的ASCII碼值；

S202：利用所有字符兩兩組合產(chǎn)生的最大哈希值作為輔助數(shù)組中元素的個(gè)數(shù)，且字符兩兩組合產(chǎn)生的哈希值的大小為所述元素的位置序號(hào)；

S203：將S201中計(jì)算出的哈希值映射到輔助數(shù)組中，具體方式如下：

哈希值H[i]對(duì)應(yīng)位置上的元素為1，若模式串中兩組及以上相鄰兩字符組合產(chǎn)生的哈希值H[i]相同，則將該哈希值H[i]對(duì)應(yīng)位置上的元素設(shè)為大于1的數(shù)，輔助數(shù)組中其余位置上的元素均為0。

3.根據(jù)權(quán)利要求2所述的一種基于Sunday算法的字符搜索方法，其特征在于：所述利用輔助數(shù)組進(jìn)行判斷方法為：計(jì)算文本字符串中需要判斷的相鄰兩字符的哈希值，利用該哈希值查找輔助數(shù)組中對(duì)應(yīng)位置上的元素，若元素為1，則代表文本字符串中相鄰兩字符與模式串匹配或出現(xiàn)在模式串中：若元素為0，則代表文本字符串中相鄰兩字符與模式串不匹配或未出現(xiàn)在模式串中；若元素為大于1的數(shù)，則代表該字符組合與其余字符組合的哈希值相同，則進(jìn)行步驟3的內(nèi)容。