Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

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?

share|improve this question
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
Strange I don't remember this question at all... Admit that moderators above 10K are allowed to use SE time machines. Also, I wonder whether a tree or tree-graph tag would be useful, as it would covere some questions like this, would fit nicely between list-manipulation and graphs-and-networks (though being a subset of the latter) and (as my major reason) would have helped me to find this post earlier. –  István Zachar Mar 26 '12 at 12:39
@István add tags as you see fit. –  Mr.Wizard Mar 27 '12 at 3:43

2 Answers 2

up vote 25 down vote accepted

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

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]]

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

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

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

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,

In[41]:= tree = makeTree[words]
Out[41]= {a->{b->{s->{c->{e->{s->{s->{{}->{},e->{d->{{}->{}},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,

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

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.


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.

share|improve this answer
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

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]

Mathematica graphics

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]

Mathematica graphics

share|improve this answer
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. ;) –  d555 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. –  d555 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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.