# Can a Trie be implemented efficiently?

What is the most space and time efficient way to implement a Trie in Mathematica?

Will it be practically faster than what is natively available in appropriate cases?

• Did this arise because of this question? If so, then once again, thank you for providing the exact formal name of the problem! :) Mar 26, 2012 at 8:06
• @alancalvitti I have updated my post below. As to Dataset, I think it will be an overkill and actually not an appropriate thing to do to use it for a trie. It will also be much slower. Nov 27, 2014 at 16:12
• @LeonidShifrin, I understand the distinction but the reality in statistical analysis is that queries will vary w/ the specifics of the task and (often noSQL) data structures provided. Dataset, Query and even operator form have already reduced my codebase & dev time >5x over V9. It's not a "wrapper". The ideal solution is Dataset syntax w/ fast algorithms. For example, how easily can you modify your code to handle frequencies like here: mathematicaforprediction.wordpress.com/2013/12/06/… Nov 28, 2014 at 17:32
• @alancalvitti I understand your perspective as being a user who wants compact syntax, but for any realistic problem this is not the only dimension. What I have described is a developer's view on how to structure the functionality so that it works well for both performance and convenience dimensions. From this viewpoint, Dataset certainly is a wrapper (in the sense I explained above). Once again: I am not saying that convenience isn't important, I am saying that it is a different aspect, from pure data structure implementation. Nov 28, 2014 at 18:08
• So, five years later, I will ask...what have you, err, tried? (I crack me up.) Feb 1, 2017 at 2:13

UPDATE

Since version 10, we have Associations. Here is the modified code for trie building and querying, based on Associations. It is almost the same as the old code (which is below):

