Diary of Sacred Fox - January 25, 2003

アルゴリズムとデータ構造の試験前質問集 - No.2です

これは教科書上の問題ではなく配布資料中の問題です, 資料を持っていない方は別に親しくない人からでも構いませんが…周りの友人から入手してください
ついでに五十嵐先生のページ上にある講義時に使用したプログラムを手元に置いておくと役立つかもしれません
因みにいい加減なコードをいくつか置いてありますが, 本筋とは全く関係が無いので読み飛ばしてくださっても結構です

まず, 『番兵の手法』について
これは配列をwhileループで探索する時に配列の最後に継続条件に必ず反する終了条件を必ず満たすデータを余計に付けておいて条件判断から『まだ配列の中にある』ということをループを回すごとに命令数が1かさむのは(実行速度的に)勿体無いから別に調べる必要性をなくすことです

では順に見ていきましょう
ここでは検索される文字列のことテキストの長さをn, 検索する文字列のことパターンの長さをmとして話を進めます
テキストはPascalなので配列の添字は1から始まっていますが, 実際にはCで組むでしょうから0からとして話を進めます

先ずは『素朴なアルゴリズム』
これは単純にマッチ部分の開始位置で0～n - m - 1ループを組み, その中でパターン内の各文字に対して0 ～ m - 1ループを組んで一致しなければbreakすると言う方法です
Cで組むと動作確認はしてませんが…次のような感じでしょうか…

int simplematch(char * t と同じ意味です, 配列 = ポインタ, 覚えておこうchar t[], char p[]) {
  int n = strlen(t);
  int m = strlen(p);
  int i, j;
  for (i = 0; i < n - m; i++) {
    for (j = 0; j < m; j++)
      if (t[i + j] != p[j]) break;
    if (j = m) return i;     //見つかった(正常にループを抜けた)
    }
  }
  return -1;                 //見つからなかった
}

番兵の手法を使う場合は一時的にt[n]に最初からp[m]に入っていてパターン中にはあらわれない文字列終端記号, 2つの番兵は違っている必要があるので…'\0'以外の文字を入れておいて配列は実際には先頭のポインタで渡されているので中身はもとにもどさないとね関数を抜ける直前に元に戻すことにでもしておきましょう
こういうこういうのが大好きな人は少なからずいらっしゃいますが…姑息な改良は本質を見辛くするので理解するまでは改良前のアルゴリズムで考えたほうがよさそうです

次にKMPアルゴリズムを考えてみましょう
これは後述のBMアルゴリズムでも同じこのアルゴリズムの基本方針はまずパターンの特徴を解析して無駄な比較を減らすことにあります
パターンの≠ 1であることを仮定しています, 1だと何も情報は得られないので…j文字目で不一致が起こった時には既にテキスト中の手前(j - 1)文字はパターンの最初(j - 1)文字と一致していて今見ているの文字はパターンのk文字目とは違うと言うことまでは既に判っているのです
従ってこの情報を利用すれば今見ている文字よりも前の文字に戻って探索しなくても其処までの情報からある程度の探索を飛ばすことができるのです

では, 実際にどのぐらい飛ばせばいいの?
基本的には今までに見てきた(j - 1)文字のこういうのが無ければそこまでの部分はパターンに入っている可能性はありませんね最後の(t - 1)文字がパターン最初の(t - 1)文字と一致しているような被っている部分が多いと言うことはそれだけ少ししかパターンを動かせない最悪の場合と言えるでしょう最大のtを求めて, 丁度見ている文字の手前(t - 1)文字はパターンの最初部分に一致, 要するに新しいjはtになる!!(j - t)文字分先に進んで今の文字から比較を再開すればいいことになります
このjにとってのtをnext[j]として配列に保存していきます
ここでさらにp[j] = p[t]ならば移動後の比較でもすぐに『既に今見ている文字はp[j] = p[t]ではないと言うことも判っていますよね不一致→移動』と言う動作を行うので移動先はtのt文字目で不一致があったときのジャンプ量をj文字目の分についても足しこんでOK移動先と一緒で構わないことになります
つまりこれをやる前にnext[t]を求めておかなければいけないですねnext[j] = next[t]にできます, next[j]は小さい方が効率が良くて嬉しいというわけです
後はだけど一番良く起こる状況特殊な状況, j = 1についても考えておきます, 要するに最初からパターンと一致などしていない場合です
このときの動作は今までとは違ってその文字についてはこれ以上検討せずに次の文字からをパターンの最初からで検索することになります
このときの最初の文字での値, Pascalならnext[1]next[0]の値は今までの動作と違うことが判るように今までの『(k - 1)文字一致』で表現ざれるkの範囲(1以上)から外れた値を入れておけば区別できますよね0を入れておきましょう
あとはこのルールに従って最初から順番にnext[]の値を決めていけばいいのです
配布資料のプログラムではさらに大分姑息なことをやっている上に何も解説されていなかったりしますが, 基本方針はこんな感じです

