DawgEx (DawgEx v0.2.0)

A compact, binary-encoded DAWG (directed acyclic word graph).

from_list/2 builds a minimal automaton from a word list and flattens it into a single binary. member?/2 then queries that binary directly — the DAWG is never decoded back into terms, so a dictionary costs one binary on the heap regardless of how many processes read it.

Binary layout

The encoding is parameterized by offset_width, the number of bits an edge spends addressing its child. The first byte records that width, so a DAWG carries everything member?/2 needs to walk it:

<<offset_width::8, root_offset::size(offset_width + 2)>>

The root offset is stored two bits wider than it needs to be so the header, like every edge, fills whole bytes. The header is followed by the edges themselves. Every node is a run of consecutive edges, and an edge packs its two flag bits into the same bytes as its offset:

<<char::8, child_offset::size(offset_width), terminal?::1, more?::1>>

terminal? marks the end of a word, child_offset is the edge index of the child node, and more? is set on every edge except the last of its node. Offset 0 is a sentinel: the slot right after the header holds a single placeholder edge (char 0xFF, both flags clear), and every node with no outgoing edges is encoded as a child offset of 0 rather than spending a slot of its own. Real nodes start at offset 1.

Both the header and an edge are a whole number of bytes, since from_list/2 requires offset_width plus the two flag bits to be a multiple of 8:

`offset_width`	header	edge	maximum edges
6	2 bytes	2 bytes	64
14 (default)	3 bytes	3 bytes	16_384
22	4 bytes	4 bytes	4_194_304

Offsets are edge indices rather than byte positions, so offset_width is what caps the size of a DAWG — see from_list/2.

Example

iex> dawg = DawgEx.from_list(["cat", "cats", "dog"])
iex> DawgEx.member?(dawg, "cat")
true
iex> DawgEx.member?(dawg, "ca")
false

Summary

Types

t()

A DAWG serialized to its binary representation.

Functions

from_list(words, offset_width \\ 16 - 2)

Builds a minimal DAWG from words and encodes it as a binary.

member?(dawg, word)

Returns true if word was in the list dawg was built from.

Types

t()

@type t() :: <<_::8, _::_*8>>

A DAWG serialized to its binary representation.

Always an offset_width byte followed by a root offset, a sentinel edge, and a whole number of real edges, all sized from that width, which is what makes the bit arithmetic in member?/2 total.

Functions

from_list(words, offset_width \\ 16 - 2)

@spec from_list([binary()], pos_integer()) :: t()

Builds a minimal DAWG from words and encodes it as a binary.

The list is sorted internally, so the caller does not need to pre-sort it. Words are compared bytewise: a UTF-8 binary works, but multi-byte graphemes are traversed one byte at a time. An empty list builds a DAWG that no word is a member of.

offset_width sets how many bits each edge spends on its child offset. Each edge also carries two flag bits, and the two fields together must fill whole bytes, so the width must be positive with offset_width + 2 a multiple of 8: 6, 14, 22, and so on. It trades size against capacity: an edge costs 1 + div(offset_width + 2, 8) bytes, and because offsets are edge indices the automaton is capped at 2 ** offset_width edges. The default of 14 is the balanced choice at 3 bytes per edge and room for 16_384 of them.

Minimization runs before encoding and is unaffected by offset_width, so the same word list always yields the same number of edges at every width.

iex> dawg = DawgEx.from_list(["cat", "cats", "dog"], 6)
iex> byte_size(dawg)
18
iex> DawgEx.member?(dawg, "cats")
true

Raises ArgumentError if the minimized automaton needs more edges than offset_width can address, rather than encoding offsets that would wrap into a DAWG answering member?/2 incorrectly. The message reports the edge count and the width to rebuild at, so narrowing the default is safe to try on a word list whose minimized size is not known up front.

member?(dawg, word)

@spec member?(t(), binary()) :: boolean()

Returns true if word was in the list dawg was built from.

Runs against the encoded binary, reading the offset width from its header, so no offset_width needs to be threaded back in from the build. The walk is one linear scan per node and allocates nothing beyond the sub-binaries it matches out of word.

The empty binary is never a member, even though it is a prefix of every word.