4 ms·

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 search

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.
  - rocqua 10y ago
    I missed the point (as others have said) that a Trie will take less memory as it stores common prefixes only once. As for early mismatch detection, the statistics of that elude me at the moment. Certainly, early detection decreases as you get more words. However, as you get more words, you probably get longer words (lest you run out of space) so that makes early detection more valuable.

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.
- rocqua 10y ago
  I missed the point (as others have said) that a Trie will take less memory as it stores common prefixes only once. As for early mismatch detection, the statistics of that elude me at the moment. Certainly, early detection decreases as you get more words. However, as you get more words, you probably get longer words (lest you run out of space) so that makes early detection more valuable.