README
@kamilmielnik/trie
Trie data structure implementation in TypeScript. Highly performant. No dependencies. Built for a Scrabble Solver.
Table of contents
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');
console.log(trie.hasPrefix('man')); // false
console.log(trie.hasPrefix('mas')); // true
console.log(trie.has('mas')); // false
console.log(trie.remove('mas')); // false
console.log(trie.has('master')); // true
console.log(trie.serialize()); // "(m(a(s(t(e(r))k))))"
console.log(trie.remove('master')); // true
console.log(trie.serialize()); // "(m(a(s(k))))"
Functional API
Manipulate existing instances of Node
with functions.
Example
The following example works identical 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');
console.log(hasPrefix(root, 'man')); // false
console.log(hasPrefix(root, 'mas')); // true
console.log(has(root, 'mas')); // false
console.log(remove(root, 'mas')); // false
console.log(has(root, 'master')); // true
console.log(serialize(root)); // "(m(a(s(t(e(r))k))))"
console.log(remove(root, 'master')); // true
console.log(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;
};
Node
to a file
Serialize import { Trie } from '@kamilmielnik/trie';
import fs from 'fs';
const toFile = (trie: Trie): void => {
const serialized = trie.serialize();
fs.writeFileSync(filepath, serialized);
};
Node
from a file
Load serialized 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 1.01864 compression ratio (98.17%) 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 - logarithmic complexity (millions of operations per second).
deserialize
, fromArray
, serialize
, toArray
are slow - linear complexity (few operations per second).