[Haskell] Fingerprints and hashing
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