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

GADDAG (Gordon, 1994) data structure implemented in TypeScript:

• Highly performant
• No dependencies
• Backed by flat typed arrays — compact in memory, microseconds to deserialize
• Built for Scrabble Solver
• CJS & ESM compatible

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..) (the separator ◇ is omitted 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 full API Docs - generated by typedoc.

Good to know:

• a Gaddag is immutable — to change the dictionary, build a new one with Gaddag.fromArray
• Gaddag.deserialize checks the header, the alphabet, and two arc labels (the root's state boundary and the final arc's terminator), trusting the arcs otherwise — see Garbage in, garbage out
• immutability is not enforced: the backing typed arrays are exposed directly (and shared with the input of Gaddag.deserialize when it is 4-byte aligned) — treat them as read-only, writing to them corrupts the automaton
• all exports are named (there is no default export)
• MAX_LETTERS, MAX_WORD_LENGTH, and MAX_WORDS are described in Limits
• the build pipeline behind Gaddag.fromArray (scanWords, encodeWords, generateItems, sortItems, insertItems) is exported too, along with its types, for custom tooling

There are 2 ways to use the API.

Word API

Build a Gaddag from a word list (any order, duplicates allowed) with Gaddag.fromArray and use its methods.

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 arc-by-arc: start at rootRef, map UTF-16 code units to letter indices with getLetter (-1 when outside the alphabet), and follow arcs with getArc (0 when absent). State refs encode (firstArcIndex << 1) | isWordEnd — after following the last letter of a word, check ref & 1 to know whether the path spells a complete word. LAST_ARC_FLAG and LETTER_MASK describe the bit layout of arc labels for direct arcLabels/arcTargets traversal.

Example

This is how a Scrabble move generator consumes the automaton — e.g. verifying 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 — no board fits it anyway, and a split position takes 6 bits. | | Word count (MAX_WORDS) | 33,554,432 (2^25) | Gaddag.fromArray throws a RangeError when more words remain after skipping — a word index and a split position pack into one 31-bit integer. |

Distinct characters (MAX_LETTERS) and word length (MAX_WORD_LENGTH) are counted in UTF-16 code units, not code points: a character outside the Basic Multilingual Plane (an emoji, a rare CJK ideograph) is a surrogate pair, so it takes two alphabet slots and two of a word's 63 characters. Words are matched consistently either way, and hasPrefix accepts a lone leading surrogate as a prefix.

Code units are also matched without Unicode normalization: a precomposed é (one code unit) and its decomposed form e + combining accent (two code units) are different words. Normalize word lists and queries consistently — e.g. with String.prototype.normalize — when they may mix forms.

Empty words are skipped; a non-string entry throws a TypeError. Duplicated words and unsorted input are fine — the same minimal automaton is produced regardless of word order.

Garbage in, garbage out

Gaddag.deserialize rejects a wrong magic number, a wrong byte length, a malformed alphabet, a root ref outside the arcs or pointing mid-state, and an unterminated final arc — cheap checks that read at most two arc labels. It does not walk the arcs, so nothing verifies that the bytes describe a well-formed automaton. On bytes that did not come from Gaddag.serialize:

• has, hasPrefix, and getArc terminate, but may answer incorrectly
• a traversal you write on top — 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

Only deserialize data you serialized yourself. To load a word list from a source you do not control, build from text with Gaddag.fromArray instead.

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

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.deserialize trusts the file's content beyond cheap format checks — see Garbage in, garbage out.

Find all words with a given prefix

A GADDAG stores reverse(prefix) + ◇ + suffix paths, so all words starting with a prefix live behind a single 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 carry no such bound — see Garbage in, garbage out.

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

const 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;
};

const 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;
    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

Benchmarks are produced by bench/index.ts using tinybench, against these dictionaries. Run bun run bench to regenerate the table and charts below.

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