Algorithms and Data Structures: Trie (Prefix tree)

https://medium.com/algorithms/trie-prefix-tree-algorithm-ee7ab3fe3413#.ydm9bvqbh

by juliascript • 10 years ago

137 32 10 years ago

It is refreshing to see a data structure "explained" without a drawing of some boxes and arrows. +1 there for the creativity -- I'd be even more pleased to see a data structure explained with words without relying on images at all.

Also:

  ...to check if a word exists in the text file, it takes
  at most, as many operations as the length of the word
  itself. Much better than the 235,887 operations it
  was going to take before.

But your source for the words (/usr/share/dict/words) is probably already sorted! I don't think that's a fair upper bound to quote.

rocqua5• 10 years ago

Still, trie lookup time is independent from your dictionary size. Sadly, in practice they are hurt by the many pointer dereferences of traversing the tree.

If you have a sorted list of strings, you can speed up the search by tracking how many starting characters on the left and right boundary of your interval already match the given word. In practice, this turns out to be almost as good as tries as most steps eliminate quite a few characters to check.

If you like theory, you can add on Range Minimal Query to get the same theoretical performance as tries. In practice though, this isn't necessary.

mbrumlow4• 10 years ago

" that means 235,887 operations for each string that I want to verify as a real word."

/usr/share/dict/words is sorted. A binary search would be much more suitable than iterating over each word, at least for a first run.

And depending on the constraints of the actual problem you are trying to solve a binary search is likely going to be the best well rounded case.

(This mostly depends if memory and disk space constraints are in place).

But I would imagine most spell checkers store their dictionary much differently than that of dict/words

(off to take a look at the aspell source)

kbenson• 10 years ago

But I would imagine most spell checkers store their dictionary much differently than that of dict/words

From my understanding, they often use a Trie (when in memory at least), which I assume is the point of this post. :)

mbrumlow4• 10 years ago

I would argue a trie is not that good compared to a hash. Each letter is going to be a list (which you have to search), or have a fixed sized array pointing to the next letter (could be problematic with languages that use more than a-zA-z).

I just don't want to pretend that its trie or check all 235,887 words every time.

This blog post could have been something much more, had it not stuck with the naive search every word method as the only alternative to a trie.

rocqua5• 10 years ago

Ok, so I did my bachelor thesis on Tries (suffix tries to be exact). So imma run wild

If you get to preproccess, the trie is best. Building the trie takes time and memory that is O(size of dict = k). After that, lookups are O(length of words = n). Meanwhile, binary search is O(n log k) (that factor n their is kinda contentious as generally you will find a mismatch early in the word).

So if the dictonary is really large, or you're doing a shitton of lookups, the trie is better than binary search. Sadly, in practice tries don't work very well with caches. However, there is a very interesting intermediary form based on something called LCP.

LCP stands for longest common prefix. The idea is to prevent rechecking the first part of the word by keeping track how well we matched at the left and right boundaries of our search interval.

There is another magic trick we can use to get this technique up to the level of a trie. This depends on the Range Minimal Querry. A range minimal querry asks, given a range (i, j) and an array A, what is the index of the minimum of A between A[i] and A[j]. It turns out that, with linear preprocessing, we can answer this in constant time. Now, we build an array that, for any 2 adjacent words stores their LCP. Any time we have an interval in our search, we don't go to the middle, but to the RMQ-index of that interval. This way we split our search space more efficiently. In fact each interval in this search method corresponds to a branching node in the trie.

mbrumlow4• 10 years ago

I agree that binary search might not be the best (depending on constraints), my initial complaint was there were faster ways to solve problem stated than searching every word every time.

I personally like the binary tree method for systems that don't or can't load a dictionary in memory. I particularly like it because you can implement a search that requires little memory and does not require you to read the entire file. But I imagine that there are better ways to lay out the data that potentially could get you the best of both worlds.

