NAME

DAWG - Directed Acyclic Word Graph implementation for Raku

SYNOPSIS

use DAWG;

# Create a new DAWG
my $dawg = DAWG.new;

# Add words with optional values
$dawg.add("apple", 1);
$dawg.add("application", 2);
$dawg.add("apply", 3);

# Build/minimize the DAWG
$dawg.minimize;

# Lookup operations
say $dawg.contains("apple");        # True
say $dawg.lookup("apple");          # { word => "apple", value => 1 }

# Prefix search
my @words = $dawg.find-prefixes("app");
# Returns: ["apple", "application", "apply"]

# Save and load
$dawg.save("my-dawg.dat");
my $loaded = DAWG.load("my-dawg.dat");

DESCRIPTION

DAWG (Directed Acyclic Word Graph) is a space-efficient data structure for storing a set of strings, such as a dictionary. It combines the features of a trie with the space efficiency of a minimal DFA (Deterministic Finite Automaton).

This implementation provides:

• Fast lookup (O(m) where m is the length of the string)

• Space-efficient storage

• Prefix search capability

• Optional value storage for each word

• Serialization support

AUTHOR

Danslav Slavenskoj

COPYRIGHT AND LICENSE

Copyright 2025 Danslav Slavenskoj

This library is licensed under the Artistic License 2.0.

METHODS

new()

Creates a new empty DAWG.

add(Str $word, $value?)

Adds a word to the DAWG with an optional associated value.

contains(Str $word)

Returns True if the word exists in the DAWG.

lookup(Str $word)

Returns a hash with the word and its associated value (if any), or Nil if not found.

find-prefixes(Str $prefix)

Returns an array of all words that start with the given prefix.

all-words()

Returns an array of all words in the DAWG.

minimize()

Minimizes the DAWG by merging equivalent nodes. This should be called after adding all words.

save(Str $filename)

Saves the DAWG to a file.

load(Str $filename)

Class method that loads a DAWG from a file.

stats()

Returns a hash with statistics about the DAWG.