LoginSignup
7

More than 3 years have passed since last update.

パターン部分一致の文字列検索 (KMP法)

Posted at

はじめに

ただの集団 AdventCalendar PtW.2019 9日目の記事です. Merry Golden week 🔔🌲
8日目は pino さんの 多分わかりやすいBi-LSTM-CRF入門 でした.

最近 retrieval という単語に出会うことがよくあります. retrieval は 探索、検索 という意味を持つ単語で、過去の記事で少し触れたトライ木(Trie)も、この retrieval を語源としているようです.

今回は、身近な例である文字列検索について、少し触れてみたいと思います.
結論から言うと、タイトルの通りの話を予定しているので、古いながらも(1977年)有名な部分マッチテーブルアルゴリズムの復習になります.

ゴール

次のようなクイズがあります. 探したい単語のパターンを意識して、全文照合方式で考えていくこと.

長さ N の文字列と、長さ k のパターンが与えられます.
文字列の中のパターンを、最悪の場合でも O(N * k)より短い探索時間で見つけてみましょう.
パターンが見つかったら、始まりのインデックスを返します. なかったら -1 を返します.

ほしい結果 (test)

def test_kmp_search(self):
    text = "ABABABABC"
    word = "ABABC"

    expected = 4  # text[4] から word が始まる
    actual = kmp_search(text, word)

    self.assertEqual(expected, actual)

def test_kmp_search_same_prefix_suffix(self):
    text = "ababbabcababababcabaabbb"
    word = "abababcaba"

    expected = 10
    actual = kmp_search(text, word)

    self.assertEqual(expected, actual)

シンキングタイム

  • Input : 長さ N の文字列と、長さ k のパターンです.
  • Output : バターンが始まるインデックスです(なかったら -1).

パターンというのがキーワードになりそうですね. ですが、現時点では浮かぶアイデアがありません.

仕方ないので、まずは紙とペンを用意して探索を始めます.
文字列は ABABABABC パターンは ABABC です.

ABABABABC
ABABC

ABABまで一致したもののCが違いますね ザンネン 😇

ABABABABC
 A

最初からあってませんね. 飛ばしましょうか.

ABABABABC
  ABABC

ABAB までは一致しているけど、Cが違いますね
(先ほどもこのザンネンなパターンがあった気が🤔)

この探索は、飽きました. ひと文字あたり、パターンの長さ k の比較が発生して、文字数は N です. O(N * k)な世界が目に浮かびます.

Input の文字列が ACTTCCAAGGGAAGATGAAGGGC... などの長い文字列になると、なおさら疲れそうです.

後戻りせずに、不要な探索はスキップしたい

一個一個比べて、一致しなかったらやり直し...いい加減パターンを覚えておきたいです.

「パターンのなかで、ここまで一致していれば、ここまでスキップできる」という情報があれば「次はここから探索を再開すればよい」ということができます.

一文字ずつ見ていく探索そのもののやりかたは既存の brute force と大きく変わりません.
ただ、一致しなかった場合、1文字あたり最大 k 回(パターンの長さ)存在していた「後戻り」をせずに、探索を再開することが可能なため、無駄(重複)な探索を減らせそうです.

重複して探索しうるサブパターン(パターンの内部でパターン化できるもの)を覚えて、再利用します. つまり、探索中に不一致が出た場合、パターンを先頭から見ずに、何文字(インデックス)スキップできるかを記録していこうと思います.

Knuth-Morris-Pratt アルゴリズム(KMP法)は、このような考えを背景としています.

やりたいこと

ホップ

ABABABABC # index 4 で一致しない
ABABC

ステップ

ABABABABC # index 4 から再開, index 6 で一致しない
  __ABC   # ひとつ前の探索で一致していた部分(AB の2文字)は見ない

ジャンプ

ABABABABC # index 6 から再開
    __ABC # ひとつ前の探索で一致していた部分(AB の2文字)は見ない

見つけた 👀

Partial match table (部分一致テーブル)

パターンの中のサブパターンスキップできる文字数を意識して、
スキップできる文字数を1次元配列として部分マッチテーブルを作成したいと思います.

さきほどの検索対象のパターンはABABCです. 例として以下に着目します.

  • ABABABが重複して構成されている点
  • ABAAが重複している点

先頭のAからスタートして、右に進めてパターンの部分を見ていきます.

パターンA

Aという一文字だけです.
そもそも一文字のみなので、スキップの意味はなさそうです(つまり0).

パターンが先頭の時点で不一致したら、パターンの先頭から探索を再開する必要があります.

パターンAB

Aで始まりBで終わるパターンです.
区切れそうなサブパターンが見つからないため、スキップするのはできないでしょう(つまり0).

