Method and system for motif extraction in electronic documents

• US 9,483,463 B2
• Filed: 09/10/2012
• Issued: 11/01/2016
• Est. Priority Date: 09/10/2012
• Status: Expired due to Fees

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Galle, Matthias, Renders, Jean-Michel
• Primary Examiner(s): Desir, Pierre-Louis
• Assistant Examiner(s): THOMAS-HOMESCU, ANNE L
• Application Number:
  US13/608,312
• Publication Number:
  US 20140074455A1
• Time in Patent Office: 1,513 Days
• Field of Search: 702/19, 702/20, 704/9, 704/235, 704/257, 704/254, 707/709, 707/755, 707/738, 707/776, 715/234, 715/255, 715/742, 709/203, 709/219, 709/224
• US Class Current: 1/1
• CPC Class Codes: G06F 40/186 Templates
• CPC Class Codes: G06F 40/289 Phrasal analysis, e.g. finite state techniques or chunking

Abstract

A method, system, and computer program product for extracting text motifs from the electronic documents is disclosed. A user provides a largest-maximal repeat or a super-maximal repeat as a first text block. The occurrences of the first text block are detected to identify the second text blocks in the vicinity of the occurrences of the first text block on the basis of pre-defined parameters. The text motifs are determined by combining the first text block and the second text block. Finally, the text motifs are extracted from the electronic documents.

Claims

1. A method for extracting one or more text motifs from one or more electronic documents, the method comprising:

receiving, by a processor, a first text block from a user, wherein the first text block corresponds to at least one of a largest-maximal repeat (LMR) or a super-maximal repeat (SMR);

receiving, by the processor via an input device coupled to the processor, an array of repeats, wherein the array of repeats comprises a list of repeats of one or more text blocks occurring at one or more positions in the one or more electronic documents;

detecting, by the processor, one or more occurrences of the first text block in the one or more electronic documents based on the array of repeats;

identifying, in the one or more electronic documents by the processor, a second text block in vicinity of an occurrence of the first text block based on a pre-defined set of parameters, such that the second text block and the first text block are repeated together at least two times in the one or more electronic documents, wherein the pre-defined set of parameters comprises a maximum number of text blocks in the one or more text motifs;

determining, by the processor, the one or more text motifs in the one or more electronic documents, wherein each of the one or more text motifs is a combination of the first text block and the second text block;

checking, by the processor, for extension of the one or more text motifs if a number of text blocks in the one or more text motifs is less than the maximum number of text blocks in the one or more text motifs, wherein the checking for extension further comprises using the one or more text motifs as a new text block and repeating the identifying and determining steps for the new text block until the maximum number of text blocks is reached;

extracting, by the processor, the one or more text motifs from each of the one or more electronic documents; and

creating, by the processor, a template by collating the one or more extracted text motifs.

2. The method of claim 1, wherein the one or more electronic documents corresponds to at least one of emails, news articles, journals, or any electronic document containing text.

3. The method of claim 1, wherein the LMR corresponds to a repeat comprising at least one occurrence that is right-context and left-context unique.

4. The method of claim 1, wherein the SMR corresponds to a repeat that is not a substring of any other repeat in the one or more electronic documents.

5. The method of claim 1, wherein the pre-defined set of parameters further comprises at least one of a minimum length of a text block, a minimum length of a text motif, a minimum number of occurrences of the text motif, and a maximum length of a gap between the first text block and the second text block.

6. The method of claim 5 further comprising checking, by the processor, whether the number of occurrences of the text motif in the one or more electronic documents is greater than the minimum number of occurrences of the text motif in the one or more electronic documents, wherein the one or more text motifs are extracted when the number of occurrences of the text motif is greater than the minimum number of occurrences of the text motif.

7. The method of claim 5, wherein the vicinity is determined based on the maximum length of the gap between the first text block and the second text block.

8. A method for removing boilerplate text in one or more electronic documents, the method comprising:

receiving, by a processor via an input device coupled to the processor, a first text block from a user, wherein the first text block corresponds to at least one of a largest-maximal repeat (LMR) or a super-maximal repeat (SMR);

receiving, by the processor, an array of repeats, wherein the array of repeats comprises a list of repeats of one or more text blocks occurring at one or more positions in the one or more electronic documents;

