文字の除去に対応した検索

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

文字の除去に対応した検索

出典: フリー百科事典『ウィキペディア（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文字目まで完全一致で進行した場合、n文字目までをn + 1文字の最後の1文字が除去されたものとみなし、n + 1文字目まで一致と認める処理と言える。これにより、次に現れた文字がパターンのn + 2文字目と一致する文字だった場合も、アルゴリズムの表と同じ処理で一致と判定される。 除去2文字目が現れた場合、state[0]（更新後）のn文字目のビットはすでに0になっているので state[1] のn + 1文字目のビットは1にならない。つまり、state[1] は1文字の除去まで許容した検索となる。 文字の挿入・置換の時と同様に、state[2] では同様の処理を state[1] を参照して行い、これは2文字の除去まで許容した検索となる。以下、state[3], state[4], ... を実装することで、許容する除去文字数を増やした検索が可能になる。#実装例のコードのハイライト部分をこのフローに従って修正すると以下のようになる。 # 実際に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| state[j] = (state[j] << 1 | 1) & 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 state の初期値が完全一致・挿入・置換の場合とは異なっている。これは、検索対象文字列先頭にすでに除去された文字がある場合に対応したものである。state[n] なら先頭n文字以内の除去の可能性を考慮して、初期値は下位nビット分を1にしておく。これによって、例えばパターン "acbaca" に対して検索対象文字列 "cbacaccc" なら、state[1], state[2], ... では対象文字列先頭で "a" が除去されていると判定し、パターンとのマッチが検出される。