BAG-OF-REPEATS REPRESENTATION OF DOCUMENTS

• US 20140229160A1
• Filed: 02/12/2013
• Published: 08/14/2014
• Est. Priority Date: 02/12/2013
• Status: Active Grant

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Galle, Matthias
• Granted Patent: US 9,183,193 B2
• Time in Patent Office: Days
• US Class Current: 704/9
• 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 occur more than once;

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; and

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

2. The system according to claim 1, wherein the representation accounts for context of at least some of the repeats.

3. The system according to claim 2, further comprising a context calculator for identifying repeats in the set of repeats which are at least one of:

left context diverse;

right context diverse;

left context unique; and

right context unique.

4. The system of claim 3, wherein:

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

a repeat is identified as right context diverse if it appears in at least two different right contexts;

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

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

5. The system according to 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 at least one of left context diverse, right context diverse, left context unique, and right context unique.

6. The system according to 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 at least one of:

both left and right context diverse and both left and right context unique.

7. The method of claim 5, 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.

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

9. 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.

10. 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.

11. The system according to claim 10, 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.

12. The system according to claim 10, 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.

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

14. 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.

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

16. 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.

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

18. 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 occur more than once;

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

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

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

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

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

22. The method according to claim 18, 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.

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

24. 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;

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.