Bitapアルゴリズム
(Shift-orアルゴリズム から転送)
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2024/01/08 17:36 UTC 版)
Bitapアルゴリズム（英: Bitap algorithm）とは、ビット演算の並列性を利用した文字列探索アルゴリズムである。Baeza–Yates–Gonnetアルゴリズムや、shift-andアルゴリズム・shift-orアルゴリズムとも呼ばれる（andとorがあるのは、ブール代数の双対性にもとづくバリエーションである）。レーベンシュタイン距離などの編集距離に基づく「似た」文字列を見つけ出すあいまい検索に利用できることが、他の文字列探索アルゴリズムにない特徴である。
- ^ 直訳すれば「ビット並列近似的パターンマッチング」。
- ^
~はビット単位のNOT。 - ^ 例えば pattern: "acbaca" なら6文字なので下位6ビット分。
- ^ この場合のレーベンシュタイン距離は、1文字挿入、1文字除去、1文字置換の全てを距離1として計測したものとなる。記載のアルゴリズムに幾許かの変更を施すことで、置換の距離を2にすることもできる。（#文字の挿入・置換・除去に対応した検索を参照）
- ^ WuとManberの原論文は、この記事の実装例と同じくshift-and型ではあるものの、ビット順が逆（1文字目が上位でマッチングを進める度に右シフトしていく）で説明されており、また右シフトは必ず最上位ビットを1で埋める ("We assume that the right shift fills the first position with a 1."[5]:3) とあらかじめ規定して説明している。ここでは左シフトでマッチングが進行し、1でのORも明記する形で説明する。
- ^ OR用マスクを連想配列でない配列で ormask[S] のように取得することを考えると、OR用マスクは巨大なものになりえる。例えば32文字のパターンでマッチングするとき、通常の配列で単純にOR用マスクを実装すると 4294967296 (配列の要素数: すなわち32ビット整数の取りえる全ての値の数) * 4 (OR用マスクのバイト長) = 16 GB ものメモリが必要になる。連想配列を使用すれば、Sが取りえない値についてメモリを確保しないですむため問題は緩和されるが、それでもXなどのマーカーが32個あるような複雑な正規表現の場合は同じ問題に直面する。OR用マスクが使用するメモリを削減する方法としては、Sの値を1バイト（8ビット）ごとに分割し、それぞれのバイトごとにOR用マスクの配列を用意することが考えられる[5]:11。この対策により、前記の32文字パターンの場合、通常配列でもOR用マスクが使用するメモリ量は 256 (配列の要素数: すなわち8ビット整数の取りえる全ての値の数) * 4 (OR用マスクのバイト長) * 4 (Sの分割数) = 4 KB ですむ。
Shift-orアルゴリズム
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/09/12 03:39 UTC 版)
「Bitapアルゴリズム」の記事における「Shift-orアルゴリズム」の解説
以上の説明はshift-and型のバリエーションを前提としている。ブール代数の双対性により、このアルゴリズムにはshift-or型のバリエーションがある。shift-orアルゴリズムでは、shift-andアルゴリズムにおけるビットを反転させた上でビット単位のORで探索を行う。すなわち、#実装例のRubyコードの state（#アルゴリズムの表のR）の初期状態 (R0) は全て1が立っているビット列になり、文字列比較をしていた部分である state = (state << 1 | 1) & mask[tc] は state = (state << 1) | ~mask[tc] になる。state が使用するビット範囲の最上位ビットが0になったときにパターンとマッチする部分が発見されたことになる。 まとめると、shift-orでは実装例のコードの黄色でハイライトした部分が以下のように変更される。 # 実際にtextと照合させる state = ~0 # 状態遷移を保持 ret = Array.new # マッチした位置をまとめるための配列 text.chars.each_with_index do |tc, i| state = (state << 1) | ~mask[tc] if (state & finish) == 0 # 最上位ビットが0である ret.push(i) # マッチした位置iを配列に追加 end end mask[tc] をあらかじめビット反転しておけば、 state = (state << 1) | mask[tc] としてやや効率化できる。Shift-andと比較すると、1とのビット単位のORを取る操作が減っているが、実際の性能への影響（例えばC言語実装が機械語にコンパイルされた時、実行速度がどの程度改善するか）は微妙だろう。
※この「Shift-orアルゴリズム」の解説は、「Bitapアルゴリズム」の解説の一部です。
「Shift-orアルゴリズム」を含む「Bitapアルゴリズム」の記事については、「Bitapアルゴリズム」の概要を参照ください。
「Shift-or アルゴリズム」の例文・使い方・用例・文例
- 毎日大量の株を売買していることから、アルゴリズム取引のユーザーの大半を大手機関投資家が占めている。
- マーティンが発明したアルゴリズムは、株価の変動によってオプション価格がどれくらい変化するかを予測することができる。
- 数字の平方根を探すために、アルゴリズム用の擬似コードを書きなさい。
- あなたの平均を探すアルゴリズムをAとする。
- このソフトウエアはギブスサンプリングのアルゴリズムによりマルコフ連鎖モンテカルロ法の計算を行います。
- アルゴリズムの、アルゴリズムに関する、または、アルゴリズムの特徴がある
- リストを分類するアルゴリズム
- 共通の語幹への語形を減少するために屈折語尾と派生語尾を取り除くためのアルゴリズム
- 微積分学の問題の解決に近似するためのアルゴリズムを研究する数学の部門
- 代数的表現式に類似した命令文を持つアルゴリズム言語
- アルゴリズムを表すために設計された人工言語
- プログラミング言語で、コンピュータプログラムをアルゴリズムとして記述するのに使う
- 意図した結果を得ることに対する間違ったアルゴリズム、または方法の選択から生じるエラー
- 大きな既存のデータベースでのパターンと相関関係を発見するために高度なデータ検索能力と統計アルゴリズムを用いるデータ処理
- コンピューターグラフィックスで,Zバッファアルゴリズムという図形処理の手順
- ワーノック型アルゴリズムという,人間の視覚情報処理の手続きをコンピューターグラフィックス向けに一般化した手順
- Shift-orアルゴリズムのページへのリンク
