文字の置換に対応した検索
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/09/12 03:39 UTC 版)
「Bitapアルゴリズム」の記事における「文字の置換に対応した検索」の解説
この図は、文字の置換のみに対応したshift-and型Bitapアルゴリズムにおいて、state を新しい値 state' に更新する時のデータフローである。 state[0] は完全一致マッチングなので、#アルゴリズムの表と変わりは無い。一方、state[1] では、まず state[0] と同じ処理を行い、その後 state[0] の更新前の値を1ビット左シフトして1をORした値をORしている。これは、n - 1文字目まではパターンと完全一致し、n文字目でパターンに一致しない文字が現れた場合に、1文字が置換されたとみなしてn文字目も一致と認める（つまり1回不一致を見逃す）処理と言える。 置換2文字目が現れた場合、state[0]（更新前）のn - 1文字目のビットはすでに0になっているので state[1] のn文字目のビットは1にならない。つまり、state[1] は1文字の置換まで許容した検索となる。 文字の挿入の時と同様に、state[2] では同様の処理を state[1] を参照して行い、これは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| state[j] = state[j] << 1 | 1 next_rstr = state[j] # state[j + 1]のビットを1にする位置 state[j] &= mask[tc] state[j] |= rstr_mask rstr_mask = next_rstr end if (state[distance] & finish) == finish # 最上位ビットが1である ret.push(i) # マッチした位置iを配列に追加 end end
※この「文字の置換に対応した検索」の解説は、「Bitapアルゴリズム」の解説の一部です。
「文字の置換に対応した検索」を含む「Bitapアルゴリズム」の記事については、「Bitapアルゴリズム」の概要を参照ください。
- 文字の置換に対応した検索のページへのリンク
