DawgEx

A compact, binary-encoded DAWG (directed acyclic word graph) for fast set-membership queries over large word lists.

DawgEx.from_list/2 builds a minimal automaton and flattens it into a single binary; DawgEx.member?/2 queries that binary directly, without decoding it back into terms — compact storage, cheap lookups.

Installation

Add dawg_ex to your dependencies in mix.exs:

def deps do
  [
    {:dawg_ex, "~> 0.1.0"}
  ]
end

Usage

dawg = DawgEx.from_list(["cat", "cats", "dog"])

DawgEx.member?(dawg, "cat")   #=> true
DawgEx.member?(dawg, "cats")  #=> true
DawgEx.member?(dawg, "ca")    #=> false

The binary is a plain term, so it can be built once at compile time and embedded in a module attribute:

defmodule Dictionary do
  @dawg "priv/words.txt" |> File.read!() |> String.split("\n", trim: true) |> DawgEx.from_list()

  def word?(word), do: DawgEx.member?(@dawg, word)
end

Choosing an offset width

from_list/2 takes the number of bits each edge spends addressing its child. Together with the two flag bits every edge carries, it must fill whole bytes — offset_width + 2 must be a multiple of 8 — and it trades encoded size against how many edges the automaton can hold:

DawgEx.from_list(words)      # 3 bytes per edge, up to 16_384 edges
DawgEx.from_list(words, 6)   # 2 bytes per edge, up to 64 edges
DawgEx.from_list(words, 22)  # 4 bytes per edge, up to 4_194_304 edges

The width is recorded in the binary, so member?/2 needs no matching argument and the default of 14 suits most word lists. Asking for a width too narrow to address the minimized automaton raises rather than encoding offsets that would wrap, and the message names the width to rebuild at:

** (ArgumentError) cannot address 2244 edges with an offset_width of 6

6 bits reach at most 64 edges. Rebuild with a wider offset:

DawgEx.from_list(words, 14)

Binary layout

The first byte records the offset width, followed by the root node's offset, stored two bits wider than the width so the header fills whole bytes:

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

The rest of the binary is edges. Each 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: a single placeholder edge (char 0xFF, both flags clear) sits right after the header, and every node with no outgoing edges points at it instead of occupying a slot of its own.

Requiring offset_width + 2 to be a multiple of 8 keeps both the header and every edge — 1 + (offset_width + 2) / 8 bytes each — a whole number of bytes. Offsets are edge indices rather than byte positions, which is why the width caps the edge count rather than the byte size.

Development

mix deps.get
mix check      # format, compile --warnings-as-errors, credo --strict, test, dialyzer

Individual steps are available as mix credo --strict, mix dialyzer, and mix test. The first Dialyzer run builds a PLT under priv/plts/ and takes a few minutes; later runs are incremental.

License

MIT — see LICENSE.

Next Page → Changelog