Skip to main content

Dictionary Engines

Our engine ships with multiple dictionary backends so you can trade lookup speed, memory footprint, and additional capabilities (prefix walks, move generation). All engines share the same Dictionary trait, so you can swap them without touching the rules layer.

Engine overview​

  • SetDictionary — simplest option. Backed by a HashSet. Great for tests or tiny lexica but has higher memory use and no prefix search.
  • FstDictionary — compressed finite-state transducer. Extremely fast lookups and small footprint. Supports prefix queries, and is the default in the WASM demo.
  • DawgDictionary — deterministic acyclic word graph. Slightly heavier build step than FST but keeps prefix traversal entirely in-memory and stays Rust-native (no fst dependency).
  • GaddagDictionary — specialised structure for anchor-based move generation. Provides both prefix and "reverse+suffix" walks so the generator can extend in both directions.

All engines now respect tokenization hooks and normalization modes from DictionaryOptions, so you can opt into NFKC, RTL alphabets, or custom grapheme segmentation.

Benchmarks​

Below is a small, precomputed snapshot (10k TWL06 words on an Intel Core i9-10850K). Interpret it as directional guidance; results vary by hardware and workload.

Offline benchmark snapshot (10k words, Intel Core i9-10850K). Lower lookup/build numbers are better.
Engine
Lookup (ms)
Build (ms)
Memory (KiB)
Set
0.84
2.8
420
FST
1.21
4.3
115
DAWG
3.40
10.9
152
GADDAG
1.21
153.1
260

Reproduce benchmarks​

Run the dictionary‑engine microbenchmarks (10k TWL06 words) locally to compare on your machine:

cargo bench -p tiletangle-engine --bench dict_engines

This runs two groups:

  • Build time: dict_build_{set,fst,dawg,gaddag}_10k
  • Lookup time: dict_lookup_{set,fst,dawg,gaddag}_4k (2k present + 2k absent queries)

Interpretation:

  • The chart on this page is a precomputed snapshot. Your timings will differ by hardware and toolchain.
  • Lookup time is the total for a batch of 4k queries (2k present + 2k absent). Build time constructs each structure from a 10k‑word slice. Memory figures are approximate and provided for rough comparison only.

Selecting an engine at runtime​

Rust
use tiletangle_engine::{DictionaryOptions, FstDictionary, GaddagDictionary, TokenizerRef};

let opts = DictionaryOptions {
    case_fold: true,
    tokenizer: TokenizerRef::default(),
    ..Default::default()
};
let lex = FstDictionary::from_words_opts(words.clone(), opts.clone());
let gaddag = GaddagDictionary::from_words_opts(words, opts);

On the web playground you can now switch engines from the Dictionary engine dropdown. When the "GADDAG" option is selected the move generator immediately benefits from the richer structure.

WASM helper​

WASM
import init, {new_game, set_dictionary_from_text_engine} from 'tiletangle_wasm';
await init();
const game = new_game(JSON.stringify(cfg), 2);
const text = await (await fetch('/dictionaries/TWL06.txt')).text();
set_dictionary_from_text_engine(game, text, 'gaddag', true);

Use 'set', 'fst', 'dawg', or 'gaddag' for the engine argument. The helper automatically applies NFC and optional case-folding before building the data structure.