文字の挿入に対応した検索

ウィキペディア小見出し辞書

文字の挿入に対応した検索

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/09/12 03:39 UTC 版)

「Bitapアルゴリズム」の記事における「文字の挿入に対応した検索」の解説

この図は、文字の挿入のみに対応したshift-and型Bitapアルゴリズムにおいて、state を新しい値 state' に更新する時のデータフローである。 state[0] は完全一致マッチングなので、#アルゴリズムの表と変わりは無い。一方、state[1] では、まず state[0] と同じ処理を行い、その後 state[0] の更新前の値をORしている。これは、n - 1文字目まではパターンと完全一致し、n文字目でパターンに一致しない文字が現れた場合に、余計な1文字が挿入されたとみなしてn - 1文字までマッチングした状態に戻しておく（つまり状態更新を1回休みにする）処理と言える。n文字目に来るはずだった文字がn + 1文字目で現れれば、以降は完全一致と同様に状態がアップデートされていく。n文字目がパターンに一致した場合もn - 1文字目のビットが1になるが、これは例えば "acbaca" の "acb" まで一致した時に、実は "acbbaca"と続く場合など、同じ文字が余計に入っている可能性を表すものと解釈できる。 挿入2文字目が現れた場合、state[0]（更新前）のn - 1文字目のビットはすでに0になっているので state[1] のn - 1文字目のビットは1にならない。つまり、state[1] は1文字の挿入まで許容した検索となる。 state[2] は state[1] と同様の処理だが、ORするのは state[1] の更新前の値となる。挿入2文字目が現れた場合、state[1]（更新前）のn - 1文字目のビットはまだ1なので、state[2] のn - 1文字目のビットは1になる。つまり state[2] は2文字の挿入まで許容した検索となる。同様にして state[3], state[4], ... を実装することで、許容する挿入文字数を増やした検索が可能になる。#実装例のコードのハイライト部分をこのフローに従って修正すると以下のようになる。 # 実際にtextと照合させる distance = 2 # 許容する挿入文字数 state = Array.new(distance + 1) {0} # 状態遷移を保持 ret = Array.new # マッチした位置をまとめるための配列 text.chars.each_with_index do |tc, i| rstr_mask = 0 # ビットを1にする位置を示すマスク state.each_index do |j| next_rstr = state[j] # state[j + 1]のビットを1にする位置 state[j] = (state[j] << 1 | 1) & mask[tc] state[j] |= rstr_mask rstr_mask = next_rstr end if (state[distance] & finish) == finish # 最上位ビットが1である ret.push(i) # マッチした位置iを配列に追加 end end state[0] でも rstr_mask とのORを行っているが、この時の rstr_mask の値は0なので state[0] の値は変化しない。