文字列検索の話(その1): ナーイブ検索と KMP法 BM法

株式会社レトリバ

2023年8月28日 13:00

※こちらの記事は、2020年5月21日にRetrieva TECH BLOGにて掲載された記事を再掲載したものとなります。

CTO武井です。今回は2018/10/02にセミナーでお話した、文字列検索の話をブログにしようと思います。

セミナーでは時間の都合もあって、スライドにコードを載せてもなぁ、という感じで詳細は省いたのですが、ブログではコードが載せられますので、コードを載せつつ説明していこうと思います。

ブログの文量が毎回とんでもないことになってしまうので (参考: 前回(33654文字) 前々回(27624文字))、今回は3～4回ぐらいに分けて、月1ぐらいのペースで書いていこうかなと思っています。

セミナー動画はこちらからご視聴いただけます。
タイトル「基本に立ち返って文字列検索の話をします」

初回の今回は、インデックスを作らない検索、つまり、ナイーブな検索と、クエリを前処理する検索(KMP法とBM法)について説明します。

次回以降は、インデックスを作る検索やより複雑な検索の話、セミナーでは話せなかったAho-Corasickの話などをできればと思っています。 3/25にパッケージ版をリリースしました、高速塩基配列検索ソフトウェアGGGenomeでも使われているFM-Indexの話もする予定です！

文字列検索とは

まず、文字列検索について簡単に。

レトリバの製品のひとつにSedueという統合検索エンジンがあります。検索エンジンと聞くと、多くのところで使われており、それこそ小さなサービスでも実装されている、すでになじみの深い「どこにでもあるもの」と思われるかもしれません。

しかし、その検索エンジンを構成する要素は様々で、単純にクエリ文字列にマッチする文書を探す単純検索以外に、文書から文書を探すレコメンドであったり、マッチした文書をどんな順序で出すかのランキング、クエリ文字列をどのように解釈するかの意味解釈、あるいは前段処理として文章の構文を理解する構文解析、などなど、多岐にわたります。

これら全部を説明しようとすると、それこそ 500ページ近い本になってしまうわけですが、今回はその中でも「クエリ文字列にマッチする文書を探す単純検索」の「探すだけ」の部分、つまり文字列検索アルゴリズムについて取り上げようと思います。

情報検索全体については過去にレトリバセミナーで岩田が「情報検索の基礎」というタイトルで話しておりますので、こちらも是非ご覧ください！

文字列検索の一般的なタスクは「探し出したい文字列と、その文字列を探し出してくる元の文章が与えられた際、一致する箇所を返す」です。一致する箇所を返すのではなく、文書のなかにあるかどうかだけを真偽値で返すようなタスクや、一致した箇所をとりあえずどこでも一個だけ返す、あるいは一致した箇所はともかく個数を返すだけでいい、といったバリエーションもあります。

以降、このブログでは、探し出したい文字列を「クエリ」、探し出してくる元の文章を「テキスト」、一致する箇所を「ヒットポジション」と呼ぶことにします。 (「検索対象文字列」とかだとクエリなのかテキストなのか分からなくなってしまうことがあるのです……。)

ナイーブな方法

まずはナイーブな方法、つまり素朴で愚直な方法で文字列検索をしてみます。

// https://tech.retrieva.jp/entry/yyyy/dd/mm/HHMMDD

ssize_t NaiveSearch(const std::string& query, const std::string& text) {
  for (size_t t = 0; t + query.size() <= text.size(); ++t) {
    size_t q;
    for (q = 0; q < query.size(); ++q) {
      if (text[t + q] != query[q]) break;
    }
    if (q == query.size()) return t;
  }
  return -1;
}

二重ループの実装で、外側のループはテキストとクエリを合わせる位置で、一つずつずらしていきます。内側のループでクエリとの一致を確かめ、最後まで一致したらマッチ、といった感じです。

