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. A dictionary therefore costs one binary on the heap no matter how many processes read it.

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. It must be a positive multiple of 8, and it trades encoded size against how many edges the automaton can hold:

DawgEx.from_list(words)      # 4 bytes per edge, up to 65_536 edges
DawgEx.from_list(words, 8)   # 3 bytes per edge, up to 256 edges
DawgEx.from_list(words, 24)  # 5 bytes per edge, up to 16_777_216 edges

The width is recorded in the binary, so member?/2 needs no matching argument and the default of 16 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 8

8 bits reach at most 256 edges. Rebuild with a wider offset:

    DawgEx.from_list(words, 16)

Binary layout

The first byte records the offset width, followed by the root node's offset at that width:

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

The rest of the binary is edges. Each node is a run of consecutive edges:

<<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 still occupies one slot, filled with a placeholder edge whose char is 0xFF and whose flags are both clear.

Requiring the width to be a multiple of 8 keeps both the header (1 + offset_width / 8 bytes) and every edge (2 + offset_width / 8 bytes) 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.