Aho Corasick 法

適当な単語群を含む辞書があったとします。「京都の高倉二条に美味しいつけ麺のお店がある」*1という文章が入力として与えられたとき、この文章中に含まれる辞書中のキーワードを抽出したい、ということがあります。例えば辞書に「京都」「高倉二条」「つけ麺」「店」という単語が含まれていた場合には、これらの単語(と出現位置)が入力に対しての出力になります。

この類の処理は、任意の開始位置から部分一致する辞書中のキーワードをすべて取り出す処理、ということで「共通接頭辞検索 (Common Prefix Search)」などと呼ばれるそうです。形態素解析、Wikipedia やはてなキーワードのキーワードリンク処理などが代表的な応用例です。

任意のテキストから辞書に含まれるキーワードをすべて抽出するという処理の実現方法は色々とあります。Aho Corasick 法はその方法のひとつです。Aho Corasick 法はAlfred V. Aho 氏, Margaret J. Corasick 氏の 1975 年の論文 "Efficient String Matching: An Aid to Bibliographic Search" で提案されたもので、辞書中からパターンマッチングを行うオートマトンを構築し入力テキストに対して線形な計算時間を実現します。辞書サイズに計算量が依存しない高速な手法です。

詳しい解説は情報検索アルゴリズムの第5章にあります。以下、その解説をもとに Aho Corasick 法の概要を説明します。

まずはじめに辞書から、辞書中に含まれる各文字がエッジになった木構造であるトライ木を構築します。各文字がエッジで、各ノードには辞書中のキーワードが(あれば)保持されます。トライ木については wikipedia:トライ木に解説がありますのでそちらを参照されると良いでしょう。

例えばキーワード集合 {'ab', 'bc', 'bab', 'd', 'abcde'} からトライ木を作ると以下の図のようになります。

このトライ木は、各ノードが状態、エッジを状態遷移であるオートマトンとみなすことができます。入力として任意のテキストを与えると、そのテキストを一文字ずつ先頭から見て一文字進む毎に対応した状態遷移を行うオートマトンです。例えばこのトライ木では 'bcc' という入力に対して 0 → 3 → 4 → (遷移先なし) と状態が遷移します。状態遷移は関数で書くことができて、例えば

0 → 3 の移動は g(0, 'b') = 3
3 → 4 は g(3, 'c') = 4
4 → 遷移なしは g(4, 'c') = False

となります。この g() を goto 関数と呼びます。

さて、途中経由した状態 4 には 'bc' が保持されています。このように、経由した状態にキーワードが保持されていたら、入力がそのキーワードを含んでいるとみなすことができます。

入力が 'bc' のときは良いのですが、'babcdex だとするとどうでしょう。0 → 3 → 5 → 6 → (遷移先なし) と遷移します。経由した状態 6 に 'bab' が見つかるので、bab が抽出されたことになります。確かにこれは正しいのですが、キーワード集合には 'ab', 'bc' や 'abcde' や 'd' も含まれているわけですから、babcdex からは bab 意外にそれらもキーワード抽出されて欲しいところです。

そこで次の遷移先がないと分かったところで状態 0 に戻り、入力の照合箇所を一文字に先に進める (babcdex → abcdex → bcdex → cdex ...) という安直な方法もありますが、例えば babcdex では bab が見つかった次は ab が見つかることは分かりきっているのですから、状態遷移失敗時に 0 に遷移するのではなく 2 に遷移できれば無駄な計算を省けて嬉しいわけです。この状態遷移に失敗した場合に戻るべき道筋を追加したオートマトンを用いるのが Aho Corasick 法です。

図の赤の矢印が、遷移失敗時の遷移先です。例えば状態 6 で遷移に失敗すると状態 2 に戻ります。これは failure(6) = 2 と関数で記述できます。これを failure 関数と呼びます。failure 関数が決まっていれば効率よく状態遷移を行うことができるのはわかりましたが、failure 関数をどのように構成すれば良いかが問題です。

