文字列検索

• 最も単純な文字列検索
• KMP法
• BM法

最も単純な文字列検索

基本的な考え方

　先頭から順番に1つずつ調べていき、文字列パターンが一致するまで進めていく。単純だけれど、効率はあまりよくない。

def simpleSearch( text, pattern )
  n = 0
  while n < text.length
    much = false
    
    # 検索状態を確認するための表示
    printf "    本文 : #{text}¥nパターン : "
    i = 0
    while i < n
      print(" ")
      i += 1
    end
    puts "#{pattern}"
    
    # 検索
    i = 0
    while i < pattern.length
      if pattern[i] != text[n + i]
        # 一致しなかったので、最初のループに戻る
        much = false
        break
      end
      much = true
      i += 1
    end
    n += 1
    return n if much == true
  end
  # 最終的に一致しなかった
  return false
end

p simpleSearch("TeamSwift", "if")
p simpleSearch("TeamSwift", "id")

KMP法

基本的な考え方

　比較に失敗したときに、再比較を開始する位置を把握しておく。

　理論上は非常に効率がいいが、現実的にはアルゴリズムが複雑な分、オーバヘッドが大きくなってしまい、あまり長くない文字列を検索する場合は、単純な文字列検索の方が良好なパフォーマンスを示すことが多い。

def kmpSearch( text, pattern )
  textIndex = 1
  patternIndex = 0
  cacheTable = Array.new(pattern.length + 1)
  cacheTable[0] = cacheTable[1] = 0
  
  # KMP 検索に必要な情報を予め計算し、配列にキャッシュする
  while pattern.length > textIndex
    if pattern[textIndex] == pattern[patternIndex]
      # 一致したら再比較は pattern_index 文字から始める
      textIndex += 1
      patternIndex += 1
      cacheTable[textIndex] = patternIndex
    elsif
      # パターン1文字目で不一致なら再検索は先頭から
      textIndex += 1
      cacheTable[textIndex] = 0
    else
      # パターン1文字目以外で不一致なら再検索の位置は cache_table から参照
      patternIndex = cacheTable[patternIndex]
    end
  end
  
  # ここから実際の検索
  i = 0
  n = 0
  while n < text.length
    printf "    本文：#{text}¥n"
    printf "パターン："
    l = 0
    while l < n
      printf " "
      l += 1
    end
    printf "#{pattern[i].chr}¥n"
    
    if text[n] == pattern[i]
      # テキストとパターンが一致していれば、1字ずつ比較を続ける
      n += 1
      i += 1
      if pattern.length == i
        # 全て一致すれば OK
        return n - pattern.length
      end
    elsif i == 0
      # パターン最初の文字で失敗した場合は、比較場所を1つ進める
      n += 1
    else
      # 最初の文字でない場合は、テーブルから比較位置を取得する
      i = cacheTable[i]
    end
  end
  return false
end

p kmpSearch("a eighty-eighty-eighth key", "eighty-eighth")

BM法

基本的な考え方

　KMP 法では、文字列をパターンの前方から後方に向かって比較していたのに対して、BM法では、後方から前方に向かって比較する。

1. パターンの末尾から前方に向かって文字の比較を行う
2. 不一致が生じたときに、本文側の文字がパターンに含まれていなければ、パターンの先頭をその次の位置に移動する
3. 不一致が生じたときに、本文側の文字がパターンに含まれていれば、パターンの中でその文字が最後に登場する位置が、不一致発生点に重なるようにパターンを移動する
4. パターンが前に戻ってしまう場合は、1つだけ後ろにずらす
5. パターン全体が一致したら「発見」。比較位置が本文の最後を超えてしまったら「検索失敗」

def bmSearch( text, pattern )
  # 文字列で不一致が生じたときの比較点の移動量を予め計算してキャッシュするテーブル
  cacheTable = Array.new(256)
  
  # 不一致が生じた移動量を予め計算し、キャッシュする
  cacheTable.each_index do |i|
    cacheTable[i] = pattern.length
  end
  
  i = 0
  while i < pattern.length
    # パターンに含まれている文字は、それに併せてずらす。
    # 同じ文字が複数含まれている場合は、最後に登場する文字にあわせる
    cacheTable[pattern[i]] = pattern.length - i - 1
    i += 1
  end
  
  # 移動量のキャッシュはここまで
  textIndex = pattern.length - 1
  
  while textIndex < text.length
    printf "    本文：#{text}¥n"
    printf "パターン："
    i = 0
    while i < textIndex - pattern.length + 1
      printf " "
      i += 1
    end
    puts pattern
    
    # パターンの後ろから比較を始める
    patternIndex = pattern.length - 1
    
    while text[textIndex] == pattern[patternIndex]
      if patternIndex == 0
        # パターンの先頭文字まで全て比較成功すれば OK
        return textIndex
      end
      textIndex -= 1
      patternIndex -= 1
    end
    
    if cacheTable[text[textIndex]] > pattern.length - patternIndex
      # その文字に応じて比較点を移動
      textIndex += cacheTable[text[textIndex]]
    else
      textIndex += pattern.length - patternIndex
    end
  end
  return false
end

p bmSearch("On a dark desert highway, cool wind in my hair", "wind")