# 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! :) – István Zachar Mar 26 '12 at 8:06
@István no, look at the date on this. It is not clear to me how this structure would be used to solve that problem, though it does appear related. (back to lurking now...) – Mr.Wizard Mar 26 '12 at 11:32
@István well, it seems that it's clear to you. I'll read your answer in detail tomorrow. :-) – Mr.Wizard Mar 26 '12 at 11:33
@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. – Leonid Shifrin Nov 27 '14 at 16:12
@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. – Leonid Shifrin Nov 28 '14 at 18:08

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. :-) – Mr.Wizard Jan 28 '12 at 23:58
@Spartacus (Mr.Wizard - sorry, old habits) - I did not mean to. Thanks for the accept. – Leonid Shifrin Jan 29 '12 at 10:25
Thanks for the update, even it it wasn't specifically for me. – Mr.Wizard Nov 27 '14 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. – Leonid Shifrin Nov 27 '14 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 '14 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. ;) – jonaprieto Sep 16 '13 at 16:03
How can I set an absolute root for the tree? for example, put 'ho' as root of tree or another. – jonaprieto Sep 16 '13 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). – István Zachar Sep 16 '13 at 21:29