[Haskell-cafe] Optimizing spelling correction program

[Johan Tibell]

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
> 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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20090622/e66fa5ad/attachment.html