5 ms·
For the basic word list, possibly tries (https://en.wikipedia.org/wiki/Trie https://en.wikipedia.org/wiki/Trie), DAGs (https://en.wikipedia.org/wiki/Directed_ac
by Someone 1y ago
For the basic word list, possibly tries (https://en.wikipedia.org/wiki/Trie https://en.wikipedia.org/wiki/Trie), DAGs (https://en.wikipedia.org/wiki/Directed_acyclic_graph#Data_compression https://en.wikipedia.org/wiki/Directed_acyclic_graph#Data_co...), or Bloom filter (https://en.wikipedia.org/wiki/Bloom_filter https://en.wikipedia.org/wiki/Bloom_filter)
- tetraodonpuffer 1y agoaccording to https://en.wikipedia.org/wiki/Ispell https://en.wikipedia.org/wiki/Ispell ispell (1971) already used Levenshtein Distance (although from the article it is not stated if this already existed in the original version, or if it was added in later years).
- Someone 1y agoLevenshtein distance up to 1, according to that article. If you have a hierarchical structure (trie or a DAG; in some sense, a DAG is a trie, but stored more efficiently, with the disadvantage that adding or removing words is hard) with valid words, it is not hard to check what words satisfy that. If you only do the inexact search after looking for the exact word and finding it missing I think it also won’t be too slow when given ‘normal’ text to spell-check.
- bazzargh 1y agoThe limit given in the article is 360KB (on floppy). At that size, you can't use Tries, you need lossy compression. A Bloom filter can get you 1 in 359 false positives with the size of word list given https://hur.st/bloomfilter/?n=234936&p=&m=360KB&k= https://hur.st/bloomfilter/?n=234936&p=&m=360KB&k= The error rate goes up to 1 in 66 for 256KB (in memory only);
- Aurornis 1y agoThe article is about fitting large dictionaries into small memory footprints. Writing a 200K word spell checker on a machine with only 256K memory. When you need to store your dictionary in under 1 byte per word, a trie won't cut it.