Tries

Tries are data structures that can be used to store sequences - e.g. words as sequences of letters.
Tries support faster and more precise query executions related to those sequences.

Classical Tries

Usage Examples

import { Trie } from "https://deno.land/x/tries/mod.ts"

const trie = new Trie()

const exampleSequence1 = "be"
const exampleSequence2 = "bet"
const exampleSequence3 = "bed"
const exampleSequence4 = "bed and breakfast"
const exampleSequence5 = "justice"

trie.insert(exampleSequence1)
trie.insert(exampleSequence3)
trie.insert(exampleSequence2)
trie.insert(exampleSequence5)
trie.insert(exampleSequence4)

console.log(trie.hasSequence(exampleSequence3)) // true
console.log(trie.hasSequence(exampleSequence4)) // true
console.log(trie.hasSequence("breakfast")) // false because it is not added as a discrete sequence
console.log(trie.hasSequence("missing")) // false 

Letters and Words Prediction Tries

import { LettersWordsPredictionTrie } from "https://deno.land/x/tries/mod-letters-and-word-prediction.ts"

const lettersWordsPredictionTrie = new LettersWordsPredictionTrie()

lettersWordsPredictionTrie.learn(['ether', 'eth', 'ethereum', 'super'])

const brain = lettersWordsPredictionTrie.getBrain()

console.log(JSON.stringify(brain, undefined, 2))

Radix Tree

A Radix Tree is a compressed version of a trie - see this introduction

There are several variations of Radix Trees. In some cases there is no consistent naming / definition to be found (yet?).
A rather famous variation of a Radix Tree is the PATRICIA Trie:
P Practical
A Algorithm
T To
R Retrieve
I Information
C Coded
I In
A Alphanumeric

PATRICIA Tries are Radix Trees with the radix 2.
Merkle PATRICIA Tries aka Merkle PATRICIA Trees became especially famous as in the Ethereum Blockchain pretty much everything (state trie, transaction trie, receipt trie, ...) is stored in those kinds of data structures. For details I can recommend this video. Keep in mind that (currently) some people use different words for the same thing and some people use the same word for different things in these contexts.

Merkle PATRICIA Trie / Tree

import merklePatriciaTree from 'https://cdn.skypack.dev/merkle-patricia-tree'

// For specific usage examples you might check https://www.skypack.dev/view/merkle-patricia-tree

Usage Examples

... Under Construction ...

Unit Tests

For further usage examples etc. please check the unit tests.

Contribute

Contributions / Pull Requests are welcome.