5 ms·

Algorithms and Data Structures: Trie (Prefix tree)

137 points by juliascript 10y ago

no_protocol 10y 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.
- rocqua 10y 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.
mbrumlow 10y 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 10y 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. :)
  - mbrumlow 10y 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.
    - pjscott 10y ago
      > I would argue a trie is not that good compared to a hash. It can be more memory efficient than a hash table if there are enough shared prefixes, and it supports prefix and range queries. As always, different data structures have different tradeoffs. > 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). A common maneuver here is to encode strings as byte sequences in UTF-8 (or some such encoding), use 256-element arrays for nodes with enough children that the linear search would be inefficient, and possibly to use hash tables for nodes that are somewhere in the middle. See here for more discussion: https://en.wikipedia.org/wiki/HAT-trie https://en.wikipedia.org/wiki/HAT-trie
- rocqua 10y 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.
dukoid 10y ago
"I wrote the simplest version of a trie, using nested dictionaries." (⊙_◎)
- nuggien 10y 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 10y 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 10y ago
I wonder if the op compared the performance of this vs "word in set(words)"; tries are very interesting data structures mind.
- foobarian 10y 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).
bluefox 10y 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 10y 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.
  - bluefox 10y 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)))
kristianp 10y 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 10y 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 10y 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 https://github.com/RyanEdwardHall/anagrambler
rukuu001 10y 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 10y 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/ http://ejohn.org/blog/javascript-trie-performance-analysis/
blt 10y 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 10y 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 https://cr.yp.to/critbit.html
elcct 10y ago
I wish medium was more developer friendly. Articles about programming on that platform are unreadable for me.

137 points by juliascript 10y 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.

rocqua 10y 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.

mbrumlow 10y 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 10y 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. :)
- mbrumlow 10y 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.
  - pjscott 10y ago
    > I would argue a trie is not that good compared to a hash. It can be more memory efficient than a hash table if there are enough shared prefixes, and it supports prefix and range queries. As always, different data structures have different tradeoffs. > 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). A common maneuver here is to encode strings as byte sequences in UTF-8 (or some such encoding), use 256-element arrays for nodes with enough children that the linear search would be inefficient, and possibly to use hash tables for nodes that are somewhere in the middle. See here for more discussion: https://en.wikipedia.org/wiki/HAT-trie https://en.wikipedia.org/wiki/HAT-trie
rocqua 10y 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.

dukoid 10y ago

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

nuggien 10y 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 10y 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 10y ago

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

foobarian 10y 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).

bluefox 10y 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 10y 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.
- bluefox 10y 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)))

kristianp 10y 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 10y 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 10y 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 https://github.com/RyanEdwardHall/anagrambler

rukuu001 10y 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 10y 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/ http://ejohn.org/blog/javascript-trie-performance-analysis/

blt 10y 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 10y 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 https://cr.yp.to/critbit.html

elcct 10y ago

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