I can see how a trie would be useful for doing things more than just checking if the word is spelled correctly viz finding list of words that start with a prefix. The question asked was mostly about looking up a word. I posted something on this below before I found your reply. In my post below I am concerned with only checking if the word exist. Are my concerns with regards to the trie valid? Would you agree that hash table would faster than a trie (any kind) for checking if the word exist? Or have I overlooked something?

thaunatos• 10 years ago

What do you think about finite state machines for storing strings? (http://blog.burntsushi.net/transducers/)

It doesn't support adding words at run-time, but it seems to have attractive space usage.

dukoid• 10 years ago

"I wrote the simplest version of a trie, using nested dictionaries." (⊙_◎)

nuggien• 10 years ago

What's wrong with this? What would be the alternative? A preallocated array of 26 (or more if you account for special chars) for each node?

Jach• 10 years ago

I recently wrote a basic trie in Nim for fun, I started with a preallocated array and then rewrote parts to hashtables, it's simpler since you don't need to care about the dictionary size and it can have space savings depending on how the table grows. It wouldn't surprise me if there was a fancy bitmapping approach though, or if you could be more efficient if you had n-gram statistics. (And as mentioned elsewhere for the purposes of storing/searching a dictionary you could just have a flat hashtable indexed by the words, or a bloom filter if you only care about certainly not existing...)

alexchamberlain• 10 years ago

I wonder if the op compared the performance of this vs "word in set(words)"; tries are very interesting data structures mind.

foobarian• 10 years ago

The problem with anagrams is you'd have to test all permutations of a word, which is n! hash lookups. Alternately you could store all prefixes in the set and prune the permutations that way. Slightly more interesting than word in set(words).

bluefox2• 10 years ago

If I understand the task correctly, it is to map a word into another word that belongs to the set of words that have the same letter frequency distribution.

So a possible solution is to define a representation for a letter frequency distribution, and use an associative data type for the mapping.

Since the problem does not concern itself with prefixes, there is no need for a prefix tree - in Python, a simple dict would do.

A few words about style: when you write code, you have to come up with names for variables, functions, and other things. In this case, it seems you just went ahead and wrote down the first thing that came to mind, which is sometimes verbose because you're still in problem exploration mode and things are not clear. It's OK to do that, but please consider re-naming later on, so that instead of a first-thing-I-thought-of name, you'll have a name that gives the reader a sense of clarity. The process of doing that usually leads to better understanding of the problem and perhaps better code. With experience, you'll find that the need to re-name is reduced.

As a rule of thumb, the length of the name should correlate with the its scope. Names with indefinite scope tend to be long, while names with limited scopes tend to be shorter.

Finally, I encourage you to write more posts, and hope my critique is helpful.

jedimastert• 10 years ago

So a possible solution is to define a representation for a letter frequency distribution, and use an associative data type for the mapping.

out of curiosity, could one such representation just be all of the letters in the word, sorted? I wonder how the time-complexities would compare. I assume a trie would still be faster.

bluefox2• 10 years ago

Yes. Another simple representation if you assume a maximum number of occurrences per letter:

  (defvar *alphabet* "abcdefghijklmnopqrstuvwxyz")
  
  (defconstant capacity-in-bits 3)
  
  (defun key (word)
    (loop with key = 0
          with max-occurrences = (1- (ash 1 capacity-in-bits))
          for letter across *alphabet*
          for i upfrom 0
          for occurrences = (count letter word)
          do (if (> occurrences max-occurrences)
                 (error "too many occurrences")
                 (setf (ldb (byte capacity-in-bits (* i capacity-in-bits)) key)
                       occurrences))
          finally (return key)))

kornish• 10 years ago

It could be. Here's a python implementation:

  from collections import Counter
  
  freq_to_words = {}
  make_freq = lambda word: tuple(sorted(dict(Counter(word)).items()))
  
  with open('/usr/share/dict/words', 'r') as f:
      for line in f.read().split('\n'):
          freq = make_freq(line)
          if freq not in freq_to_words:
              freq_to_words[freq] = []
          freq_to_words[freq].append(line)
  
  print freq_to_words[make_freq('gas')] # ['gas', 'sag']

For time complexities, this requires O(n) preprocessing but can do O(1) lookups, since it's a hash structure.

ttub• 10 years ago

This problem also has an "infamous" and very simpe, elegant solution described in Programming Pearls:

"The idea is to give words that are anagrams a common signature, sort all the words together by their signatures, and then print them."

https://www.gnu.org/software/gawk/manual/html_node/Anagram-P...

thr0waway1239• 10 years ago

Since the problem does not concern itself with prefixes, there is no need for a prefix tree

This is a very important point, and many others in this thread have missed the fundamental point with using a trie. A real world example would immediately showcase its benefit.

In the old feature phones, you needed to punch the number keys many times to get a letter. Some people improved this using something called predictive typing - which basically goes like this:

1. Each number can be mapped to one of 3-4 possible letters 2. Based on the current sequence of numbers typed in (i.e. the prefix up to this point), this can mean 0 or more words which are in the dictionary. 3. Using a trie data structure, you basically have a few possible leaf nodes (only dictionary words can be leaf nodes in the predictive typing scenario) which all map to the current sequence of numbers. 4. Hence you will notice one or more options from which you can select based on the number sequence you typed, thus saving you many keystrokes

You can present the different options sorted by word frequency etc. if there are multiple matching leaf nodes for the given prefix.

When the prefix scenario does not matter - as in OP's article, from what I remember the trie gives no benefit over a simple sorted dictionary.

kristianp• 10 years ago

I'm not familiar with Python, but would a C extension be the best way to implement a data structure like this, that requires high performance? Or is it possible to write efficient enough code in Python?

erubin• 10 years ago

When algorithms matter, you do get a lot of performance out of a better algorithm. But I actually recently wrote an admittedly not production ready trie extension in C and it was about five lines of SWIG to use it from python.

Fragguccino• 10 years ago

Not everyday I get to share this! I wrote some code in Go that uses a trie to quickly find anagrams. My trick is that I load the trie with a dictionary, but before I insert each word, I sort it alphabetically (ex: sort -> orst). Before I lookup a word I sort it alphabetically, so when I locate it in the trie, I also get all the other words that share the same characters. Because of the nature of the data structure, I can also quickly find all the smaller anagrams which will be handy when I get around to turning this into a full fledged scrabble playing AI: https://github.com/RyanEdwardHall/anagrambler

rukuu001• 10 years ago

I've implemented a trie exactly once in my 15 years of professional programming, and I'm so happy I knew about tries when the time finally came :)

