Repository files navigation

Trie / DAWG implementation for JavaScript.

Construct a trie out of a list of words for efficient searches. The trieprovides a#freeze method to dedupe its suffixes, turning it into a directedacyclic word graph (DAWG).

More excitingly, there is aTrie#encode method which outputs the trie in asuccinct binary format. (The trie does not need to be DAWG-ified in order toencode it, but it usually makes sense to do so.) The binary format is output inBase-64 and can be transmitted as JSON.

To use an encoded trie, there is aPackedTrie class. This class can makequeries against the trie without ever having to parse the binary file. Thisclass has virtually no initialization cost and low memory overhead withoutsacrificing lookup speed.

There are no specific character or size constraints on the Trie input. Unicodeinput should work, provided you treat the encoded string as unicode (it willcontain the unicode characters somewhere in it.)

BothTrie andPackedTrie supporttest andsearch methods which supportfuzzy-matching (i.e., wildcards) and prefix search.

See complete docs athttps://jnu.github.io/tiny-trie/

constwords=['spit','spat','spot','spits','spats','spots'];consttrie=newTrie();words.forEach(word=>trie.insert(word));// test membershiptrie.test('spit');// -> truetrie.test('split');// -> falsetrie.search('sp*t',{wildcard:'*'});// -> ['spit', 'spat', 'spot']trie.search('spi',{prefix:true});// -> ['spit', 'spits']// finalize the trie, turning it into a DAWGtrie.freeze();// encode the trieletencoded=trie.encode();// -> 'A4AAAAMEspiaotI0NmhqfPzcsQLwwrCCcBAQE'// This string describes the DAWG in a concise binary format. This format can// be interpreted by the `PackedTrie` class.constsmallDawg=newPackedTrie(encoded);smallDawg.test('spit');// -> truesmallDawg.test('split');// -> falsesmallDawg.search('sp*t',{wildcard:'*'});// -> ['spit', 'spat', 'spot']smallDawg.search('spi',{prefix:true});// -> ['spit', 'spits']

import{TinyTrie}from'tiny-trie';importPackedTriefrom'tiny-trie/lib/PackedTrie';

The default module export also provides some convenience functional tools:

importtinyTriefrom'tiny-trie';tinyTrie.createSync(['foo','bar']);// equivalent to://  > var t = new Trie();//  > ['foo', 'bar'].forEach(word => t.insert(word));tinyTrie.createFrozenSync(['foo','bar']);// equivalent to://  > var t = new Trie();//  > ['foo', 'bar'].forEach(word => t.insert(word));//  > t.freeze();

Bundled, ES5-compatible equivalents to the above are in./dist.

// tiny-trie[.min].jsTinyTrie.TrieTinyTrie.createSyncTinyTrie.createFrozenSync// packed-trie[.min].jsPackedTrie

Quick benchmarks with the initial implementation on an MBP, node v5.0.0.

Usingdictionary.txt, a Scrabble dictionary with 178,692 words.

varwords=fs.readFileSync('./dictionary.txt','utf8').split('\n');

Gives an idea roughly how long things take.

>vartrie=TinyTrie.createSync(words);// 846 milliseconds>trie.test(...);// avg: 0.05 milliseconds>trie.freeze();// 124 seconds>varencoded=trie.encode();// 936 milliseconds>varpacked=newPackedTrie(encoded);// 0.06 milliseconds (compare `new Set(words)`, which takes about 1s)>packed.test(...);// avg: 0.05 milliseconds (not significantly different from the unpacked trie!)

The init time of almost 1s is not acceptable for a client-side application.The goal of runningTrie#freeze(); Trie#encode(); at build time is toproduce a packed version of the DAWG that has virtuallyno init time - and itcan still be queried directly, with speeds approaching the fullTrie's veryfast 50 microsecond times.

>words.join('').length// 1584476 (bytes)>encoded.length// 698518 (bytes)>encoded.length/words.join('').length// 0.44085110787414894

The encoded trie uses just 44% of the bytes as the full dictionary. Gzippinggives a trie of 483kb, compared with 616kb for the dictionary.

• Real benchmarks, comparison with other implementations

• Optimize inPackedTrie - reduce size, increase perf. Node order couldprobably be revised to shrink pointer field width.

• Spec out limitations on encoding inputs