daachorse
1.0.0
Быстрая реализация алгоритма Ахо-Корасика с использованием компактной структуры данных с двумя массивами.
Основные технические идеи, лежащие в основе этой библиотеки, изложены в следующей статье:
Сюнсуке Канда, Коичи Акабе и Юсуке Ода. Разработка более быстрых двухматрицных автоматов Ахо-Корасика. Программное обеспечение: практика и опыт (SPE) , 53(6): 1332–1361, 2023 (arXiv)
Здесь также доступна оболочка Python.
Daachorse — это ящик для быстрого сопоставления нескольких шаблонов с использованием алгоритма Ахо-Корасика, работающего за линейное время по всей длине входного текста. В этом наборе используется компактная структура данных с двумя массивами для реализации автомата сопоставления с образцом для экономии времени и памяти. Структура данных не только поддерживает переход от одного состояния к другому за постоянное время, но также представляет каждое состояние в пространстве всего 12 байт.
Например, по сравнению с NFA ящика aho-corasick, который является самой популярной реализацией Aho-Corasick в Rust, Daachorse может выполнять сопоставление с образцом в 3,0–5,2 раза быстрее , потребляя при этом на 56–60% меньше памяти при использовании словаря слов размером 675 тыс. шаблонов. Другие экспериментальные результаты доступны на Wiki.
Для сборки этого ящика требуется Rust 1.61 или выше.
Daachorse содержит несколько вариантов поиска: от стандартного сопоставления с алгоритмом Ахо-Корасика до более сложного сопоставления. Они будут работать очень быстро благодаря структуре данных с двойным массивом и могут быть легко подключены к вашему приложению, как показано ниже.
Чтобы найти все вхождения зарегистрированных шаблонов, допускающих позиционное перекрытие во входном тексте, используйте 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() . Он выполняет поиск на автомате Ахо-Корасика и сообщает о шаблонах, впервые обнаруженных на каждой итерации.
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 ).
Этот репозиторий содержит интерфейс командной строки 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 .)
Не поддерживается. Эта библиотека использует автоматы Ахо-Корасика, построенные со структурой данных, называемой двойным массивом trie . Алгоритм этой структуры данных работает с операциями 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}
}
См. рекомендации.
