5 ms·

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

by 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.

mbrumlow 10y 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?
- rocqua 10y ago
  Comparing a hash-table to a trie is difficult in practice. Theoretically, they are equally fast. Both take O(length of word) time. You could give an advantage to the trie because it allows for early failure detection, whilst the hash table requires processing the full word. In practice though, for short words (e.g. < block size of the hash) the hash might effectively be constant time. Finally, cache behavior is going to really matter tries require a pointer dereference for each character (you can mitigate this someone by storing non-branching paths along the trie better). Such dereferences tend to really wreck a cache. So in the end, it's better cache behaviour for the hash table vs early stopping for the trie. Cache misses are so expensive, I'd guess the hash table wins in most situations, but that is really a guess.
  - mbrumlow 10y ago
    I see your point about early detection. While a trie will have precise early failure detection a hash will have 2 ways to fail early. One would be the hash is simply not found. But at that point you had to at least look at the entire input word, compute the hash and check for the hash. I have not done any actual analysis on this but just for thought let us look at the hypothetical case that words would fail near halfway through the testing process. In a hash we would have needed to at least read the full word while in a trie comparison of at least half the word with half the letters in the trie path would have needed to be processed. So conceptually (at least in my head) both the hash and trie would need to have done something with about the same number of letters. The question there is is computing and checking the hash more efficient than traversing the trie. The second way the hash would fail early is when we have a hash match and comparing the resulting words the hash entry held. Now if the collision rate was low then we might only have to check one word, if it is high then many words. So I would hope the hash was tuned for a low collision rate. But when comparing two words there is also early detection (this is the point I was getting at). The entire word does not need to be compared, it would likely be compared word at a time (word as in 4 or 8 bytes at a time). If I have time this weekend I think I want to implement both of these to benchmark. All that being said, the more I think about it I think a trie would be the best for a spell checker in general. Simply checking if this is a word or not is nice, but what is nicer is the ability to suggest alternatives to the misspelled word and a trie would be mucher nicer to work with with building that list.
thaunatos 10y ago
What do you think about finite state machines for storing strings? (http://blog.burntsushi.net/transducers/ http://blog.burntsushi.net/transducers/) It doesn't support adding words at run-time, but it seems to have attractive space usage.
- rocqua 10y ago
  If I recall correctly, that is kind of like a compressed trie, only instead of a tree one builds a directed acyclic graph. Basically, taking common suffixes into account aswell. Space usage is indeed the biggest advantage, as you are reducing redundant branches from the tree for of a trie. Construction of these seems difficult (from the article, it seems to involve building the tree, and using hashes to find redundant branches. I think I never gave them much thought because it doesn't work for suffix tries, which can be used not to search for prefixes (like a normal trie) but for substrings (considering them prefixes of suffixes). The optimalization to get the O(n^2) total length of all suffixes seem to make it hard to turn this into a DAG.

by rocqua 10y ago

mbrumlow 10y 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?

rocqua 10y ago
Comparing a hash-table to a trie is difficult in practice. Theoretically, they are equally fast. Both take O(length of word) time. You could give an advantage to the trie because it allows for early failure detection, whilst the hash table requires processing the full word. In practice though, for short words (e.g. < block size of the hash) the hash might effectively be constant time. Finally, cache behavior is going to really matter tries require a pointer dereference for each character (you can mitigate this someone by storing non-branching paths along the trie better). Such dereferences tend to really wreck a cache. So in the end, it's better cache behaviour for the hash table vs early stopping for the trie. Cache misses are so expensive, I'd guess the hash table wins in most situations, but that is really a guess.
- mbrumlow 10y ago
  I see your point about early detection. While a trie will have precise early failure detection a hash will have 2 ways to fail early. One would be the hash is simply not found. But at that point you had to at least look at the entire input word, compute the hash and check for the hash. I have not done any actual analysis on this but just for thought let us look at the hypothetical case that words would fail near halfway through the testing process. In a hash we would have needed to at least read the full word while in a trie comparison of at least half the word with half the letters in the trie path would have needed to be processed. So conceptually (at least in my head) both the hash and trie would need to have done something with about the same number of letters. The question there is is computing and checking the hash more efficient than traversing the trie. The second way the hash would fail early is when we have a hash match and comparing the resulting words the hash entry held. Now if the collision rate was low then we might only have to check one word, if it is high then many words. So I would hope the hash was tuned for a low collision rate. But when comparing two words there is also early detection (this is the point I was getting at). The entire word does not need to be compared, it would likely be compared word at a time (word as in 4 or 8 bytes at a time). If I have time this weekend I think I want to implement both of these to benchmark. All that being said, the more I think about it I think a trie would be the best for a spell checker in general. Simply checking if this is a word or not is nice, but what is nicer is the ability to suggest alternatives to the misspelled word and a trie would be mucher nicer to work with with building that list.

thaunatos 10y ago

What do you think about finite state machines for storing strings? (http://blog.burntsushi.net/transducers/ http://blog.burntsushi.net/transducers/) It doesn't support adding words at run-time, but it seems to have attractive space usage.

rocqua 10y ago
If I recall correctly, that is kind of like a compressed trie, only instead of a tree one builds a directed acyclic graph. Basically, taking common suffixes into account aswell. Space usage is indeed the biggest advantage, as you are reducing redundant branches from the tree for of a trie. Construction of these seems difficult (from the article, it seems to involve building the tree, and using hashes to find redundant branches. I think I never gave them much thought because it doesn't work for suffix tries, which can be used not to search for prefixes (like a normal trie) but for substrings (considering them prefixes of suffixes). The optimalization to get the O(n^2) total length of all suffixes seem to make it hard to turn this into a DAG.