System and method for textual near-duplicate grouping of documents
A method for efficiently grouping electronic documents that are likely textual near-duplicates includes processing first and second electronic documents to determine respective sets of character sequence counts. The processing includes, for each document, (1) identifying non-contiguous character sequences expressed within the document text, with each character sequence corresponding to a different starting position within the text and including at least a first character at the respective starting position and a second character at a pre-defined offset from the respective starting position, and (2) determining character sequence counts for each unique character sequence within the identified character sequences. The method also includes generating one or more similarity metrics, at least by comparing the sets of character sequence counts determined for the first and second electronic documents. The method may also include assigning, based on the similarity metric(s), the second electronic document to a same document group as the first electronic document.
1. A method, implemented by one or more processors of a computing system, for efficiently grouping electronic documents that are likely textual near-duplicates, the method comprising:
processing, by the one or more processors, a first electronic document and a second electronic document to determine respective sets of character sequence counts, wherein processing the first electronic document and the second electronic document includes, for each electronic document,
identifying a plurality of non-contiguous character sequences expressed within text of the electronic document, each non-contiguous character sequence corresponding to a different starting position within the text and including (i) a first character at the respective starting position, and (ii) a second character at a pre-defined offset from the respective starting position, and
determining a set of character sequence counts, at least in part by determining, for each unique non-contiguous character sequence occurring within the identified plurality of non-contiguous character sequences, a character sequence count specifying how many times the unique non-contiguous character sequence is expressed within the text of the electronic document;
generating, by the one or more processors, one or more similarity metrics, wherein generating the one or more similarity metrics includes comparing (i) the set of character sequence counts determined for the first electronic document to (ii) the set of character sequence counts determined for the second electronic document; and
assigning, by the one or more processors and based on the one or more similarity metrics, the second electronic document to a same document group as the first electronic document.
2. The method of claim 1 , wherein assigning the second electronic document to the same document group as the first electronic document includes causing a user interface of either the computing system or a remote client device to display information indicating that the second electronic document is assigned to the same document group as the first electronic document.
3. The method of claim 1 , wherein each of the different starting positions is a particular letter of a different word within the text.
4. The method of claim 3 , wherein each of the different starting positions is a first letter of a different word within the text.
5. The method of claim 4 , wherein the pre-defined offset is a pre-defined number of words.
6. The method of claim 1 , wherein the different starting positions are within successive words of a contiguous sequence of words within the text of the electronic document.
7. The method of claim 1 , wherein each of the plurality of non-contiguous character sequences consists of two characters.
8. The method of claim 1 , further comprising:
calculating, by the one or more processors and using the one or more similarity metrics, a similarity score for the first electronic document and the second electronic document,
wherein assigning the second electronic document to the same document group as the first electronic document is performed based on the similarity score.
9. The method of claim 8 , further comprising:
determining, by the one or more processors, one or more additional similarity metrics indicating commonality of words between the first electronic document and the second electronic document,
wherein calculating the similarity score includes calculating the similarity score using (i) the one or more similarity metrics and (ii) the one or more additional similarity metrics.
10. The method of claim 8 , wherein assigning the second electronic document to the same document group as the first electronic document includes:
determining that the similarity score is greater than a threshold score; and
in response to determining that the similarity score is greater than the threshold score, assigning the second electronic document to the same document group as the first electronic document.
11. The method of claim 1 , further comprising, prior to processing the first electronic document and the second electronic document to determine the respective sets of character sequence counts:
determining, by the one or more processors, a first set of one or more characteristics of the text of the first electronic document;
determining, by the one or more processors, a second set of one or more characteristics of the text of the second electronic document; and
determining, by the one or more processors and using the first set of one or more characteristics and the second set of one or more characteristics, that the first electronic document and the second electronic document are not logically excluded from satisfying one or more similarity criteria,
wherein processing the first electronic document and the second electronic document to determine the respective sets of character sequence counts is performed in response to determining that the first electronic document and the second electronic document are not logically excluded from satisfying the one or more similarity criteria.
12. The method of claim 11 , wherein the first set of one or more characteristics and the second set of one or more characteristics include one or more of: (i) word count information for the texts of the respective electronic documents, (ii) unicode block information for the texts of the respective electronic documents, (iii) word length information for the texts of the respective electronic documents, or (iv) information about a first letter of each word for the texts of the respective documents.
13. A system for efficiently grouping electronic documents that are likely textual near-duplicates, the system comprising:
a first memory storing an electronic document repository containing a plurality of electronic documents, including a first electronic document and a second electronic document;
a computing device comprising one or more processors and a second memory, the second memory storing instructions that, when executed by the one or more processors, cause the computing device to obtain electronic documents stored in the first memory to
process the first electronic document and the second electronic document to determine respective sets of character sequence counts, at least in part by, for each electronic document,
(a) identifying a plurality of non-contiguous character sequences expressed within text of the electronic document, each non-contiguous character sequence corresponding to a different starting position within the text and including (i) a first character at the respective starting position, and (ii) a second character at a pre-defined offset from the respective starting position, and
(b) determining a set of character sequence counts, at least in part by determining, for each unique non-contiguous character sequence occurring within the identified plurality of non-contiguous character sequences, a character sequence count specifying how many times the unique non-contiguous character sequence is expressed within the text of the electronic document,
generate one or more similarity metrics, at least in part by comparing (i) the set of character sequence counts determined for the first electronic document to (ii) the set of character sequence counts determined for the second electronic document, and
assign, based on the one or more similarity metrics, the second electronic document to a same document group as the first electronic document.
14. The system of claim 13 , wherein each of the different starting positions is a particular letter of a different word within the text.
15. The system of claim 13 , wherein the pre-defined offset is a pre-defined number of words.
16. The system of claim 13 , wherein the different starting positions are within successive words of a contiguous sequence of words within the text of the electronic document.
17. The system of claim 13 , wherein:
the instructions, when executed by the one or more processors, further cause the computing device to calculate, using the one or more similarity metrics, a similarity score for the first electronic document and the second electronic document, and
the instructions, when executed by the one or more processors, cause the computing device to assign the second electronic document to the same document group as the first electronic document based on the similarity score.
18. A non-transitory, computer-readable medium storing instructions that, when executed by one or more processors of a computing device, cause the computing device to:
process a first electronic document and a second electronic document to determine respective sets of character sequence counts, at least in part by, for each electronic document,
(a) identifying a plurality of non-contiguous character sequences expressed within text of the electronic document, each non-contiguous character sequence corresponding to a different starting position within the text and including (i) a first character at the respective starting position, and (ii) a second character at a pre-defined offset from the respective starting position, and
(b) determining a set of character sequence counts, at least in part by determining, for each unique non-contiguous character sequence occurring within the identified plurality of non-contiguous character sequences, a character sequence count specifying how many times the unique non-contiguous character sequence is expressed within the text of the electronic document;
generate one or more similarity metrics, at least in part by comparing (i) the set of character sequence counts determined for the first electronic document to (ii) the set of character sequence counts determined for the second electronic document; and
assign, based on the one or more similarity metrics, the second electronic document to a same document group as the first electronic document.
19. The non-transitory, computer-readable medium of claim 18 , wherein each of the different starting positions is a particular letter of a different word within the text.
20. The non-transitory, computer-readable medium of claim 18 , wherein the pre-defined offset is a pre-defined number of words.