Category: Trie
Journal: SIGIR Forum
Comment: ある文字列が与えられたキーワードの集合に属するかど
        うかを効率よく判定するためのデータ構造。コンパイラ、
        スペルチェック等に応用できる。基本はAho-Corasick法
        \cite{Aho:stringmatch}であるが、分岐がおこらないこと
        がはっきりした時点でstrcmpを使うことでデータ構造を小
        さくおさえている。また、複数のステートから別のステー
        トへのマージは起こらないということにしてもデータ構造
        を小さくおさえている。
Abstract: A description is given of a method of implementing a
        static transition table of a string pattern matching
        machine to locate all occurrences of a finite number
        of keywords in a text string. The scheme combines the
        fast access of an array representation with the
        compactness of a list structure. Each transition can
        be computed from the present data structure in O(1)
        time and the storage is as small as the list
        structure. The construction and pattern matching
        programs associated with the data structure are
        provided and the efficiency is evaluated by empirical
        results
Number: 3,4
Bibtype: Article
Author: Jun'ichi Aoe
Pages: 22-33
Month: Spring/Summer
Title: An Efficient Implementation of String Pattern
        Matching Machines for a Finite Number of Keywords
Comment1: 状態遷移をプログラムするには普通多数のテーブルが必要
        となる。例えばflexでは文字列abcdeを認識するのに状態を
        5つ経由しなければならないため6要素のテーブルが2個必要
        となっている。これはstrcmpすることにすれば6バイトです
        む。このようにして一般的なテーブルコンパクションを行
        なうことは可能かもしれない。
        flexではステート数は最小になるがステート最小がテーブ
        ル最小に必ずしもならないということだろうか。
Year: 1989
Volume: 23
Keyword: string pattern matching, information retrieval, text
        scannning