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

有效

• 申請號: 201710375615.6
• 申請日: 2017-05-24
• 公開（公告）號: CN107220333B
• 公開（公告）日: 2020-01-31
• 發明（設計）人: 劉小壘;張小松;牛偉納;胡斌;王中晴
• 申請（專利權）人: 電子科技大學
• 主分類號: G06F16/903
• 分類號: G06F16/903
• 代理公司: 51230 成都弘毅天承知識產權代理有限公司
• 代理人: 徐金瓊;劉東

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

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

步驟2：文本窗口與文本字符串左對齊，所述文本字符串為待搜索文本，所述文本窗口在所述文本字符串上滑動；利用所述輔助數組判斷所述文本窗口內最后兩個字符是否在模式串中出現；若未出現，跳轉到步驟4；若出現，則將模式串中出現的字符與所述最后兩個字符對齊，判斷模式串與文本字符串對應位置上的字符是否匹配，若匹配，則匹配成功程序結束；若不匹配，則跳轉到步驟3；

步驟3：采用Sunday算法進行下一次的匹配和跳轉，若采用Sunday算法匹配成功，則程序結束；若采用Sunday算法匹配失敗，則判斷Sunday算法跳轉的長度是否超過文本窗口的長度，若超過文本窗口長度，則跳轉到步驟4；若未超過文本窗口長度，則重復步驟3；

步驟4：文本窗口向右移動J個字符長度，將文本窗口中的末位字符和文本窗外與所述末位字符相鄰的字符作為組合字符，利用輔助數組判斷所述組合字符是否在模式串中出現；若出現，跳轉到步驟5；若未出現，判斷文本窗口是否超出文本字符串，若超出，則匹配失敗程序結束；若未超出，重復步驟4的內容；其中模式串的長度和文本窗口的長度均為J個字符長度；

步驟5：模式串中出現的字符與所述組合字符對齊，判斷模式串與文本字符串對應位置上的字符是否匹配；若匹配則匹配成功程序結束；若不匹配，跳轉到步驟3。

2.根據權利要求1所述的一種基于Sunday算法的字符搜索方法，其特征在于：步驟1中輔助數組構建方式如下：

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

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

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

S202：利用所有字符兩兩組合產生的最大哈希值作為輔助數組中元素的個數，且字符兩兩組合產生的哈希值的大小為所述元素的位置序號；

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

哈希值H[i]對應位置上的元素為1，若模式串中兩組及以上相鄰兩字符組合產生的哈希值H[i]相同，則將該哈希值H[i]對應位置上的元素設為大于1的數，輔助數組中其余位置上的元素均為0。

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