ガリル規則
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/12/10 16:30 UTC 版)
「ボイヤー-ムーア文字列検索アルゴリズム」の記事における「ガリル規則」の解説
1979年、Zvi Galil はボイヤー-ムーア法に単純だが重要な改良を施した。追加されたガリル規則はシフト量を決めるものではなく、各位置での照合を高速化するものである。位置 k1 で P と T を照合して T 上の文字 c まで照合し、次にシフトした位置 k2 によりパターンの先頭の位置が c と k1 の間になったとき、P のプレフィックスは部分文字列 T[(k2 - n)..k1] と必ず一致する。したがってこの際の文字照合は T の k1 の位置まででよく、k1 より前の照合は省略できる。ガリル規則はボイヤー-ムーア法の効率を向上させるだけでなく、最悪ケースでも線型時間であることを保証するのに必須である。
※この「ガリル規則」の解説は、「ボイヤー-ムーア文字列検索アルゴリズム」の解説の一部です。
「ガリル規則」を含む「ボイヤー-ムーア文字列検索アルゴリズム」の記事については、「ボイヤー-ムーア文字列検索アルゴリズム」の概要を参照ください。
ウィキペディア小見出し辞書の「ガリル規則」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- ガリル規則のページへのリンク
