[Haskell-cafe] Optimizing spelling correction program
johan.tibell at gmail.com
Mon Jun 22 05:00:36 EDT 2009
On Mon, Jun 22, 2009 at 10:10 AM, Ketil Malde <ketil at malde.org> wrote:
> Kamil Dworakowski <kamil at dworakowski.name> 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
> > gets changed. This program creates a dictionary at start which then is
> > being used to read from: an ideal application for the Data.PerfectHash
> > by Mark Wotton available on Hackage .
> 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"
Typo? Bloom filters have O(1) lookup and tries O(m) lookup where m is the
number of characters in the string.
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Haskell-Cafe