python ahocorasickの紹介

python ahocorasickの紹介
ahocorasickモジュールの紹介
ahocorasickはpythonモジュールであり、Aho-Corasickアルゴリズムはマルチモードマッチングにおける古典的なアルゴリズムであり、現在は実際の応用に多い.
trieとAho-Corasickオートマチック、略称ACオートマチックの2つのデータ構造によって実現される.
マルチモードマッチング:
マルチモードマッチングとは、複数のパターン列P 1,P 2,P 3...,Pmがあり、これらのパターン列が連続テキストT 1...nに存在する可能性のあるすべての位置を求めることである.
たとえば、指定したテキスト「sdmfhsgnshejfgnihaofhsrnihao」に現れる可能性のあるすべての位置を、モードセット{「nihao」,「hao」,「hs」,「hsr」)で求める.
アルゴリズムの原理:
rootノードから、読み込んだ文字に基づいてオートマチックに沿って下に移動します.
読み込んだ文字がブランチに存在しない場合、失敗したパスを再帰します.失敗したパスをrootノードに移動した場合、その文字をスキップして次の文字を処理します.
ACオートマトンは入力テキストの最長接尾辞に沿って移動するので、すべての入力テキストを読み出した後、最後にルートノードに到達するまで失敗経路を再帰し、すべてのモードを検出することができる.
Trieは文字列インデックスの辞書で、関連項目を取得する際の時間と文字列の長さに比例します.
MACオートマトンは、1回の実行中に所与のセットのすべての文字列を見つけることができる.
MACオートマトンは,実際にはTrieツリー上でKMPを実現し,マルチモード列のマッチングを完了することができる.
例:

#coding:utf-8
import ahocorasick

def make_AC(AC, word_set):
    for word in word_set:
        AC.add_word(word,word)
    return AC

def test_ahocorasick():
    '''
    ahocosick：      
                   ，                    
    '''
    key_list = ["  ", "  ", " ", "  ", "  ", "   ", "  ", "   "]
    AC_KEY = ahocorasick.Automaton()
    AC_KEY = make_AC(AC_KEY, set(key_list))
    AC_KEY.make_automaton()
    test_str_list = ["         ：  、    ", "       ，        "]
    for content in test_str_list:
        name_list = set()
        for item in AC_KEY.iter(content):# AC_KEY      content     ，      
            name_list.add(item[1])
        name_list = list(name_list)
        if len(name_list) > 0:
            print content, "--->       ：", "\t".join(name_list)
if __name__ == "__main__":
    test_ahocorasick()

実行結果:

         ：  、     --->       ：  	  	  
       ，         --->       ：