ClearAll[makeTreeAssoc];
makeTreeAssoc[wrds : {__String}] := Association@makeTreeAssoc[Characters[wrds]];
makeTreeAssoc[wrds_ /; MemberQ[wrds, {}]] :=
Prepend[makeTreeAssoc[DeleteCases[wrds, {}]], {} -> {}];
makeTreeAssoc[wrds_] :=
Reap[
If[# =!= {}, Sow[Rest[#], First@#]] & /@ wrds,
_,
#1 -> Association@makeTreeAssoc[#2] &
][[2]]


You can see that the only difference is that Association is added to a couple of places, otherwise it's the same code. The lookup functions also are very similar:

ClearAll[getSubTreeAssoc];
getSubTreeAssoc[word_String, tree_] := Fold[Compose, tree, Characters[word]]

ClearAll[inTreeQAssoc];
inTreeQAssoc[word_String, tree_] := KeyExistsQ[getSubTreeAssoc[word, tree], {}]


The tests similar to the ones below (for entire dictionary) show that the lookup based on this trie (Associations - based) is about 3 times faster than the one based on rules, for a trie built from a dictionary. The new implementation of getWords is left as an exercise to the reader (in fact, that function could be optimized a lot, by storing entire words as leaves in the tree, so that one doesn't have to use StringJoin and combine the words).

A combination of rules and recursion is able to produce rather powerful solutions. Here is my take on it:

ClearAll[makeTree];
makeTree[wrds : {__String}] := makeTree[Characters[wrds]];
makeTree[wrds_ /; MemberQ[wrds, {}]] :=
Prepend[makeTree[DeleteCases[wrds, {}]], {} -> {}];
makeTree[wrds_] :=
Reap[If[# =!= {}, Sow[Rest[#], First@#]] & /@
wrds, _, #1 -> makeTree[#2] &][[2]]

ClearAll[getSubTree];
getSubTree[word_String, tree_] := Fold[#2 /. #1 &, tree, Characters[word]]

ClearAll[inTreeQ];
inTreeQ[word_String, tree_] :=  MemberQ[getSubTree[word, tree], {} -> {}]

ClearAll[getWords];
getWords[start_String, tree_] :=
Module[{wordStack = {}, charStack = {}, words},
words[{} -> {}] :=
wordStack = {wordStack, StringJoin[charStack]};
words[sl_ -> ll_List] :=
Module[{},
charStack = {charStack, sl};
words /@ ll;
charStack = First@charStack;
];
words[First@Fold[{#2 -> #1} &, getSubTree[start, tree],
Reverse@Characters[start]]
];
ClearAll[words];
Flatten@wordStack];


The last function serves to collect the words from a tree, by performing a depth-first tree traversal and maintaining the stack of accumulated characters and words.

Here is a short example:

In[40]:= words = DictionaryLookup["absc*"]
Out[40]= {abscess,abscessed,abscesses,abscessing,abscissa,abscissae,abscissas,
abscission,abscond,absconded,absconder,absconders,absconding,absconds}

In[41]:= tree = makeTree[words]
Out[41]= {a->{b->{s->{c->{e->{s->{s->{{}->{},e->{d->{{}->{}},s->{{}->{}}},
i->{n->{g->{{}->{}}}}}}},i->{s->{s->{a->{{}->{},e->{{}->{}},s->{{}->{}}},
i->{o->{n->{{}->{}}}}}}},o->{n->{d->{{}->{},e->{d->{{}->{}},r->{{}->{},s->{{}->{}}}},
i->{n->{g->{{}->{}}}},s->{{}->{}}}}}}}}}}

In[47]:= inTreeQ[#,tree]&/@words
Out[47]= {True,True,True,True,True,True,True,True,True,True,True,True,True,True}

In[48]:= inTreeQ["absd",tree]
Out[48]= False

In[124]:= getWords["absce", tree]
Out[124]= {"abscess", "abscessed", "abscesses", "abscessing"}


I only constructed here a bare-bones tree, so you can only test whether or not the word is there, but not keep any other info. Here is a larger example:

In[125]:= allWords =  DictionaryLookup["*"];

In[126]:= (allTree = makeTree[allWords]);//Timing
Out[126]= {5.375,Null}

In[127]:= And@@Map[inTreeQ[#,allTree]&,allWords]//Timing
Out[127]= {1.735,True}

In[128]:= getWords["pro",allTree]//Short//Timing
Out[128]= {0.015,{pro,proactive,proactively,probabilist,
<<741>>,proximate,proximately,proximity,proxy}}

In[129]:= DictionaryLookup["pro*"]//Short//Timing
Out[129]= {0.032,{pro,proactive,proactively,probabilist,<<741>>,
proximate,proximately,proximity,proxy}}


I don't know which approach has been used for the built-in functionality, but the above implementation seems to be generally in the same calss for performance. The slowest part is due to the top-level tree-traversing code in getWords. It is slow because the top-level code is slow. One could speed it up considerably by hashing words to integers - then it can be Compiled. This is how I'd do that, if I were really concerned with speed.

EDIT

For a really nice application of a Trie data structure, where it allows us to achieve major speed-up (w.r.t. using DictionaryLookup, for example), see this post, where it was used it to implement an efficient Boggle solver.

• Thank you Leonid. I was waiting for other answers to compare but you are too intimidating. :-) Jan 28, 2012 at 23:58
• @Spartacus (Mr.Wizard - sorry, old habits) - I did not mean to. Thanks for the accept. Jan 29, 2012 at 10:25
• Thanks for the update, even it it wasn't specifically for me. Nov 27, 2014 at 16:21
• @Mr.Wizard No problem :). This didn't take any time to check, in any case. I was actually a bit surprised with a speedup, given a small number of rules on every level. Nov 27, 2014 at 16:28
• Now we are talking, it needed to be 3 times faster to deserve my +1, so there you go (kidding, I was surprised to see I hadn't voted before)
– Rojo
Nov 30, 2014 at 5:11

This might not give you the answer you expect, neither is this better than Leonid's solution, but. Since your fairly general question leaves a lot of room for answers and since I felt that it might be relevant, I gave it a go.

Assuming, that we have a list of prefix representations of a string (e.g. from here), it can be plotted easily with TreeForm:

decompTree = {"ar", {"c", {"h", {{"b", {"i", {"s", {{"h", {"o", {"p"}}},
{"ho", {"p"}}}}}}, {"bi", {"s", {{"h", {"o", {"p"}}}, {"ho", {"p"}}}}}}}}};
TreeForm[decompTree, VertexRenderingFunction -> (Style[Text[#2, #1], 14,
Background -> White] &), ImageSize -> 400]


Now let's convert it to a graph. First, assign a unique integer to each leaf:

decompList = Cases[decompTree //. {x__String, y__List} :>
(Join[{x}, #] & /@ {y}), {__String}, \[Infinity]];
vertexRep = Thread[Range@Length@# -> #] &@ Cases[decompTree, _String, \[Infinity]];
counter = 1;
vertexTree = Replace[decompTree, _String :> counter++, \[Infinity]]

{1, {2, {3, {{4, {5, {6, {{7, {8, {9}}}, {10, {11}}}}}}, {12, {13,
{{14, {15, {16}}}, {17, {18}}}}}}}}}


And then building the edge list of the graph by traversing all possible routes with ReplaceRepeated in the (now integer-valued) decomposition tree:

edgeTree = vertexTree //. {{x_Integer, {y_Integer, z___}} :> {x -> y, {y, z}},
{x_Integer, y : {__List}} :> {x -> First@# & /@ y, y}};
edgeList = Cases[edgeTree, _Rule, \[Infinity]];
TreePlot[edgeList, Left, VertexRenderingFunction -> (Style[Text[#2 /. vertexRep, #1], 14,
Background -> White] &), ImageSize -> 400]


• I liked so much the result of your code. Actually, I'd implemented it too. So, I'm trying to decipher line to line your code. ;) Sep 16, 2013 at 16:03
• How can I set an absolute root for the tree? for example, put 'ho' as root of tree or another. Sep 16, 2013 at 16:40
• Thanks @d555, I'm glad that you find it helpful. To root the graph, simply use Graph[edgeList, VertexLabels -> vertexRep, ImagePadding -> 10, GraphLayout -> {"LayeredEmbedding", "RootVertex" -> 10}] (for further details, see this thread). Sep 16, 2013 at 21:29

The Markdown document

(and this blog post) describe the installation and use in Mathematica of Tries with frequencies implemented in Java through a corresponding Mathematica package. Note that the set-up requires some efforts.

## Basic examples

Basic examples can be found in this album of images that shows the "JavaTrie.*" commands with their effects:

More detailed explanations can be found in the Markdown document.

## Performance evaluation (finding dictionary infixes)

The following performance tests are done on a 2015 MacBook Pro. The query timings are almost the same as those of Leonid's implementation; the creation timings are 5-10 times smaller.

Get all words from a dictionary (~93,000):

allWords =  DictionaryLookup["*"];
allWords // Length

(* 92518 *)


Trie creation and shrinking:

AbsoluteTiming[
jDTrie = JavaTrieCreateBySplit[allWords];
jDShTrie = JavaTrieShrink[jDTrie];
]

(* {0.30508, Null} *)


JSON form extraction:

AbsoluteTiming[
jsonRes = JavaTrieToJSON[jDShTrie];
]

(* {3.85955, Null} *)


(The data transfer from Java to Mathematica takes time...)

Here are the node statistics of the original and shrunk tries:

JavaTrieNodeCounts[jDTrie]
(* <|"total" -> 224937, "internal" -> 160090, "leaves" -> 64847|> *)

JavaTrieNodeCounts[jDShTrie]
(* <|"total" -> 115504, "internal" -> 50657, "leaves" -> 64847|> *)


Find the infixes that have more than three characters and appear more than 10 times:

Multicolumn[#, 4] &@
Select[SortBy[
Tally[Cases[
jsonRes, ("key" -> v_) :> v, Infinity]], -#[[-1]] &], StringLength[#[[1]]] > 3 && #[[2]] > 10 &]