4 ms·

I would like to know some of the details of the algorithmic tricks that were employed to solve this problem. As I was reading, I was thinking of a tree structur

I would like to know some of the details of the algorithmic tricks that were employed to solve this problem. As I was reading, I was thinking of a tree structure encoding the dictionary with each letter (of a valid word) being a node. If the next letter isn't found, or if you reach a leaf with letters left in the candidate word, then you've misspelled something. Does anyone have an idea of how much compression could be achieved through such a structure?

henrik_w 14y ago
You're describing a trie, http://en.wikipedia.org/wiki/Trie http://en.wikipedia.org/wiki/Trie
- clarkmoody 14y ago
  Thanks for the link! I guess he did say that in the article, but "trie" wasn't part of my algorithmic vocabulary...until now.
- joshuahedlund 14y ago
  Multiple software engineers independently arriving at the same obvious solution? Sounds like something somebody would try to patent today...
  - sukuriant 14y ago
    Thankfully many of the novel solutions that were created in the early days weren't created by people that just wanted a buck.
dpritchett 14y ago
It's not quite the same thing but this problem strongly reminded me of Chapter 1 of Programming Pearls: http://www.cs.bell-labs.com/cm/cs/pearls/cto.html http://www.cs.bell-labs.com/cm/cs/pearls/cto.html
mratzloff 14y ago
Good guess! That's the trie that he mentions. I would have also approached it that way.
chipsy 14y ago
Tries for dictionaries are the simplest method. However, it limits the search method to forward-only. For more sophisticated dictionary searches there is DAWG: http://en.wikipedia.org/wiki/Directed_acyclic_word_graph http://en.wikipedia.org/wiki/Directed_acyclic_word_graph http://www.pathcom.com/~vadco/cwg.html http://www.pathcom.com/~vadco/cwg.html (a highly compressed DAWG derivative)
- kmike84 14y ago
  Does DAWG really provide more sophisticated searches than a trie being basically a minimized automata for the trie?
hythloday 14y ago
Given the set of valid words in a document is (by definition) a subset of the words in the dictionary, I'd imagine you're better off holding the document in memory, building a datastructure from that and then looking through the disk for the set of words in the document that weren't found in the dictionary.
Encosia 14y ago
Taking that to the next level, you can improve that data structure to allow sharing between later similarities in words after they've diverged from their common prefixes. That's particularly helpful to cut down on redundant storage of suffixes like -ing, -ed, -ly, etc. The directed acyclic word graph (DAWG) is a popular approach to that: http://en.wikipedia.org/wiki/Directed_acyclic_word_graph http://en.wikipedia.org/wiki/Directed_acyclic_word_graph
pmb 14y ago
It is called a Trie or a Prefix Tree, and has been (re)invented many times.
kmike84 14y ago
The compression of a trie may not be the best because of the node storage requirement. I've benchmarked the memory usage of some Python trie libraries here: http://kmike.ru/python-data-structures/ http://kmike.ru/python-data-structures/ I also tried to compress "/usr/share/dict/words" with https://github.com/kmike/DAWG https://github.com/kmike/DAWG and https://github.com/kmike/marisa-trie https://github.com/kmike/marisa-trie Python libraries: import dawg import marisa_trie words = open('/usr/share/dict/words', 'r').read().splitlines() dawg.DAWG(words).save('words.dawg') marisa_trie.Trie(words).save('words.trie') The result is a bit surprising: 1220612 words.dawg 743128 words.trie Please note that MARISA-trie is not a classic trie, it is a smart & crazy recursive trie (something like DAWG-Trie hybrid). By the way, I was expecting DAWG to perform much better; for my data (5mln Russian words) the DAWG compression was much more impressive.
lurker14 14y ago
That's optimal for 100% accuracy. You can get much lower memory usage using Bloom filters (basically, hashing words into a small range of hashcodes, expecting collisions, and storing a mask of all the hashcodes that correspond to words), at the expense of false positives. (thinking a mispelled word is correct.) This was a common solution in the 80s.

henrik_w 14y ago

You're describing a trie, http://en.wikipedia.org/wiki/Trie http://en.wikipedia.org/wiki/Trie

clarkmoody 14y ago
Thanks for the link! I guess he did say that in the article, but "trie" wasn't part of my algorithmic vocabulary...until now.
joshuahedlund 14y ago
Multiple software engineers independently arriving at the same obvious solution? Sounds like something somebody would try to patent today...
- sukuriant 14y ago
  Thankfully many of the novel solutions that were created in the early days weren't created by people that just wanted a buck.

dpritchett 14y ago

It's not quite the same thing but this problem strongly reminded me of Chapter 1 of Programming Pearls: http://www.cs.bell-labs.com/cm/cs/pearls/cto.html http://www.cs.bell-labs.com/cm/cs/pearls/cto.html

mratzloff 14y ago

Good guess! That's the trie that he mentions. I would have also approached it that way.

chipsy 14y ago

Tries for dictionaries are the simplest method. However, it limits the search method to forward-only. For more sophisticated dictionary searches there is DAWG: http://en.wikipedia.org/wiki/Directed_acyclic_word_graph http://en.wikipedia.org/wiki/Directed_acyclic_word_graph http://www.pathcom.com/~vadco/cwg.html http://www.pathcom.com/~vadco/cwg.html (a highly compressed DAWG derivative)

kmike84 14y ago
Does DAWG really provide more sophisticated searches than a trie being basically a minimized automata for the trie?

hythloday 14y ago

Given the set of valid words in a document is (by definition) a subset of the words in the dictionary, I'd imagine you're better off holding the document in memory, building a datastructure from that and then looking through the disk for the set of words in the document that weren't found in the dictionary.

Encosia 14y ago

Taking that to the next level, you can improve that data structure to allow sharing between later similarities in words after they've diverged from their common prefixes. That's particularly helpful to cut down on redundant storage of suffixes like -ing, -ed, -ly, etc. The directed acyclic word graph (DAWG) is a popular approach to that: http://en.wikipedia.org/wiki/Directed_acyclic_word_graph http://en.wikipedia.org/wiki/Directed_acyclic_word_graph

pmb 14y ago

It is called a Trie or a Prefix Tree, and has been (re)invented many times.

kmike84 14y ago

The compression of a trie may not be the best because of the node storage requirement. I've benchmarked the memory usage of some Python trie libraries here: http://kmike.ru/python-data-structures/ http://kmike.ru/python-data-structures/ I also tried to compress "/usr/share/dict/words" with https://github.com/kmike/DAWG https://github.com/kmike/DAWG and https://github.com/kmike/marisa-trie https://github.com/kmike/marisa-trie Python libraries: import dawg import marisa_trie words = open('/usr/share/dict/words', 'r').read().splitlines() dawg.DAWG(words).save('words.dawg') marisa_trie.Trie(words).save('words.trie') The result is a bit surprising: 1220612 words.dawg 743128 words.trie Please note that MARISA-trie is not a classic trie, it is a smart & crazy recursive trie (something like DAWG-Trie hybrid). By the way, I was expecting DAWG to perform much better; for my data (5mln Russian words) the DAWG compression was much more impressive.

lurker14 14y ago

That's optimal for 100% accuracy. You can get much lower memory usage using Bloom filters (basically, hashing words into a small range of hashcodes, expecting collisions, and storing a mask of all the hashcodes that correspond to words), at the expense of false positives. (thinking a mispelled word is correct.) This was a common solution in the 80s.