字符串的匹配查找方法

2023-07-05 23:36:41

專利名稱：字符串的匹配查找方法
技術領域：
本發明涉及數據識別查找技術領域，尤其涉及一種在文本中進行字符串匹配查找 的方法。
背景技術：
隨著計算機、電子閱讀器、MP4等電子設備的普及，電子文本的文件檔案廣泛地應 用在文件編輯、網頁設計等方方面面。對電子文本的編輯過程中，經常需要在文本中查詢某 一特定的字符或字符串，對於單個字符的匹配查找，通常是將需要查找的字符與文本中每 一字符進行逐一對比，查找出相應的字符。對於字符串的查找，則有多種不同的查找方法， 包括從後向前查找、從前向後查找、從前後兩端同時查找等，目前最為常用的查找方法是BM 算法。需要說明的是，本文所說的「字符」均是通用的ASCII碼，一共256個字符。參見 圖1，應用BM算法時，首先需要將匹配查找的字符串P與文本T左對齊，也就是將字符串P 的第一個字符Pl與文本T中的第一個字符Tl對齊。本文所說的「對齊」是指需要匹配查 找的字符串中的一個字符與文本的一個字符建立對應關係，此時，字符串的其他字符也與 文本中的部分字符建立對應關係，以首先建立對應關係的兩個字符為基準，字符串中其他 字符與該基準字符之間的位數等於文本中其他字符與基準字符之間的位數。如圖1所示， 字符Pl與字符Tl對齊，則位於字符Pl後一位的字符P2與位於字符Tl後一位的字符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的第一個字符Pl將與文本T的第六個字符T6對齊，再次 從右至左逐一比較兩兩對齊的字符。如圖1所示的例子，字符T5為「c」，其與字符串P中的字符P3相同，因此需要將字 符串P向後移動若干位，使得字符P3與字符T5對齊，如圖2所示。然後，再從右至左逐一 比較兩兩對齊的字符，即字符T7與字符P5比較，字符T6與字符P4比較，以此類推。由於BM算法中，字符串P每向後跳進一次，均需要訪問文本中與字符串最後一個字符對齊的字符，在比較文本中的字符與字符串最後一個字符不相等後，需要將該字符與 字符串中其他字符進行一次比較分析。在實際應用中，由於字符串最後一個字符跟文本中 與其對齊的字符不相等的情況是最為普遍的情況，因此在字符串每次跳進後執行上述操作 將消耗大量的時間，導致字符串匹配查找的效率低下。此外，應用BM算法查找匹配的字符時，為了避免向後跳進時跳出文本的邊界，在 每次跳進後均需要判斷是否到達文本的最後一個字符，執行該判斷也消耗大量的時間，導 致字符串匹配查找的效率不高。

