5 ms·

" 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 suit

" 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.
- 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?

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.

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?