When do we actually use a Trie?

I am starting to read about Trie. I got also references from friends here in: Tutorials on Trie

I am not clear on the following:
It seems that to go on and use a Trie one assumes that all the input strings that will be the search space and used to build the Trie are separated in distinct word boundaries.
E.g. all the example tutorials I have seen use input such as:

S={ball, bid, byte, car, cat, mac, map etc...}

Then we build the trie from S and do our searches (really fast)
My question is: How did we end up with S to begin with?
I mean before starting to read about tries I imagined that S would be an arbitrarily long text e.g. A Shakespeare passage.

Then using a Trie we could find things really fast.
But it seems this is not the case.

Is the assumption here that the input passage (of Shakespeare for example) is pre-processed first extracting all the words to get S?

So if one wants to search for patterns (same way as you do when you Google and see all pages having also spaces in your search query) a Trie is not appropriate?
When can we know if a Trie is the data structure that we can actually use?

Edit Report

1 Answer

There are multiple ways to use tries. The typical example is a lookup such as the one you have presented. However Tries can also be used to fully index a complete text. Either you use the Ukkonen suffix tree algorithm, to produce a suffix trie, or you explicetly construct the suffix trie by storing suffixes (much slower than Ukkonens algorithm, but also much simpler). As this is preprocessing, which needs to be done only once speed is not that crucial.

For this you would just take your text, insert the full text, then chop of the first letter, insert the resulting text, chop of second letter, insert...

So if we have the text "The Text" we would insert the following set:

{"The Text", "he Text", "e Text", " Text", "Text", "ext", "xt", "t"}

In the resulting suffix trie we can easily search for any kind of prefix. Also this is space efficient, because we do not need to store the whole string, since common prefixes are stored only once.

If you need to store much longer strings space efficiently it is best not only to store prefixes together but also suffixes. In that case you could build up a directed acyclic word graph (DAWG), which is very similar to a trie in conception.

So a trie in that sense allows finding arbitrary substrings, including partial words. If you are only interested in storing words, a different data structure should be used, for example a inverted list (if order is important) or a vector space based retrieval algorithm (in case word order does not matter).

answered 2012-05-22T12:45:28.520

When do we actually use a Trie?

1 Answer

Your Answer