[Haskell-cafe] Optimizing spelling correction program

Ketil Malde ketil at malde.org
Mon Jun 22 06:05:51 EDT 2009

Johan Tibell <johan.tibell at gmail.com> writes:

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

Typically you need to examine the (whole) search string in order to
compute the hash function, so I think it is fair to consider them both 

(Sorry about the alphabet confusion, I should of course have made it
clear that I referred to search pattern size, not the data size.)

If I haven't seen further, it is by standing in the footprints of giants

More information about the Haskell-Cafe mailing list