著者
Ricardo A. Baeza-Yates, Gaston H. Gonnet
タイトル
A New Approach to Text Searching
書籍
SIGIR89
ページ
168-175
日時
June 1989
概要
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
概要
Waterloo大学のパターンマッチシステム。長さnのパターン のマッチングを計算するとき、マッチ状態をnビットで表現 し、ビットkがk文字マッチしていることを示すようにする。 例えば"11101"は2文字マッチしていることを示す。次の文 字がcであるとき、この状態変数を1ビット左にシフトし、 T[c]とのORを計算することにより新しい状態を計算する。 T[c]はあらかじめ計算しておく値で、パタン文字==cの位置 だけ0になっている。(例えば、パタン"abac"に対し T['a']="0101"となる。) k個のミスマッチを許すときはOR のかわりに加算を使ってミスマッチ個数を計算する。
感想
Shifter Algorithmと呼ぶらしい。条件によってはBMより実 行が速いといっているがどのようなものであろうか。状態 の表現方法が違うだけのような気がするが。Univ. of Waterlooのシステムを使ったと称するIRシステムが商用に なっているが、これのことなのだろうか? ミスマッチには いろいろなタイプがあるが、どのタイプに対しても計算可 能なのだろうか?
カテゴリ
String, IR
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