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

有效

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

本發明屬于計算機軟件應用領域，公開了一種基于Sunday算法的字符搜索方法。通過判斷文本窗口的末位和文本窗口外的下一位字符的組合是否出現在模式串中，來對模式串和文本模式串進行匹配，若匹配成功，程序結束；若匹配不成功，則移動文本窗口，繼續利用上述的方法進行判斷，直到文本窗口到達文本字符串的末端或者匹配成功，程序才會結束；利用此方法，可有效的減小原算法的無效匹配次數，提升文本的匹配效率。

技術領域

本發明涉及字符搜索，特別是一種基于Sunday算法的字符搜索方法，用于計算機網絡領域中對字符進行搜索。

背景技術

字符串是計算機科學中常見的基本概念，搜索問題也是計算機科學中的基本問題。隨著互聯網的日漸龐大，信息也是越來越多，如何在海量的信息中快速查找自己所要的信息是網絡搜索研究的熱點所在；在這其中，字符串匹配算法起著非常重要的作用，一個高效的字符串匹配算法，可以極大的提高搜索的效率和質量。字符串匹配在網絡領域有著廣泛的應用。比如，拼寫檢查、語言翻譯、數據壓縮、搜索引擎、網絡入侵檢測等。

現有的常見的字符串匹配算法有Brute force、KMP、Boyer Moore、Sunday、robin_karp和bitap等。其中，Sunday算法是平均效率較高的一種匹配方案。

Sunday算法是Daniel M.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。