5 releases

0.0.7 Jan 2, 2025
0.0.6 Jan 2, 2025
0.0.5 Nov 26, 2023

#581 in Algorithms

Download history 11/week @ 2024-09-18 23/week @ 2024-09-25 1/week @ 2024-10-09 1/week @ 2024-10-30 1/week @ 2024-11-06 1/week @ 2024-12-04 1/week @ 2024-12-11 261/week @ 2025-01-01

263 downloads per month

MIT/Apache

40KB
744 lines

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

Licensed under either of Apache License, Version 2.0 or MIT license at your option.

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());

Dependencies

~0.6–1.2MB
~25K SLoC