Winnowing
A Python implementation of the Winnowing (local algorithms for document fingerprinting)
Original Work
The original research paper can be found at http://dl.acm.org/citation.cfm?id=872770.
Usage
>>> winnow('A do run run run, a do run run')
set([(5, 23942), (14, 2887), (2, 1966), (9, 23942), (20, 1966)])
>>> winnow('run run')
set([(0, 23942)]) # match found!
Default Hash Function
Quite honestly, I did not know what hash function to use. The paper did not talk about it. So I decided to use a part of SHA-1; more precisely, the last 16 bits of the digest.
Custom Hash Function
You may use your own hash function as demonstrated below.
def hash_md5(text):
import hashlib
hs = hashlib.md5(text)
hs = hs.hexdigest()
hs = int(hs, 16)
return hs
# Override the hash function
winnow.hash_function = hash_md5
winnow('The cake was a lie')
Lower Bound of Fingerprint Density
(TODO: Write this section)