例えば「メカシャーク対メカメカジキ」というテキストから、「メカジキ」というクエリを探す場合、以下のようになります。不一致箇所は「×」、途中のbreakで比較が省かれた部分は「・」で表しています。

text:  メカシャーク対メカメカジキ
query: メカジキ
t=0:   メカ×・　　　　　　　　　　　二文字目まで一致、三文字目で不一致
t=1:   　×・・・
t=2:   　　×・・・
t=3:   　　　×・・・
t=4:   　　　　×・・・
t=5:   　　　　　×・・・
t=6:   　　　　　　×・・・
t=7:   　　　　　　　メカ×・　　　二文字目まで一致、三文字目で不一致
t=8:   　　　　　　　　×・・・
t=9:   　　　　　　　　　メカジキ　一致！

最悪計算量となるケースですとテキスト長×クエリ長の計算量が必要となります。たとえばこんな例ですね

text:  ららららららららららららららららららららら～
query: らららららら～
t= 0:  らららららら×
t= 1:  　らららららら×
t= 2:  　　らららららら×
t= 3:  　　　らららららら×
t= 4:  　　　　らららららら×
t= 5:  　　　　　らららららら×
t= 6:  　　　　　　らららららら×
t= 7:  　　　　　　　らららららら×
t= 8:  　　　　　　　　らららららら×
t= 9:  　　　　　　　　　らららららら×
t=10:  　　　　　　　　　　らららららら×
t=11:  　　　　　　　　　　　らららららら×
t=12:  　　　　　　　　　　　　らららららら×
t=13:  　　　　　　　　　　　　　らららららら×
t=14:  　　　　　　　　　　　　　　らららららら×
t=15:  　　　　　　　　　　　　　　　らららららら～

テキスト側での比較位置を見ると、行ったり来たり、三歩進んでは二歩下がる、という感じになっています。

ちょっと工夫したいですね。

KMP法

ナイーブな方法での比較位置の逆走を解消するアルゴリズムがKMP法になります。

逆走が必要なケースと、そうでないケースを比較してみます。たとえば「あいうえお」というクエリは、どんなテキストであれ、逆走する必要はありません。

text:  ああいうえをあいうえお
query: あいうえお
t= 0:  あ×・・・
t= 1:  　あいうえ×
t= 2:  　　×・・・・　←ここでは絶対ヒットしない。テキスト側の文字は必ず「い」のはずなので「あ」は絶対一致しない
t= 3:  　　　×・・・・　←ここでも絶対ヒットしない。テキスト側の文字は必ず「う」のはずなので「あ」は絶対一致しない
t= 4:  　　　　×・・・・　←ここも。テキスト側の文字は必ず「え」のはずなので、同上
t= 5:  　　　　　×・・・・　←ここは可能性があるかもしれない
t= 6:  　　　　　　あいうえお　←ヒット

というのも、例えば「お」で不一致した場合、その手前まではテキストがクエリの「あいうえ」が一致していたことを示します。

つまり、「あ」に続くテキストの次の文字は必ず「い」であるはずです。さらに次の文字は「う」ですし、更に次は「え」のはずです。

そしてそれらは、クエリの一文字目の「あ」とはマッチしないことは自明ですので、比較することなく、処理をスキップすることができます。

text:  ああいうえをあいうえお
query: あいうえお
t= 0:  あ×・・・
t= 1:  　あいうえ×
t= 5:  　　　　　×・・・・　←ここまで一気にスキップ！
t= 6:  　　　　　　あいうえお　←ヒット

だいぶ無駄を省けましたね。

では、「あいあいさ」というクエリはどうでしょうか？

text:  あいあいあいあいさ
query: あいあいさ
t= 0:  あいあい×
t= 1:  　×・・・・　←ここは絶対ヒットしない。テキスト側は「い」のはず
t= 2:  　　あいあい×　←ここはまだ可能性あり
t= 3:  　　　×・・・・　←ここは絶対ヒットしない
t= 4:  　　　　あいあいさ

