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

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

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