[發明專利]大字符串匹配方法

無效

• 申請號: 02134428.0
• 申請日: 2002-07-24
• 公開（公告）號: CN1392497A
• 公開（公告）日: 2003-01-22
• 發明（設計）人: 彭泉
• 申請（專利權）人: 彭泉
• 主分類號: G06F17/22
• 分類號: G06F17/22
• 代理公司: 廣州市新諾專利事務所有限公司
• 代理人: 華輝

1.一種大字符串匹配方法，按以下步驟進行：

a)在需要匹配的兩個大的字符串M、N中選擇一個特征字符或字

??符串序列，根據特征字符或字符串序列對所要匹配的兩個字符

??串分別分段，得到{M_i}，{N_j}，用散列變換方法計算每段小字符

??串M_i和N_j的散列值，以散列值為元素組成變換序列(a_i，b_i)和

??(c_j，d_j)，這樣把需要匹配的兩個大的字符串分別變換成序列{(a_i，b_i)}

??以及{(c_j，d_j)}；

b)然后對序列{(a_i，b_i)}、{(c_j，d_j)}按照a_i＝c_j并且b_i＝d_j為條件進行匹

??配，標記出匹配項；

c)序列{(a_i，b_i)}、{(c_j，d_j)}中匹配和不匹配所對應的段分別處理，其

??中匹配項對應的小字符串段進行字符串匹配，并進一步標記出

??小字符串段中的匹配和非匹配內容并輸出匹配和非匹配內容；

??做為粗匹配，非匹配項對應的小字符串段全部作為非匹配內容

??輸出；做為細匹配，可以對各個非匹配段進行進一步匹配，找

??出更多的匹配內容。

2.按權利要求1所述的一種大字符串匹配方法，其特征在于：所述步驟a)中的散列變換采用計算每段小字符串的長度和以及段中各字符累加和的散列計算方式，變換為一對關于段的長度及段中各字符累加和的序列M_i(a_i，b_i)以及N_j(c_j，d_j)。

3.按權利要求1或2所述的一種大字符串匹配方法，其特征在于：所述的M_i(a_i，b_i)與數組N_j(c_j，d_j)的匹配以及各段小字符串的匹配采用對角線優先匹配方法，按以下步驟進行：a)把需要匹配的兩個字符串生成一個矩陣，以矩陣左上角元素，??即M(0，0)為起點，b)從起點開始，搜索從該點向右下方向的一個1*1矩陣，檢查該??點是否匹配，如果是，將該點的右下點作為新的起點，重復步??驟(b)；c)否則，將該矩形向右下擴大一行和一列，即以矩形右下角的點??的右下點作為新的矩形右下角，在矩形內部搜索匹配點，如果??找到，則以該點的右下點為新的起點，轉回步驟(b)繼續搜索；d)如果沒有找到，重復步驟(c)，直到搜索達到矩陣的邊界為止，??搜索結束；e)標記步驟(a)-(d)中搜索到的匹配點，就是兩個數組或字符串的匹??配部分。