from Generate and Filter

シフタアルゴリズムによる曖昧パタンマッチ

は「restaurant」というパタンを正確に認識するためのものであるが、これを拡張することによって曖昧検索を実行できる状態遷移機械を構築することができる。

たとえば曖昧検索によって「ristorante」という文字列が「restaurant」に近いということを認識することができる。

に状態を追加して のように拡張することにより、検索単語「restaurant」に対して0～3 個のミスマッチを許す曖昧検索を実行することができる。

最下行の右端の◎は入力が完全に「restaurant」にマッチしたときの遷移先であり、下から二番目の行の右端の◎は1 文字誤りを含んでマッチしたときの遷移先を示している。

「*」(あらゆる文字にマッチ)、「\epsilon」(空文字にマッチ) による縦と斜め方向の遷移を追加していることにより曖昧マッチングが可能になっている。

最初は左下のノードだけがアクティブになっているが、「r」以外の文字が入力されたときは「*」と書かれた遷移がアクティブとなり、接続されたノードがアクティブになる。

同時に「\epsilon」と書かれた遷移も自動的にアクティブになる。

これらの組み合わせにより、1文字余分/1 文字不足/文字置換に対する曖昧検索が可能になっている。

この状態遷移機械に「ristorante」という文字列を入力したときの様子を図15 に示す。

図 15 「restaurant」を認識するマッチャに「ristorante」を入力.

"r"の認識後の状態

"ri"の認識後の状態

"ris"の認識後の状態

"ristorante"の認識後の状態

「ristorante」による遷移が終了すると、右上のノードだけがアクティブになっているので、「ristorante」と「restaurant」は3 文字誤りでマッチすることがわかる。図 15 の状態遷移は複雑に見えるが、4 個の整数変数の間の論理演算を行なうだけで遷移を計算しているため高速でメモリ効率も良い。