[!WARNING] This project — including this very warning — has been 100% LLM-generated. Use it at your own risk.

GADDAG (Gordon, 1994) data structure in TypeScript, built for Scrabble Solver.

• Highly performant
• No dependencies
• Stored in flat typed arrays: compact in memory, and deserialized without copying when the input is 4-byte aligned
• CJS and ESM

A GADDAG is a minimized automaton that, for every word w and every split point s (1 ≤ s ≤ |w|), accepts reverse(w[0..s)) + ◇ + w[s..), omitting the separator ◇ when s = |w|. This lets a move generator extend words in both directions from any anchor cell, which is what makes GADDAG-based Scrabble engines an order of magnitude faster than naive dictionary scans.

Table of contents

• Installation
• API
  • Word API
  • Arc API
• Limits
• Garbage in, garbage out
• Examples
  • Load a dictionary from a file
  • Serialize a GADDAG to a file
  • Load a serialized GADDAG from a file
  • Find all words with a given prefix
• Performance

Installation

# Bun
bun add @kamilmielnik/gaddag

# npm
npm install @kamilmielnik/gaddag

# Yarn
yarn add @kamilmielnik/gaddag

API

See the full API docs, generated by typedoc.

Notes:

• A Gaddag is immutable by convention, not enforcement. To change the dictionary, build a new one with Gaddag.fromArray.
• The backing typed arrays are exposed directly. Treat them as read-only: writing to them corrupts the automaton. Given a 4-byte-aligned input, Gaddag.deserialize returns a Gaddag that shares the input's buffer, so treat that buffer as read-only too.
• Gaddag.deserialize runs only cheap format checks. Call validate on bytes you did not serialize yourself. See Garbage in, garbage out.
• All exports are named. There is no default export.
• The build pipeline behind Gaddag.fromArray (scanWords, encodeWords, generateItems, sortItems, insertItems) is exported with its types, for custom tooling.

There are two ways to use the API.

Word API

Build a Gaddag from a word list with Gaddag.fromArray and call its methods. The list can be in any order and contain duplicates.

Example

import { Gaddag } from '@kamilmielnik/gaddag';

const gaddag = Gaddag.fromArray(['scrabble', 'solver']);
gaddag.has('solver');                   // true
gaddag.has('solve');                    // false
gaddag.hasPrefix('scra');               // true
gaddag.hasPrefix('solvers');            // false

const bytes = gaddag.serialize();       // Uint8Array in a compact binary format
const copy = Gaddag.deserialize(bytes); // zero-copy when the input is 4-byte aligned
copy.has('scrabble');                   // true

Arc API

Walk the automaton one arc at a time:

1. Start at rootRef.
2. Map a UTF-16 code unit to a letter index with getLetter. It returns -1 outside the alphabet.
3. Follow an arc with getArc. It returns 0 when there is no such arc.

A state ref is (firstArcIndex << 1) | isWordEnd. After the last letter of a word, ref & 1 tells whether the path spells a complete word.

To read arcLabels and arcTargets directly, use LAST_ARC_FLAG and LETTER_MASK, which describe the bit layout of an arc label.

Example

This is how a Scrabble move generator walks the automaton. Here it checks that "cat" can be formed around an anchor on the letter a:

import { Gaddag, SEPARATOR } from '@kamilmielnik/gaddag';

const gaddag = Gaddag.fromArray(['cat']);
const a = gaddag.getLetter('a'.charCodeAt(0));
const c = gaddag.getLetter('c'.charCodeAt(0));
const t = gaddag.getLetter('t'.charCodeAt(0));

// Read "ca" leftwards from the anchor (reversed), cross the separator, read "t" rightwards.
let ref = gaddag.rootRef;
ref = gaddag.getArc(ref, a);
ref = gaddag.getArc(ref, c);
ref = gaddag.getArc(ref, SEPARATOR);
ref = gaddag.getArc(ref, t);

const isWord = (ref & 1) === 1; // true

Limits

| Limit | Value | Behavior when exceeded | | --- | --- | --- | | Distinct characters (MAX_LETTERS) | 63 | Gaddag.fromArray throws a RangeError. A letter index takes 6 bits, and 0 is reserved for the ◇ separator. | | Word length (MAX_WORD_LENGTH) | 63 | The word is skipped. A split position takes 6 bits, and no board is that long anyway. | | Word count (MAX_WORDS) | 33,554,432 (2^25) | Gaddag.fromArray throws a RangeError if more words remain after skipping. A word index and a split position share one 31-bit integer. |

MAX_LETTERS and MAX_WORD_LENGTH count UTF-16 code units, not code points. A character outside the Basic Multilingual Plane, such as an emoji or a rare CJK ideograph, is a surrogate pair: it takes two alphabet slots and two of a word's 63 characters. Such words still match correctly, and hasPrefix accepts a lone leading surrogate as a prefix.

Characters are compared without Unicode normalization, so a precomposed é (one code unit) and e followed by a combining accent (two code units) are different words. If your word list and queries may mix the two forms, normalize both the same way, for example with String.prototype.normalize.

Empty words are skipped, and a non-string entry throws a TypeError. The same minimal automaton is built regardless of word order or duplicates.

Garbage in, garbage out

Gaddag.deserialize rejects:

• a wrong magic number or byte length
• a malformed alphabet
• a root ref outside the arcs or pointing into the middle of a state
• an unterminated final arc

These checks read at most two arc labels. Nothing walks the arcs, so nothing verifies that the bytes form a well-formed automaton. On bytes that did not come from Gaddag.serialize:

• has, hasPrefix, and getArc terminate, but may answer wrong.
• A traversal you write yourself, like Find all words with a given prefix, can loop forever on a cycle, or overflow the stack on a chain of states deeper than any real word.

