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: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] 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@haskell.org | http://www.haskell.org/mailman/listinfo/haskell _______________________________________________ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
