Hacker News Reader

Comment by clarkmoody | Hacker News Reader

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?

View on HN

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

Thanks for the link!

I guess he did say that in the article, but "trie" wasn't part of my algorithmic vocabulary...until now.

Multiple software engineers independently arriving at the same obvious solution? Sounds like something somebody would try to patent today...

Thankfully many of the novel solutions that were created in the early days weren't created by people that just wanted a buck.

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

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://www.pathcom.com/~vadco/cwg.html (a highly compressed DAWG derivative)

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

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/

I also tried to compress "/usr/share/dict/words" with https://github.com/kmike/DAWG and 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.

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

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

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.

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

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.

Reply on news.ycombinator.com