Re: [Haskell-cafe] Optimizing spelling correction program

On Mon, Jun 22, 2009 at 10:10 AM, Ketil Malde wrote:

Kamil Dworakowski writes:

...

Right... Python uses hashtables while here I have a tree with log n access time. I did not want to use the Data.HashTable, it would pervade my program with IO. The alternative is an ideal hashmap that never gets changed. This program creates a dictionary at start which then is only being used to read from: an ideal application for the Data.PerfectHash by Mark Wotton available on Hackage [3].

If you are considering alternative data structures, you might want to look at tries or Bloom filters, both have O(n) lookup, both have Haskell implementations. The latter is probably faster but probabilistic (i.e. it will occasionally fail to detect a misspelling - which you can of course check against a "real" dictionary).

Typo? Bloom filters have O(1) lookup and tries O(m) lookup where m is the number of characters in the string. Cheers, Johan