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