rust-lang / regexは線形時間で正規表現のマッチが出来るらしい

この記事は Rust Advent Calendar 2022 1日目の記事です。

正規表現によるパターンマッチについて、ナイーブな深さ優先探索による正規表現のマッチを考えるとパターンの複雑さによって計算時間が大幅に変化しそうです。例えば文字列 aaaaaaaa がパターン (aa|a)+b にマッチしないことを確かめる方がパターン a+b にマッチしないことを確かめるよりも時間がかかりそうです。

しかし、Rustの正規表現モジュールregexはパターンによらず線形時間で探索が可能だと言っています。

all searches execute in linear time with respect to the size of the regular expression and search text

やってみた

ケース1

100万文字の"a"の後ろに"c"がついた文字列が、"a"をいくつか繰り返した後に"b"が続くパターンにマッチしないことを確認するプログラムで速度を検証してみます。愚直に考えれば"a"の塊の選択肢数が増えれば増えるほど分岐が大きなり全パターン試すために必要な時間が大きくなるはずです。

#![feature(test)]
extern crate test;
use regex::Regex;

fn setup() -> String {
    String::from("a".repeat(1_000_000) + "c")
}

#[cfg(test)]
mod tests {
    use super::*;
    use test::Bencher;

    #[bench]
    fn bench_simple_pattern(b: &mut Bencher) {
        let text = setup();
        let regex_simple = Regex::new(r"^a+b$").unwrap();
        b.iter(|| regex_simple.is_match(&text));
    }
    #[bench]
    fn bench_complex_pattern(b: &mut Bencher) {
        let text = setup();
        let regex_complex = Regex::new(r"^(aa|a)+b$").unwrap();
        b.iter(|| regex_complex.is_match(&text));
    }
    #[bench]
    fn bench_very_complex_pattern(b: &mut Bencher) {
        let text = setup();
        let regex_very_complex = Regex::new(r"^(aaaa|aa|aaa|a)+b$").unwrap();
        b.iter(|| regex_very_complex.is_match(&text));
    }
}

パターン	ns/iter
`^a+b$`	1,757,635
`^(aa\|a)+b$`	1,763,643
`^(aaaa\|aa\|aaa\|a)+b$`	1,756,747

パターンの複雑さに応じて実行時間が増えるという傾向はなさそうです。

ケース2

aaaaabbbbb を10万回繰り返し100万文字にしたものが、 a または b の繰り返しであることを確かめるプログラムで検証してみます。5文字ごとに文字が変わるため偶数文字消費後に奇数文字の経路を通る必要があり、選択肢が多いほうが時間がかかりそうに思います。

fn setup2() -> String {
    String::from("aaaaabbbbb".repeat(100_000))
}
#[cfg(test)]
mod tests {
    use super::*;
    use test::Bencher;

    #[bench]
    fn bench_simple_pattern2(b: &mut Bencher) {
        let text = setup2();
        let regex_simple = Regex::new(r"^(a|b)+$").unwrap();
        b.iter(|| regex_simple.is_match(&text));
    }
    #[bench]
    fn bench_complex_pattern2(b: &mut Bencher) {
        let text = setup2();
        let regex_complex = Regex::new(r"^(aa|bb|a|b)+$").unwrap();
        b.iter(|| regex_complex.is_match(&text));
    }
    #[bench]
    fn bench_very_complex_pattern2(b: &mut Bencher) {
        let text = setup2();
        let regex_very_complex = Regex::new(r"^(aaaa|aa|aaa|bbbb|bb|bbb)+$").unwrap();
        b.iter(|| regex_very_complex.is_match(&text));
    }
}

パターン	ns/iter
`^(a\|b)+$`	1,751,427
`^(aa\|bb\|a\|b)+$`	1,759,543
`^(aaaa\|aa\|aaa\|bbbb\|bb\|bbb)+$`	1,750,460

こちらもパターンによる実行時間の差は1%以下でパターンの数で所要時間が変わっているわけでは無さそうです。

実装を読んでみた

実験で実行時間がパターンの複雑性に依存しないように感じましたが、詳しいことは実装を読んで見る必要がありそうです。 ※この記事は書きかけです。どこを読むべきかが書かれていますが、肝心のアルゴリズムの読み解きが終わっていません。

github.com

まずは　

regex/HACKING.md at 79809ce6d02a250d3d03b326db99b09405053789 · rust-lang/regex · GitHub

を読みましょう。次の4種類のマッチングエンジンが実装されているようです。

The Pike VM (supports captures).

Bounded backtracking (supports captures).

Literal substring or multi-substring search.

Lazy DFA (no support for Unicode word boundary assertions).

ソースコードを読んでいきます。

パース

正規表現のパース処理がregex_syntaxモジュールに切り出されている事がわかります。中間生成物の形を確認しておきます。

use regex_syntax::ParserBuilder;


fn main() {
    let pat = String::from(r"((aa)+|aa|a)+b");
    let mut parser = ParserBuilder::new()
        .build();
    let expr = parser.parse(&pat).unwrap();
    println!("{:?}", expr);
}

Hir { kind: Concat([Hir { kind: Repetition(Repetition { kind: OneOrMore, greedy: true, hir: Hir { kind: Group(Group { kind: CaptureIndex(1), hir: Hir { kind: Alternation([Hir { kind: Repetition(Repetition { kind: OneOrMore, greedy: true, hir: Hir { kind: Group(Group { kind: CaptureIndex(2), hir: Hir { kind: Concat([Hir { kind: Literal(Unicode('a')), info: HirInfo { bools: 1537 } }, Hir { kind: Literal(Unicode('a')), info: HirInfo { bools: 1537 } }]), info: HirInfo { bools: 1537 } } }), info: HirInfo { bools: 1 } } }), info: HirInfo { bools: 1 } }, Hir { kind: Concat([Hir { kind: Literal(Unicode('a')), info: HirInfo { bools: 1537 } }, Hir { kind: Literal(Unicode('a')), info: HirInfo { bools: 1537 } }]), info: HirInfo { bools: 1537 } }, Hir { kind: Literal(Unicode('a')), info: HirInfo { bools: 1537 } }]), info: HirInfo { bools: 1 } } }), info: HirInfo { bools: 1 } } }), info: HirInfo { bools: 1 } }, Hir { kind: Literal(Unicode('b')), info: HirInfo { bools: 1537 } }]), info: HirInfo { bools: 1 } }

探索部分

re_unicode.rs -> re_builder.rs -> exec.rs/ExecBuilder -> exec.rs/ExecBuilder/build と辿っていくと choose_match_type というメソッドで使うマッチタイプを計算しておいて、is_match などが呼ばれた際にそれぞれのエンジンに処理を流している事がわかります。

バックトラック部分の本体であるhttps://github.com/rust-lang/regex/blob/9ca3099037dcb2faf1b49e6493f4c758532f2da1/src/backtrack.rsを見ると、探索位置のメモ化を使って枝刈りしているような雰囲気を感じます。

此処から先は更に理解をした後、この記事を更新します。