状態遷移機械を用いた文字列検索algorithm

bit-parallel approximate pattern matching

検索文字列長が計算機で表現可能なビット数に制限されるという欠点がある

まあ64文字(=64bit)あれば普通は十分だろう

複数のビット列に分割すれば任意長文字列に対応できないこともない

特徴

pros

部分一致文字列検索を安定して高速に実行できる

一回だけ検索対象文字列を走査すればいい

後戻りすることがない

マッチ判定を並列実行できるとこがミソ

複数のマッチ判定情報を一つのレジスタに重ね合わせて格納している

ビット演算で全てのマッチ判定を一度に行える

あいまい検索にも拡張できる

レジスタの個数分のLevenshtein距離の範囲で一致する文字列を検索できる

すこし計算式をいじることで、一部の文字を編集距離計算から除外する事も出来る

ワイルドカードを実現できる

cons

SESを計算できない

別途diff algorithmで探す必要がある

マッチした位置なら計算できる

部分完全一致検索はマッチしたときの遷移数から計算できる

曖昧検索だと後戻りが発生する

予め与えた最大値nまでしかLevenshtein距離を測れない

それ以上は「n+1以上離れている」ということしかわからなくなる

いろんな名前がある

使っている演算方法の違い

双対性から、AND演算とOR演算のどちらでも実装できる

展開ヘルプの論文ではシフタアルゴリズムと呼称されている

algorithmの流れ

shift-and型を使って解説する

遷移方向は右向きとする

最上位ビットから開始する

ビットが立っている場所は、検索パターンのうちその位置までの部分文字列と一致した箇所があることを示してしている

たとえば検索パターン abcde である文字列を検索している際に 01100 というレジスタに状態遷移したら、そこまでの状態遷移で ab と abc にマッチする箇所が検索対象文字列から見つかったということになる

曖昧検索の場合は、それぞれのレジスタが担当する距離以内で見つかった検索パターンの部分文字列を表す

たとえば検索パターン abcde で次のレジスタに遷移したとする

距離2: 01111

距離1: 01110

距離0: 00100

これは、完全一致で abc 、距離1以内で ab と abc と abcd 、距離2以内で abc と abcd と abcde が検索対象文字列から見つかったことを表している

状態遷移とビット演算との対応

このような流れでマッチ判定する

n+1番目が完全一致

1. n+1回目に遷移可能な位置にビットをたてる

n回遷移したレジスタを1回右シフトする

後方一致も含めるなら、最初のビットをたてておく

ORするだけ

2. 入力する文字が入りうる場所だけビットをたてる

入力する文字と対応するビットマスクをかぶせる

n+1番目に一文字追加

1. 入力された文字を飛ばす

n回遷移したレジスタをそのまま次のレジスタとして扱う

2. 距離を1つ増やす

担当する距離が一つ多いレジスタにORで合成する

n+1番目が一文字置換

1. 完全一致1.と同じ手順を踏む

n+1回目に遷移可能な位置全てに遷移したと考える

2. 距離を1つ増やす

n+2番目が一文字削除

1. n+1回遷移したレジスタから遷移可能な全ての位置にビットをたてる

n+2回目の遷移をする前に、すでにn+2回目に遷移可能な全ての位置に遷移したと見なす

2. 距離を1つ増やす

これでn+2回目以降で判定する文字番号を一つ早めることができる

初期状態は常に1が立つとわかっているので、レジスタに加える必要はない

asearchの実装だと加えてしまっているので、検索パターンに使える最大文字列長が1文字分少ない

/nishio/Bitapアルゴリズムで言及されている

実装

2021-10-09 19:12:11 ようやく仕組みを理解しはじめた

あとで解説を書く

References

部分完全一致検索、正規表現に拡張した検索algorithmまで解説されている

ちゃんと文章読んだら、これが一番詳しい解説だと気づいた

benchmarkあり

参考文献リストがある

#2024-07-21 07:27:30

#2022-02-11 09:56:57

#2022-01-31 05:54:24

#2021-11-03 22:36:09

#2021-10-18 15:25:54

#2021-10-16 18:27:07

#2021-10-09 19:12:02