daachorse下載 - daachorse原始碼下載

daachorse

其他源碼

1.0.0

下載

？ daachorse：雙陣列 Aho-Corasick

使用緊湊雙數組資料結構快速實現 Aho-Corasick 演算法。

該庫背後的主要技術思想出現在以下論文中：

神田俊介、赤部浩一、小田佑介。設計更快的雙陣列 Aho-Corasick 自動機。軟體：實務與經驗 (SPE) ，53(6)：1332–1361，2023 (arXiv)

此處也提供了 Python 包裝器。

概述

Daachorse 是一個使用 Aho-Corasick 演算法進行快速多重模式匹配的包，在輸入文字的長度上以線性時間運行。此板條箱使用緊湊的雙數組資料結構來實現模式匹配自動機，以提高時間和記憶體效率。此資料結構不僅支援恆定時間狀態到狀態的遍歷，而且僅以12位元組的空間來表示每個狀態。

例如，與 aho-corasick crate 的 NFA（Rust 中最受歡迎的 Aho-Corasick 實作）相比，當使用以下單字字典時，Daachorse 執行模式匹配的速度提高了 3.0-5.2 倍，同時消耗的記憶體減少了56 -60% 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 ( ) ) ;

尋找具有最長匹配的非重疊出現

如果要在每次迭代中搜尋沒有位置重疊的最長模式，請使用leftmost_find_iter()並在建構中指定MatchKind::LeftmostLongest 。

 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 crate 的全域分配器）。

命令列介面

此儲存庫包含一個名為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結構。）
不支援。該函式庫使用 Aho-Corasick 自動機，該自動機使用稱為雙數組 trie的資料結構建構。此資料結構上的演算法與輸入乾草堆上的異或運算一起工作。因此，乾草堆一定是一個整數序列。該函式庫專門針對整數序列中的str和[u8]進行了最佳化。
該庫是否提供與 Rust 以外的程式語言的綁定？
我們正在提供 Python 綁定。目前不計劃支援其他程式語言。如果您對編寫綁定感興趣，歡迎您這樣做。 daachorse是免費軟體。

鬆弛

我們有一個 Slack 工作區，供開發人員和使用者提出問題並討論各種主題。

https://daac-tools.slack.com/
請從這裡獲取邀請函。

執照

已獲得以下任一許可

Apache 許可證，版本 2.0（LICENSE-APACHE 或 http://www.apache.org/licenses/LICENSE-2.0）
MIT 授權（LICENSE-MIT 或 http://opensource.org/licenses/MIT）

由您選擇。

如果您在學術環境中使用該庫，請引用以下論文。

 @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}
}