[Haskell] Fingerprints and hashing

Lauri Alanko la at iki.fi
Thu Oct 11 06:27:16 EDT 2007

If compositionality is important, at least Rabin's fingerprints are
worth considering: http://citeseer.ist.psu.edu/broder93some.html

They have the neat property that the fingerprint of a concatenation of
strings can be cheaply computed from the fingerprints of the
constituents. I think this effectively means that the plusFP operation
can be made associative, which might offer optimization opportunities.

I remember implementing it some seven years ago when prototyping for a
C implementation. The code is lost, though. I can give it a shot
again, if this is considered a reasonable algorithm.


More information about the Haskell mailing list