@kamilmielnik/trie

Trie data structure implemented in TypeScript:

• Highly performant
• No dependencies
• Lightweight
• Well-documented
• Built for Scrabble Solver

Table of contents

• Installation
• API
  • Object-oriented API
  • Functional API
• Examples
  • Load dictionary from file
  • Serialize Node to a file
  • Load serialized Node from a file
  • Find all words with given prefix
• Serialization and compression
• Performance

Installation

npm

npm install @kamilmielnik/trie --save

yarn

yarn add @kamilmielnik/trie

API

See full API Docs - generated by typedoc.

Good to know:

• all objects are mutable
• every class, interface, type, constant and function is exported
• all exports are named (there is no default export)

There are 2 ways to use the API.

Object-oriented API

Create Trie instance and use its methods.

Example

import { Trie } from '@kamilmielnik/trie';

const trie = new Trie();
trie.add('master');
trie.add('mask');
trie.hasPrefix('man'); // false
trie.hasPrefix('mas'); // true
trie.has('mas');       // false
trie.remove('mas');    // false
trie.has('master');    // true
trie.serialize();      // "(m(a(s(t(e(r))k))))"
trie.remove('master'); // true
trie.serialize();      // "(m(a(s(k))))"

Functional API

Manipulate existing instances of Node with functions.

Example

The following example works identically to the object-oriented example above.

import { add, has, hasPrefix, Node, remove, serialize } from '@kamilmielnik/trie';

const root: Node = {};

add(root, 'master');
add(root, 'mask');
hasPrefix(root, 'man'); // false
hasPrefix(root, 'mas'); // true
has(root, 'mas');       // false
remove(root, 'mas');    // false
has(root, 'master');    // true
serialize(root);        // "(m(a(s(t(e(r))k))))"
remove(root, 'master'); // true
serialize(root);        // "(m(a(s(k))))"

Examples

• Load dictionary from file
• Serialize Node to a file
• Load serialized Node from a file
• Find all words with given prefix

Load dictionary from file

import { fromArray, Node } from '@kamilmielnik/trie';
import fs from 'fs';

const fromFile = (filepath: string): Node => {
  const file = fs.readFileSync(filepath, 'utf-8');
  // Assuming file contains 1 word per line
  const words = file.split('\n').filter(Boolean);
  const node = fromArray(words);
  return node;
};

Serialize Node to a file

import { Trie } from '@kamilmielnik/trie';
import fs from 'fs';

const toFile = (filepath: string, trie: Trie): void => {
  const serialized = trie.serialize();
  fs.writeFileSync(filepath, serialized);
};

Load serialized Node from a file

import { deserialize, Node } from '@kamilmielnik/trie';
import fs from 'fs';

const fromFile = (filepath: string): Node => {
  const serialized = fs.readFileSync(filepath, 'utf-8');
  const node = deserialize(serialized);
  return node;
};

Find all words with given prefix

import { find, Node, toArray } from '@kamilmielnik/trie';

const findWordsWithPrefix = (node: Node, prefix: string): string[] => {
  const prefixNode = find(node, prefix) || {};
  const descendants = toArray(prefixNode, { prefix, sort: true, wordsOnly: true });
  const words = descendants.map(({ prefix: word }) => word);
  return words;
};

Serialization and compression

This package can be used to efficiently serialize and compress dictionaries. It reaches 54.79 compression ratio (98.17% space saving) for Polish dictionary when combined with 7-Zip at ultra compression level.

| Language | 🇺🇸 en-US | 🇬🇧 en-GB | 🇵🇱 pl-PL | | ------------------------------------------------------------------- | ----------------------------------------------------------------------- | --------------------------------------------------------------------------- | ----------------------------------------- | | Name | TWL06 | SOWPODS | SJP.PL | | Source | Download | Download | Download | | Words count | 178,691 | 267,753 | 3,045,878 | | File size [B] | 1,941,856 | 2,974,773 | 42,838,508 | | File size (serialized) [B] | (-29.75%) 1,364,242 | (-31.57%) 2,035,697 | (-56.33%) 18,705,990 | | File size (7z) [B] | (-80.46%) 379,483 | (-81.04%) 563,913 | (-87.58%) 5,320,397 | | File size (serialized + 7z) [B] | (-89.94%) 195,299 | (-90.40%) 285,430 | (-98.17%) 781,875 |

Performance

add, find, has, hasPrefix, remove are very fast - $O(\log_2 n)$ (millions of operations per second).

deserialize, fromArray, serialize, toArray are slow - $O(n)$ (few operations per second).