文字の挿入置換除去に対応した検索

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

文字の挿入・置換・除去に対応した検索

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

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

この図は、文字の挿入・置換・除去の全てに対応した本来のshift-and型Bitapアルゴリズムにおいて、state を新しい値 state' に更新する時のデータフローである。 ここまでに説明した挿入・置換・除去それぞれに対応したアルゴリズムで使用したマスクを全てORでまとめた形になっている。state[1] はレーベンシュタイン距離1（挿入・置換・除去のいずれか1回のみ）の変更を許容しており、state[2], state[3], ... で許容するレーベンシュタイン距離を増やした検索が可能になる。#実装例のコードのハイライト部分をこのフローに従って修正すると以下のようになる。 # 実際にtextと照合させる distance = 2 # 許容するレーベンシュタイン距離 state = Array.new(distance + 1) {|i| (1 << i) - 1} # 状態遷移を保持 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 next_rstr |= state[j] # state[j + 1]のビットを1にする位置 (置換時用) state[j] &= mask[tc] state[j] |= rstr_mask next_rstr |= state[j] << 1 | 1 # state[j + 1]のビットを1にする位置 (除去時用) rstr_mask = next_rstr end if (state[distance] & finish) == finish # 最上位ビットが1である ret.push(i) # マッチした位置iを配列に追加 end end 1文字置換のレーベンシュタイン距離を2としたい場合は、 next_rstr |= state[j] # state[j + 1]のビットを1にする位置 (置換時用) の行を除去すれば良い。この行の処理がない場合、1文字の置換は1文字挿入の後に1文字除去したものとして扱われ、レーベンシュタイン距離2とすることができる。 注意点としては、ある位置でマッチが検出された場合、その位置の前後でより悪い（レーベンシュタイン距離が長い）マッチが検出されることがある。例えば、"abca" という文字列から "abc" というパターンをレーベンシュタイン距離1以内で探す場合、"ab"（末尾1文字除去）, "abc"（完全一致）, "abca"（末尾1文字挿入）の3カ所でマッチが検出されることになる。そのため、検出位置が重要な場合は対策が必要になる。また開始位置はわからないので検出位置からパターン文字列の長さ＋発見された距離数分戻った位置からやり直して確定することになるが、この場合にも慎重に組まないと直観とは異なる位置が開始位置として算出されることがある。