11 releases
0.1.10 | Oct 5, 2023 |
---|---|
0.1.9 | Oct 5, 2023 |
0.1.8 | Jun 6, 2022 |
0.1.7 | Sep 2, 2021 |
0.1.1 | Jun 6, 2020 |
#93 in Data structures
189,875 downloads per month
Used in 100 crates
(2 directly)
175KB
857 lines
esaxx-rs
This code implements a fast suffix tree / suffix array.
This code is taken from and to be used by .
Small wrapper around sentencepiece's esaxx suffix array C++ library. Usage
let string = "abracadabra";
let suffix = esaxx_rs::suffix(string).unwrap();
let chars: Vec<_> = string.chars().collect();
let mut iter = suffix.iter();
assert_eq!(iter.next().unwrap(), (&chars[..4], 2)); // abra
assert_eq!(iter.next(), Some((&chars[..1], 5))); // a
assert_eq!(iter.next(), Some((&chars[1..4], 2))); // bra
assert_eq!(iter.next(), Some((&chars[2..4], 2))); // ra
assert_eq!(iter.next(), Some((&chars[..0], 11))); // ''
assert_eq!(iter.next(), None);
lib.rs
:
Small wrapper around sentencepiece's esaxx suffix array C++ library. Usage
#[cfg(feature="cpp")]
{
let string = "abracadabra";
let suffix = esaxx_rs::suffix(string).unwrap();
let chars: Vec<_> = string.chars().collect();
let mut iter = suffix.iter();
assert_eq!(iter.next().unwrap(), (&chars[..4], 2)); // abra
assert_eq!(iter.next(), Some((&chars[..1], 5))); // a
assert_eq!(iter.next(), Some((&chars[1..4], 2))); // bra
assert_eq!(iter.next(), Some((&chars[2..4], 2))); // ra
assert_eq!(iter.next(), Some((&chars[..0], 11))); // ''
assert_eq!(iter.next(), None);
}
The previous version uses unsafe optimized c++ code. There exists another implementation a bit slower (~2x slower) that uses safe rust. It's a bit slower because it uses usize (mostly 64bit) instead of i32 (32bit). But it does seems to fix a few OOB issues in the cpp version (which never seemed to cause real problems in tests but still.)
let string = "abracadabra";
let suffix = esaxx_rs::suffix_rs(string).unwrap();
let chars: Vec<_> = string.chars().collect();
let mut iter = suffix.iter();
assert_eq!(iter.next().unwrap(), (&chars[..4], 2)); // abra
assert_eq!(iter.next(), Some((&chars[..1], 5))); // a
assert_eq!(iter.next(), Some((&chars[1..4], 2))); // bra
assert_eq!(iter.next(), Some((&chars[2..4], 2))); // ra
assert_eq!(iter.next(), Some((&chars[..0], 11))); // ''
assert_eq!(iter.next(), None);