Category: String IR
Abstract: Introduces a family of simple and fast algorithms for
        solving the classical string matching problem, string
        matching with don't care symbols and complement
        symbols, and multiple patterns. The same problems are
        solved allowing up to k mismatches. These algorithms
        are real time algorithms, they don't need to buffer
        the input, and they are suitable for implementation
        in hardware
Bibtype: InProceedings
Booktitle: SIGIR89
Author: Ricardo A. Baeza-Yates
        Gaston H. Gonnet
Pages: 168-175
Month: jun
Title: A New Approach to Text Searching
Comment1: Waterloo大学のパターンマッチシステム。長さnのパターン
        のマッチングを計算するとき、マッチ状態をnビットで表現
        し、ビットkがk文字マッチしていることを示すようにする。
        例えば"11101"は2文字マッチしていることを示す。次の文
        字がcであるとき、この状態変数を1ビット左にシフトし、
        T[c]とのORを計算することにより新しい状態を計算する。
        T[c]はあらかじめ計算しておく値で、パタン文字==cの位置
        だけ0になっている。(例えば、パタン"abac"に対し
        T['a']="0101"となる。) k個のミスマッチを許すときはOR
        のかわりに加算を使ってミスマッチ個数を計算する。
Year: 1989
Comment2: Shifter Algorithmと呼ぶらしい。条件によってはBMより実
        行が速いといっているがどのようなものであろうか。状態
        の表現方法が違うだけのような気がするが。Univ. of
        Waterlooのシステムを使ったと称するIRシステムが商用に
        なっているが、これのことなのだろうか？ ミスマッチには
        いろいろなタイプがあるが、どのタイプに対しても計算可
        能なのだろうか？
Keyword: algorithm theory; database theory; information
        retrieval; text searching; fast algorithms; string
        matching problem; don't care symbols; complement
        symbols; multiple patterns; mismatches; real time
        algorithms