daachorse
1.0.0
コンパクトな二重配列データ構造を使用した Aho-Corasick アルゴリズムの高速実装。
このライブラリの背後にある主な技術的アイデアは、次の論文に記載されています。
神田俊介、赤壁滉一、小田裕介。より高速な二重配列 Aho-Corasick オートマトンを設計します。ソフトウェア: 実践と経験 (SPE) 、53(6): 1332–1361、2023 (arXiv)
Python ラッパーもここから入手できます。
Daachorse は、Aho-Corasick アルゴリズムを使用した高速複数パターン マッチングのためのクレートで、入力テキストの長さにわたって線形時間で実行されます。このクレートは、時間とメモリの効率を高めるためにパターン マッチ オートマトンを実装するためにコンパクトな二重配列データ構造を使用します。このデータ構造は、定数時間の状態間のトラバーサルをサポートするだけでなく、わずか 12 バイトのスペースで各状態を表します。
たとえば、Rust で最も人気のある Aho-Corasick 実装である aho-corasick クレートの NFA と比較して、Daachorse は、単語辞書を使用する場合、消費メモリを56 ～ 60% 削減しながらパターン マッチングを3.0 ～ 5.2 倍高速に実行できます。 675K パターン。他の実験結果は Wiki で入手できます。
このクレートを構築するには、Rust 1.61 以降が必要です。
Daachorse には、Aho-Corasick アルゴリズムを使用した標準的なマッチングから、より複雑なマッチングまで、いくつかの検索オプションが含まれています。以下に示すように、これらは二重配列データ構造に基づいて非常に高速に実行され、アプリケーションに簡単にプラグインできます。
入力テキスト内で位置の重複を許可する登録済みパターンのすべての出現を検索するには、 find_overlapping_iter()を使用します。構築にnew()使用すると、ライブラリは入力順序の各パターンに一意の識別子を割り当てます。一致結果には、出現のバイト位置とその識別子が含まれます。
use daachorse :: DoubleArrayAhoCorasick ;
let patterns = vec ! [ "bcd" , "ab" , "a" ] ;
let pma = DoubleArrayAhoCorasick :: new ( patterns ) . unwrap ( ) ;
let mut it = pma . find_overlapping_iter ( "abcd" ) ;
let m = it . next ( ) . unwrap ( ) ;
assert_eq ! ( ( 0 , 1 , 2 ) , ( m.start ( ) , m.end ( ) , m.value ( ) ) ) ;
let m = it . next ( ) . unwrap ( ) ;
assert_eq ! ( ( 0 , 2 , 1 ) , ( m.start ( ) , m.end ( ) , m.value ( ) ) ) ;
let m = it . next ( ) . unwrap ( ) ;
assert_eq ! ( ( 1 , 4 , 0 ) , ( m.start ( ) , m.end ( ) , m.value ( ) ) ) ;
assert_eq ! ( None , it.next ( ) ) ;位置の重複を許可したくない場合は、代わりにfind_iter()使用してください。 Aho-Corasick オートマトンで検索を実行し、各反復で最初に見つかったパターンを報告します。
use daachorse :: DoubleArrayAhoCorasick ;
let patterns = vec ! [ "bcd" , "ab" , "a" ] ;
let pma = DoubleArrayAhoCorasick :: new ( patterns ) . unwrap ( ) ;
let mut it = pma . find_iter ( "abcd" ) ;
let m = it . next ( ) . unwrap ( ) ;
assert_eq ! ( ( 0 , 1 , 2 ) , ( m.start ( ) , m.end ( ) , m.value ( ) ) ) ;
let m = it . next ( ) . unwrap ( ) ;
assert_eq ! ( ( 1 , 4 , 0 ) , ( m.start ( ) , m.end ( ) , m.value ( ) ) ) ;
assert_eq ! ( None , it.next ( ) ) ;各反復で位置の重複のない最長パターンを検索したい場合は、構築でMatchKind::LeftmostLongestを指定してleftmost_find_iter()を使用します。
use daachorse :: { DoubleArrayAhoCorasickBuilder , MatchKind } ;
let patterns = vec ! [ "ab" , "a" , "abcd" ] ;
let pma = DoubleArrayAhoCorasickBuilder :: new ( )
. match_kind ( MatchKind :: LeftmostLongest )
. build ( & patterns )
. unwrap ( ) ;
let mut it = pma . leftmost_find_iter ( "abcd" ) ;
let m = it . next ( ) . unwrap ( ) ;
assert_eq ! ( ( 0 , 4 , 2 ) , ( m.start ( ) , m.end ( ) , m.value ( ) ) ) ;
assert_eq ! ( None , it.next ( ) ) ;検索位置から開始して最も古い登録パターンを検索したい場合は、 leftmost_find_iter()にMatchKind::LeftmostFirst指定して使用します。
これはいわゆる左端の最初の一致であり、aho-corasick クレートでサポートされているトリッキーな検索オプションです。たとえば、次のコードでは、最も早く登録されているabが報告されます。
use daachorse :: { DoubleArrayAhoCorasickBuilder , MatchKind } ;
let patterns = vec ! [ "ab" , "a" , "abcd" ] ;
let pma = DoubleArrayAhoCorasickBuilder :: new ( )
. match_kind ( MatchKind :: LeftmostFirst )
. build ( & patterns )
. unwrap ( ) ;
let mut it = pma . leftmost_find_iter ( "abcd" ) ;
let m = it . next ( ) . unwrap ( ) ;
assert_eq ! ( ( 0 , 2 , 0 ) , ( m.start ( ) , m.end ( ) , m.value ( ) ) ) ;
assert_eq ! ( None , it.next ( ) ) ;パターンとユーザー定義値のペアからオートマトンを構築するには、識別子を自動的に割り当てる代わりに、 with_values()使用します。
use daachorse :: DoubleArrayAhoCorasick ;
let patvals = vec ! [ ( "bcd" , 0 ) , ( "ab" , 10 ) , ( "a" , 20 ) ] ;
let pma = DoubleArrayAhoCorasick :: with_values ( patvals ) . unwrap ( ) ;
let mut it = pma . find_overlapping_iter ( "abcd" ) ;
let m = it . next ( ) . unwrap ( ) ;
assert_eq ! ( ( 0 , 1 , 20 ) , ( m.start ( ) , m.end ( ) , m.value ( ) ) ) ;
let m = it . next ( ) . unwrap ( ) ;
assert_eq ! ( ( 0 , 2 , 10 ) , ( m.start ( ) , m.end ( ) , m.value ( ) ) ) ;
let m = it . next ( ) . unwrap ( ) ;
assert_eq ! ( ( 1 , 4 , 0 ) , ( m.start ( ) , m.end ( ) , m.value ( ) ) ) ;
assert_eq ! ( None , it.next ( ) ) ;マルチバイト文字でより高速なオートマトンを構築するには、代わりにCharwiseDoubleArrayAhoCorasickを使用してください。
標準バージョンのDoubleArrayAhoCorasick文字列を UTF-8 シーケンスとして処理し、バイト値を使用して遷移ラベルを定義します。一方、 CharwiseDoubleArrayAhoCorasick Unicode コード ポイント値を使用するため、遷移の数が減り、マッチングが高速になります。
use daachorse :: CharwiseDoubleArrayAhoCorasick ;
let patterns = vec ! [ "全世界" , "世界" , "に" ] ;
let pma = CharwiseDoubleArrayAhoCorasick :: new ( patterns ) . unwrap ( ) ;
let mut it = pma . find_iter ( "全世界中に" ) ;
let m = it . next ( ) . unwrap ( ) ;
assert_eq ! ( ( 0 , 9 , 0 ) , ( m.start ( ) , m.end ( ) , m.value ( ) ) ) ;
let m = it . next ( ) . unwrap ( ) ;
assert_eq ! ( ( 12 , 15 , 2 ) , ( m.start ( ) , m.end ( ) , m.value ( ) ) ) ;
assert_eq ! ( None , it.next ( ) ) ; no_std Daachorse はstdに依存しません (ただし、 allocクレートを使用したグローバル アロケーターが必要です)。
このリポジトリには、テキスト ファイル内のパターンを検索するためのdaacfindという名前のコマンドライン インターフェイスが含まれています。
% cat ./pat.txt
fn
const fn
pub fn
unsafe fn
% find . -name "*.rs" | xargs cargo run --release -p daacfind -- --color=auto -nf ./pat.txt
...
...
./src/errors.rs:67: fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
./src/errors.rs:81: fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
./src/lib.rs:115: fn default() -> Self {
./src/lib.rs:126: pub fn base(&self) -> Option<u32> {
./src/lib.rs:131: pub const fn check(&self) -> u8 {
./src/lib.rs:136: pub const fn fail(&self) -> u32 {
...
...
このライブラリはstrと[u8]以外のデータ型をサポートしていますか? (例: Eqを実装する構造体)
サポートされていません。このライブラリは、 double-array trieと呼ばれるデータ構造で構築された Aho-Corasick オートマトンを使用します。このデータ構造のアルゴリズムは、入力干し草の山に対する XOR 演算で機能します。したがって、干し草の山は一連の整数でなければなりません。このライブラリは、整数シーケンスのうちstrと[u8]に対して特に最適化されています。
このライブラリは Rust 以外のプログラミング言語へのバインディングを提供しますか?
Python バインディングを提供しています。他のプログラミング言語は現時点ではサポートされる予定はありません。バインディングの作成に興味がある場合は、ぜひそうしてください。 daachorseはフリーソフトウェアです。
開発者とユーザーが質問したり、さまざまなトピックについて話し合ったりできる Slack ワークスペースがあります。
次のいずれかに基づいてライセンスが付与されている
あなたのオプションで。
このライブラリを学術環境で使用する場合は、次の論文を引用してください。
@article{10.1002/spe.3190,
author = {Kanda, Shunsuke and Akabe, Koichi and Oda, Yusuke},
title = {Engineering faster double-array {Aho--Corasick} automata},
journal = {Software: Practice and Experience},
volume={53},
number={6},
pages={1332--1361},
year={2023},
keywords = {Aho–Corasick automata, code optimization, double-array, multiple pattern matching},
doi = {https://doi.org/10.1002/spe.3190},
url = {https://onlinelibrary.wiley.com/doi/abs/10.1002/spe.3190},
eprint = {https://onlinelibrary.wiley.com/doi/pdf/10.1002/spe.3190}
}
ガイドラインを参照してください。
