cspell-trie

Trie library for use with cspell

This library allows easily building of a Trie from a word list.

The resulting trie can then be compressed into a DAFSA|DAWG.

Installation

npm install -S cspell-trie-lib

File Format V3

Header

TrieXv3
base=10
# Comments
__DATA__

The header has two parts.

• TrieXv3 -- the format identifier.
• base -- references are stored using the base (10, 16, 32) are common. higher the base, the smaller the file. Max is 36

Data

The data is a stream of characters and operators. Each character represents a node in the Trie. The operators adjust the position in the Trie.

Conceptual Format

Given a sorted list of words:

joust
jouster
jousting
joy
joyful
joyfuller
joyfullest

It is possible to think of the same list stored as a series of operations.

| op | Meaning | | ----- | ------------------- | | < | remove 1 character | | << | remove 2 characters | | <<< | remove 3 characters | | <2 | remove 2 characters | | <3 | remove 3 characters | | $ | end of word | | _ | visual place holder |

joust$
_____er$
_____<<
_____ing$
__<<<<<<
__y$
___ful$
______ler$
________<
________st$

Becomes:

joust$er$<2ing$<6y$ful$ler$<st$

Trie:

j─o┬u─s─t┬$
   │     ├e─r─$
   │     └i─n─g─$
   └y┬$
     └f─u─l┬$
           └l─e┬r─$
               └s─t─$

Data Format

| op | Meaning | | ----- | --------------------------------------------------------------------------------------------------------- | | < | remove 1 character | | <n | remove n characters where n is [2-9] to remove 12 characters use <9<3 | | $ | end of word | | \ | escape next character. All characters can be escaped. \\ -> \ \# -> # \a -> a | | #n; | reference to an already imported trie node where n is the node number |

Sample Data

CSpell for Enterprise