"failure 関数による遷移は、照合中の文字列の接頭語が照合対象から外れることを意味する" ということに気付くことがポイントです。例えば入力 babc に対しては 0 → 3 → 5 → 6 と遷移したところで遷移が失敗するので failure(6) = 2 で 2 に遷移します。2 に遷移したということは、(failure関数がない場合に) 2 に到達までの道のり 0 → 1 → 2 を考えると ab を照合したことになります。次に見るべきは c なので 8 に遷移します。次の遷移が失敗するので failure(8) = 4 で 4 に遷移します。4 に遷移したということは (failure 関数がない場合に) 4 まで到達するための道のり 0 → 3 → 4 を考えると bc を照合したことになります。ここまでの流れを見ると確かに、babc → failure() → abc → failure() → bc と、failure 関数が一度呼ばれるたびに接頭語を一つ削った照合が行われていることが分かります。

このように働くように failure 関数を構成すればよいのです。すなわち、failure 関数は現在照合しているテキストの接尾辞のうち、辞書中に含まれる最長の接尾辞の状態に戻るように構成します。例えばこのトライ木では abab に対しては bab が、abc に対しては bc が辞書中に含まれる最長の接尾辞に相当します。

この辞書中の最長の接尾辞を探すという処理を効率的に行うには、どのように実現すればよいでしょうか? ここが Aho Corasick 法の肝で、木を幅優先探索しながら一つ先の状態の最長の接尾辞を探していく方法を取ります。まずトライ木を先にすべて構築して、トライ木が完成したら、トライ木を根から幅優先探索して最長の接尾辞を探していきます。(つまり辞書の更新に対してオートマトンをオフラインで構成する必要がある。参考文献では動的にオートマトンを更新する方法も解説されている。) failure 関数は照合中のテキストの接頭語を削る、つまり照合中のテキストの接尾辞を求めることにほかならないわけですから、幅優先探索でその時点での最長接尾辞を探していくと、数学的帰納法的に自然と failure 関数が決まっていきます。

以下にその様子のアニメーションのパワーポイントを作りました。

https://www.dropbox.com/s/amhzbagxg5jurqx/aho_corasick.ppt?dl=0

failure 関数でリンクを張った先のノードにキーワードがある場合はリンク元のノードにもそのキーワードを含めておく(和集合を取っておく) と良いのですが、そのあたりはコードを見てもらうのが良いでしょう。

failure 関数が決まればオートマトンはほぼ完成です。入力を与えれば自動的にキーワードが抽出できます。

Aho Corasick 法の Python による実装

Aho Corasick 法を Python で実装してみました。

#!/usr/bin/env python

class MachineAC:
    class State:
        def __init__ (self, id):
            self.id   = id
            self.next = {}

        def has_key(self, x):
            return self.next.has_key(x)

    def __init__ (self, terms):
        self.state  = [ MachineAC.State(0) ]
        self.output = [[]]
        self._make_goto(terms)
        self._make_failure()

    def _make_goto(self, terms):
        for term in terms:
            cur = self.state[0]
            for x in term:
                if not cur.has_key(x):
                    new = MachineAC.State( len(self.state) )
                    cur.next[x] = new
                    self.state.append(new)
                    self.output.append([])
                cur = cur.next[x]
            s = cur.id
            self.output[s].append(term)

    def _make_failure(self):
        failure = [0] * len(self.state)
        queue   = [ 0 ]
        while len(queue) > 0:
            s = queue.pop(0)
            for x in self.state[s].next.keys():
                next = self.g(s, x)
                if next is not None:
                    queue.append(next)
                if s != 0:
                    f = failure[s]
                    while self.g(f, x) is None:
                        f = failure[f]
                    failure[next] = self.g(f, x)
                    self.output[next].extend( self.output[failure[next]] )
        self.failure = failure

    def g(self, s, x):
        if x in self.state[s].next:
            return self.state[s].next[x].id
        else:
            if s == 0:
                return 0
            else:
                return

    def match (self, query):
        s = 0
        for i in xrange(len(query)):
            while self.g(s, query[i]) is None:
                s = self.failure[s]
            s = self.g(s, query[i])
            for x in self.output[s]:
                print '%d,%d => %s' % (i - len(x) + 1, i, x)

