• 作成:

アルゴリズムとデータ構造2(文字列探索(2))

前回のおさらい

KMP法のnext配列生成の方法を全く記憶できていません.

難しいというのも理由の1つですが, BM法の方が高速なのにKMP法のアルゴリズムをちゃんと覚える気にならないということもあります.

BF法とKMP法とBM法

BF法による比較回数の数え上げがあまりにも面倒臭くてついRustでコードを書いてしまったのですが,

fn bf(source: &[char], word: &[char]) -> Option<usize> {
    let mut counter = 0;        // 比較回数
    for i in 0..source.len() {
        for j in 0..word.len() {
            counter += 1;
            if source[i + j] == word[j] {
                if j == word.len() - 1 {
                    println!("counter: {}", counter);
                    println!("index: {}", i);
                    return Some(i);
                }
            } else {
                break;
            }
        }
    }
    return None;
}

fn main() {
    bf(&("ちゅーちゅちゅっちゅちゅーるちゅるちゅるりら".chars().collect::<Vec<char>>()),
       &("ちゅる".chars().collect::<Vec<char>>()));
}

思い出してみると, 昔｢テキスト処理｣の講義でRubyで3つとも実装していました.

require 'benchmark'
require 'minitest/autorun'
require 'minitest/unit'

def simple_match(text, pattern)
  for i in 0 .. text.length - pattern.length
    for j in 0 ... pattern.length
      if text[i + j] != pattern[j]
        break
      end
      if j == pattern.length - 1
        return i
      end
    end
  end
  return -1
end

def kmp_match(text, pattern)
  i = 0
  j = -1
  back = [-1]
  while i < pattern.length - 1
    while j >= 0 && pattern[i] != pattern[j]
      j = back[j]
    end
    i += 1
    j += 1
    back[i] = j
  end

  i = 0
  while i < text.length - pattern.length + 1
    j = 0
    while text[i + j] == pattern[j] && j < pattern.length
      if j == pattern.length - 1
        return i
      end
      j += 1
    end
    b = j - back[j]
    i += b == 0 ? 1 : b
  end
  return -1
end

def boyer_match(text, pattern)
  for i in 0 .. text.length - pattern.length
    # 素直にdownto使ったら滅茶苦茶遅かった
    # for j in (pattern.length - 1).downto(0)
    #   if text[i + j] != pattern[j]
    #     break
    #   end
    #   if j == 0
    #     return i
    #   end
    # end
    j = pattern.length - 1
    while text[i + j] == pattern[j]
      if j == 0
        return i
      end
      j -= 1
    end
  end
  return -1
end

class TestMatch < MiniTest::Unit::TestCase
  def test_simple_kmp_boyer
    t = ('a'..'f').to_a
    1000.times {
      text = (0..rand(10000)).map { t[rand(t.length - 1)] }.join
      pattern = (0..rand(1000)).map { t[rand(t.length - 1)] }.join
      s = simple_match(text, pattern)
      k = kmp_match(text, pattern)
      b = boyer_match(text, pattern)
      assert([s, k, b].uniq.length == 1,
             "text: #{text}, pattern #{pattern}, #{s}, #{k}, #{b}")
    }
  end
end

Benchmark.bm 1000 do |r|
  t = ('a'..'f').to_a
  text = (0..rand(10000)).map { t[rand(t.length - 1)] }.join
  pattern = (0..rand(1000)).map { t[rand(t.length - 1)] }.join

  r.report('simple') {
    simple_match(text, pattern)
  }

  r.report('kmp') {
    kmp_match(text, pattern)
  }

  r.report('boyer') {
    boyer_match(text, pattern)
  }
end

実装はしていたのですが, KMP法のアルゴリズムはよくわかりません. どうやって実装してたんだ私?

ただ, このRuby実装はどうも講義のリファレンス実装と異なっていたようで, 検証には使えませんでした.

kmp_matchはnext配列を作るのではなくback配列を作るようになっていて, リファレンス実装と違って比較回数が短いみたいですね. back配列をどうやって作っているのかは謎. 過去の私の記憶がない.

boyer_matchは逆にリファレンス実装と比べて工夫が足りていないようで, 単に後ろから見ていっているだけで, 前処理のずらし配列を作っていないようです. リファレンス実装はパターンに含まれていない文字が出た時にずらしを最大にしていますが, 私の実装はそういった前処理を一切行っていないので比較回数が多いです.

ボイヤー-ムーア文字列検索アルゴリズム - Wikipediaなどを見て, 私のboyer_match実装はまともに前処理を行っていないBM法の要件を満たさないものだとわかりました.

プロファイリングを取ってboyer_matchが一番速かったから実装できていると思っていました. むしろなんでこんなので一番これが速いんだ…? まあ, もっと高速化する余地があったということみたいですね.

本物のBM法は不一致文字規則のために2次元テーブルを作るのは, std::array<std::map<char, int>>のようにすれば出来そうだなと用意にわかりますが, 一致サフィックス規則は何言ってるのか今ひとつわかりません. webにあるコードもちゃんと2次元テーブルを実装しているものすら無いですし…

頑張れば読み込めそうかなと思いましたが, コードを見てもひどく複雑でちょっと今読むのは諦めてしまいました.