dawg_ex

# DawgEx

[![Hex.pm](https://img.shields.io/hexpm/v/dawg_ex.svg)](https://hex.pm/packages/dawg_ex)
[![Docs](https://img.shields.io/badge/hex-docs-blue.svg)](https://hexdocs.pm/dawg_ex)

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`:

```elixir
def deps do
  [
    {:dawg_ex, "~> 0.3.0"}
  ]
end
```

## Usage

```elixir
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:

```elixir
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:

```elixir
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
and two flag bits that give the header the same shape as an edge:

```
<<offset_width::8, root_offset::size(offset_width), empty?::1, 0::1>>
```

`empty?` sits where an edge's `terminal?` would and records whether the empty
word is a member — the root has no incoming edge to carry its terminality, so
it lives in the header. The final bit is always clear.

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. The sentinel is not the
root: a root without outgoing edges points at offset 0 like any other
childless node, and whether the empty word is a member stays in the header.

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](LICENSE).