ac = MachineAC(['ab', 'bc', 'bab', 'd', 'abcde'])

print 'in: xbabcdex'
ac.match('xbabcdex')

print 'in: abc'
ac.match('abc')

_make_goto() が goto 関数を構成する、つまりトライ木を作る処理です。_make_failure() が failure 関数の構成です。failure 関数は入力 1 つに対して出力 1 が固定的に決まるので、ここでは配列によるテーブルで実装しました。キューを使ってトライ木を幅優先探索し、過去に求まった failure 関数を使いながらより深い状態の failure 関数の値を決めていっています。

match() が入力テキストに対してパターンマッチを行うメソッドです。入力を先頭から照合するのですが、goto 関数と failure 関数を使って状態を適切な位置に遷移させながら、出力を探していき見つかったキーワードをその位置 (開始オフセット, 終了オフセット) とともに出力しています。

実行結果は以下のようになります。

% python aho_corasick.py
in: xbabcdex
1,3 => bab
2,3 => ab
3,4 => bc
5,5 => d
2,6 => abcde
in: abc
0,1 => ab
1,2 => bc

ここでは論文や情報検索アルゴリズムでの解説に近い実装するため output や failure のような、状態番号を添字にするテーブルを用意しましたが、これらの情報を各ノード (MachineAC.State オブジェクト) に持たせてノード同士を結ぶ形で実現しても良いのではないかと思います。

2005年に話題になったはてなキーワードリンクの処理の高速化

はてなキーワードのキーワードリンクは昔は巨大な正規表現を使っていました。ユーザー登録辞書が大きくなってきた 2005年頃にこの処理が重たいというのが話題になって、きまぐれ日記や弾さんの日記で解決方法を提示していただいたことがありました。その中で Aho Corasick 法やダブル配列トライを使った Common Prefix Search、トライベースの正規表現など色々な手法が話題になりました。その当時は力不足であまり理解できず、歯がゆい思いをしたのでした。もう 3 年以上が経つのですね、早いものです。

Perl で Common Prefix Search

Perl で Aho Corasick 法を使ったパターンマッチを行うには Algorithm::AhoCorasick を利用することができます。また、関連するものとしてトライベースの正規表現を構築する Regexp::Trie、darts によるダブル配列トライ (ダブル配列についても後日解説してみたいと思っています)でのパターンマッチを実現する Text::Darts、簡潔データ構造によるトライ木を構築する Tx を用いて同様の処理を行う Text::Tx などもあります。それぞれ特徴があるのでケースによって使い分けてみるのも良いでしょう。

Algorithm::AhoCorasick (http://search.cpan.org/dist/Algorithm-AhoCorasick/)
Regexp::Trie (http://search.cpan.org/dist/Regexp-Trie/)
Text::Darts (http://search.cpan.org/dist/Text-Darts/)
Text::Tx (http://search.cpan.org/dist/Text-Tx/)

参考文献

Alfred V. Aho, Margaret J. Corasick "Efficient String Matching: An Aid to Bibliographic Search", Comm. ACM, 1975
北研二, 津田和彦, 獅子堀正幹『情報検索アルゴリズム』, 共立出版, 2002

追記

コメントでいただいた点を修正

diff --git a/aho_corasick.py b/aho_corasick.py
index c1ac3d5..5ee2e11 100644
--- a/aho_corasick.py
+++ b/aho_corasick.py
@@ -26,7 +26,7 @@ class MachineAC:
                     self.state.append(new)
                     self.output.append([])
                 cur = cur.next[x]
-            s = len(self.state) - 1
+            s = cur.id
             self.output[s].append(term)

     def _make_failure(self):

*1:本当にあります。麺や高倉二条