今度はBMアルゴリズムについても見ていきましょう
これはKMP的作戦のほかにテキストをできるだけ飛ばし読みすると言う作戦が入っています
先ずは飛ばし読み作戦についてだけ考えて見ましょう
これはテキストをパターンの右側から当てはめていって最初に不一致が起こった文字についてその文字を含むパターンの当て方のうち最もずれが少ないものを次の比較対象にすればいい事がわかります
当然パターン中に無い文字が現れた場合はその文字が入っている部分は一致しないことが明らかなのでそのそこからm文字スキップしたところから調べればOK次の文字から始まるパターンについて調べ始めればよいということになります
また, 一致しない文字が右端に来るパターンは調べ終わっていることは明らかなので考慮しなくても良いですね
あとは配布資料中のプログラム5.1.7そのままです

蛇足: Cでは処理系によってはsignedだったりするcharを配列の添え字にはできませんから次のような感じにする必要があるとは思いますが…

int * initskip(char p[]) {
  int m = strlen(p);
  int * skip = この配列は関数の外でも使うので動的メモリ確保, グローバルな配列にしてもいいですcalloc(charのとる最大値(文字コードとしてintに自動でキャストされます), limits.hで定義されていますCHAR_MAX - CHAR_MIN + 1, sizeof(int));
  int i;
  for (i = CHAR_MIN; i <= CHAR_MAX; i++)
    skip[i 配列の範囲は0からなのでずらしてあげる必要があります, 使うときも同じ- CHAR_MIN] = m;
  for (i = 0; i < m 最後の文字を除いていますね- 1; i++)
    skip[p[i] 配列の範囲は0からなのでずらしてあげる必要があります, 使うときも同じ- CHAR_MIN] = m - j - 1;
  return skip;
}

ここで問題があります
例えばパターンが『abcde』の時に『abceedcdeabcde』を探索することを考えてみましょう
先ずは1～5文字目を探索, 5文字目のeが一致しているので4文字目を探索, 一致せず, skipにはパターンの最後以外にあらわれてませんよねeは無いので次は5～9文字目を探索, 後ろ3文字を見た後, 'b' $x[ne] 'd'なのでskipの'd'に正直に従うと…3～7文字目を探索, 戻ってしまっています
これでは無意味なのでもし探索範囲が戻る場合にはskipを無視して探索範囲を右に1ずらすようにする必要があります
それでもほんの少ししか動かせないのは勿体無い, だって'c'が次にあることは判っているのに'e'と比較する, 無駄でしょ?どうせ一致しないのは判っているのに…
というわけでKMP的手法をそこに取り入れることにしましょう
KMPとは違ってパターンをずらす方向がKMP: 比較は左から, ずらすのは右へ, BM: 比較は右から, ずらすのも右へ相対的に逆なので配布資料の図5.1.12～14のように少し複雑になります, そこでのs(ずらす量)の条件はそのページの右側にある式そのままです
表nextの計算方法についてはあまり本質的な感じではないような気がするので…, 必要だといわれたらまたやりますが…疲れてきたので省略します
結局はこの両方の作戦で求めたずらし量のうち大きい方を採用しつづければ上手くいくというのがBMアルゴリズムなのです

