README-work

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);

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

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

Here we shrink the trie with probabilities above:

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

Here we retrieve a sub-trie with a key:

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

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);

Compare with the original one:

native-trie-say($ptr)

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);

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".