Method and apparatus for a character-based comparison of documents

• US 20050132197A1
• Filed: 05/13/2004
• Published: 06/16/2005
• Est. Priority Date: 05/15/2003
• Status: Abandoned Application

• Current Assignee: Symantec Corporation (NortonLifeLock Inc.)
• Original Assignee: Symantec Corporation (NortonLifeLock Inc.)
• Inventors: Medlar, Art
• Application Number:
  US10/845,648
• Publication Number:
  US 20050132197A1
• Time in Patent Office: Days
• US Class Current: 713/176
• CPC Class Codes: H04L 51/063 Content adaptation, e.g. replacement of unsuitable content
• CPC Class Codes: H04L 51/212 using filtering or selective blocking

Abstract

A method and system for a character-based document comparison are described. In one embodiment, the method includes dividing a first document into tokens. Each token includes a predefined number of sequential characters from the first document. The method further includes calculating hash values for the tokens and creating, for the first document, a signature including a subset of hash values from the calculated hash values and additional information pertaining to the tokens of the first document. The signature of the first document is subsequently compared with a signature of a second document to determine resemblance between the first document and the second document.

Claims

1. A method comprising:

dividing a first document into a plurality of tokens, each token including a predefined number of sequential characters from the first document;

calculating a plurality of hash values for the plurality of tokens; and

creating, for the first document, a signature including a subset of hash values from the plurality of hash values and additional information pertaining to the plurality of tokens of the first document, the signature of the first document being subsequently compared with a signature of a second document to determine resemblance between the first document and the second document.

2. The method of claim 1 further comprising:

prior to dividing the first document into the plurality of tokens, changing each upper case alphabetic character within the first document to a lower case alphabetic character, and changing each non-alphabetic character within the first document to a single predefined non-alphabetic character.

3. The method of claim 1 wherein the first document is a first email message and the second document is a second email message.

4. The method of claim 1 wherein calculating the plurality of hash values for the plurality of tokens comprises:

creating a shingle for each of the plurality of tokens by combining said each of the plurality of tokens with a number of occurrences of said each of the plurality of tokens within the first document; and

applying a hashing function to each created shingle.

5. The method of claim 4 wherein shingles created for the plurality of tokens are represented as a histogram.

6. The method of claim 1 wherein the predefined number of sequential characters in each token is equal to three.

7. The method of claim 1 wherein the additional information pertaining to the plurality of tokens comprises a number of the plurality of tokens contained in the first document.

8. The method of claim 1 wherein creating the signature for the first document comprises:

sorting the plurality of hash values; and

selecting a predefined number of smallest hash values from the sorted plurality of hash values.

9. The method of claim 7 further comprising:

determining whether the number of the plurality of tokens contained in the first document is within an allowed range with respect to a number of a plurality of tokens contained in the second document; and

if the number of the plurality of tokens contained in the first document is not within the defined range from the number of the plurality of tokens contained in the second document, deciding that the first document does not resemble the second document.

10. The method of claim 9 further comprising:

determining that the number of the plurality of tokens contained in the first document is within the defined range from the number of the plurality of tokens contained in the second document;

determining whether the subset of hash values contained in the signature of the first document is similar to a subset of hash values contained in the signature of the second document; and

if the subset of hash values contained in the signature of the first document is similar to the subset of hash values contained in the signature of the second document, deciding that the first document resembles the second document.

11. The method of claim 10 wherein the second email message is a spam email message.

12. The method of claim 11 further comprising:

marking the first email message as spam upon deciding that the first document resembles the second document.

13. A system comprising:

a parser to divide a first document into a plurality of tokens, each token including a predefined number of sequential characters from the first document; and

a message data generator to calculate a plurality of hash values for the plurality of tokens, and to create, for the first document, a signature including a subset of hash values from the plurality of hash values and additional information pertaining to the plurality of tokens of the first document, the signature of the first document being subsequently compared with a signature of a second document to determine resemblance between the first document and the second document.

14. The system of claim 13 wherein the message data generator is further to change each upper case alphabetic character within the first document to a lower case alphabetic character, and to change each non-alphabetic character within the first document to a single predefined non-alphabetic character.

15. The system of claim 13 wherein the first document is a first email message and the second document is a second email message.

16. The system of claim 13 wherein the message data generator is to calculate the plurality of hash values for the plurality of tokens by creating a shingle for each of the plurality of tokens by combining said each of the plurality of tokens with a number of occurrences of said each of the plurality of tokens within the first document, and applying a hashing function to each created shingle.

17. The system of claim 13 wherein the predefined number of sequential characters in each token is equal to three.

18. The system of claim 13 wherein the additional information pertaining to the plurality of tokens comprises a number of the plurality of tokens contained in the first document.

19. The system of claim 13 wherein the message data generator is to create the signature for the first document by sorting the plurality of hash values, and selecting a predefined number of smallest hash values from the sorted plurality of hash values.

20. The system of claim 18 further comprising a resemblance identifier to determine whether the number of the plurality of tokens contained in the first document is within an allowed range with respect to a number of a plurality of tokens contained in the second document, and, if the number of the plurality of tokens contained in the first document is not within the defined range from the number of the plurality of tokens contained in the second document, to decide that the first document does not resemble the second document.

21. The system of claim 20 wherein the resemblance identifier to determine that the number of the plurality of tokens contained in the first document is within the defined range from the number of the plurality of tokens contained in the second document, to determine whether the subset of hash values contained in the signature of the first document is similar to a subset of hash values contained in the signature of the second document, and, if the subset of hash values contained in the signature of the first document is similar to the subset of hash values contained in the signature of the second document, to decide that the first document resembles the second document.

22. An apparatus comprising:

means for dividing a first document into a plurality of tokens, each token including a predefined number of sequential characters from the first document;

means for calculating a plurality of hash values for the plurality of tokens; and

means for creating, for the first document, a signature including a subset of hash values from the plurality of hash values and additional information pertaining to the plurality of tokens of the first document, the signature of the first document being subsequently compared with a signature of a second document to determine resemblance between the first document and the second document.

23. The apparatus of claim 22 wherein the predefined number of sequential characters in each token is equal to three.

24. The apparatus of claim 22 wherein the additional information pertaining to the plurality of tokens comprises a number of the plurality of tokens contained in the first document.

25. A computer readable medium comprising executable instructions which when executed on a processing system cause said processing system to perform a method comprising:

dividing a first document into a plurality of tokens, each token including a predefined number of sequential characters from the first document;

calculating a plurality of hash values for the plurality of tokens; and

creating, for the first document, a signature including a subset of hash values from the plurality of hash values and additional information pertaining to the plurality of tokens of the first document, the signature of the first document being subsequently compared with a signature of a second document to determine resemblance between the first document and the second document.

26. The computer readable medium of claim 25 wherein the predefined number of sequential characters in each token is equal to three.

27. The computer readable medium of claim 25 wherein the additional information pertaining to the plurality of tokens comprises a number of the plurality of tokens contained in the first document.