Edit: swapped used with implemented

dugmartin• 10 years ago

John Resig wrote up a nice analysis of tries using Javascript five years ago. It is well worth the read: http://ejohn.org/blog/javascript-trie-performance-analysis/

blt• 10 years ago

The coolest use of Tries I've ever seen is the Apriori algorithm. It exploits the trie properties and the structure of the query sequence in a really clever way. It's beautiful.

aidenn0• 10 years ago

One might note that properly implemented hash tables also have O(k) lookup times. And in fact, much of the time well-tuned hash tables outperform well-tuned tries.

Tries still have some advantages though:

1) The naive implementation of a trie of using an alphabet-sized vector for the child nodes is much closer to the ideal performance than the naive implementation of a hash table. If I had to implement a dictionary on short notice, I would use a trie.

2) Tries preserve ordering, while still allowing O(1) [in the number of items in the dictionary] insert, removal and lookup. If you need to get the key that is lexicographically next or previous, to another key, or you need to find the two keys that bound a particular value, it's a great structure to use. Comparison based trees can also do this but not with constant time insert and remove.

For a really space-efficient trie-like structure, see crit-bit trees[1] which are basically a space-efficient radix tree with on a binary alphabet (so each internal node has a fanout of exactly 2).

1: https://cr.yp.to/critbit.html

elcct• 10 years ago

I wish medium was more developer friendly. Articles about programming on that platform are unreadable for me.

Algorithms and Data Structures: Trie (Prefix tree)

Related Stories