パターンABA

Aで始まりAで終わるパターンです. サブパターンとしてAがあると言えます.
Aの長さの分だけ(つまり1)スキップして探索を再開しても良さそうです.

パターンABAB

ABで始まりABで終わるパターンです.
ABの長さの分だけ(つまり2)スキップして探索を再開しても良さそうです.

パターンABABC

Aで始まりCで終わるパターンです.
区切れそうなサブパターンが見つからないため、ここでスキップするのはできないでしょう(つまり0).

先頭文字からはじまる全パターンを見ることができました.

上から順番にスキップするインデックスを記録したとすると、[0, 0, 1, 2, 0]といった配列が求められます.

python code

def partial_match_table(word):
    table = [0] * (len(word) + 1)
    table[0] = -1
    i, j = 0, 1

    while j < len(word):
        matched = word[i] == word[j]

        if not matched and i > 0:
            i = table[i]
        else:
            if matched:
                i += 1
            j += 1
            table[j] = i

    return table

この実装では[-1, 0, 0, 1, 2, 0]が得られます.
jが 1 から操作を始めるため、便宜上、長さを +1 とってあります. table[0]に意味はないので-1を入れました.

上記の例のパターンだと、table[1]が、パターンA

そもそも一文字のみなので、スキップの意味はなさそうです(つまり0) ...

に該当します.

jを1から始める理由

どれくらいスキップできるか (パターン内の重複した文字の並び) を知るために、パターンとパターン自身を比較する方法があります.
パターンとパターン自身を比較するために、二つを重ねてみます.

[A]BABC
[X]BABC

実際の探索で、そもそもパターンが1文字目から一致しない場合、2文字以上のスキップができないので、

[A]BABC
_[B]ABC

[A]BABC
_B[A]BC

A[B]ABC
_BA[B]C

2文字目から比較を始めるためです. table[1]は初期値の0である理由ともつながりました.

サブパターン一致判断の流れ (一部)

pattern[0] == pattern[1]

AB
一致する prefix と suffix なし.

pattern[0] == pattern[2]

ABA
prefix A と suffix A が一致.

pattern[1] == pattern[3]

ABAB
prefix B と suffix B が一致.
pattern[0] の A と pattern[2] の A はすでに一致していることがわかっている.
そのため AB と AB が一致しているとも言える.

test

def test_partial_match_table(self):
    pattern = "ABABC"

    expected = [-1, 0, 0, 1, 2, 0]
    actual = partial_match_table(pattern)

    self.assertEqual(expected, actual)

def test_partial_match_table_same_prefix_suffix(self):
    pattern = "abababcaba"

    expected = [-1, 0, 0, 1, 2, 3, 4, 0, 1, 2, 3]
    actual = partial_match_table(pattern)

    self.assertEqual(expected, actual)

作成したテーブルを用いて探索

文章の中を探索して、不一致の場合、文章の中のカーソルを戻さず探索を続けます.
準備した部分マッチテーブルを活用します.

python code

def kmp_search(text, word):
    table = partial_match_table(word)
    i, p = 0, 0

    while i < len(text) and p < len(word):
        if text[i] == word[p]:
            i += 1
            p += 1
        elif p == 0:
            i += 1
        else:
            p = table[p]

    return (-1, i - p)[p == len(word)]

文章(text)をなぞるカーソルiは、左から右へ進む間に、パターン(word)をなぞるカーソルpが再開を始める位置を決めます.
ipがそれぞれ文章と単語の末尾インデックスに到達する間に、三つの分岐を行います.

  • 文字が一致する場合 (両カーソルを右に進める)
  • 文字が一致せず、スキップできない場合 (文章内カーソルを右に進める. パターンは先頭文字から照合を再開する)
  • 文字が一致せず、スキップできる場合 (照合を再開するパターン内文字の位置をテーブルから取得する)

どちらかのカーソルが末尾に到達したら、
パターンの最後まで探索ができた p == len(word) 場合のみ、その距離をリターンします.

文章の中の文字を一度見たら、またそこに戻ることはありません.
文章の長さを N とおくと、この関数はO(N)の探索時間で動いていると言えます.

おわりまして

文字列探索を線形時間で行えたアルゴリズムは KMP 法が初だそうです.
ただ、すべての工程 部分マッチテーブル作成 + 検索 を合わせると、厳密には O(k + N)です.
部分マッチテーブル作成 といった前処理の複雑性をも考慮すると、実用的な線形探索とは言い難いでしょう. 複雑な気分.

でもやはり、サブパターンを見つけてスキップ数を記録するやり方そのものが、面白いと思います.

以上

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
7