文字列マッチング

2024年8月8日

概要

文字列マッチングは、テキストデータに含まれる特定の部分文字列 (パターン) を効率的に検索する技術である。大きな文書や巨大なデータベースで特定の単語やフレーズを見つけ出すために使用される。

概要
Naïve アルゴリズム
Rabin-Karp アルゴリズム
1. ローリングハッシュ
2. Rabin-Karp 文字列マッチング
Boyer-Moore アルゴリズム
参考文献

文字列マッチングの課題は次のように定義される。

入力: テキスト $t$ とパターン (検索文字列) $p$ 。
出力: パターン $p$ がテキスト $t$ の中に現われる最初の位置、またはすべての位置。

たとえば $t$ ="training the trainer"、 $p$ ="rain" の場合、文字列マッチングアルゴリズムは 1 または {1, 14} を返す必要がある。

Naïve アルゴリズム

ナイーブアルゴリズムによる文字列マッチングはテキスト $t$ の先頭から 1 文字ずつパターン $p$ と比較してその出現位置を検索する。

function naive(text, pattern) {
  let results = [];
  for (let i=0; i <= text.length-pattern.length; i++) {
    let j;
    for (j=0; j < pattern.length; j++) {
      if (text[i+j] !== pattern[j]) {
          break;
      }
    }
    if (j === pattern.length) {
      results.push(i);
    }
  }
  return results;
}

$|s|$ を文字列 $s$ の長さとすると、ナイーブアルゴリズムは最悪計算量は $O(|t||p|)$ で表される。これはテキスト $t$ ="aaaaaaa...", パターン $p$ ="aaa" のように、検索するパターンが頻繁に一致するようなケースにおいて最悪計算量に近くなる。

Rabin-Karp アルゴリズム

Rabin-Karp はテキスト $t$ からパターン $p$ を効率的に検索する手法である。最悪ケースで $O(|t||p|)$ だが、現実的に $O(|t|+|p|)$ を期待できることから、特にパターン $p$ が大きな文字列の場合にナイーブアルゴリズムより効率が良い。

ローリングハッシュ

ローリングハッシュ (rolling hash) は文字列のスライディングウィンドウに対して効率的にハッシュ値を更新できるハッシュ法である。Rabin-Karp アルゴリズムではローリングハッシュを使用して計算量を削減している。

ローリングハッシュの基本的なアイディアは、文字列 $s$ 上の $k$ -スライディングウィンドウを 1 文字ずつ右にずらすときに、新しいハッシュ値を前のハッシュ値から単純に算出することで、ハッシュ値を効率的に更新する。これによりハッシュ値の再計算にかかる時間を $O(k)$ から $O(1)$ に削減する点である。

ローリングハッシュの単純な例は、 $k$ -ウィンドウ内の文字の ASCII コードや Unicode の合計をハッシュ値とする実装である。 $\begin{equation} h(s[i:i+k]) = s_i + s_{i+1} + \ldots + s_{i+k-1} \label{rh0} \end{equation}$ ここで $s[i:j]$ は文字列 $s$ の $i$ 番目から始まり $j-1$ 番目で終わる部分文字列である。このようなハッシュ関数であれば、現在のハッシュ値から $k$ -ウィンドウから外れた文字を減算し、 $k$ -ウィンドウに新しく入った文字を加算することで次のハッシュ値を算出できる。 $\begin{eqnarray} h(s[i:i+k]) & = & h(s[i-1:i+k-1]) - s_{i-1} + s_{i+k-1} \label{rh} \\ & = & \left( s_{i-1} + s_i + \ldots + s_{i+k-2} \right) - s_{i-1} + s_{i+k-1} \nonumber \\ & = & s_i + s_{i+1} + \ldots + s_{i+k-2} + s_{i+k-1} \nonumber \end{eqnarray}$ 式 ( $\ref{rh}$ ) の計算量は $k$ によらず $O(1)$ であることに注意。ローリングハッシュにより $h(x) = h(y)$ のときに高い確率で $x = y$ を期待できる。

Rabin-Karp 文字列マッチング