さきほどの「あいうえお」の例では不一致した位置、この例でいう「t=4」までスキップしていましたが、「t=2」でもヒットする可能性が残っています。実際、「t=2」で失敗した後、(範囲外ですが)「t=6」までスキップしてしまうと、「t=4」のヒットを見逃してしまいます。

クエリの途中(部分文字列)に、クエリの先頭(接頭辞)と一致する部分がある場合、そこを合わせるようにスキップさせる必要があります。

ではスキップを導入してみましょう。

text:  あいあいあいあいさ
query: あいあいさ
t= 0:  あいあい×
t= 2:  　　あいあい×
t= 4:  　　　　あいあいさ

これだけだと、まだ比較位置はまだテキストの上を行ったり来たりしていそうです……。

もう少し考えると、「t=2」や「t=4」での先頭の「あい」は既に比較済みなことが分かります。改めて比較し直す必要はなく、先頭二文字のチェックは省けそうです。

text:  あいあいあいあいさ
query: あいあいさ
t= 0:  あいあい×
t= 2:  　　・・あい×　←先頭2文字は、一個手前で既にチェックしている
t= 4:  　　　　・・あいさ 　←先頭2文字は、一個手前で既にチェックしている

先頭に「・」が来ていますが、ここは比較の必要がない場所です。

この「いくつジャンプしてスキップできるか」、はテキストに依存せず、クエリだけで先に計算しておくことができます。

また、検索時は、 1) クエリ先頭での不一致は単に一個進める、 2) 途中での不一致は先に計算したスキップする量テーブル(よく next 関数とか言われます)で進む、とするだけでokです。

C++での実装例です。

class KMP {
 public:
  explicit KMP(const std::string& query) : query_(query) {
    next_.resize(query_.size());
    if (query_.empty()) return;
    next_[0] = -1;
    next_[1] = 0;

    size_t i = 2, j = 0;
    while (i < query_.size()) {
      if (query_[i - 1] == query_[j]) {
        next_[i++] = ++j;
      } else if (j > 0) {
        j = next_[j];
      } else {
        next_[i++] = 0;
      }
    }
  }

  ssize_t Search(const std::string& text, size_t i = 0) const {
    size_t q = 0;
    while (i < text.size()) {
      if (text[i] == query_[q]) {  // 一致: 照合を進める
        ++q;
        ++i;
      } else if (q == 0) {  // 先頭で不一致のときは次のテキストに進む
        ++i;
      } else {
        q = next_[q];  // 先頭以外での不一致はテキストは進めずに、nextで次の照合位置を得る
      }
      if (q == query_.size()) return (i - q);
    }
    return -1;
  }

 private:
  std::string query_;
  std::vector<size_t> next_;
};

コンストラクタで next の構築をしています。

構築はクエリを走査しつつ、その手前までの部分文字列が、クエリ全体の先頭と一致するか探して構築します。インデックス i でクエリを走査しつつ、インデックス j で先頭から並列して走査することでクエリ先頭と一致する文字列を探します。

接頭辞に一致する最長の部分文字列を見つけるため、文字が一致する限りは部分文字列を伸ばしていきますが、一致しなかった場合には、いっきに部分文字列の長さをゼロにするのではなく、少しずつ縮めていく必要があります。

例えば、 ABABAC....ABABAB というようなクエリでは、最後の B を除いた場合には ABABA が接頭辞が一致する部分文字列になっていますが、 B をいれた場合には ABAB と若干縮めた部分文字列が接頭辞と一致する最長の部分文字列となります。部分文字列を縮めるさいには、一文字ずつ縮めて試すのではなく、それまでに計算した next を使うことでより効率的に求めることができます。

以下は AABAAAA というクエリでの実際の挙動です。

コードと見比べながら挙動を追うと理解が進むかと思います！

検索に関しては不一致だった場合に、 next を使うケースが一個生えるだけです。

実装を見て分かる通り、テキストの比較位置(i)は遡ることがないため、ストリーム入力であったり、一文字ずつ入力されるようなケースでも、バッファを持つことなく検索することができます。

計算量としては、比較位置がテキスト上で逆走することなく進んでいくのでテキスト長だけで済むことが分かります。ただし、検索の前に next の構築が必要で、これがクエリ長の計算量になるため、テキスト長 + クエリ長が合計の計算量になります。

テキスト長 × クエリ長なナイーブな検索に比べると、ぐっとよくなりました。

BM法

テキスト長 + クエリ長なKMP法に対し、(一般的なケースでは) テキスト長 / クエリ長の計算量で検索をするアルゴリズムがBM法です。

BM法もKMP法と同じくスキップすることで計算量を減らしますが、BM法のコンセプトを分かりやすく言うと

「クエリってだいたい一致しないし後ろから見て、知らない文字ならまるごとスキップしてしまえ」

です。

つまり、

text:  あかさたなはまやらわ
query: あいうえお
t= 0:  ・・・・×　←クエリ「お」に対して「な」で不一致。ところで「な」ってクエリに含まれていないから……
t= 5:  　　　　　・・・・×　←ここまで一気に飛んでしまえ！

という感じに、KMP法では使わなかった「テキスト側の文字がなんだったか」という情報を使いジャンプ位置を決めます。上の例の場合、「な」がクエリに含まれていないため、クエリ長まるごとスキップすることができます。

理想的には、末尾で照合失敗すればクエリ長分だけスキップしつづけるため、計算量がテキスト長 / クエリ長となります。

ジャンプ位置の決定は、簡単には「失敗したテキストの文字とクエリの文字を合わせる」ようにジャンプします(不一致文字規則)。

つまり、クエリ「あいうえお」に対して、テキストが「う」で失敗した場合は以下のように、2文字ジャンプすることになります。

text:  おおあいうえお
query: あいうえお
t= 0:  ・・・・×　←失敗した相手は「う」
t= 2:  　　あいうえお　←クエリ中の「う」をテキストと合わせる位置にジャンプ

実装するには、文字毎にクエリのどこに出現するかのテーブル(というか辞書)が必要になります。クエリ中に同じ文字が複数回表れる場合は、検索漏れを防ぐため一番ジャンプ幅の少ないものを採用します。

簡単な実装は以下の様になります。

class BM {
 public:
  explicit BM(const std::string& query) : query_(query) {
    for (size_t i = 0; i < query_.size() - 1; ++i) {  // 最後の文字は最初に比較されるのでジャンプ計算から省く
      char_pos_[query_[i]] = i;
    }
  }

  ssize_t Search(const std::string& text, size_t i = 0) const {
    while (i + query_.size() <= text.size()) {
      ssize_t q;
      for (q = query_.size() - 1; q >= 0; --q) {
        if (text[i + q] != query_[q]) break;
      }
      if (q < 0) return i;  // みつかった

      // 不一致
      char text_ch = text[i + q];
      std::map<char, size_t>::const_iterator it = char_pos_.find(text_ch);
      if (it != char_pos_.end()) {
        ssize_t shift = q - it->second;  // クエリ内の最右出現位と、テキストを重ねるようにシフトする
        if (shift < 0) shift = 1;  // 最右出現位置を越してしまっていたら後戻りせず1だけずらす
        i += shift;
      } else {
        i += (q + 1);  // クエリにない文字なのでまるごとジャンプ
      }
    }
    return -1;
  }

 private:
  std::string query_;
  std::map<char, size_t> char_pos_;
};

この実装では、各文字のクエリでの最右出現位置を覚えておき、文字照合に失敗したときに今のクエリ位置に最右出現位置をあわせるようにしています。ただし、出現位置が現在の比較位置より右側にある場合、クエリとテキストをあわせようとすると逆戻りしてしまうので仕方なく1進めています。

BM法にはいくつかのバリエーションがあり、ひとつのバリエーションとして、この「仕方なく1進める」を防ぐため、最右出現位置だけでなく全箇所での出現位置を覚えておく実装も考えられます。

実現方法としては、クエリでの各位置での、そこから左側だけを考慮した最右出現位置を保存するテーブルを作ればokです。

例えば、 abracadabra に対しては以下のような表になります。 (-1 は出現しない = it != char_pos_.end() と同様)

クエリ文字比較位置(ソースコードでは q )でテーブルを引いて、あとは先ほどの同じようにすればokです。

あるいは他のバリエーションとして、KMP法同様に、途中まで一致した、という情報を使うものもあります(一致サフィックス規則)。

BM法の場合はKMP法と違い後ろからにはなりますが、考え方は同じで「途中まで一致した = そのパターンがクエリ内にあればその位置に合わせる」ということをします。

text:  れとりばらぶらどーる
query: あぶらかたぶら
t= 0:  ・・・・×ぶら
t= 2:  　　あぶらかたぶら　←不一致のテキストの「ら」を合わせるならここだけど
t= 4:  　　　　あぶらかたぶら　←接尾辞の「ぶら」が一致する最初のところはここ

この場合、どちらも照合は失敗してしまいますが、「t=2」では「ぶら」が絶対一致しないことが分かるため、よりジャンプ量の多い「t=4」まで飛ぶことができます。複数の規則を使う場合、よりジャンプ量の多いものを採用することで、計算量を減らすことができます。

さて、計算量としては前述の通り、「一般的なケース」ではテキスト長 / クエリ長で検索できそうですが、最悪ケースではどうでしょうか？

この「一般的なケース」から外れるケースとしては、例えば「文字数が極端に少ないケース(= まるごとジャンプできるケースがない)」や「テキストとクエリが同じ文字・同じパターンが大量に並ぶ(= 不一致文字規則が全然効かない)」などが挙げられます。

遺伝子の検索(文字種がACGTの4種しかなく、繰り返しパターンが多い)や、バイナリ列のパターン検索(文字種が2個しかない！)などが該当します。

最悪ケースの計算量は、簡単な実装だと「クエリをほぼまるごと走査した上で、ちょっとしかジャンプできない」が発生し、ナイーブな実装と同じテキスト長 × クエリ長まで落ちてしまいます。

また、クエリ長が短い場合にも、計算量の割り算部分の効きが少なくなるため、やはり計算時間が掛かってしまいす。

最悪計算量をテキスト長の線形、つまり計算量の悪化をKMP法と同等ぐらいまでおさえるヒューリスティック(ガリル規則)もありますが、自然言語処理の場合には、文字種が十分に多く、不一致したときの文字が合うようにずらす「不一致文字規則」が非常によく効いてくれるため、「不一致文字規則」だけの簡易なBM法でも十分(かつ実装としてもシンプル)なことが多いようです。

まとめ

さて、今回はインデックスを作らない検索を紹介しました。

ナイーブな検索ではテキスト長 × クエリ長の計算量が必要したが、不一致になったクエリの位置を使って逆走するのを防ぐKMP法ではテキスト長 + クエリ長、不一致になったテキストの文字種を使ってジャンプするBM法ではテキスト長 / クエリ長、と少ない計算量で検索することができます。

ただ、それでもインデックスを作らない検索ではどうしても、テキストの端から端まで、飛ばし飛ばしとはいえども辿る必要があり、巨大な文書では太刀打ちできなくなってしまいます。

そこで、検索対象のテキストをあらかじめ処理して検索を行う、インデックスを使った検索の登場です。あらかじめ全テキストに処理をするため、前処理の時間は掛かってしまいますが、一回あたりの検索速度をあげることができます。

次回はインデックスを使った検索、転置インデックスSuffix Arrayなどを紹介しようと思います。