發明內容
本發明的目的是提供一種效率較高的字符串的匹配查找方法。為此，本發明提供的字符串匹配查找方法包括以下步驟
建表步驟依需查找的字符串確定查找過程中遇到預先設定位數的字符個數的任意字 符時字符串的跳進距離，建立跳進表格；
對齊步驟將字符串的第一個字符與文本的第一個字符對齊； 跳進步驟查詢文本中與字符串倒數設定位數個字符對齊的判別字符，根據判別字符 查詢跳進表格，確定字符串的跳進距離，字符串向後跳進該跳進距離； 重複執行跳進步驟到達預先設定次數；
比較步驟自字符串最後一位字符開始，判斷字符串的每一字符跟文本中與該字符串 每一字符所對齊的字符是否相同，若相同，則比較下一字符，直至查找到匹配的字符串；若 不相同，返回執行跳進步驟。由上述方案可見，查找匹配字符串時，不需要將文本中的字符與字符串中的所有 字符進行逐一比較，而是直接根據跳進表格進行多次跳進，並在多次跳進後進行一次比較， 這樣可大大減少匹配過程所消耗的時間，提高字符串匹配查找的效率。一個優選的方案是，比較步驟中比較下一字符時，若下一字符跟文本中與該字符 對齊的字符不相同，則字符串向後跳進一位，返回執行跳進步驟。由此可見，比較過程不是將文本的字符與字符串的所有字符進行逐一比較，而是 一旦發現有不同的字符，即馬上返回執行跳進步驟，也能減少匹配查找過程中的時間消耗。進一步的方案是，執行對齊步驟後、跳進步驟前，在文本最後一個字符後增加一組 字符串形成擴展文本，查找到匹配的字符串後，判斷是否到達擴展文本的最後字符。可見，查找匹配的字符串過程中，無需每跳進一次判斷是否超出文本邊界，只有在 查找到匹配的字符串後才進行一次判斷工作，也大大減少在判斷是否超出文本邊界時所消 耗的時間，提高字符串匹配查找的效率。再進一步的方案是，建表步驟還包括去掉字符串的最後一位字符形成輔助字符 串，根據輔助字符串建立輔助跳進表格；跳進步驟還包括重複執行跳進步驟到達設定次數 後，查詢文本中與輔助字符串倒數設定位數個字符對齊的輔助判別字符，根據輔助判別字 符查詢輔助跳進表格，確定字符串的跳進距離，字符串向後跳進相應位數。這樣，通過輔助字符串及輔助跳進表格輔助字符串的跳進，可有效避免因文本中 出現連續多個與字符串最後一個字符相同的字符而導致字符串多次不跳進或跳進距離過 短，從而提高字符串的匹配查找效率。
此外，本發明提供的字符串匹配查找方法還可以是通過以下步驟實現
建表步驟在需要查找的原字符串後添加與原字符串相同的擴展字符串形成對比字符 串，根據對比字符串確定查找過程中遇到任意一對字符時對比字符串的跳進距離，建立跳 進表格；
對齊步驟將對比字符串的第一個字符與文本的第一個字符對齊； 跳進步驟查詢文本中與原字符串最後一位字符對齊的第一判別字符以及與擴展字符 串最後一位字符對齊的第二判別字符，根據第一判別字符及第二判別字符查詢跳進表格， 確定對比字符串的跳進距離，對比字符串向後跳進該跳進距離； 重複執行跳進步驟到達預先設定次數；
比較步驟判斷原字符串最後一字符跟文本中與原字符串最後一字符所對齊的字符是 否相同，並判斷擴展字符串的最後一字符跟文本中與擴展字符串最後一字符所對齊的字符 是否相同，若上述判斷結果為任一相同，則比較結果為相同的一組字符串的餘下字符，直至 查找到匹配的字符串，若上述判斷結果為均不相同，返回執行所述跳進步驟。由上述方案可見，字符串匹配過程中無需將文本的字符與字符串中所有字符進行 逐一比較分析，可減少因逐一比較分析所消耗的時間，提高了字符串匹配查找的效率。此 外，在原字符串後添加擴展字符串，可同時對原字符串與擴展字符串進行比較，跳進的距離 更長，有利於對比字符串的快速跳進，可更快地查找出匹配的字符串。一個優選的方案是，比較步驟中比較餘下字符時，若餘下字符中任一字符跟文本 中與該字符對齊的字符不相同，則對比字符串向後跳進一位，返回執行所述跳進步驟。由此可見，在比較步驟後，文本的字符也不需要與字符串中所有字符進行逐一比 較，一旦發現有不相同的字符，即馬上跳進，減少不必要的時間消耗，提高匹配查找的效率。


