一種基於Sunday算法的字符搜索方法與流程
2023-10-09 00:23:09 2
本發明涉及字符搜索，特別是一種基於sunday算法的字符搜索方法，用於計算機網絡領域中對字符進行搜索。
背景技術：
字符串是計算機科學中常見的基本概念，搜索問題也是計算機科學中的基本問題。隨著網際網路的日漸龐大，信息也是越來越多，如何在海量的信息中快速查找自己所要的信息是網絡搜索研究的熱點所在；在這其中，字符串匹配算法起著非常重要的作用，一個高效的字符串匹配算法，可以極大的提高搜索的效率和質量。字符串匹配在網絡領域有著廣泛的應用。比如，拼寫檢查、語言翻譯、數據壓縮、搜尋引擎、網絡入侵檢測等。
現有的常見的字符串匹配算法有bruteforce、kmp、boyermoore、sunday、robin_karp和bitap等。其中，sunday算法是平均效率較高的一種匹配方案。
sunday算法是danielm.sunday於1990年提出的一種字符串模式匹配算法。其核心思想是：在匹配過程中，模式串並不被要求一定要按從左向右進行比較還是從右向左進行比較，它在發現不匹配時，算法能跳過儘可能多的字符以進行下一步的匹配，從而提高了匹配效率。
sunday算法思想跟bm算法很相似，在匹配失敗時關注的是文本串中參加匹配的最末位字符的下一位字符。如果該字符沒有在匹配串中出現則直接跳過，即移動步長＝匹配串長度+1；否則，同bm算法一樣其移動步長＝匹配串中最右端的該字符到末尾的距離+1。
sunday算法在模式串很長的時候(很多實際應用中，模式串都會很長)，文本窗口外下一個字符在模式串中出現的概率會很高，這樣會增加很多無效匹配，由此sunday算法的效率會顯著降低。
技術實現要素：
基於以上技術問題，本發明提供了一種基於sunday算法的字符搜索方法,從而解決了在字符搜索中產生很多無效匹配的技術問題。
本發明的技術方案如下：
一種基於sunday算法的字符搜索方法，包括以下步驟：
步驟1：利用模式串中相鄰兩字符的信息構建輔助數組，所述模式串為待匹配的字符串；
步驟2：文本窗口與文本字符串左對齊，所述文本字符串為待搜索文本，所述文本窗口在所述文本字符串上滑動；利用所述輔助數組判斷所述文本窗口內最後兩個字符是否在模式串中出現；若未出現，跳轉到步驟4；若出現，則將模式串中出現的字符與所述最後兩個字符對齊，判斷模式串與文本字符串對應位置上的字符是否匹配，若匹配，則匹配成功程序結束；若不匹配，則跳轉到步驟3；
步驟3：採用sunday算法進行下一次的匹配和跳轉，若採用sunday算法匹配成功，則程序結束；若採用sunday算法匹配失敗，則判斷sunday算法跳轉的長度是否超過文本窗口的長度，若超過文本窗口長度，則跳轉到步驟4；若未超過文本窗口長度，則重複步驟3；
步驟4：文本窗口向右移動j個字符長度，將文本窗口中的末位字符和文本窗外與所述末位字符相鄰的字符作為組合字符，利用輔助數組判斷所述組合字符是否在模式串中出現；若出現，跳轉到步驟5；若未出現，判斷文本窗口是否超出文本字符串，若超出，則匹配失敗程序結束；若未超出，重複步驟4的內容；其中模式串的長度和文本窗口的長度均為j個字符長度；
步驟5：模式串中出現的字符與所述組合字符對齊，判斷模式串與文本字符串對應位置上的字符是否匹配；若匹配則匹配成功程序結束；若不匹配，跳轉到步驟3。
進一步的，步驟1中輔助數組構建方式如下：
s201：利用模式串中字符的ascii碼值和設定的index值，計算模式串中相鄰兩字符的哈希值，採用如下公式：
h[i]＝a[i]×index+a[i+1]×(index+1)(1)
其中，i表示模式串中字符的位置序號；h[i]表示模式串中相鄰兩字符的哈希值；a[i]表示第i個字符的ascii碼值；
s202：利用所有字符兩兩組合產生的最大哈希值作為輔助數組中元素的個數，且字符兩兩組合產生的哈希值的大小為所述元素的位置序號；
s203：將s201中計算出的哈希值映射到輔助數組中，具體方式如下：
哈希值h[i]對應位置上的元素為1，若模式串中兩組及以上相鄰兩字符組合產生的哈希值h[i]相同，則將該哈希值h[i]對應位置上的元素設為大於1的數，輔助數組中其餘位置上的元素均為0。
進一步的，所述利用輔助數組進行判斷方法為：計算文本字符串中需要判斷的相鄰兩字符的哈希值，利用該哈希值查找輔助數組中對應位置上的元素，若元素為1，則代表文本字符串中相鄰兩字符與模式串匹配或出現在模式串中；若元素為0，則代表文本字符串中相鄰兩字符與模式串不匹配或未出現在模式串中；若元素為大於1的數，則代表該字符組合與其餘字符組合的哈希值相同，則進行步驟3的內容。
綜上所述，由於採用了上述技術方案，本發明的有益效果是：
採用字符的ascii值和index值進行哈希值的計算，簡便易行；利用組合字符形式來進行匹配，可有效的降低無效匹配的概率，從而提高sunday算法的效率。
模式串一旦確定，通過預處理得出輔助數組後再匹配，提高在實際應用中的使用效率；比如網絡入侵中惡意代碼的檢測、論文檢索中大段文本的搜索，病毒多特徵掃描，由於這些應用的模式串一般都很長，所以在本發明的應用上能有較大效率的提升。
附圖說明
圖1是本發明的流程圖；
圖2是本發明的實驗結果圖
具體實施方式
本說明書中公開的所有特徵，除了互相排斥的特徵和/或步驟以外，均可以以任何方式組合。
下面結合附圖對本發明作詳細說明。
一種基於sunday算法的字符搜索方法，包括以下步驟：
步驟1：利用模式串中相鄰兩字符的信息構建輔助數組，所述模式串為待匹配的字符串；
輔助數組構建方式如下：
s201：利用模式串中字符的ascii碼值和設定的index值，計算模式串中相鄰兩字符的哈希值，採用如下公式：
h[i]＝a[i]×index+a[i+1]×(index+1)(2)
其中，i表示模式串中字符的位置序號；h[i]表示模式串中相鄰兩字符的哈希值；a[i]表示第i個字符的ascii碼值；
s202：利用所有字符兩兩組合產生的最大哈希值作為輔助數組中元素的個數，且字符兩兩組合產生的哈希值的大小為所述元素的位置序號；
s203：將s201中計算出的哈希值映射到輔助數組中，具體方式如下：
哈希值h[i]對應位置上的元素為1，若模式串中兩組及以上相鄰兩字符組合產生的哈希值h[i]相同，則將該哈希值h[i]對應位置上的元素設為大於1的數，輔助數組中其餘位置上的元素均為0。
步驟2：文本窗口與文本字符串左對齊，所述文本字符串為待搜索文本，所述文本窗口在所述文本字符串上滑動；計算所述文本窗口內最後兩個字符的哈希值，在輔助數組中，若計算出的哈希值對應位置上的元素為0，則代表最後兩個字符未出現在模式串中，跳轉到步驟4；若計算出的哈希值對應位置上的元素為1，則代表則代表最後兩個字符出現在模式串中，則將模式串中出現的字符與所述最後兩個字符對齊，判斷模式串與文本字符串對應位置上的字符是否匹配，若匹配，則匹配成功程序結束；若不匹配，則跳轉到步驟3；若計算出的哈希值對應位置上的元素為大於1的值，則代表存在另外組合字符的哈希值與該哈希值相同，為減小錯誤率，跳轉到步驟3。
步驟3：採用sunday算法進行下一次的匹配和跳轉，若採用sunday算法匹配成功，則程序結束；若採用sunday算法匹配失敗，則判斷sunday算法跳轉的長度是否超過文本窗口的長度，若超過文本窗口長度，則跳轉到步驟4；若未超過文本窗口長度，則重複步驟3；
步驟4：文本窗口向右移動j個字符長度，將文本窗口中的末位字符和文本窗外與所述末位字符相鄰的字符作為組合字符，計算所述組合字符的哈希值，在輔助數組中，若計算出的哈希值對應位置上的元素為0，則代表最後兩個字符未出現在模式串中，判斷文本窗口是否超出文本字符串，若超出，則匹配失敗程序結束；若未超出，重複步驟4的內容；若計算出的哈希值對應位置上的元素為1，則代表則代表最後兩個字符出現在模式串中，跳轉到步驟5；若計算出的哈希值對應位置上的元素為大於1的值，則代表存在另外組合字符的哈希值與該哈希值相同，為減小錯誤率，跳轉到步驟3；其中模式串的長度和文本窗口的長度均為j個字符長度；
步驟5：模式串中出現的字符與所述組合字符對齊，判斷模式串與文本字符串對應位置上的字符是否匹配；若匹配則匹配成功程序結束；若不匹配，跳轉到步驟3。
本發明的工作原理是：構建輔助數組，文本窗口在文本字符串上滑動，滑動長度為模式串的長度；將文本窗口的最後一個字符與文本窗外的下一個字符進行組合，通過輔助數組來判斷該字符組合是否出現在模式串中，以此來對字符串進行匹配。
下面，結合具體實施例來對本發明做進一步詳細說明。
具體實施例
具體實施例1
以下為本發明c語言的實現程序：
具體實施例2
以下為本發明的實驗結果圖，具體為與sunday算法的效率比較圖。
生成10kb的隨機純英文字母和數字作為文本字符串，選取特定特點的字符串作模式串，用原sunday算法和本發明採用的算法進行搜索，比較它們的實際效率，重複調用1000次求總時間(單位:毫秒)，得出下列統計圖。
圖中，a代表sunday算法，b代表本發明採用的算法；
柱體1採用的模式串為：abcdef；
柱體2採用模式串為：abcdefghijklmnopqrstuvwxyz；
柱體3採用模式串為：
abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyz；
柱體4採用模式串為：
abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyz1234567
如上所述即為本發明的實施例。本發明不局限於上述實施方式，任何人應該得知在本發明的啟示下做出的結構變化，凡是與本發明具有相同或相近的技術方案，均落入本發明的保護範圍之內。