Region-Matching Transducers for Text-Characterization

• US 20100161314A1
• Filed: 12/18/2008
• Published: 06/24/2010
• Est. Priority Date: 12/18/2008
• Status: Active Grant

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Palo Alto Research Center, Inc. (Xerox Holdings Corp.)
• Inventors: Karttunen, Lauri J., Fang, Ji
• Granted Patent: US 8,510,097 B2
• Time in Patent Office: Days
• US Class Current: 704/9
• CPC Class Codes: G06F 40/289 Phrasal analysis, e.g. finite state techniques or chunking

Abstract

Computer methods, apparatus and articles of manufacture therefor, are disclosed for text-characterization using a finite state transducer that along each path accepts on a first side an n-gram of text-characterization (e.g., a language or a topic) and outputs on a second side a sequence of symbols identifying one or more text-characterizations from a set of text-characterizations. The finite state transducer is applied to input data. For each n-gram accepted by the finite state transducer, a frequency counter associated with the n-gram of the one or more text-characterizations in the set of text-characterizations is incremented. The input data is classified as one or more text-characterizations from the set of text-characterizations using the frequency counters associated therewith.

Claims

1. A computer implemented method, comprising:

(A) recording in computer memory (a) computer readable instructions for performing text-characterization, (b) input data and (c) a finite state transducer that along each path (i) accepts on a first side an n-gram representing a text-characterization and (ii) outputs on a second side a sequence of symbols identifying one or more text-characterizations from a set of text-characterizations;

(B) processing the computer readable instructions with a computer processor;

(C) wherein the computer processor in processing the computer readable instructions;

(a) applying the finite state transducer to the input data to identify n-grams of text-characterization in the input data accepted by the finite state transducer on the first side;

for each n-gram accepted by the finite state transducer on the first side, incrementing a frequency counter associated with the one or more text-characterizations in the set of text-characterizations;

(b) assigning the input data one or more text-characterizations from the set of text-characterizations using the frequency counters associated therewith.

2. The method according to claim 1, wherein the frequency counter associated with the one or more text-characterizations in the set of text-characterizations is incremented by a predefined additional amount when an n-gram is associated with only one text-characterization in the set of text-characterizations.

3. The method according to claim 1, wherein the sequence of symbols further identifies a frequency of occurrence of the n-gram for the text-characterization.

4. The method according to claim 1, wherein said assigning further comprises tagging the input data to identify the sequence of sequence of symbols identifying the one or more text-characterizations from a set of text-characterizations.

5. The method according to claim 1, further comprising resetting the frequency counters associated with the ones of the set of text-characterizations before repeating (a)-(d).

6. The method according to claim 1, wherein said assigning classifies the input data according to the one or more text-characterizations.

7. The method according to claim 1, wherein the input data is recorded from a document using a recording device, and wherein the computer processor in processing the computer readable instructions further comprises identifying characters in the input data.

8. The method according to claim 1, wherein the computer processor in processing the computer readable instructions further comprises tagging the input data with the one or more text-characterizations.

9. The method according to claim 1, wherein the input data is natural language data and the one or more text-characterizations are one or more language identifiers.

10. The method according to claim 1, wherein the input data is natural language data and the one or more text-characterizations are one or more topics.

11. The method according to claim 1, wherein said assigning assigns the input data one or more text-characterizations from the set of text-characterizations with text-characterizations associated with frequency counters that are greater in value than text-characterizations associated with other frequency counters.

12. A computing apparatus, comprising:

a memory for recording (a) computer readable instructions for performing text-characterization, (b) input data and (c) a finite state transducer that along each path (i) accepts on a first side an n-gram representing a text-characterization and (ii) outputs on a second side a sequence of symbols identifying one or more text-characterizations from a set of text-characterizations;

a processor for processing the computer readable instructions;

wherein the processor in processing the computer readable instructions;

(a) applying the finite state transducer to the input data to identify n-grams of text-characterization in the input data accepted by the finite state transducer on the first side;

for each n-gram accepted by the finite state transducer on the first side, incrementing a frequency counter associated with the one or more text-characterizations in the set of text-characterizations;

(b) assigning the input data one or more text-characterizations from the set of text-characterizations using the frequency counters associated therewith.

13. The apparatus according to claim 12, wherein the input data is natural language data and the one or more text-characterizations are one or more language identifiers.

14. The apparatus according to claim 12, wherein the input data is natural language data and the one or more text-characterizations are one or more topics.

15. A computing apparatus, comprising:

a memory for recording (a) computer readable instructions for performing text-characterization, (b) input data and (c) a finite state transducer that along each path (i) accepts on a first side an n-gram representing a text-characterization and (ii) outputs on a second side a sequence of symbols identifying one or more text-characterizations from a set of text-characterizations;

an FST engine (a) for applying the finite state transducer to the input data to identify n-grams of text-characterization in the input data accepted by the finite state transducer on the first side;

for each n-gram accepted by the finite state transducer on the first side, incrementing a frequency counter associated with the one or more text-characterizations in the set of text-characterizations; and

(b) assigning the input data one or more text-characterizations from the set of text-characterizations using the frequency counters associated therewith.

16. The apparatus according to claim 15, wherein the input data is natural language data and the one or more text-characterizations are one or more language identifiers.

17. The apparatus according to claim 15, wherein the input data is natural language data and the one or more text-characterizations are one or more topics.

18. An article of manufacture comprising computer usable media including computer readable instructions embedded therein that causes a computer to perform a method, wherein the method comprises:

recording (a) input data and (b) a finite state transducer that along each path (i) accepts on a first side an n-gram representing a text-characterization and (ii) outputs on a second side a sequence of symbols identifying one or more text-characterizations from a set of text-characterizations;

applying the finite state transducer to the input data to identify n-grams of text-characterization in the input data accepted by the finite state transducer on the first side;

for each n-gram accepted by the finite state transducer on the first side, incrementing a frequency counter associated with the one or more text-characterizations in the set of text-characterizations;

assigning the input data one or more text-characterizations from the set of text-characterizations using the frequency counters associated therewith.

19. The article of manufacture according to claim 18, wherein the input data is natural language data and the one or more text-characterizations are one or more language identifiers.

20. The article of manufacture according to claim 18, wherein the input data is natural language data and the one or more text-characterizations are one or more topics.