cspell-trie-lib
Trie Data Structure to support cspell.
Last updated 2 years ago
by jason-dent
.
MIT
·
Repository
·
Bugs
·
Original npm
·
Tarball
·
package.json
$ gnpm install cspell-trie-lib
SYNC missed versions from
official npm registry.
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
Big Apple$8races\: \{\}\[\]\(\)$9<5
New York$7umbers \0\1\2\3\4\5\6\7\8\9$9<9
ap#6;<rrow \<$7
big a#5;<4urned$r$2ing$3s$$4
chalk#56;<3u#54;<3
eol \\n$3w \$$4scape \\\$8
fun journey$7wal#27;<7
journalism$tic$2$3s$$2eyer$2man$2e#103;<2$4ste#101;<i#58;<$3vialit#85;<2$4wly$$2yfuller$st$4ness$4$3lessn#120;<$4ou#125;<2ridde#103;<2er$$i#58;<3od#8;<3
stic#27;<4$3
lift#56;<3ong w#86;<6
ref \#$5
t#61;<
wa#62;<2
File Format V1
Header
TrieXv1
base=10
The header has two parts.
- TrieXv1 -- the identifiers
- base -- offsets are stored using the base (10, 16, 32) are common. higher the base, the smaller the file. Max is 36
Data
The first line of data is always a *
Each line is a node in the Trie.
The format of each line is:
star [char index [, char index]*]
- star - the presence of a star indicates that the node is the ending of a word.
- char - a character that can be appended to the word followed by the node at index.
- index - the offset in the list of nodes to continue appending
In other words, each line has an optional * followed by 0 or more (char, index) pairs.
A missing index implies an index of 0, which is the end of word flag.
Example Line: *s1,e -- The word can stop here, or add an s and continue at node 1, or add an e
Example:
Word List:
- walk
- walked
- walker
- walking
- walks
- talk
- talks
- talked
- talker
- talking
becomes
Output: (Offsets are added for clarity, but do not exist in output)
Offset Output
------- --------
TrieXv1
base=10
0 *
1 d,r
2 g
3 n2
4 *e1,i3,s
5 k4
6 l5
7 a6
8 t7,w7
The root of the trie is the last offset, 8. It is designed for the entire trie to be in memory, which is why the root is at the end. This allows for efficiently building the trie as the file loads line by line, because each line can only refer to previous lines.
How to walk the data to see if "talks" is in it.
- Start with the root at offset 8.
- t found goto 7
- a found goto 6
- l found goto 5
- k found goto 4
- s found stop (goto 0 is stop).
CSpell for Enterprise
Available as part of the Tidelift Subscription.
The maintainers of cspell and thousands of other packages are working with Tidelift to deliver commercial support and maintenance for the open source packages you use to build your applications. Save time, reduce risk, and improve code health, while paying the maintainers of the exact packages you use. Learn more.
Brought to you by
Street Side Software
Current Tags
- 4.2.8 ... cspell4 (4 years ago)
- 5.21.2 ... cspell5 (3 years ago)
- 5.21.2-alpha.0 ... cspell5-next (3 years ago)
- 7.3.6 ... latest (a year ago)
- 7.0.1-alpha.9 ... next (a year ago)
243 Versions
- 7.3.6 ... a year ago
- 7.3.5 ... a year ago
- 7.3.4 ... a year ago
- 7.3.3 ... a year ago
- 7.3.2 ... a year ago
- 7.3.1 ... a year ago
- 7.3.0 ... a year ago
- 7.2.0 ... a year ago
- 7.1.1 ... a year ago
- 7.0.2 ... a year ago
- 7.0.1 ... a year ago
- 7.0.0 ... a year ago
- 7.0.1-alpha.9 ... a year ago
- 6.31.3 ... a year ago
- 7.0.1-alpha.8 ... a year ago
- 7.0.1-alpha.7 ... a year ago
- 7.0.1-alpha.6 ... a year ago
- 7.0.1-alpha.5 ... a year ago
- 7.0.1-alpha.4 ... a year ago
- 7.0.1-alpha.3 ... a year ago
- 7.0.1-alpha.2 ... a year ago
- 7.0.1-alpha.1 ... a year ago
- 7.0.1-alpha.0 ... 2 years ago
- 7.0.0-alpha.2 ... 2 years ago
- 7.0.0-alpha.1 ... 2 years ago
- 6.31.1 ... 2 years ago
- 6.31.0 ... 2 years ago
- 6.30.2 ... 2 years ago
- 6.30.1 ... 2 years ago
- 6.30.0 ... 2 years ago
- 6.29.3 ... 2 years ago
- 6.29.2 ... 2 years ago
- 6.29.1 ... 2 years ago
- 6.29.0 ... 2 years ago
- 6.28.0 ... 2 years ago
- 6.27.0 ... 2 years ago
- 6.26.3 ... 2 years ago
- 6.26.2 ... 2 years ago
- 6.26.1 ... 2 years ago
- 6.26.0 ... 2 years ago
- 6.25.0 ... 2 years ago
- 6.24.0 ... 2 years ago
- 6.23.1 ... 2 years ago
- 6.23.0 ... 2 years ago
- 6.22.0 ... 2 years ago
- 6.21.0 ... 2 years ago
- 6.20.1 ... 2 years ago
- 6.20.0 ... 2 years ago
- 6.19.2 ... 2 years ago
- 6.19.1 ... 2 years ago
- 6.19.0 ... 2 years ago
- 6.18.1 ... 2 years ago
- 6.18.0 ... 2 years ago
- 6.17.0 ... 2 years ago
- 6.16.0 ... 2 years ago
- 6.15.1 ... 2 years ago
- 6.15.0 ... 2 years ago
- 6.14.3 ... 2 years ago
- 6.14.2 ... 2 years ago
- 6.14.1 ... 2 years ago
- 6.14.0 ... 2 years ago
- 6.13.3 ... 2 years ago
- 6.13.2 ... 2 years ago
- 6.13.1 ... 2 years ago
- 6.13.0 ... 2 years ago
- 6.12.0 ... 2 years ago
- 6.11.1 ... 2 years ago
- 6.11.0 ... 2 years ago
- 6.10.1 ... 2 years ago
- 6.10.0 ... 2 years ago
- 6.9.1 ... 2 years ago
- 6.9.0 ... 2 years ago
- 6.8.2 ... 2 years ago
- 6.8.1 ... 2 years ago
- 6.8.0 ... 2 years ago
- 6.7.0 ... 2 years ago
- 6.6.1 ... 2 years ago
- 6.6.1-alpha.9 ... 2 years ago
- 6.6.1-alpha.2 ... 2 years ago
- 6.6.1-alpha.1 ... 2 years ago
- 6.6.1-alpha.0 ... 2 years ago
- 6.6.0 ... 2 years ago
- 6.5.0 ... 2 years ago
- 6.4.2 ... 2 years ago
- 6.4.1 ... 2 years ago
- 6.4.0 ... 2 years ago
- 6.4.0-alpha.0 ... 2 years ago
- 6.3.0 ... 2 years ago
- 6.2.4-alpha.0 ... 2 years ago
- 6.2.3 ... 2 years ago
- 6.2.2 ... 2 years ago
- 6.2.1 ... 2 years ago
- 6.2.0 ... 2 years ago
- 6.2.0-alpha.1 ... 2 years ago
- 6.2.0-alpha.0 ... 2 years ago
- 6.1.3 ... 2 years ago
- 6.1.3-alpha.1 ... 2 years ago
- 6.1.3-alpha.0 ... 2 years ago
- 6.1.2 ... 3 years ago
- 6.1.1 ... 3 years ago
- 6.1.0 ... 3 years ago
- 6.1.0-alpha.0 ... 3 years ago
- 5.21.2 ... 3 years ago
- 6.0.0 ... 3 years ago
- 5.21.2-alpha.0 ... 3 years ago
- 6.0.0-alpha.0 ... 3 years ago
- 5.21.1 ... 3 years ago
- 5.21.0 ... 3 years ago
- 5.20.0 ... 3 years ago
- 5.19.7 ... 3 years ago
- 5.19.6 ... 3 years ago
- 5.19.5 ... 3 years ago
- 5.19.4 ... 3 years ago
- 5.19.3 ... 3 years ago
- 5.19.2 ... 3 years ago
- 5.19.1 ... 3 years ago
- 5.19.0 ... 3 years ago
- 5.18.5 ... 3 years ago
- 5.18.4 ... 3 years ago
- 5.18.3 ... 3 years ago
- 5.18.2 ... 3 years ago
- 5.18.1 ... 3 years ago
- 5.18.0 ... 3 years ago
- 5.18.0-alpha.0 ... 3 years ago
- 5.17.0 ... 3 years ago
- 5.17.0-alpha.0 ... 3 years ago
- 5.16.0 ... 3 years ago
- 5.15.3 ... 3 years ago
- 5.15.2 ... 3 years ago
- 5.15.1 ... 3 years ago
- 5.15.0 ... 3 years ago
- 5.14.0 ... 3 years ago
- 5.14.0-alpha.0 ... 3 years ago
- 5.13.4 ... 3 years ago
- 5.13.3 ... 3 years ago
- 5.13.2 ... 3 years ago
- 5.13.1 ... 3 years ago
- 5.13.0 ... 3 years ago
- 5.12.6 ... 3 years ago
- 5.12.5 ... 3 years ago
- 5.12.4 ... 3 years ago
- 5.12.3 ... 3 years ago
- 5.12.2 ... 3 years ago
- 5.12.0 ... 3 years ago
- 5.12.0-alpha.0 ... 3 years ago
- 5.11.1 ... 3 years ago
- 5.11.0 ... 3 years ago
- 5.11.0-alpha.0 ... 3 years ago
- 5.10.1 ... 3 years ago
- 5.10.0 ... 3 years ago
- 5.10.0-alpha.6 ... 3 years ago
- 5.10.0-alpha.5 ... 3 years ago
- 5.10.0-alpha.4 ... 3 years ago
- 5.10.0-alpha.3 ... 3 years ago
- 5.10.0-alpha.2 ... 3 years ago
- 5.9.1 ... 3 years ago
- 5.9.1-alpha.1 ... 3 years ago
- 5.9.0 ... 3 years ago
- 5.9.0-alpha.0 ... 3 years ago
- 5.8.2 ... 3 years ago
- 5.8.1 ... 3 years ago
- 5.8.0 ... 3 years ago
- 5.7.0 ... 3 years ago
- 5.6.7 ... 3 years ago
- 5.6.5 ... 3 years ago
- 5.6.4 ... 3 years ago
- 5.6.3 ... 4 years ago
- 5.6.2 ... 4 years ago
- 5.6.1 ... 4 years ago
- 5.6.0 ... 4 years ago
- 5.5.2 ... 4 years ago
- 5.5.1 ... 4 years ago
- 5.5.0 ... 4 years ago
- 5.4.1 ... 4 years ago
- 5.4.0 ... 4 years ago
- 5.3.12 ... 4 years ago
- 5.3.11 ... 4 years ago
- 5.3.10 ... 4 years ago
- 5.3.8 ... 4 years ago
- 5.3.7 ... 4 years ago
- 5.3.7-alpha.3 ... 4 years ago
- 5.3.5 ... 4 years ago
- 5.3.4 ... 4 years ago
- 5.3.3 ... 4 years ago
- 5.3.2 ... 4 years ago
- 5.3.1 ... 4 years ago
- 5.3.0 ... 4 years ago
- 5.3.0-alpha.4 ... 4 years ago
- 5.3.0-alpha.3 ... 4 years ago
- 5.3.0-alpha.2 ... 4 years ago
- 5.3.0-alpha.1 ... 4 years ago
- 5.3.0-alpha.0 ... 4 years ago
- 5.2.2 ... 4 years ago
- 5.2.0 ... 4 years ago
- 5.1.3 ... 4 years ago
- 5.1.0 ... 4 years ago
- 5.0.8 ... 4 years ago
- 4.2.8 ... 4 years ago
- 5.0.4 ... 4 years ago
- 5.0.3 ... 4 years ago
- 4.2.7 ... 4 years ago
- 5.0.2 ... 4 years ago
- 5.0.1 ... 4 years ago
- 5.0.1-alpha.15 ... 4 years ago
- 4.2.6 ... 4 years ago
- 5.0.1-alpha.13 ... 4 years ago
- 4.2.4 ... 4 years ago
- 5.0.1-alpha.12 ... 4 years ago
- 5.0.1-alpha.11 ... 4 years ago
- 5.0.1-alpha.8 ... 4 years ago
- 4.2.2 ... 4 years ago
- 4.2.1 ... 4 years ago
- 5.0.1-alpha.6 ... 4 years ago
- 4.2.0 ... 4 years ago
- 5.0.1-alpha.5 ... 4 years ago
- 4.1.10 ... 5 years ago
- 4.1.9 ... 5 years ago
- 5.0.1-alpha.3 ... 5 years ago
- 4.1.8 ... 5 years ago
- 4.1.7 ... 5 years ago
- 4.1.6 ... 5 years ago
- 4.1.5 ... 5 years ago
- 4.1.4 ... 5 years ago
- 4.1.2 ... 5 years ago
- 4.1.1 ... 5 years ago
- 4.1.0 ... 5 years ago
- 4.0.16 ... 5 years ago
- 4.0.15 ... 5 years ago
- 4.0.14 ... 5 years ago
- 4.0.13 ... 6 years ago
- 4.0.12 ... 6 years ago
- 4.0.11 ... 6 years ago
- 4.0.10 ... 6 years ago
- 4.0.9 ... 6 years ago
- 4.0.8 ... 6 years ago
- 4.0.7 ... 6 years ago
- 4.0.6 ... 6 years ago
- 4.0.5 ... 6 years ago
- 4.0.4 ... 6 years ago
- 4.0.3 ... 6 years ago
- 3.0.13 ... 6 years ago
- 3.0.12 ... 6 years ago
- 3.0.11 ... 6 years ago
Maintainers (1)
Downloads
Today
0
This Week
0
This Month
144
Last Day
0
Last Week
144
Last Month
0
Dependencies (3)
- @cspell/cspell-pipe ^6.2.3
- fs-extra ^10.1.0
- gensequence ^3.1.1
Dev Dependencies (7)
- @cspell/cspell-types ^6.2.3
- @cspell/dict-en_us ^2.2.10
- @cspell/dict-es-es ^2.2.0
- @types/fs-extra ^9.0.13
- @types/node ^18.0.3
- jest ^28.1.2
- rimraf ^3.0.2
Dependents (5)