README

A small PHP library for creating and querying word data structures from word lists.

Trie stores strings by shared prefixes, which makes exact lookups and prefix-based lookups straightforward.
Gaddag stores reversed-prefix word forms for Scrabble-style move generation and anchor-letter searches.

Installation

composer require r34117y/trie

Usage

<?php

use Agrzelec\Trie\Trie;
use Agrzelec\Trie\Gaddag;

$trie = Trie::fromWords(['tea', 'ted', 'ten', 'to']);

$trie->contains('tea'); // true
$trie->contains('te'); // false
$trie->startsWith('te'); // true

$trie->wordsStartingWith('te'); // ['tea', 'ted', 'ten']

$trie->insert('team');
$trie->contains('team'); // true

$gaddag = Gaddag::fromWords(['explain', 'play']);

$gaddag->encodedFormsFor('explain');
// ['e+xplain', 'xe+plain', 'pxe+lain', 'lpxe+ain', 'alpxe+in', 'ialpxe+n', 'nialpxe']

$gaddag->containsEncodedForm('pxe+lain'); // true
$gaddag->wordsReachableFrom('p'); // ['explain', 'play']

The library treats input words as case-sensitive UTF-8 strings, so locale-specific characters such as ą, ę, ó, and ź are stored and matched as complete characters. Duplicate words are stored once. Trie supports empty strings as valid words; Gaddag requires non-empty words.

API

Trie

Trie::fromWords(iterable $words): Trie creates a trie from a word list.
insert(string $word): void inserts a word.
contains(string $word): bool checks whether a complete word exists.
startsWith(string $prefix): bool checks whether a prefix path exists.
wordsStartingWith(string $prefix): list<string> returns all stored words beginning with a prefix.
wordsWithPrefix(string $prefix): list<string> aliases wordsStartingWith().
words(): list<string> returns all stored words in deterministic traversal order.
count(): int returns the number of unique stored words.
isEmpty(): bool checks whether the trie contains no words.
toArray(): array{isWord: bool, children: array<string, mixed>} exports the trie as nested arrays.

GADDAG

A GADDAG stores one encoded form for each non-empty prefix of a word. For a word split into prefix x and suffix y, the encoded form is reverse(x) + separator + y; the full-word reversal omits the separator. The default separator is +.

Gaddag::fromWords(iterable $words, string $separator = '+'): Gaddag creates a GADDAG from a word list.
insert(string $word): void inserts a non-empty word.
contains(string $word): bool checks whether an original word exists.
containsEncodedForm(string $encodedForm): bool checks whether a GADDAG encoded path exists.
encodedFormsFor(string $word): list<string> returns the encoded forms for a word.
encodedForms(): list<string> returns all stored encoded forms.
wordsReachableFrom(string $encodedPrefix): list<string> returns original words represented below an encoded prefix.
separator(): string returns the configured separator.
count(): int returns the number of unique stored words.
isEmpty(): bool checks whether the GADDAG contains no words.
toArray(): array{isWord: bool, children: array<string, mixed>} exports the GADDAG as nested arrays.

GADDAG words must be non-empty and must not contain the separator character.

Benchmarks

These reference numbers were measured with PHP 8.4.6 CLI and Xdebug disabled, using the bundled word lists in tests/word_lists. They are intended as local comparison points, not performance guarantees across machines or PHP builds.

The benchmark builds each structure from the full file, runs 1,000 deterministic exact/path lookup queries, and runs 20 deterministic GADDAG anchor-collection queries. Memory is the approximate PHP heap increase after construction.

Word list	Words	GADDAG forms	Trie build	Trie memory	Trie `contains()` 1k	Trie `startsWith()` 1k	GADDAG build	GADDAG memory	GADDAG encoded lookup 1k	GADDAG `wordsReachableFrom()` 20
`7.txt`	14,423	100,961	44.34 ms	17.52 MiB	3.23 ms	0.68 ms	885.20 ms	128.15 MiB	3.35 ms	518.56 ms
`8.txt`	19,496	155,968	66.87 ms	27.33 MiB	3.22 ms	0.65 ms	1,348.02 ms	232.12 MiB	3.26 ms	792.94 ms

GADDAG construction and anchor collection are expected to be substantially heavier than trie prefix checks because each word contributes multiple encoded forms and wordsReachableFrom() collects original words below an encoded anchor path.

Development

composer install
composer check

Individual checks:

composer test
composer phpstan
composer cs

License

MIT

r34117y / phpgaddag

Maintainers

Package info

Statistics

Security