Rabin-Karp アルゴリズムで使用されるローリングハッシュは Rabin フィンガープリント (Rabin fingerprint) に基づいている。これは式 ( $\ref{rh0}$ ) を基数 $b$ で多項式化したものである。 $\begin{equation} h(s[i:i+k]) = \left( s_i b^{k-1} + s_{i+1} b^{k-2} + \ldots + s_{i+k-1} \right) \bmod m \label{rkrh0} \end{equation}$ ここで $m$ は大きな素数のモジュロである。基数 $b$ はしばしば $s$ を構成する文字が取り得る最大値 + 1 (ASCII 文字であれば 256) が採用される。

式 ( $\ref{rkrh0}$ ) より、前のハッシュ値から次のハッシュ値は式 ( $\ref{rkrh}$ ) で算出できる。 $\begin{equation} h(s[i:i+k]) = \left\{ \left( h(s[i-1:i+k-1]) - s_{i-1} b^{k-1} \right) b + s_{i+k-1} \right\} \bmod m \label{rkrh} \end{equation}$ 式 ( $\ref{rkrh}$ ) の計算量は項 $b^{k-1}$ より $k$ に依存するが、 $b^{k-1}$ の値は $s_i$ に依存しないため最初の計算結果を再利用できる。

このようなローリングハッシュ関数 $h$ を想定すると、Rabin-Karp アルゴリズムは次のように表すことができる。

1.	${\bf function} \ {\rm RabinKarp}(t[n], p[k])$
2.	$\hspace{12pt}phash := h(p)$
3.	$\hspace{12pt}thash := h(t[0:k])$
4.	$\hspace{12pt}{\bf for} \ i \leftarrow 0 \ {\rm to} \ n-k \ {\bf do}$
5.	$\hspace{24pt}{\bf if} \ phash = thash \ {\bf then}$
6.	$\hspace{36pt}{\bf if} \ p = t[i:i+k] \ {\bf then}$
7.	$\hspace{48pt}{\it The} \ p {\it \ found \ at \ position \ } i.$
8.	$\hspace{24pt}thash := h(thash, t[i], t[i+k])$

8 行目のローリングハッシュ $h$ が $O(1)$ の計算量を持つためには、2 行目の $h(p)$ を計算したときに算出した $b^{k-1}$ を状態としてどこかに保持する必要がある。このため Rabin-Karp による文字列パターン検索は次のような実装になる。

function rabinKarp(text, pattern) {
  const base = 256; // 基数（ASCII文字の場合は256が一般的）
  const mod = 101;  // モジュロ（素数）
  let patternHash = 0;
  let currentHash = 0;
  let highestBase = 1;
  let result = [];

  // パターンと最初のテキスト部分文字列のハッシュ値を計算
  for(let i=0; i < pattern.length; i++) {
    patternHash = (patternHash * base + pattern.charCodeAt(i)) % mod;
    currentHash = (currentHash * base + text.charCodeAt(i)) % mod;
    if(i < pattern.length - 1) {
      highestBase = (highestBase * base) % mod;
    }
  }

  // テキスト内の部分文字列をスライドしてハッシュ値を比較
  for(let i=0; i <= text.length - pattern.length; i++) {
    if(currentHash === patternHash) {
      // ハッシュ値が一致する場合、文字ごとの比較を行う
      if(text.substr(i, pattern.length) === pattern) {
        result.push(i);
      }
    }

    // 次の部分文字列のハッシュ値を計算
    if(i < text.length - pattern.length) {
      currentHash = ((currentHash - text.charCodeAt(i) * highestBase) * base + text.charCodeAt(i + pattern.length)) % mod;
      if(currentHash < 0) {
        currentHash += mod;
      }
    }
  }

  return result;
}

ただし、最悪ケースでの計算量が多いことから、Rabin-Karp アルゴリズムは Knuth-Morris-Pratt や Boyer-Moore、その他のより高速な文字列マッチングよりも劣っている [1]。

Boyer-Moore アルゴリズム

Boyer-Moore アルゴリズムは最も効率的な文字列マッチングアルゴリズムであると考えられており、通常の文字列マッチングアプリケーションでは Knuth-Morris-Pratt アルゴリズムに比べても大幅に優れている [1]。このアルゴリズムやその簡略版はしばしばテキストエディタの検索や置換として実装されている。

参考文献

Himanshu B. Dave. Design and Analysis of Algorithms. ピアソン (2013)