regexクレートを歩く(固定文字検索編)

前回の記事はこちら

固定文字列検索による最適化

固定文字列とはただの文字列のことです。例えば、「Cat」や「Dog」などは固定文字列です。正規表現であれば　例えば (Apple|Banana)* というような正規表現によって「Apple」や「AppleBanana」など複数の文字列を表すことができますが、固定文字列は単一の文字列のみを表します。一般に正規表現マッチングよりも固定文字列検索のほうが効率よく行うことができます。そこで、現代の正規表現エンジンではマッチングの高速化を図るために固定文字列検索手法が取り入れられているものもあります。具体的には入力として与えられた正規表現の先頭や末尾から固定文字列を括りだし、正規表現マッチングを行う開始位置を、括りだした固定文字列を検索することによって見つけ出します。

例えば http://([^/?#]*)?([?#]*)(\?([^#]*))?(#(.*))?というような正規表現を使ってマッチングを行う場合にはhttp://の部分を固定文字列として括りだし、固定文字列検索手法を用いてマッチング対象中からhttp://の位置を見つけ出し、その位置から正規表現マッチングを行ないます。

regexクレートにおける固定文字列検索

さて本題ですが、Rustの正規表現ライブラリであるregexでも固定文字列検索手法が取り入れられてます。今回はregexクレート内で使用されている固定文字列検索手法についてまとめていこうと思います。ただ、今回はそれぞれの手法がどのようなときに使われるかを中心に見ていくので、各手法の実装の詳細については立ち入りません。

固定文字列検索についてのコードはregexクレートのsrc/literals内に配置されてあります。使用される固定文字列マッチャは以下のようになっています。

#[derive(Clone, Debug)]
enum Matcher {
    /// No literals. (Never advances through the input.)
    Empty,
    /// A set of four or more single byte literals.
    Bytes(SingleByteSet),
    /// A single substring, find using memchr and frequency analysis.
    FreqyPacked(FreqyPacked),
    /// A single substring, find using Boyer-Moore.
    BoyerMoore(BoyerMooreSearch),
    /// An Aho-Corasick automaton.
    AC(FullAcAutomaton<Literal>),
    /// A simd accelerated multiple string matcher. Used only for a small
    /// number of small literals.
    TeddySSSE3(TeddySSSE3),
    /// A simd accelerated multiple string matcher. Used only for a small
    /// number of small literals. This uses 256-bit vectors.
    TeddyAVX2(TeddyAVX2),
}

Matcherの選択はMatcher::new内で行われます。また、以後はprefixの場合について記述していますが、suffixの場合も基本的に同様です。

Empty

Emptyは固定文字列検索を行わない場合に選択されます。

        if lits.literals().is_empty() {
            return Matcher::Empty;
        }
        if sset.dense.len() >= 26 {
            // Avoid trying to match a large number of single bytes.
            // This is *very* sensitive to a frequency analysis comparison
            // between the bytes in sset and the composition of the haystack.
            // No matter the size of sset, if its members all are rare in the
            // haystack, then it'd be worth using it. How to tune this... IDK.
            // ---AG
            return Matcher::Empty;
        }

ssetはprefixの先頭1文字(suffixの場合は末尾の1文字)として現れる文字の種類数です。regexクレートでは先頭1文字目に現れる文字が26種類以上の場合は固定文字列検索を行わないようです。固定文字列検索は基本的にマッチすることのない文字列をスキップすることで効率よく文字列を走査します。しかし、パターンに含まれる文字種が多いとスキップできる文字が少なくなるので効率が悪くなります。

ただ、文字種が多くても、それらの各文字が検索対象の文字列中において十分低い出現頻度であれば効率よくスキップを行えるようです。(ソースコード内のコメントにはそこらへんのうまい調整の仕方は分からないみたいなことが書いてあるんだと思います)。

Bytes

Bytesはprefixの各パターンの最大長が1の場合に用いられます。

        if sset.complete {
            return Matcher::Bytes(sset);
        }

Bytesのマッチングにはrust-memchrが使われています。rust-memchrはRustによって実装された高速なバイト文字検索ライブラリです。内部でSIMDを使用することで高速な検索を行います。

FreqyPacked

prefixのパターンが1つだけの場合にはBoyerMooreか、FreqyPackedが使用されます。 prefixが(Dog|Cat) というようなパターンで表されている場合はprefixになりうる文字列が「Dog」もしくは「Cat」というように複数になるのこれらのマッチャは使われません。prefixが複数の場合のマッチャについては後述します。

        if lits.literals().len() == 1 {
            let lit = lits.literals()[0].to_vec();
            if BoyerMooreSearch::should_use(lit.as_slice()) {
                return Matcher::BoyerMoore(BoyerMooreSearch::new(lit));
            } else {
                return Matcher::FreqyPacked(FreqyPacked::new(lit));
            }
        }