ここで3つのアルゴリズムを比較しておきましょう

1. 素朴・単純: テキストを何度も読みうる
2. KMP: テキストを丁度1通り読む
3. BM: テキストを適宜飛ばし読みする

最後に配布資料の範囲外ですが, 講義で扱ったので当然試験範囲Suffix Arrayについて簡単に説明して終わりにしましょう
これは文字列を2分探索するという考え方から出来た探索法で今までのようにパターンに加工を施すのではなくテキスト自体に加工を施します
因みにSuffixとは『接尾語』, 文字列の終わりの方という意味です
今までの逆ですね複数のパターンを一つのテキストに適用する時に威力を発揮します
例えば『聖狐はこれを早口では言えませんばすがすばくはつ』をこの方法で処理してみましょう
2分探索をするということは検索対象を辞書順にソートしておく必要があります
で, 何をソートするかと言うと『何処からパターンに当てはめるか』をソートすることになります
実際にやってみた方が早いので…

1. 先ずこの文を各開始位置からのSuffixのリストにします
   『ばすがすばくはつ』, 『すがすばくはつ』, 『がすばくはつ』, 『すばくはつ』, 『ばくはつ』, 『くはつ』, 『はつ』, 『つ』
2. これをソート法自体はどんな方法でもいいです, 普通はQuick Sortかな辞書順にソートします
   『がすばくはつ』, 『くはつ』, 『すがすばくはつ』, 『すばくはつ』, 『つ』, 『はつ』, 『ばくはつ』, 『ばすがすばくはつ』
3. この中からパターンを2分探索で探します(ex. 『ばくは』)
   境界上にパターンが来た時には後ろのリストを辿るようにすればリストの要素が1つになったときにパターンと一致するかどうかを判定すればOKです
   この場合リストの『ばくはつ』のところに来て, パターン『ばくは』が頭に来ているので見つかった事になります

この方法の欠点はこういうリストを保管するための領域が結構要るということにあると講義中でやっていましたが, Cだとポインタを悪用(?)すればさほどはかかりません(Javaだとかなり大変なことになりそう…)
いい加減に書いてみたルーチンでこのことを示すことによってこの話題を締めくくらせていただきます

char *(文字列)の配列char ** initsuffix(char * str) {
  int l = strlen(str);
  char ** sufary = calloc(l, sizeof(char *));
  int i:
  for (i = 0; i < l; i++)
    sufary[i] = str + i;                  //i番の要素はi文字目からのsuffixが入る
  /* sufary[]をstrcmpによる比較でソート */
  return sufary;
}
int find (char * t; char ** sufary, char * p) {
  int i = 0;
  int j = strlen(t) - 1;
  char * res;
  while (i < j) {
    int pivot = (i + j) / 2;
    int r = strcmp(sufary[pivot], p);
    if (r == 0) return ポインタの差 = 先頭からの文字数sufary[pivot] - t; //一致, これ以上探索する必要はない
    else if (r < 0) j = pivot;
    else i = pivot + 1;
  }
  res = sufary[i];
  while (*p != '\0') {                    //最初のm文字が一致してもテキストはまだ続くのでその次の文字で引っかかるstrcmpは使えないので手動比較
    if(*p != *res) return -1;             //不一致
    p++;
    res++;                                //次の文字へ
  }
  return ポインタの差 = 先頭からの文字数sufary[i] - t;                   //一致, resは壊してしまったのでこっちを利用
}
int main(int argc, char * argv[]) {
  char * str = "ばすがすばくはつ";
  char ** sufary = initsuffix(str);
  printf("%d", find(str, sufary, "ばくは"));
  return 0;
}

だってソートを書くのが面倒なんだもん…動作確認はしていないので保証はできません
因みに一種の横着かもしれませんが…インデックスはポインタの引き算で求めているので引数tはinitsuffixで用いたものと文字列としてではなくポインタとして等しいということ全く同一のものである必要があります
単にsufaryの仕様を1番から使うことにして0番にt自体を記録しておけばOKもう少し変えれば要らなくなる引数なのですが…