Bitapアルゴリズム
(Bitap algorithm から転送)
出典: フリー百科事典『ウィキペディア（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 ですむ。
[続きの解説]
「Bitapアルゴリズム」の続きの解説一覧
このページでは「ウィキペディア」からBitapアルゴリズムを検索した結果を表示しています。
Weblioに収録されているすべての辞書からBitapアルゴリズムを検索する場合は、下記のリンクをクリックしてください。
全ての辞書からBitapアルゴリズム を検索
Weblioに収録されているすべての辞書からBitapアルゴリズムを検索する場合は、下記のリンクをクリックしてください。
全ての辞書からBitapアルゴリズム を検索 - Bitapアルゴリズムのページへのリンク