detecting, by the processor, one or more occurrences of the first text block in the one or more electronic documents based on the array of repeats;

identifying, in the one or more electronic documents by the processor, a second text block in vicinity of an occurrence of the first text block based on a maximum length of a gap between the first text block and the second text block, such that the second text block and the first text block are repeated together, at least two times in the one or more electronic documents;

determining, by the processor, one or more text motifs in the one or more electronic documents, wherein each of the one or more text motifs is a combination of the first text block and the second text block;

checking, by the processor, for extension of the one or more text motifs if a number of text blocks in the one or more text motifs is less than a maximum number of text blocks in the one or more text motifs, wherein the checking for extension further comprises using the one or more text motifs as a new text block and repeating the identifying, and determining steps for the new text block until the maximum number of text blocks is reached;

removing, by the processor, the one or more text motifs from each of the one or more electronic documents; and

creating, by the processor, a template by collating the one or more extracted text motifs.

9. The method of claim 8 further comprising checking, by the processor, whether the number of occurrences of a text motif is greater than a minimum number of occurrences of the text motif defined by the user, wherein the one or more text motifs is removed if the number of occurrences of the text motif is greater than the minimum number of occurrences of the text motif.

10. A system for extracting one or more text motifs from one or more electronic documents, the system comprising:

a processor configured to;

detect one or more occurrences of a first text block in the one or more electronic documents, wherein the first text block corresponds to at least one of a largest-maximal repeat (LMR) or a super-maximal repeat (SMR) based on an array of repeats, wherein the array of repeats comprises a list of repeats of one or more text blocks occurring at one or more positions in the one or more electronic documents, the list of repeats being received at the processor via an input device;

identify, in the one or more electronic documents, a second text block in vicinity of an occurrence of the first text block based on a maximum length of a gap between the first text block and the second text block, such that the second text block and the first text block are repeated together, at least two times in the one or more electronic documents;

determine one or more text motifs in the one or more electronic documents, wherein each of the one or more text motifs is a combination of the first text block and the second text block;

check for extension of the one or more text motifs if a number of text blocks in the one or more text motifs is less than a maximum number of text blocks in the one or more text motifs, wherein the check further comprises using the one or more text motifs as a new text block and repeating the identifying, and determining steps for the new text block until the maximum number of text blocks is reached;

extract the one or more text motifs from each of the one or more electronic documents; and

create a template by collating the one or more extracted text motifs.

11. The system of claim 10, wherein the processor is further configured to receive at least one of the first text block, the array of repeats, and a pre-defined set of parameters from a user.

12. The system of claim 10, wherein the processor is further configured to store the extracted one or more text motifs as the template, wherein the extracted one or more text motifs are collated to create the template.

13. A non-transitory computer program product for use with a computer, the non-transitory computer program product comprising a computer readable program code embodied therein for extracting one or more text motifs in a one or more electronic documents, the computer readable program code is executable by a processor to:

receive a first text block from a user via an input device, wherein the first text block corresponds to at least one of a largest-maximal repeat (LMR) or a super-maximal repeat (SMR);

receive an array of repeats via the input device, wherein the array of repeats comprises a list of repeats of one or more text blocks occurring at one or more positions in the one or more electronic documents;

detect one or more occurrences of the first text block in the one or more electronic documents based on the array of repeats;

identify, in the one or more electronic documents, a second text block in vicinity of an occurrence of the first text block based on a pre-defined set of parameters, such that the second text block and the first text block are repeated together in the one or more electronic documents, wherein the pre-defined set of parameters comprises a maximum number of text blocks in the one or more text motifs;

determine the one or more text motifs in the one or more electronic documents, wherein each of the one or more text motifs is a combination of the first text block and the second text block;

check for extension of the one or more text motifs if a number of text blocks in the one or more text motifs is less than the maximum number of text blocks in the one or more text motifs, wherein the checking for extension further comprises using the one or more text motifs as a new text block and repeating the identifying and determining steps for the new text block until the maximum number of text blocks is reached;

extract the one or more text motifs from each of the one or more electronic documents; and

create a template by collating the one or more extracted text motifs.