ML::TriesWithFrequencies::Native

This Raku package has C-implementations of functions for creation and manipulation of Tries (Prefix trees) with frequencies.

The package provides Machine Learning (ML) functionalities, not "just" a Trie data structure.

The package is a faster and compatible version of the Raku package "ML::TriesWithFrequencies", [AAp1].

This Raku implementation is based on the code of the C implementation, [AAp2], which, in turn, closely follows the Java implementation [AAp5].

The subset of functions with the prefix "native-trie-" follows the one used in the:

Raku package [AAp1] with prefix "trie-"
Mathematica package [AAp4].

Installation

Via zef-ecosystem:

zef install ML::TriesWithFrequencies::Native

From GitHub:

zef install https://github.com/antononcube/Raku-ML-TriesWithFrequencies-Native

Usage

Consider a trie (prefix tree) created over a list of words:

use ML::TriesWithFrequencies::Native;
use ML::TriesWithFrequencies;

my $tr = native-trie-create-by-split( <bar bark bars balm cert cell> );
 
# define visualization function
sub native-trie-say($t) { trie-say(trie-from-map-format(native-trie-to-map($t))) };

native-trie-say($tr);

# TRIEROOT => 6
# ├─b => 4
# │ └─a => 4
# │   ├─l => 1
# │   │ └─m => 1
# │   └─r => 3
# │     ├─k => 1
# │     └─s => 1
# └─c => 2
#   └─e => 2
#     ├─l => 1
#     │ └─l => 1
#     └─r => 1
#       └─t => 1

Here we convert the trie with frequencies above into a trie with probabilities:

my $ptr = native-trie-node-probabilities( $tr );
native-trie-say($ptr);

# TRIEROOT => 1
# ├─b => 0.6666666666666666
# │ └─a => 1
# │   ├─l => 0.25
# │   │ └─m => 1
# │   └─r => 0.75
# │     ├─k => 0.3333333333333333
# │     └─s => 0.3333333333333333
# └─c => 0.3333333333333333
#   └─e => 1
#     ├─l => 0.5
#     │ └─l => 1
#     └─r => 0.5
#       └─t => 1

Here we shrink the trie with probabilities above:

native-trie-say(native-trie-shrink($ptr));

# TRIEROOT => 1
# ├─ba => 0.6666666666666666
# │ ├─lm => 0.25
# │ └─r => 0.75
# │   ├─k => 0.3333333333333333
# │   └─s => 0.3333333333333333
# └─ce => 0.3333333333333333
#   ├─ll => 0.5
#   └─rt => 0.5

Here we retrieve a sub-trie with a key:

native-trie-say(native-trie-retrieve($ptr, 'bar'.comb))

# TRIEROOT => 0.75
# ├─k => 0.3333333333333333
# └─s => 0.3333333333333333

Generate random words using trie, make a new trie, and visualize it:

my @randomWords = native-trie-random-choice($ptr, 200);
my $ptrRandom = native-trie-node-probabilities(native-trie-create(@randomWords));
native-trie-say($ptrRandom);

# TRIEROOT => 1
# ├─b => 0.62
# │ └─a => 1
# │   ├─l => 0.25806451612903225
# │   │ └─m => 1
# │   └─r => 0.7419354838709677
# │     ├─k => 0.4673913043478261
# │     └─s => 0.532608695652174
# └─c => 0.38
#   └─e => 1
#     ├─l => 0.5
#     │ └─l => 1
#     └─r => 0.5
#       └─t => 1

Compare with the original one:

native-trie-say($ptr)

# TRIEROOT => 1
# ├─b => 0.6666666666666666
# │ └─a => 1
# │   ├─l => 0.25
# │   │ └─m => 1
# │   └─r => 0.75
# │     ├─k => 0.3333333333333333
# │     └─s => 0.3333333333333333
# └─c => 0.3333333333333333
#   └─e => 1
#     ├─l => 0.5
#     │ └─l => 1
#     └─r => 0.5
#       └─t => 1

Remark: It is expected with large numbers of generated words to get frequencies very close to those of the original trie.

Representation

Such trees can be nicely represented as hashmaps. For example:

my $tr = native-trie-shrink(native-trie-create-by-split(<core cort>));
native-trie-to-map-format($tr);

# {TRIEROOT => {TRIEVALUE => 2, cor => {TRIEVALUE => 2, e => {TRIEVALUE => 1}, t => {TRIEVALUE => 1}}}}

Performance

This package "ML::TriesWithFrequencies::Native" is approximately 10÷15 times faster than "ML::TriesWithFrequencies" on "larger" lists of words. See the benchmark file "Native-Trie-creation-profiling.raku".