[Haskell] Fingerprints and hashing

[Simon Peyton-Jones]

Interesting! The associativity property is the kind of thing I was after.  Except that I don't really care if FP(as ++ bs) = FP(as) `plusFP` FP(bs).  I only care that the latter is robust in the sense of having low probabilty of collision.  So the Rabin scheme does more than I really need (which is probably fine).

On page 1 he draws a distinction between fingerprinting and hashing, which relates to my last wish.  Does one need a different technique for the two, or is it enough to reduce the number of bits in the Rabin scheme, and thereby get a hashing scheme?

Strangely the paper gives no comparison with other fingerprinting schemes.

Simon

| -----Original Message-----
| From: haskell-bounces at haskell.org [mailto:haskell-bounces at haskell.org] On Behalf Of Lauri Alanko
| Sent: 11 October 2007 11:27
| To: haskell
| Subject: Re: [Haskell] Fingerprints and hashing
|
| 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.
|
|
| Lauri
| _______________________________________________
| Haskell mailing list
| Haskell at haskell.org
| http://www.haskell.org/mailman/listinfo/haskell