Content deleted Content added
Added whiney complaint about style. |
Chmduquesne (talk | contribs) |
||
Line 187:
Also, adding a comma as the thousands separator to decimal values seems strange in the context of a computer science example. My first thought when seeing these numbers was, "Where did these tuple values come from? Did I miss something?" You don't expect this kind of formatting when reading about algorithms... Not to mention that it's not localized. What if my locale uses '.' for the thousands divider? Why make it messy and confusing? It's not as if keeping track of the thousands position is important to understanding the algorithm. This isn't a financial spreadsheet. --[[Special:Contributions/50.0.241.18|50.0.241.18]] ([[User talk:50.0.241.18|talk]]) 19:34, 22 February 2016 (UTC)
== The hash function used is wrongly referred to as a Rabin Fingerprint ==
Although the hash function described is indeed a rolling hash, this is NOT the original Rabin fingerprint. A Rabin fingerprint is the result of a modulo operation (rest of a division) of the hashed string, taken as a sequence of bits (not bytes), and interpreted as a polynomial over GF(2), by another polynomial irreducible over GF(2). This is NOT equivalent to a modulo operation with an actual prime number. Multiplications and Additions of polynomials over GF(2) do NOT equate to multiplications and additions over n-bits integers, mainly because there is no carry. See https://en.wikipedia.org/wiki/Rabin_fingerprint for a more detailed explanation. It contains a link to the original paper. The coefficients of the polynomial are the bits, not the bytes (this is not a typo).
Note that the pdf linked as a reference does NOT actually refer to the fingerprint function being used as a Rabin fingerprint, so it is correct. The Rabin Karp algorithm does not require using the Rabin Fingerprint, but any rolling hash will work.
| |||