Bag-of-repeats representation of documents

• US 9,183,193 B2
• Filed: 02/12/2013
• Issued: 11/10/2015
• Est. Priority Date: 02/12/2013
• Status: Expired due to Fees

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Galle, Matthias
• Primary Examiner(s): Tieu, Benny Q
• Assistant Examiner(s): Chacko, Sunil
• Application Number:
  US13/765,066
• Publication Number:
  US 20140229160A1
• Time in Patent Office: 1,001 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 40/237 Lexical tools

Abstract

A system and method for representing a textual document based on the occurrence of repeats are disclosed. The system includes a sequence generator which defines a sequence representing words forming a collection of documents. A repeat calculator identifies a set of repeats within the sequence, the set of repeats comprising subsequences of the sequence which each occur more than once. A representation generator generates a representation for at least one document in the collection of documents based on occurrence, in the document, of repeats from the set of repeats.

Claims

1. A system for representing a textual document based on the occurrence of repeats, comprising:

a sequence generator which defines a sequence representing words forming a collection of documents;

a repeat calculator which identifies a set of repeats within the sequence, the set of repeats comprising subsequences of the sequence which each have more than one occurrence in the sequence;

a context calculator which identifies at least one of a left context and a right context for each occurrence of a repeat in the set of repeats, the left context of an occurrence of the repeat being a word which immediately precedes the occurrence of the repeat in the document collection sequence, the right context of an occurrence of the repeat being a word which immediately follows the occurrence of the repeat in the document collection sequence, the context calculator identifying repeats in the set of repeats which are at least one of left context diverse, riqht context diverse, left context unique, and right context unique based on the identified at least one of the left context and the right context for each occurrence of the repeat,

a repeat being identified as left context diverse if it appears in at least two different left contexts,

a repeat being identified as riqht context diverse if it appears in at least two different right contexts,

an occurrence of a repeat being identified as left context unique if it is the sole occurrence of the repeat in that left context, and

an occurrence of a repeat being identified as right context unique if it is the sole occurrence of the repeat in that right context;

a representation generator which generates a representation for at least one document in the collection of documents based on occurrence, in the document, of repeats from the set of repeats, the representation accounting for the context of at least some of the repeats in the set of repeats; and

a processor which implements the sequence generator, repeat calculator, and representation generator.

2. The system according to claim 1, wherein the representation of the document is based on occurrence, in the document, of repeats from the set of repeats that have been identified as being at least one of left context diverse, right context diverse, left context unique, and right context unique.

3. The system according to claim 1, wherein the representation of the document is based on occurrence, in the document, of repeats from the set of repeats that have been identified as being at least one of:

both left and right context diverse, and

both left and right context unique.

4. The method of claim 3, wherein the representation of the document is based on occurrence, in the document, of repeats from the set of repeats that have been identified as being both left and right context unique.

5. The system of claim 1, wherein the context calculator, for each identified repeat, identifies the left and right contexts of occurrences of the repeats in the documents.

6. The system of claim 1, wherein the sequence generator defines a sequence representing words forming the collection of documents, where each word is represented by a symbol that uniquely identifies a normalized form of the word.

7. The system according to claim 1, further comprising a classifier component which predicts the classification of the at least one document based on the document representation.

8. The system according to claim 7, wherein the classifier component predicts the classification of a document based a document representation indexed by largest maximal repeats, the largest maximal repeats comprising repeats from the set of repeats that are both left and right context unique.

9. The system according to claim 7, wherein the classifier component predicts the classification of a document based a document representation indexed by maximal repeats, the maximal repeats comprising repeats from the set of repeats that are both left and right context diverse.

10. The system according to claim 1, further comprising a clustering component which clusters documents in the collection of documents based on the document representation.

11. The system of claim 1 further comprising a comparison component which compares representations of at least two documents in the collection and outputs information based on the comparison.

12. The system according to claim 1, further including a parser component for pre-processing the collection of documents to identify words.

13. The system according to claim 1, wherein the sequence representing words in the collection of documents is a concatenation of atomic symbols, wherein each symbol represents a word or a normalized form thereof.

14. The system of claim 1, wherein the repeats are identified regardless of sequence length.

15. A method for representing a textual document based on the occurrence of repeats, comprising:

receiving a collection of text documents;

defining a sequence representing words forming the collection of documents;

identifying a set of repeats within the sequence, the set of repeats comprising subsequences of the sequence which each have more than one occurrence in the sequence;

for each repeat in the set of repeats, identifying at least one of a left context and a right context for each occurrence of the repeat, the left context of the occurrence of the repeat being a word which immediately precedes the occurrence of the repeat in the document collection sequence, the right context of the occurrence of the repeat being a word which immediately follows the occurrence of the repeat in the document collection sequence;

generating a representation for at least one document in the collection of documents based on occurrence, in the document, of repeats from the set of repeats and their identified at least one of left and right contexts; and

wherein at least one of the defining a sequence, identifying a set of repeats, and generating a representation is performed by a computer processor.

16. The method according to claim 15, further including assigning a maximality class to at least one repeat within the identified set of all repeats.

17. The method according to claim 16, wherein the assigned maximality class is at least one of a maximal repeat and a largest maximal repeat.

18. The method according to claim 15, wherein the representation is indexed by the at least one of maximal repeats and largest maximal repeats.

19. The method according to claim 15, further comprising at least one of:

classifying the document based on the generated representation and outputting information based on the classification;

clustering documents in the collection based on their representations and outputting information on the clusters; and

computing a comparison measure between at least two documents in the collection based on their representations and outputting information based on the computed comparison measure.

20. A computer program product comprising a non-transitory storage medium storing instructions, which when executed by a processor, perform the method according to claim 15.

21. The method according to claim 15, further comprising identifying maximal repeats in the set of repeats, each maximal repeat being both left-context diverse and right-context diverse, a repeat being identified as left context diverse if it appears in at least two different left contexts, a repeat being identified as right context diverse if it appears in at least two different right contexts.

22. The method according to claim 15, further comprising identifying largest maximal repeats, each largest maximal repeat being an occurrence of one of the repeats in the set of repeats which is both left-context unique and right-context unique, an occurrence of a repeat being identified as left context unique if it is the sole occurrence of the repeat in that left context, and an occurrence of a repeat being identified as right context unique if it is the sole occurrence of the repeat in that right context.

23. A method for representing a textual document based on the occurrence of repeats, comprising:

receiving a collection of documents;

defining a sequence representing words forming the collection of documents;

identifying a set of repeats within the sequence, the set of repeats comprising all subsequences of the sequence which each occur more than once, the repeats being identified regardless of length;

from the set of repeats, identifying a subset of the repeats that are at least one of;

both left and right context diverse and both left and right context unique;

generating a vectorial representation for at least one document in the collection of documents based on occurrence, in the document, of repeats identified as being in the subset of repeats; and

wherein at least one of the defining a sequence, identifying a set of repeats, identifying a subset of the repeats, and generating a representation is performed by a computer processor.

24. The method of claim 23, wherein a repeat is identified as left and right context diverse if it occurs in at least two different left contexts and at least two different right contexts, and an occurrence of a repeat is identified as left and right context unique if it is the sole occurrence of the repeat in that left context and that right context.