文字列処理のアルゴリズム-代表的なアルゴリズム4

この記事での学習内容 基本情報 応用情報

文字列処理のアルゴリズムを理解する。

用語例:文字列照合、KMP法(クヌース・モリス・プラット法)、BM法(ボイヤ・ムーア法)

文字列処理のアルゴリズム

文字列処理のアルゴリズムは、一連の文字の並びを処理するアルゴリズムです。

  • 連結: 一つの文字列の後へ別の文字列を追加して、一つの文字列にします。
  • 挿入: 文字列の途中に別の文字列を挿入して、一つの文字列にします。
  • 削除: 文字列の一部の文字を取り除いて、残りを一連の文字列にします。
  • 照合: 文字列が別の文字列の中に含まれるか、有無を調べて位置を特定します。

順次探索法

  1. 対象の文字列の先頭の文字から、特定の文字列を一文字ずつ照合する。
    すべての文字が一致したら、全体の処理を終了して対象の文字列の位置を返す。
  2. 対象の文字列の1文字後ろから1の処理を反復する。対象の文字列の最後を越えたら、探索失敗として終了する。

ボイヤ・ムーア法(BM法)

ボイヤとムーアによって考案された、高速の文字列照合アルゴリズムです。特定の文字列の後尾から前の方へ照合することと、一致しない場合には、複数の文字をスキップすることが特徴です。

  1. 特定の文字列を前処理して、「特定の文字が何文字目に出現するかを表す表」「一致した文字のパターンと、その場合にスキップしていい文字数を対応付ける表」の2表を作成する。
  2. 対象の文字列の先頭部分を特定の文字列の後尾から前方向へ、文字の比較をすすめる。
    一致したら全体の処理を終了して、対象の文字列の位置を返す。
  3. 一致しなかったら、比較時に得られた情報と1で作った表を元にして、文字をスキップし、2の処理に戻る。