DAWG (Directed Acyclic Word Graph)

References

1. Incremental Construction of Minimal Acyclic Finite-State Automata
2. Compressing Dictionaries with a DAWG
3. Lecture 25 | Programming Abstractions (Stanford) [Video]

License

NOTE:

1. THIS CRATE IS NOT PRODUCTION READY YET (Use at your own risk)
2. Contributions are welcome

lib.rs:

Implementation of Directed Acyclic Word Graph (DAWG) in Rust (pronounced "DAWG") as described by Steve Hanov Compressing Dictionaries with a DAWG (thank you!!)

Add the following to your Cargo.toml

[depedencies.dawg]
version = "x"
features = ["threading" ]

[threading] - Support Send + Sync

use dawg::Dawg;

let mut dawgie = Dawg::new();
let mut words = vec!["BAM", "BAT", "BATH", "CATH", "BATHE", "CAR", "CARS", "CAREERS, "SILENT", "LIST", "LISTEN", "AYÒ", "ÒYÀ"].iter().map(|w| w.to_string().to_uppercase()).collect::<Vec<_>>();

words.sort();

for word in words {
    dawgie.insert(word.to_string());
}

// to avoid unintended behaviours always remember to close (.finish) after building the dawg

dawgie.finish();


assert!(dawgie.lookup("BATH").is_some());
assert!(dawgie.is_some());