DawgEx (DawgEx v0.1.0)
View SourceA 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)>>The header is followed by the edges themselves. Every node is a run of consecutive edges, and an edge is laid out as:
<<char::8, terminal?::1, child_offset::size(offset_width), more?::1, 0::6>>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. A
node with no outgoing edges is still allocated one slot, filled with a
placeholder edge whose char is 0xFF and whose flags are both clear.
Both the header and an edge are a whole number of bytes, since from_list/2
requires offset_width to be a multiple of 8:
offset_width | header | edge | maximum edges |
|---|---|---|---|
| 8 | 2 bytes | 3 bytes | 256 |
| 16 (default) | 3 bytes | 4 bytes | 65_536 |
| 24 | 4 bytes | 5 bytes | 16_777_216 |
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")
falseSummary
Functions
Builds a minimal DAWG from words and encodes it as a binary.
Returns true if word was in the list dawg was built from.
Types
@type t() :: <<_::8, _::_*8>>
A DAWG serialized to its binary representation.
Always an offset_width byte followed by a root offset and a whole number
of edges, all sized from that width, which is what makes the bit arithmetic
in member?/2 total.
Functions
@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, and
must be a positive multiple of 8. It trades size against capacity: an edge
costs 2 + div(offset_width, 8) bytes, and because offsets are edge indices
the automaton is capped at 2 ** offset_width edges. The default of 16 is
the balanced choice at 4 bytes per edge and room for 65_536 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"], 8)
iex> byte_size(dawg)
26
iex> DawgEx.member?(dawg, "cats")
trueRaises 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.
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.