validate closes that gap in one pass over the arcs (timings). It checks that:

• every letter is in the alphabet
• the arcs of each state ascend by letter
• every arc has a target
• the root has no separator arc
• every target points at the start of a state that lies before the state owning the arc, which rules out cycles and bounds the depth

It does not check that a path crosses the separator at most once. That is a property of the word list, not of the automaton, so a traversal of foreign bytes should skip any separator arc it meets after the first, as the example below does.

A validated automaton answers consistently, and every traversal of it terminates. Whether it holds the words you expect is still up to whoever wrote the bytes. Call validate once on data you did not serialize yourself, or build from text with Gaddag.fromArray instead.

Examples

Load a dictionary from a file

import { readFile } from 'node:fs/promises';
import { Gaddag } from '@kamilmielnik/gaddag';

const file = await readFile('dictionary.txt', 'utf-8');
const lines = file.split('\n').map((line) => line.trim());
const gaddag = Gaddag.fromArray(lines.filter((line) => /^\p{L}+$/u.test(line)));

gaddag.has('solver');     // is "solver" in the dictionary?
gaddag.hasPrefix('scra'); // does any word start with "scra"?
gaddag.arcsCount;         // number of arcs in the automaton

Serialize a GADDAG to a file

import { writeFile } from 'node:fs/promises';
import { Gaddag } from '@kamilmielnik/gaddag';

const gaddag = Gaddag.fromArray(['scrabble', 'solver']);
await writeFile('dictionary.gaddag', gaddag.serialize());

Load a serialized GADDAG from a file

import { readFile } from 'node:fs/promises';
import { Gaddag } from '@kamilmielnik/gaddag';

const buffer = await readFile('dictionary.gaddag');
const gaddag = Gaddag.deserialize(buffer);
gaddag.validate(); // throws unless the arcs form a well-formed automaton

Skip validate only if you serialized the file yourself. See Garbage in, garbage out.

Find all words with a given prefix

A GADDAG stores reverse(prefix) + ◇ + suffix paths, so every word starting with a prefix sits behind one separator arc. Follow the reversed prefix, cross ◇, and collect every suffix.

collectWords below recurses as deep as the words are long: at most MAX_WORD_LENGTH + 1 frames for a dictionary built from a word list. Foreign bytes have no such bound unless validate has accepted them. See Garbage in, garbage out.

import { Gaddag, LAST_ARC_FLAG, LETTER_MASK, SEPARATOR } from '@kamilmielnik/gaddag';

function findWordsWithPrefix(gaddag: Gaddag, prefix: string): string[] {
  if (prefix.length === 0 || !gaddag.hasPrefix(prefix)) {
    return [];
  }

  let ref = gaddag.rootRef;

  for (let index = prefix.length - 1; index >= 0; --index) {
    ref = gaddag.getArc(ref, gaddag.getLetter(prefix.charCodeAt(index)));
  }

  const words: string[] = [];

  if ((ref & 1) === 1) {
    words.push(prefix);
  }

  collectWords(gaddag, gaddag.getArc(ref, SEPARATOR), prefix, words);
  return words;
}

function collectWords(gaddag: Gaddag, ref: number, word: string, words: string[]): void {
  let index = ref >>> 1;

  if (index === 0) {
    return;
  }

  for (;;) {
    const label = gaddag.arcLabels[index];
    const letter = label & LETTER_MASK;

    // A word list never puts a second separator on a path; validated foreign bytes might.
    if (letter !== SEPARATOR) {
      const target = gaddag.arcTargets[index];
      const next = word + String.fromCharCode(gaddag.charCodes[letter - 1]);

      if ((target & 1) === 1) {
        words.push(next);
      }

      collectWords(gaddag, target, next, words);
    }

    if (label & LAST_ARC_FLAG) {
      return;
    }

    ++index;
  }
}

const gaddag = Gaddag.fromArray(['scrabble', 'scrap', 'solver']);
findWordsWithPrefix(gaddag, 'scra'); // ['scrabble', 'scrap']

Performance

bench/index.ts measures the operations below with tinybench on these dictionaries. Run bun run bench to regenerate the tables and charts.

Measured on 2026-09-03 with Bun 1.4.0 on 13th Gen Intel(R) Core(TM) i9-13900K (linux x64).

| Language | 🇺🇸 en-US | 🇬🇧 en-GB | 🇵🇱 pl-PL | | --- | --- | --- | --- | | Name | TWL06 | SOWPODS | SJP.PL | | Source | Download | Download | Download | | Words count | 178,691 | 267,752 | 3,229,856 | | Arcs count | 830,453 | 1,203,339 | 4,749,456 |

| ops / sec | 🇺🇸 en-US | 🇬🇧 en-GB | 🇵🇱 pl-PL | | --- | ---: | ---: | ---: | | has (hit) | 7.70M | 6.98M | 4.50M | | has (miss) | 8.76M | 7.93M | 5.41M | | hasPrefix (hit) | 19.13M | 17.81M | 16.93M | | hasPrefix (miss) | 21.89M | 18.94M | 19.02M | | getArc | 32.11M | 27.46M | 24.15M | | deserialize (aligned) | 5.45M | 5.52M | 4.74M |

| ops / sec | 🇺🇸 en-US | 🇬🇧 en-GB | 🇵🇱 pl-PL | | --- | ---: | ---: | ---: | | fromArray | 3.69 | 2.39 | 0.17 |

| ops / sec | 🇺🇸 en-US | 🇬🇧 en-GB | 🇵🇱 pl-PL | | --- | ---: | ---: | ---: | | serialize | 2.25k | 1.64k | 446.15 | | deserialize (unaligned) | 9.10k | 6.27k | 1.41k | | validate | 350.82 | 250.43 | 66.39 |