DIV CSS 佈局教程網

JavaScript 數據結構與算法(五):KMP 算法與部分匹配表
編輯:JavaScript綜合知識     

上一篇講的 BF 算法勝在直白,弱點也同樣直白:失配就回退,已比較過的信息全部作廢。KMP 正是針對這一點而生的優化方案。本文用「已匹配信息能否再利用」這條主線,把 KMP 的核心——部分匹配表(next 數組)——一步步推導出來,並給出兩種 JavaScript 實現。

前綴匹配與後綴匹配

KMP 與 BM 是兩大經典算法,分別代表前綴匹配與後綴匹配。二者的區別只在比較順序:

  • 前綴匹配:模式串與主串的比較從左到右,模式串的移動也從左到右。
  • 後綴匹配:模式串與主串的比較從右到左,模式串的移動從左到右。

顯然 BF 屬於前綴匹配。KMP 是它的優化版本,名字取自三位作者 Knuth、Morris、Pratt 的姓氏首字母。

KMP 到底優化在哪

對比 BF 與 KMP 的移動距離可以發現:在文本串 T 中匹配模式串 P,當比較到第 6 個字符 c 時失配,BF 的做法是把整個模式串右移一位,KMP 則移動了兩位。

為什麼是兩位,而不是一位或三位?關鍵信息在於:模式串 P 的 ababa 這一段是匹配成功的。KMP 的核心思想就是——不要丟棄這段成功信息,不要把主串指針移回已經比較過的位置,而是利用它算出下一個合理的起點。

移動位數怎麼算

KMP 的作者們給出了公式:

移動位數 = 已匹配的字符數 − 對應的部分匹配值

要特別注意:這個偏移量只與模式串(子串)有關,與文本串完全無關。這意味著部分匹配表可以預先算好、反覆使用。

什麼是「已匹配的字符數」

T : abababaabab
P : ababacb

模式串中前綴 ababa 匹配成功,到 c 處失配,因此已匹配字符數為 5。這一步很直觀。

什麼是「部分匹配值」

這是最難理解的部分。先看一個例子:

T:aaronaabbcc
P:aaronaac

如果在匹配到 c 時出錯,按上一段的結構來看,模式串應該往哪裡移最合理?

aaronaabbcc
    aaronaac

也就是說:如果模式串內部某段字符「頭尾相同」,那麼移動時就可以跳過這一段。這個思路顯然是合理的,因為頭尾相同意味著移動後這些字符仍然能對上。

前綴與後綴的定義

要把上面的直覺變成可計算的規則,需要兩個概念:

  • 前綴:除了最後一個字符以外,一個字符串的全部頭部組合。
  • 後綴:除了第一個字符以外,一個字符串的全部尾部組合。

部分匹配值 = 前綴與後綴的最長共有元素的長度。

以 aaronaac 為例,BF 的移動劃分是 a, aa, aar, aaro, aaron, aarona, aaronaa, aaronaac,而 KMP 需要為每一個已匹配字符計算前綴與後綴的最長共有長度,最終得到部分匹配表:

a a r o n a a c
[0, 1, 0, 0, 0, 1, 2, 0]

逐位拆解部分匹配表

把每一位的計算過程列出來,規律就一目了然(p 表示前綴集合,n 表示後綴集合,r 表示結果):

a        p=>[]                             n=>[]                              r = 0
aa       p=>[a]                            n=>[a]                             r = 1
aar      p=>[a, aa]                        n=>[r, ar]                         r = 0
aaro     p=>[a, aa, aar]                   n=>[o, ro, aro]                    r = 0
aaron    p=>[a, aa, aar, aaro]             n=>[n, on, ron, aron]              r = 0
aarona   p=>[a, aa, aar, aaro, aaron]      n=>[a, na, ona, rona, arona]       r = 1
aaronaa  p=>[..., aarona]                  n=>[a, aa, naa, onaa, ronaa, ...] r = 2
aaronaac p=>[..., aaronaa]                 n=>[c, ac, aac, naac, ...]         r = 0

可以看到 aa 的前後綴都是 a,長度 1;aaronaa 的最長共有元素是 aa,長度 2;其餘位置沒有共有元素,記為 0。

實現一:預先算好匹配表

KMP 與 BF 最大的差別就在這張表——沒有表就是 BF,加上表就是 KMP。

function kmpGetStrPartMatchValue(str) {
  var prefix = [];
  var suffix = [];
  var partMatch = [];

  for (var i = 0, j = str.length; i < j; i++) {
    var newStr = str.substring(0, i + 1);   // 逐位擴展子串
    if (newStr.length == 1) {
      partMatch[i] = 0;
    } else {
      for (var k = 0; k < i; k++) {
        prefix[k] = newStr.slice(0, k + 1);  // 取前綴
        suffix[k] = newStr.slice(-k - 1);    // 取後綴
        if (prefix[k] == suffix[k]) {
          partMatch[i] = prefix[k].length;   // 記錄最長共有長度
        }
      }
      if (!partMatch[i]) partMatch[i] = 0;
    }
  }
  return partMatch;
}

回退環節幾乎可以照搬 BF,唯一要改的是:BF 失配時主串指針 i 直接回退一位,KMP 則依據匹配表算出應該移動的距離。

// 子循環核心片段
for (var j = 0; j < searchLength; j++) {
  if (searchStr.charAt(j) == sourceStr.charAt(i)) {
    if (j == searchLength - 1) { result = i - j; break; }  // 匹配完成
    else { i++; }                                          // 主串指針前進
  } else {
    // 失配:利用部分匹配表跳過無用比較
    if (j > 1 && part[j - 1] > 0) {
      i += (i - j - part[j - 1]);
    } else {
      i = (i - j);   // 沒有可複用的前綴,退回起點下一位
    }
    break;
  }
}

完整版本把匹配表生成、主循環、結果返回串在一起即可,測試時可以拿 "BBC ABCDAB ABCDABCDABDE" 與 "ABCDABD" 對比原生 indexOf 的結果,並用 Date 差值打印耗時。

實現二:動態計算 next 值

第一種實現預先把整張表算出來,屬於典型的空間換時間。第二種思路是「用到哪算到哪」:不生成完整數組,只針對當前已成功匹配的前綴即時計算部分匹配值。

function next(str) {
  var prefix = [];
  var suffix = [];
  var partMatch;
  var i = str.length;
  var newStr = str.substring(0, i + 1);

  for (var k = 0; k < i; k++) {
    prefix[k] = newStr.slice(0, k + 1);
    suffix[k] = newStr.slice(-k - 1);
    if (prefix[k] == suffix[k]) partMatch = prefix[k].length;
  }
  if (!partMatch) partMatch = 0;
  return partMatch;
}

與匹配表版本的邏輯完全一致,只是去掉了外層遍歷,直接定位到當前已匹配的串。在主循環的失配分支中改為:

} else {
  if (j > 1) {
    i += i - next(searchStr.slice(0, j));
  } else {
    i = (i - j);
  }
  break;
}

兩種實現如何取捨

  • 模式串固定、需要重複匹配大量文本:預生成匹配表更划算,一次預處理換來後續 O(1) 查表。
  • 模式串頻繁變化或只需匹配一次:動態計算 next 省去建表的時間與內存。
  • 兩者最壞時間複雜度均為 O(m + n),遠優於 BF 的 O(mn)。

理解 KMP 的門檻不在代碼,而在「為什麼可以移動兩位」。一旦接受了「前綴與後綴重合的部分可以跳過」這個前提,剩下的都是工程實現細節。後續若接觸 BM 算法,會發現它的優化邏輯換到了另一側——從後往前比較,同樣值得一看。

XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved