CTO武井です。
今回は2018/10/02にセミナーでお話した、文字列検索の話をブログにしようと思います。
セミナーでは時間の都合もあって、スライドにコードを載せてもなぁ、という感じで詳細は省いたのですが、 ブログではコードが載せられますので、コードを載せつつ説明していこうと思います。
ブログの文量が毎回とんでもないことになってしまうので (参考: 前回(33654文字) 前々回(27624文字))、 今回は3～4回ぐらいに分けて、月1ぐらいのペースで書いていこうかなと思っています。
初回の今回は、インデックスを作らない検索、つまり、ナイーブな検索と、クエリを前処理する検索(KMP法とBM法)について説明します。
次回以降は、インデックスを作る検索やより複雑な検索の話、セミナーでは話せなかったAho-Corasickの話などをできればと思っています。 3/25にパッケージ版をリリースしました、 高速塩基配列検索ソフトウェアGGGenomeでも使われているFM-Indexの話もする予定です！
文字列検索とは
まず、文字列検索について簡単に。
レトリバの製品のひとつにSedueという統合検索エンジンがあります。 検索エンジンと聞くと、多くのところで使われており、それこそ小さなサービスでも実装されている、 すでになじみの深い「どこにでもあるもの」と思われるかもしれません。
しかし、その検索エンジンを構成する要素は様々で、単純にクエリ文字列にマッチする文書を探す単純検索以外に、 文書から文書を探すレコメンドであったり、マッチした文書をどんな順序で出すかのランキング、 クエリ文字列をどのように解釈するかの意味解釈、あるいは前段処理として文章の構文を理解する構文解析、などなど、多岐にわたります。
これら全部を説明しようとすると、それこそ 500ページ近い本 になってしまうわけですが、 今回はその中でも「クエリ文字列にマッチする文書を探す単純検索」の「探すだけ」の部分、つまり文字列検索アルゴリズムについて取り上げようと思います。
情報検索全体については過去にレトリバセミナーで岩田が「情報検索の基礎」というタイトルで話しておりますので、こちらも是非ご覧ください！
文字列検索の一般的なタスクは「探し出したい文字列と、その文字列を探し出してくる元の文章が与えられた際、一致する箇所を返す」です。 一致する箇所を返すのではなく、文書のなかにあるかどうかだけを真偽値で返すようなタスクや、 一致した箇所をとりあえずどこでも一個だけ返す、あるいは一致した箇所はともかく個数を返すだけでいい、といったバリエーションもあります。
以降、このブログでは、探し出したい文字列を「クエリ」、探し出してくる元の文章を「テキスト」、一致する箇所を「ヒットポジション」と呼ぶことにします。 (「検索対象文字列」とかだとクエリなのかテキストなのか分からなくなってしまうことがあるのです……。)
ナイーブな方法
まずはナイーブな方法、つまり素朴で愚直な方法で文字列検索をしてみます。
二重ループの実装で、外側のループはテキストとクエリを合わせる位置で、一つずつずらしていきます。 内側のループでクエリとの一致を確かめ、最後まで一致したらマッチ、といった感じです。
例えば「メカシャーク対メカメカジキ」というテキストから、「メカジキ」というクエリを探す場合、以下のようになります。 不一致箇所は「×」、途中の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++での実装例です。
コンストラクタで next の構築をしています。
構築はクエリを走査しつつ、その手前までの部分文字列が、クエリ全体の先頭と一致するか探して構築します。
インデックス i でクエリを走査しつつ、インデックス j で先頭から並列して走査することでクエリ先頭と一致する文字列を探します。
接頭辞に一致する最長の部分文字列を見つけるため、文字が一致する限りは部分文字列を伸ばしていきますが、 一致しなかった場合には、いっきに部分文字列の長さをゼロにするのではなく、少しずつ縮めていく必要があります。
例えば、 ABABAC....ABABAB というようなクエリでは、
最後の B を除いた場合には ABABA が接頭辞が一致する部分文字列になっていますが、
B をいれた場合には ABAB と若干縮めた部分文字列が接頭辞と一致する最長の部分文字列となります。
部分文字列を縮めるさいには、一文字ずつ縮めて試すのではなく、それまでに計算した next を使うことでより効率的に求めることができます。
以下は AABAAAA というクエリでの実際の挙動です。
| i | j | 一致する先頭文字列(下線) | 一致する部分文字列(下線) 照合失敗文字(括弧内) |
next | 備考 |
|---|---|---|---|---|---|
| 0 | - | AABAAAA | (A) | -1 | 部分文字列無し。不正なのでとりあえず -1 |
| 1 | - | AABAAAA | A(A) | 0 | 先頭と部分文字列が同じ箇所を指していて、そこに飛ぶと無限ループになるので 0 で固定 |
| 2 | 0→1 | AABAAAA | AA(B) | 1 | A=A で一致するので部分文字列を伸ばす |
| 3 | 1→0 | AABAAAA | AAB(A) | - | A!=B で不一致。今まで一致していた部分文字列 A は長さ1なので他に候補はないので j を先頭(=0)に戻す |
| 3 | 0 | AABAAAA | AAB(A) | 0 | 先頭に戻っても A!=B で不一致 |
| 4 | 0→1 | AABAAAA | AABA(A) | 1 | A=A で一致するので部分文字列を伸ばす |
| 5 | 1→2 | AABAAAA | AABAA(A) | 2 | A=A で一致するので部分文字列を伸ばす |
| 6 | 2→1 | AABAAAA | AABAAA(A) | - | B!=A で不一致。今まで一致していた部分文字列 AA は、 i=2 の時に一文字が接頭辞と一致していることが既に分かっている(AA(B) / next[2]=1)。新しい文字を足して接頭辞と一致する可能性があるので、 j をnext[2]=1 まで戻す。 |
| 6 | 1→2 | AABAAAA | AABAAA(A) | 2 | A=A で一致するので部分文字列を伸ばす |
コードと見比べながら挙動を追うと理解が進むかと思います！
検索に関しては不一致だった場合に、 next を使うケースが一個生えるだけです。
実装を見て分かる通り、テキストの比較位置(i)は遡ることがないため、
ストリーム入力 であったり、一文字ずつ入力されるようなケースでも、バッファを持つことなく検索することができます。
計算量としては、比較位置がテキスト上で逆走することなく進んでいくので テキスト長 だけで済むことが分かります。
ただし、検索の前に next の構築が必要で、これが クエリ長 の計算量になるため、 テキスト長 + クエリ長 が合計の計算量になります。
テキスト長 × クエリ長 なナイーブな検索に比べると、ぐっとよくなりました。
BM法
テキスト長 + クエリ長 なKMP法に対し、(一般的なケースでは) テキスト長 / クエリ長 の計算量で検索をするアルゴリズムがBM法です。
BM法もKMP法と同じくスキップすることで計算量を減らしますが、BM法のコンセプトを分かりやすく言うと
「クエリってだいたい一致しないし後ろから見て、知らない文字ならまるごとスキップしてしまえ」
です。
つまり、
text: あかさたなはまやらわ query: あいうえお t= 0: ・・・・× ←クエリ「お」に対して「な」で不一致。ところで「な」ってクエリに含まれていないから…… t= 5: ・・・・× ←ここまで一気に飛んでしまえ！
という感じに、KMP法では使わなかった「テキスト側の文字がなんだったか」という情報を使いジャンプ位置を決めます。 上の例の場合、「な」がクエリに含まれていないため、クエリ長まるごとスキップすることができます。
理想的には、末尾で照合失敗すればクエリ長分だけスキップしつづけるため、計算量が テキスト長 / クエリ長 となります。
ジャンプ位置の決定は、簡単には「失敗したテキストの文字とクエリの文字を合わせる」ようにジャンプします(不一致文字規則)。
つまり、クエリ「あいうえお」に対して、テキストが「う」で失敗した場合は以下のように、2文字ジャンプすることになります。
text: おおあいうえお query: あいうえお t= 0: ・・・・× ←失敗した相手は「う」 t= 2: あいうえお ←クエリ中の「う」をテキストと合わせる位置にジャンプ
実装するには、文字毎にクエリのどこに出現するかのテーブル(というか辞書)が必要になります。 クエリ中に同じ文字が複数回表れる場合は、検索漏れを防ぐため一番ジャンプ幅の少ないものを採用します。
簡単な実装は以下の様になります。
この実装では、各文字のクエリでの最右出現位置を覚えておき、文字照合に失敗したときに今のクエリ位置に最右出現位置をあわせるようにしています。 ただし、出現位置が現在の比較位置より右側にある場合、クエリとテキストをあわせようとすると逆戻りしてしまうので仕方なく1進めています。
BM法にはいくつかのバリエーションがあり、ひとつのバリエーションとして、 この「仕方なく1進める」を防ぐため、最右出現位置だけでなく全箇所での出現位置を覚えておく実装も考えられます。
実現方法としては、クエリでの各位置での、そこから左側だけを考慮した最右出現位置を保存するテーブルを作ればokです。
例えば、 abracadabra に対しては以下のような表になります。 (-1 は出現しない = it != char_pos_.end() と同様)
| クエリ文字位置(q) ＼ 文字(text_ch) | a | b | c | d | r |
|---|---|---|---|---|---|
| 0() | -1 | -1 | -1 | -1 | -1 |
| 1(a) | 0 | -1 | -1 | -1 | -1 |
| 2(ab) | 0 | 1 | -1 | -1 | -1 |
| 3(abr) | 0 | 1 | -1 | -1 | 2 |
| 4(abra) | 3 | 1 | -1 | -1 | 2 |
| 5(abrac) | 3 | 1 | 4 | -1 | 2 |
| 6(abraca) | 5 | 1 | 4 | -1 | 2 |
| 7(abracad) | 5 | 1 | 4 | 6 | 2 |
| 8(abracada) | 7 | 1 | 4 | 6 | 2 |
| 9(abracadab) | 7 | 8 | 4 | 6 | 2 |
| 10(abracadabr) | 7 | 8 | 4 | 6 | 9 |
| 11(abracadabra) | 10 | 8 | 4 | 6 | 9 |
クエリ文字比較位置(ソースコードでは 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などを紹介しようと思います。
