dawg-lookup

A Directed Acyclic Word Graph implementation in TypeScript/JavaScript

This library takes a dictionary of (ascii) words as input, and generates a compressed datastructure based on a DAWG (like a Trie, but whose representation shares common suffixes as well as common prefixes).

Ported from my 2011 experiment: lookups

Inspired by several blog posts by John Resig:

• Dictionary Lookups in JavaScript
• JavaScript Trie Performance Analysis
• Revised JavaScript Dictionary Search

You can try out hosted version of this software at:

• JavaScript Lookups
• Unit Tests

Packed Trie Encoding Format

A Packed Trie is an encoding a textual Trie using 7-bit ascii. None of the character need be quoted themselves when placed inside a JavaScript string, so dictionaries can be easily including in JavaScript source files or read via ajax.

Example

Suppose our dictionary contains the words:

cat cats dog dogs bat bats rat rats

The corresponding Packed Trie string is:

b0c0dog1r0
at0
!s

Visually, this looks like:

![DAWG diagram](https://g.gravizo.com/g? digraph DAWG { aize = "4, 4"; 0 [label="start"] 1 [label=""] 2 [label="bat, cat, rat, dog"] 3 [label="bats, cats, rats, dogs"] 0 -> 1 [label="b"] 0 -> 1 [label="c"] 0 -> 2 [label="dog"] 0 -> 1 [label="r"] 1 -> 2 [label="at"] 2 -> 3 [label="s"] } )

This Trie (actually, a DAWG) has 3 nodes. If we follow the path of "cats" through the Trie we get the squence:

node 0. match 'c': continue at node + 1
node 1. match 'at': continue at node + 1
node 2. match s: Found!

Or 'dog':

node 0. match 'dog': continue at node + 2
node 2. nothing left to match - '!' indicates Found!

While there are conceptually 4 nodes in this DAWG, we overload the terminal 's' in the 3rd node.

Nodes

A file consists of a sequence of nodes, which are nodes in a Trie representing a dictionary. Nodes are separated by ';' characters (you can split(';') to get an array of node strings).

A node string contains an optional '!' first character, which indicates that this node is a terminal (matching) node in the Trie if there are zero characters left in the pattern.

The rest of the node is a sequence of character strings. Each string is either associated with a node reference, or is a terminal string completing a match. Node references are base 36.1 encoded relative node numbers ('0' == +1, '1' == +2, ...). A comma follows each terminal string to separate it from the next string in the sequence.

A Node reference can also be a symbol - an absolute node reference, instead of a relative one.

Symbols

Large dictionaries can be further compressed by recognizing that node references to some common suffixes can be quite large (i.e., spanning 1,000's of nodes). While encoded as only 3 or 4 characters, we can reduce the file size by replacing selected row references with symbolic references.

To do so, we prepend the file with a collection of symbol definitions:

0:B9M
1:B9O
2:B6R
3:B6B
...
aA5Kb971c82Ud7FFe6Y5f6E5g5Y7h5IDi58Tj53Xk4XOl4J0m3WMn3N0o38Sp2E3q2BZr1QIs0JFtXHuLPvE2w4Kx41y24zS

When used in a Node, a symbol reference indicates the absolute row number as defined in it's symbol definition line (above).

For each symbol we define (up to 36), we shift the meaning of all relative references down by 1. E.g.,if we define 1 symbol ('0'), then the node reference 1 now means "+1 row", whereas it normally means "+2 rows".

Base 36.1 numbers

Unlike base 36 numbers (digits 0-9, A-Z), base "36.1" distinguished between leading zeros. The counting numbers are hence:

0, 1, 2, 3, ..., 9, A, B, C, ..., Y, Z, 00, 01, 02, ... AA, ...

so we eke out a bit more space by not ignoring leading zeros.

Building this Repo

$ source tools/use
$ configure-project
$ run-tests