[發明專利]字符串的匹配查找方法

有效

• 申請號: 201110008995.2
• 申請日: 2011-01-17
• 公開（公告）號: CN102063510A
• 公開（公告）日: 2011-05-18
• 發明（設計）人: 陳翔
• 申請（專利權）人: 珠海全志科技有限公司
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 珠海智專專利商標代理有限公司 44262
• 代理人: 張中

技術領域

本發明涉及數據識別查找技術領域，尤其涉及一種在文本中進行字符串匹配查找的方法。

背景技術

隨著計算機、電子閱讀器、MP4等電子設備的普及，電子文本的文件檔案廣泛地應用在文件編輯、網頁設計等方方面面。對電子文本的編輯過程中，經常需要在文本中查詢某一特定的字符或字符串，對于單個字符的匹配查找，通常是將需要查找的字符與文本中每一字符進行逐一對比，查找出相應的字符。對于字符串的查找，則有多種不同的查找方法，包括從后向前查找、從前向后查找、從前后兩端同時查找等，目前最為常用的查找方法是BM算法。

需要說明的是，本文所說的“字符”均是通用的ASCII碼，一共256個字符。參見圖1，應用BM算法時，首先需要將匹配查找的字符串P與文本T左對齊，也就是將字符串P的第一個字符P1與文本T中的第一個字符T1對齊。本文所說的“對齊”是指需要匹配查找的字符串中的一個字符與文本的一個字符建立對應關系，此時，字符串的其他字符也與文本中的部分字符建立對應關系，以首先建立對應關系的兩個字符為基準，字符串中其他字符與該基準字符之間的位數等于文本中其他字符與基準字符之間的位數。如圖1所示，字符P1與字符T1對齊，則位于字符P1后一位的字符P2與位于字符T1后一位的字符T2對齊，以此類推。

圖1所示的例子中，文本T為“abcecabc”，需要匹配查找的字符T為“abcab”，因此文本T的前五個字符與字符P中的五個字符分別對齊。

將字符串P與文本T左對齊后，從字符串P最后一個字符開始與文本的字符進行比較，即將字符P5跟與字符P5對齊的字符T5進行比較。若字符T5與字符P5相同，則從右至左逐一比較余下的字符。若比較過程中發現任一字符不相同，則啟動兩條規則，即壞字符規則與好后綴規則。

應用壞字符規則時，首先判斷與字符串P不相同的文本T中的字符是否在字符串P的其他位置出現，例如圖1所示的例子中，判斷字符T5與字符P5不相同后，則判斷字符T5是否與字符串P的其他字符相同。這一過程需要將字符T5與字符串P中的所有字符進行逐一比較分析比較，消耗較長的時間。

若判斷字符T5與字符串P中任一字符均不相同，則字符串P向后移動，移動的位數是字符串P的長度，即字符串P的第一個字符P1將與文本T的第六個字符T6對齊，再次從右至左逐一比較兩兩對齊的字符。

如圖1所示的例子，字符T5為“c”，其與字符串P中的字符P3相同，因此需要將字符串P向后移動若干位，使得字符P3與字符T5對齊，如圖2所示。然后，再從右至左逐一比較兩兩對齊的字符，即字符T7與字符P5比較，字符T6與字符P4比較，以此類推。

由于BM算法中，字符串P每向后跳進一次，均需要訪問文本中與字符串最后一個字符對齊的字符，在比較文本中的字符與字符串最后一個字符不相等后，需要將該字符與字符串中其他字符進行一次比較分析。在實際應用中，由于字符串最后一個字符跟文本中與其對齊的字符不相等的情況是最為普遍的情況，因此在字符串每次跳進后執行上述操作將消耗大量的時間，導致字符串匹配查找的效率低下。

此外，應用BM算法查找匹配的字符時，為了避免向后跳進時跳出文本的邊界，在每次跳進后均需要判斷是否到達文本的最后一個字符，執行該判斷也消耗大量的時間，導致字符串匹配查找的效率不高。

發明內容

本發明的目的是提供一種效率較高的字符串的匹配查找方法。

為此，本發明提供的字符串匹配查找方法包括以下步驟：

建表步驟：依需查找的字符串確定查找過程中遇到預先設定位數的字符個數的任意字符時字符串的跳進距離，建立跳進表格；

對齊步驟：將字符串的第一個字符與文本的第一個字符對齊；

跳進步驟：查詢文本中與字符串倒數設定位數個字符對齊的判別字符，根據判別字符查詢跳進表格，確定字符串的跳進距離，字符串向后跳進該跳進距離；

重復執行跳進步驟到達預先設定次數；

比較步驟：自字符串最后一位字符開始，判斷字符串的每一字符跟文本中與該字符串每一字符所對齊的字符是否相同，若相同，則比較下一字符，直至查找到匹配的字符串；若不相同，返回執行跳進步驟。

由上述方案可見，查找匹配字符串時，不需要將文本中的字符與字符串中的所有字符進行逐一比較，而是直接根據跳進表格進行多次跳進，并在多次跳進后進行一次比較，這樣可大大減少匹配過程所消耗的時間，提高字符串匹配查找的效率。