まずはFreqyPackedについて説明します。 FreqyPackedは文字の頻度解析を利用して高速なマッチングを行います。

    fn new(pat: Vec<u8>) -> FreqyPacked {
        if pat.is_empty() {
            return FreqyPacked::empty();
        }

        // Find the rarest two bytes. Try to make them distinct (but it's not
        // required).
        let mut rare1 = pat[0];
        let mut rare2 = pat[0];
        for b in pat[1..].iter().cloned() {
            if freq_rank(b) < freq_rank(rare1) {
                rare1 = b;
            }
        }
        for &b in &pat {
            if rare1 == rare2 {
                rare2 = b
            } else if b != rare1 && freq_rank(b) < freq_rank(rare2) {
                rare2 = b;
            }
        }

        // And find the offsets of their last occurrences.
        let rare1i = pat.iter().rposition(|&b| b == rare1).unwrap();
        let rare2i = pat.iter().rposition(|&b| b == rare2).unwrap();

        let char_len = char_len_lossy(&pat);
        FreqyPacked {
            pat: pat,
            char_len: char_len,
            rare1: rare1,
            rare1i: rare1i,
            rare2: rare2,
            rare2i: rare2i,
        }

上のコード上のrare1はrare2は与えられたprefixパターンに現れる文字の中で、事前の統計結果において最も出現頻度の低い文字2つを表します。この出現頻度の低い文字を先程同様SIMDを使用して見つけ出すことでマッチングの高速化を図っています。頻度が低ければスキップできる文字が多くなるので効率が上がるという寸法です。頻度解析はscripts/frequencies.pyで行われ、解析結果はsrc/freq.rs 内に埋め込まれています。以下のコーパスが頻度解析に使われたようです。

ザ・ワールド・ファクトブック
rustcのソースコード
七十人訳聖書

ザ・ワールド・ファクトブックはCIAが毎年出している世界中の情報をまとめた本らしいです。あと、聖書が使われているってなんかすごいですね…。

日本語に対してマッチングを行う場合は日本語のコーパスを使ったりしたほうが当然マッチング効率良くなりそうな気がしますが、その辺はどうなんですかね。

BoyerMoore

BoyerMooreは基本的にはFreqyPackedよりも遅いらしいです。それだけSIMDが強力ということなのだと思います。ただ、いくつかのケースではBoyerMooreの方が速くなることもあるようです。

検索対象文字列がランダムな場合

この場合、各文字の出現頻度は同じくらいになるので頻度解析による効率化は望めません。しかし、事前に検索対象文字列がランダムであることを知ることはできないとコメントに書いてあったので、このケースについては特に対処されていないようです。

prefixのパターンが高出現頻度の文字で構成されている場合

この場合も同様に頻度解析を使った効率化は望めません。また、このケースはprefixのパターンを調べることで事前に知ることができるので最適化を施すことが容易です。

prefixのパターンが長い場合

SIMDは一度に扱えるデータの量に制限があるのでprefixが長い場合にはBoyerMooreによるスキップの効率の方が良くなってSIMDを上回ることができそうです。

これらのケースを考慮してregexクレートではprefixのパターンが長ければ長いほどBoyerMooreが使われやすくなるようになっています。BoyerMoore法を使うかどうかを判定する部分の詳しい実装はここ。

Teddy

ここからはprefixのパターンが複数ある場合に用いられる手法です。 TeddyはHyperscanで用いられている複数文字列マッチングアルゴリズムでSIMDを使って高速なマッチングを行えるようです。アルゴリズムについての詳細はsrc/literal/teddy_sse3/imp.rsに詳しく記されています。今回調べていて、この辺りの話に興味が出てきたので、このアルゴリズムについてもいずれ、また別の記事としてまとめるかもしれないです。

Aho-Corasick

Teddyを使うにはSSE3、もしくはAVX2が必要です。それらが使えない場合やprefixの先頭1文字に現れうる文字が1種類の場合にはAho-Corasickが使われます。Aho-Corasickは伝統的な複数文字列マッチング手法として知られている手法で特殊なオートマトンを用いてマッチングを行うことでパターンの数とマッチング対象テキストの長さに対して線形時間でマッチングが行なえます。

まとめ

今回はregexクレートで用いられている固定文字列検索手法についてまとめました。自分の当初の予想では学校で習ったBoyer-Moore法のようなアルゴリズムがメインで使われているのかなと思っていましたが、実際はSIMDがメインで使われていて、ハードウェアレベルの最適化強いな〜という感じでした。この論文辺りにそこらへんのことが色々書いてそうなのでこれから読んでいきたいと思います。

しばイヌとお茶