Method for document fingerprinting
View Patent ↗Methods and computer program products for creating sketches of a document, which are compared with sketches of other documents, in order to determine the documents' degree of similarity. A sketch is a digest of information from random locations within a document. A document is divided into a set of shingles. Each shingle is converted into a set of fingerprints. A sketch is determined based on one bit fingerprints thus created. In order to create additional sketches of the document, a new set of fingerprints are created by randomization techniques.
1. A method for creating one or more sketches of a document, the document comprising one or more tokens, the one or more tokens being used to create one or more shingles, the one or more sketches of the document being created to determine the similarity of the document with other documents, the method comprising the steps of:
a) converting the one or more shingles to a first set of integers;
b) generating a second set of integers by using the first set of integers;
c) selecting one or more integers from the second set of integers;
d) creating a sketch based on the 32 nd bit of each of the one or more integers;
e) repeating steps b, c, d, and e for creating additional sketches of the document, wherein the first set of integers is replaced with the second set of integers; and
f) storing the sketch and the additional sketches;
wherein the stored sketch and the additional sketches are used to compare the similarity of the document with other documents, and wherein the steps of the method are performed by a microprocessor.
2. The method of claim 1 , wherein the step of converting the one or more shingles to a first set of integers comprises the step of hashing each of the one or more shingles to an integer.
3. The method of claim 1 , wherein the step of converting the one or more shingles to a first set of integers comprises the step of computing a 64-bit Rabin hash of each of the one or more shingles.
4. The method of claim 1 , wherein the second set of integers is generated by using a random number generator seeded with the first set of integers.
5. The method of claim 1 , wherein the step of selecting one or more integers from the second set of integers comprises the step of identifying the one or more smallest integers.
6. A computer program product for use with a stored program computer, the computer program product comprising a computer storage medium having a computer readable program code embodied therein for creating one or more sketches of a document, the document comprising one or more tokens, the one or more tokens being used to create one or more shingles, the one or more sketches of the document being created to determine the similarity of the document with other documents, the computer readable program code performing the steps of:
a) converting the one or more shingles to a first set of integers;
b) generating a second set of integers by using the first set of integers;
c) selecting one or more integers from the second set of integers;
d) creating a sketch based on 32 nd bit of each of the one or more integers;
e) repeating steps b, c, d, and e for creating additional sketches of the document, wherein the first set of integers is replaced with the second set of integers; and
f) storing the sketch and the additional sketches;
wherein the stored sketch and the additional sketches are used to compare the similarity of the document with other documents, and wherein the computer program product interacts with a microprocessor for executing the computer readable program code.
7. The computer program product of claim 6 , wherein the computer readable program code performing the step of converting the one or more shingles to a first set of integers further comprises the computer readable program code performing the step of hashing each of the one or more shingles to an integer.
8. The computer program product of claim 6 , wherein the computer readable program code performing the step of converting the one or more shingles to a first set of integers further comprises the computer readable program code performing the step of computing a 64 bit Rabin hash of each of the one or more shingles.
9. The computer readable program product of claim 6 , wherein the computer readable program code performing the step of generating a second set of integers using the first set of integers further comprises the computer readable program code performing the step of generating the second set of integers by using a random number generator seeded with the first set of integers.
10. The computer program product of claim 6 , wherein the computer readable program code performing the step of selecting one or more integers from the second set of integers further comprises the computer readable program code performing the step of identifying the one or more smallest integers.
11. The method of claim 1 , wherein the sketches are created from one bit fingerprints.
12. The method of claim 1 , wherein the document is at least one of a text file, an image file and a web page.
13. The computer program product of claim 6 , wherein the sketches are created from one bit fingerprints.
14. The computer program product of claim 6 , wherein the document is at least one of a text file, an image file and a web page.