圖1是現有字符串匹配查找方法中字符串與文本對齊的示意圖。圖2是現有字符串匹配查找方法中字符串跳進後的示意圖。圖3是本發明第一實施例中建立跳進表格的分析原理圖。圖4是本發明第一實施例中建立的跳進表的結構圖。圖5是本發明第一實施例匹配查找字符的示意圖。圖6是本發明第一實施例中建立的輔助跳進表的結構圖。圖7是本發明第一實施例中應用輔助跳進表格進行匹配查找字符的示意圖。圖8是本發明第二實施例中建立的跳進表的結構圖。圖9是本發明第二實施例匹配查找字符的示意圖。圖10是本發明第三實施例中建立的跳進表的結構圖。圖11是本發明第三實施例匹配查找字符的示意圖。以下結合附圖及實施例對本發明作進一步說明。
具體實施例方式本發明的構思是通過建立跳進表格，根據跳進表格確定字符串的跳進距離，從而 避免每一次跳進後對字符串每一字符的循環比較分析，減少字符比較所消耗的時間。
為了確保字符串匹配查找的快速進行，需要以文本長度與字符串長度為基準，區 分多種不同情況下所使用的具體方法。因此，可設置一個文本長度閾值以及字符串長度閾 值，執行字符串匹配查找前，首先對文本長度及字符串長度進行判斷，以確定使用哪一種具 體的方式。例如，設定文本長度閾值為100k，字符串長度閾值為8個字符，則在執行字符串匹 配查找前，首先判斷文本長度是否小於或等於文本長度閾值，若小於或等於，則使用第一實 施例的方法實現字符串的匹配查找，如文本長度大於文本長度閾值，則進一步判斷字符串 的長度是否大於字符串長度閾值，若小於或等於，則使用第二實施例的方法，否則使用第三 實施例的方法。應該說明的是，依據文本長度與字符串長度劃分出多種不同的具體實現的方法更 能凸顯本發明的優越性；然而，無論文本長度與字符串長度如何，均使用以下第一實施例或 第二實施例的方法也能較現有技術提高字符串的匹配查找速度。第一實施例。如前述，對字符串匹配查找時，可先判斷文本長度及需要匹配查找的字符串長度， 在判斷文本長度小於或等於IOOk時，優先選用本實施例。本實施例需要匹配查找的字符串為「match」，字符串長度為5位。本實施例字符串 跳進原則與現有的BM算法一致，即與字符串最後一個字符對齊的字符沒有在字符串中出 現，字符串向後跳進，跳進距離與字符串的長度相等，若與字符串最後字符對齊的字符在字 符串中存在，則字符串向後跳進以使字符串及文本中的兩個相同的字符對齊。參見圖3，假設標號為「1」的行(以下簡稱行1，以此類推)為文本，行2為字符串， 跳進時以字符串最後一個字符為判斷依據，即位數為「4」的字符「h」，也就是「*」號所指向 的字符。若文本中與字符「h」對齊的字符不是字符串中的字符，如圖3中的「P」，則字符串 向後跳進5位，記為
jump[ 『ρ，]=5(式 1)
同理，遇到其他不是「match」中任一字符的字符，字符串均跳進5位，如行8所示。若與字符「h」對齊的字符為「h」，則字符串不跳進，記為 jump[『h，]=0(式 2)
若與字符「h」對齊的字符為「C」，則字符串向後跳進1位，記為
jump[ 『C，]=1(式 3)
以此類推，可得到以下式子
jump[ 『t，]=2(式 4)
jump [ 『a，]=3(式 5)
jump [ 『m，]=4(式 6)
因此，可建立一個一維的數組，並以此建立一個跳進表格，如圖4所示，表格的第一行 為與字符串最後一個字符對齊的文本字符，第二行為字符串跳進的位數。字符串匹配查找 時，判斷與字符串最後一位字符對齊的字符是哪一字符，通過查詢跳進表可確定字符串的 跳進距離。如圖5所示，假設文本為「china what you not only match huge」，需要匹配的字符串為「match」。對字符串進行匹配查找時，首先將字符串與文本左對齊，即字符串的第一 個字符與文本的第一個字符對齊。然後，查詢與字符串最後一個字符對齊的字符，即行3中 「*」號指向的字符，該字符為「a」，通過查詢跳進表格，字符串向後跳進3位，如行4所示。 然後，再次查詢與字符串中最後字符對齊的字符，查詢到該字符為「h」，然後通過查詢跳進 表格判斷字符串的跳進距離，即0位，表示不跳進。此時，字符串將繼續重複查詢與字符串最後一位字符對齊的文本字符，重複執行 的次數可預先設定，且根據字符串最後一位字符決定。若字符串最後一位字符為通常文本 文件中出現頻率較高的字符，如a、e、t、空格等，則設定重複執行跳進步驟的次數較少，若最 後一個字符為出現頻率較低的字符，如ζ等，可設定重複執行的次數較多。字符的出現頻率 通過對大量文件分析獲得，因此是預先設定好的，且每一字符對應的設定次數也是預先設 定好的，只要獲知字符串的最後一個字符，即可相應地確定該字符串需要連續執行多少次 跳進。例如，根據預先設定的次數，對於字符「h」，設定次數為5次，則字符串需要連續執 行5次跳進。因此，如圖5所示的例子中，字符串後4次的跳進均為0位，也就是浪費了 4 次的跳進。進行5次跳進後，對字符串進行一次比較，比較是從字符串最後一位開始，逐一地 比較字符串每一字符以及與該字符對齊的文本字符，由於與字符串倒數第二位對齊的字符 跟該字符不相同，因此不需要再進行比較分析，字符串向後跳進一位，再次進行查詢判斷。再次查詢時，與字符「h」對齊的字符為「a」，如行6所示，字符串向後跳進3位， 並再次查詢跳進，之後多次查詢的結果中，與字符串最後一個字符對齊的文本字符分別是 「y」、「o」、「l」，這些字符均不在字符串中，因此字符串每次跳進5位，到第四次跳進後，與字 符「h」對齊的字符為「t」，根據跳進表格，字符串跳進2位，如行16所示。此時，字符串進行比較分析，通過分析可知字符串位於行16的位置時與文本中的 字符串完全相同，即查找到匹配的字符串。由上述方案可見，字符串的匹配查找過程中，字符串是根據與最後一個字符對齊 的文本字符查詢跳進表格，並確定字符串的跳進距離，因此無需在每次跳進後對字符串的 每一字符進行比較分析，減少了字符的比較分析時間，從而提高字符串的匹配查詢效率。字符串跳進時，需要判斷是否超出文本的長度，也就是判斷是否到達文本的最後 一個字符，若每次跳進時進行判斷，則浪費大量的時間。因此，本實施例中，在文本最後一個 字符後添加一組與需要查找的字符串相同的字符串，只有查詢到匹配的字符串後，才判斷 是否超出文本長度，這樣能減少判斷是否超出文本長度的時間，更能提高字符串的匹配查 找效率。此外，若文本中存在連續多個與字符串最後一個字符相同的字符，如圖7行1所示 的情況，文本中存在連續多個字符「h」，會導致字符串連續多次跳進距離為0，即無法形成 有效跳進。因此，需要設置一個輔助跳進表格以輔助跳進。設置輔助跳進表格時，首先定義輔助字符串，輔助字符串是將原字符串的最後一 個字符去掉後所得到的字符串，本實施例中，輔助字符串為「mate」，然後確定每一對於字符 的跳進距離，其計算方法與前述的建立跳進表格時的計算方法相同，所建立的輔助跳進表 格如圖6所示。此時，若遇到字符「h」，其跳進距離是4位。
參見圖7，若字符串跳進時遇到連續多個與字符串最後一位字符相同的字符，如行 4所示，字符串將無法進行有效跳進，因為每次跳進距離均為0。因此，需要字符串每跳進若 幹次後應用輔助字符串進行輔助跳進，字符串跳進的次數根據字符串最後一位字符確定， 即與前述的設定次數相同。例如，對於字符「h」而言，設定次數為5次，則字符串每跳進5 次後需要輔助跳進一次。圖7中行4所示，字符串多次跳進距離為0，因此應用輔助跳進表格，也就是與查詢 與輔助字符串最後一個字符「C」對齊的字符，該字符為「0」，則字符串跳進4位，如行8所 示，字符串跳進後成功跳過連續多個字符「h」，避免多次無效跳進。可見，通過設置輔助跳進字符串以及輔助跳進表格，能有效提高字符串的跳進效 率，從而提高字符串的匹配查詢效率。上述實施例是針對文本的長度小於或等於IOOk的情況，當文本的長度大於IOOk 時，本實施例的效率仍不夠理想，因此需要使用改進的方法實現。當判斷文本的長度大於 IOOk時，則進一步判斷需要匹配的字符串的長度是否大於字符串長度閾值，如8位，若小於 或等於，則採用第二實施例的方法。第二實施例。本實施例大致與第一實施例相同，不同之處是在原字符串後添加一組與原字符串 相同的擴展字符串形成對比字符串，應用對比字符串與文本的字符進行匹配並跳進。應用本方法時，需要建立跳進表格，此時跳進表格為一個二維的數組，如圖8所 示，表格的第一行為與原字符串最後一個字符對齊的字符，第一列為與擴展字符串最後一 個字符對齊的字符，表格中的數據為跳進的位數。因此，若與原字符串最後一個字符對齊的 字符為「t」，與擴展字符串最後一個字符對齊的字符為「m」，則字符串的跳進的位數為2為， 以此類推。參見圖9，進行字符串查找時，首先將對比字符串與文本左對齊，即對比字符串的 第一個字符與文本的第一個字符對齊，如圖9的行2所示。然後，查詢與原字符串最後一個 字符對齊的字符及與擴展字符串最後一個字符對齊的字符，分別為「a」、「t」，通過查詢跳進 表格可知，對比字符串需要向後跳進3位，如行2所示。然後再次進行查詢，查詢結果是一 對字符1」、「0」，因此跳進距離為0。經過預定此時的跳進後，開始比較對比字符串。比較時，從原字符串的最後一位開 始比較，同時從擴展字符串的最後一個開始比較，任一組字符串的最後一個字符跟與其對 齊的字符相同，則繼續對比該組字符串的餘下字符。如行4中，與原字符串最後一個字符對齊的字符跟該字符相同，但擴展字符串的 最後一個字符跟與其對齊的字符不相同，則只對比原字符串中餘下的字符。由於原字符串 的倒數第二個字符跟與其對齊的字符不相同，因此對比字符串向後跳進1位，如行6所示， 並重複進行查詢、跳進。當然，本實施例也是根據原字符串最後一個字符確定對比字符串跳 進的設定次數。向後跳進1位後，查詢到的字符分別為「a」、「u」，根據跳進表格，對比字符串向後 跳進3位，跳進後再次進行查詢，查詢到的字符分別是「y」、「o」，則對比字符串跳進10位， 再次查詢結果是「l」、「t」，因此對比字符串跳進7位，由於此時的查詢結果為「h」、「e」，因此 對比字符串跳進距離為0。
然後，通過對原字符串的每一字符與相應字符對齊的文本字符進行比較分析，查 找出相匹配的字符串。本實施例實際上是應用兩個原字符串同時進行查詢跳進，跳進的距離更長，可更 有效地提高字符串匹配查詢效率。此外，為了避免每次跳進均需要判斷是否超出文本邊界，可在文本最後一個字符 後添加兩組與原字符串相同的字符串形成擴展文本，跳進時無需判斷是否超出文本邊界， 只有查詢到匹配的字符串時才進行判斷。當然，查詢完畢後需要將所添加的兩組原字符串 刪除。並且，本實施例也設置輔助跳進字符串以及輔助跳進表格，輔助跳進字符串是在 原字符的基礎上刪除最後一位字符獲得，其與第一實施例的輔助字符串相同，因此建立的 輔助跳進表格也相同。因輔助跳進字符串與輔助跳進表格用於輔助跳進，無需建立二維數 據，因此應用與第一實施例相同的方法設置輔助字符串及輔助跳進表格即可。由於建立二維的跳進表格需要消耗一定的時間，因此對於文本長度較小的文本， 採用第二實施例將造成實際的浪費，選用第一實施例的方法可有效對小於或等於IOOk的 文本進行字符串的匹配查找。第三實施例。對於文本的長度大於文本長度閾值，且字符串長度也大於字符串長度閾值，如8 個字符的情況，由於文本字符與字符串最後一個字符相同的機率較高，本實施例將造成擴 展字符串無法體現其作用，因此需要同時查詢文本的兩位字符，判斷該兩位字符是否與字 符串中最後兩位字符相同來實現跳進。本實施例也需要建立跳進表格，假設需要匹配查找的字符為「onlymatch」，一共9 個字符。如圖10所示，表格的第一行表示與字符串倒數第二個字符對齊的字符，第一列表 示與字符串最後一個字符對齊的字符，表格內的數據是跳進距離。例如，與字符串最後兩位 字符對齊的字符是「qm」，則字符串的跳進距離是9位，若與字符串最後兩位字符對齊的字 符是「ma」，則字符串的跳進的位數為3位，以此類推。參見圖11，假設文本最前端的字符是「china what you not onlymatch」，進行字 符串匹配查詢時，首先將字符串與文本左對齊，如圖11中的行2所示。然後，將查詢與字符 串最後兩位字符對齊的文本字符，即查詢與「ch」對齊的兩個文本字符，查詢結果為「ha」， 通過查詢跳進表格可知，字符串的跳進的位數為9位，因此字符串向後跳進9位，如行4所示。跳進後，重複進行查詢與跳進操作，由於再次查詢結果為「ot」，字符串向後跳進9 位，並再次查詢。此時，查詢結果為「ct」，通過查詢跳進表格可知，字符串向後跳進1位，如 行8所示。若字符串的跳進次數未達到設定次數，則繼續跳進。但由於此時查詢與字符串 最後兩位字符對齊的文本字符為「ch」，通過查詢跳進表格，字符串跳進距離為0，即字符串 不進行有效跳進。當字符串跳進次數達到設定次數後，自字符串的最後一位開始進行比較分析，通 過比較分析判斷與字符串對齊的一串文本字符是否為匹配的字符串。如圖11所示的，字符 串經過3次有效跳進即查找到與其匹配的字符串，查詢效率較高。與第一實施例相同，可根據字符串最後一位字符確定字符串經過多少次跳進後進行一次比較，即設定次數。此外，還可以將字符串的最後一位字符去掉形成輔助跳進字符 串，並根據輔助跳進字符串建立輔助跳進表格。當字符串跳進達到設定次數後，使用輔助跳 進表格進行一次輔助跳進。當然，為避免字符串每次跳進時判斷是否超出文本邊界，可在文本最後一個字符 後添加一組需要匹配查找的字符串形成擴展文本，這樣，可僅在查找到匹配的字符串後才 判斷是否到達文本邊界，大大減少因判斷是否到達文本邊界而進行的判斷，從而減少時間 的消耗。若字符串中出現兩個或多個相同的字符，在建立跳進表格或輔助跳進表格時，以 跳進的位數最少的該字符作為字符串遇到該字符時的跳進判斷基準。可見，使用上述方法對字符串進行匹配查找時，僅在字符串經過多次跳進後進行 一次比較分析，而不需要在每次字符串跳進後進行比較分析，能減少字符串匹配查找過程 所消耗的時間，提高字符串匹配查找的效率。當然，上述實施例僅是本發明較佳的實施方案，實際應用時還可以有更多的變化， 例如，在需要匹配查找的字符串長度更長時，使用與字符串最後三位字符對齊的文本字符 作為對比分析的對象，或者，在字符串最後兩個字符相同的情況下，可去掉最後兩個字符作 為輔助字符串等，這些改變也能實現本發明的目的。最後需要強調的是，本發明不限於上述實施方式，如跳進步驟重複執行設定次數 的改變、查詢字符的設定位數的改變等變化也應該包括在本發明權利要求的保護範圍內。
權利要求
1.字符串的匹配查找方法，包括建表步驟依需查找的字符串確定查找過程中遇到預先設定位數的字符個數的任意字 符時所述字符串的跳進距離，建立跳進表格；對齊步驟將所述字符串的第一個字符與文本的第一個字符對齊；跳進步驟查詢所述文本中與所述字符串倒數設定位數個字符對齊的判別字符，根據 所述判別字符查詢所述跳進表格，確定所述字符串的跳進距離，所述字符串向後跳進所述 跳進距離；重複執行所述跳進步驟到達預先設定次數；比較步驟自所述字符串最後一位字符開始，判斷所述字符串的每一字符跟所述文本 中與所述字符串每一字符所對齊的字符是否相同，若相同，則比較下一字符，直至查找到匹 配的字符串；若不相同，返回執行所述跳進步驟。
2.根據權利要求1所述字符串的匹配查找方法，其特徵在於所述比較步驟中比較下一字符時，若所述下一字符跟所述文本中與該字符對齊的字符 不相同，則所述字符串向後跳進一位，返回執行所述跳進步驟。
3.根據權利要求1所述字符串的匹配查找方法，其特徵在於所述建表步驟還包括判斷所述文本的文本長度是否小於或等於文本長度閾值，如是， 設定所述設定位數為一位。
4.根據權利要求3所述字符串的匹配查找方法，其特徵在於如所述文本長度大於所述文本長度閾值，則進一步判斷所述字符串的字符串長度是否 大於字符串長度閾值，如是，設定所述設定位數為二位。
5.根據權利要求1至4任一項所述字符串的匹配查找方法，其特徵在於執行所述對齊步驟後、所述跳進步驟前，在所述文本最後一個字符後增加一組所述字 符串形成擴展文本；查找到所述匹配的字符串後，判斷是否到達所述擴展文本的最後字符。
6.根據權利要求1至4任一項所述字符串的匹配查找方法，其特徵在於執行所述建表步驟前，根據所述字符串的最後一個字符確定在所述跳進步驟後重複執 行所述跳進驟的所述設定次數。
7.根據權利要求1至4所述字符串的匹配查找方法，其特徵在於所述建表步驟中還包括去掉所述字符串的最後一位字符形成輔助字符串，根據所述輔 助字符串建立輔助跳進表格；所述跳進步驟還包括重複執行所述跳進步驟到達所述設定次數後，查詢所述文本中與 所述輔助字符串倒數所述設定位數字符個數對齊的輔助判別字符，根據所述輔助判別字符 查詢所述輔助跳進表格，確定所述字符串的輔助跳進距離，所述字符串向後跳進所述輔助 跳進距離。
8.字符串的匹配查找方法，包括建表步驟在需要查找的原字符串後添加與所述原字符串相同的擴展字符串形成對比 字符串，根據所述對比字符串確定查找過程中遇到任意一對字符時所述對比字符串的跳進 距離，建立跳進表格；對齊步驟將所述對比字符串的第一個字符與文本的第一個字符對齊；跳進步驟查詢所述文本中與所述原字符串最後一位字符對齊的第一判別字符以及與 所述擴展字符串最後一位字符對齊的第二判別字符，根據所述第一判別字符及所述第二判 別字符查詢所述跳進表格，確定所述對比字符串的跳進距離，所述對比字符串向後跳進所 述跳進距離；重複執行所述跳進步驟到達預先設定次數；比較步驟判斷所述原字符串最後一字符跟所述文本中與所述原字符串最後一字符所 對齊的字符是否相同，並判斷所述擴展字符串的最後一字符跟所述文本中與所述擴展字符 串最後一字符所對齊的字符是否相同，若上述判斷結果為任一相同，則比較結果為相同的 一組字符串的餘下字符，直至查找到匹配的字符串，若上述判斷結果為均不相同，返回執行 所述跳進步驟。
9.根據權利要求8所述字符串的匹配查找方法，其特徵在於所述比較步驟中比較餘下字符時，若所述餘下字符中任一字符跟所述文本中與該字符 對齊的字符不相同，則所述對比字符串向後跳進一位，返回執行所述跳進步驟。
10.根據權利要求8或9所述字符串的匹配查找方法，其特徵在於執行所述對齊步驟後、所述跳進步驟前，在所述文本最後一個字符後增加二組所述原 字符串形成擴展文本；查找到匹配字符串後，判斷是否到達所述擴展文本的最後字符。
全文摘要
本發明提供一種字符串的匹配查找方法，包括建表步驟依需查找的字符串確定查找過程中遇到預先設定位數的字符個數的任意字符時字符串的跳進距離，建立跳進表格；對齊步驟將字符串的第一個字符與文本第一個字符對齊；跳進步驟查詢文本中與字符串倒數設定位數個字符對齊的判別字符，根據判別字符查詢跳進表格，確定字符串的跳進距離，字符串向後跳進；重複執行跳進步驟到達預先設定次數；比較步驟自字符串最後一位字符開始，判斷字符串的每一字符跟文本中與該字符串每一字符所對齊的字符是否相同，若相同，則比較下一字符，直至查找到匹配的字符串，若不相同，返回執行跳進步驟。本發明能快速地查找需要匹配的字符串，查找時間短且效率高。
文檔編號G06F17/30GK102063510SQ20111000899
公開日2011年5月18日 申請日期2011年1月17日 優先權日2011年1月17日
發明者陳翔 申請人:珠海全志科技有限公司