#word #graph #acyclic #direct #compact #online #string

seadawg

SeaDawg is a library that implements the online algorithm for Direct Acyclic Word Graph (DAWG) and Compact Direct Acyclic Word Graph (CDAWG)

3 releases

0.1.3 Jan 12, 2022
0.1.2 Dec 4, 2021
0.1.0 Jun 20, 2020

#1121 in Algorithms

MPL-2.0 license

315KB
6.5K SLoC

SeaDAWG Rust

Open high performance implementation of an Online DAWG and Online CDAWG for string indexing.

Support for Prefix, Contains, Suffix and Exact match queries.

WARNING: I encourage looking at Finite State Transducers for larger corpus of data.

Remark about Rust

Rust is stupidly weird about mutable and immutable. If I have a MUT lock on an object, then I must obviously have exclusive access to the object's internal data. WTF is this annoying error around not being able to take a non exclusive READ (immutable) lock where I already have an exclusive WRITE (mutable) lock. I resort to unsafe in order to grab mut inner data.

Dependencies

~2–4.5MB
~79K SLoC