DawgEx (DawgEx v0.3.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), empty?::1, 0::1>>The header has the shape of an edge: the width byte sits where a char would,
and two flag bits round it out to whole bytes. empty? fills the slot of an
edge's terminal? and records whether the empty word is a member — the root
node has no incoming edge to carry its terminality, so it lives here. The
final bit, where more? would sit, is always clear. 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. The sentinel is not the
root: a root without outgoing edges points at offset 0 like any other
childless node, while whether the empty word is a member stays in the
header's empty? flag.
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")
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 with the header's
flag bits, 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
@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. The empty word is a valid entry: it costs no edges and is
recorded in the header's empty? flag.
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")
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 a member exactly when "" was in the word list; it is
answered from the header's empty? flag without walking any edges.