3 ms·
> 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
by 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 agoI 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