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는 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 ( ) ) ; 검색 위치부터 시작하는 패턴 중 가장 먼저 등록된 패턴을 찾으려면 MatchKind::LeftmostFirst 지정하고 leftmost_find_iter() 사용하세요.
이것은 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 유니코드 코드 포인트 값을 사용하여 전환 횟수를 줄이고 일치 속도를 높입니다.
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}
}
지침을 참조하세요.
