Paraphrase acquisition

• US 8,271,453 B1
• Filed: 05/02/2011
• Issued: 09/18/2012
• Est. Priority Date: 09/27/2005
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Pasca, Alexandru Marius, Dienes, Peter Szabolcs
• Primary Examiner(s): Han, Qi
• Application Number:
  US13/099,239
• Time in Patent Office: 505 Days
• Field of Search: 704/9, 704/1, 704/10, 704/257, 704/7, 707/1, 707/673
• US Class Current: 707/673
• CPC Class Codes: G06F 40/247 Thesauruses; Synonyms
• CPC Class Codes: G06F 40/289 Phrasal analysis, e.g. finite state techniques or chunking
• CPC Class Codes: G06F 40/295 Named entity recognition

Abstract

Methods and apparatus, including systems and computer program products, to acquire potential paraphrases from textual input. In one aspect, textual input is received, a first map is generated, where the key of the first map is an ngram identified in the textual input and the value associated with the key of the first map is a unique identifier, a second map is generated, where the key of the second map is an anchor identified from the ngram and the value associated with the key of the second map is one or more middle portions associated with the anchor, and a third map is generated, where the key of the third map is a potential paraphrase pair identified from the middle portions and the value associated with the key of the third map is the one or more unique anchors associated with the potential paraphrase pair.

Claims

1. A method, comprising:

receiving textual input;

processing, by one or more computers, the textual input to produce a first output comprising first keys, wherein each first key is an ngram occurring in the textual input;

processing, by the one or more computers, the first output to produce a second output comprising second keys and associated second values, wherein each second key is an anchor extracted from at least one of the first keys, wherein each anchor is defined by a beginning portion and an ending portion of a respective first key ngram, the beginning portion and ending portion being separated by a middle portion of the respective first key ngram, and wherein each second value is a set of middle portions associated with each distinct anchor; and

processing, by the one or more computers, the second output to produce a third output comprising third keys and associated third values, wherein each third key is a potential paraphrase pair identified from a second value set of middle portions, and each third value is a set of anchors associated with the potential paraphrase pair.

2. The method of claim 1, wherein the textual input comprises Web documents, and wherein processing the textual input comprises splitting the Web documents into multiple subsets of Web documents and allocating each different subset to a different computer process.

3. The method of claim 1, wherein the first output comprises associated first values, wherein each first value is a count of occurrence in the textual input of an ngram of the associated key, and wherein processing the first output comprises processing only key and value pairs having a count that meets a threshold.

4. The method of claim 1, wherein identifying a potential paraphrase pair from a second value set of middle portions comprises identifying combinations of pairs of middle portions within the second value set of middle portions.

5. The method of claim 1, wherein the processing steps are performed using a distributed architecture of multiple computers.

6. The method of claim 1, wherein each third value is used to determine a quality of an associated third key potential paraphrase pair, wherein the quality is based at least in part on a number of distinct anchors in the third value set of anchors associated with the potential paraphrase pair.

7. The method of claim 1, wherein all identical first keys are processed by a same reduce process that generates the first output.

8. The method of claim 1, wherein each ngram occurs once in the first output.

9. A computer storage medium encoded with a computer program, the program comprising instructions that, when executed by one or more computers, cause the one or more computers to perform operations comprising:

receiving textual input;

processing the textual input to produce a first output comprising first keys, wherein each first key is an ngram occurring in the textual input;

processing the first output to produce a second output comprising second keys and associated second values, wherein each second key is an anchor extracted from at least one of the first keys, wherein each anchor is defined by a beginning portion and an ending portion of a respective first key ngram, the beginning portion and ending portion being separated by a middle portion of the respective first key ngram, and wherein each second value is a set of middle portions associated with each distinct anchor; and

processing the second output to produce a third output comprising third keys and associated third values, wherein each third key is a potential paraphrase pair identified from a second value set of middle portions, and each third value is a set of anchors associated with the potential paraphrase pair.

10. The storage medium of claim 9, wherein the textual input comprises Web documents, and wherein processing the textual input comprises splitting the Web documents into multiple subsets of Web documents and allocating each different subset to a different computer process.

11. The storage medium of claim 9, wherein the first output comprises associated first values, wherein each first value is a count of occurrence in the textual input of an ngram of the associated key, and wherein processing the first output comprises processing only key and value pairs having a count that meets a threshold.

12. The storage medium of claim 9, wherein identifying a potential paraphrase pair from a second value set of middle portions comprises identifying combinations of pairs of middle portions within the second value set of middle portions.

13. The storage medium of claim 9, wherein the processing steps are implemented for a distributed architecture of multiple computers.

14. The storage medium of claim 9, wherein each third value is used to determine a quality of an associated third key potential paraphrase pair, wherein the quality is based at least in part on a number of distinct anchors in the third value set of anchors associated with the potential paraphrase pair.

15. The storage medium of claim 9, wherein all identical first keys are processed by a same reduce process that generates the first output.

16. The storage medium of claim 9, wherein each ngram occurs once in the first output.

17. A system comprising:

one or more computers; and

a computer-readable storage device having stored thereon instructions that, when executed by the one or more computers, cause the one or more computers to perform operations comprising;

receiving textual input;

processing the textual input to produce a first output comprising first keys, wherein each first key is an ngram occurring in the textual input;

processing the first output to produce a second output comprising second keys and associated second values, wherein each second key is an anchor extracted from at least one of the first keys, wherein each anchor is defined by a beginning portion and an ending portion of a respective first key ngram, the beginning portion and ending portion being separated by a middle portion of the respective first key ngram, and wherein each second value is a set of middle portions associated with each distinct anchor; and

processing the second output to produce a third output comprising third keys and associated third values, wherein each third key is a potential paraphrase pair identified from a second value set of middle portions, and each third value is a set of anchors associated with the potential paraphrase pair.

18. The system of claim 17, wherein the textual input comprises Web documents, and wherein processing the textual input comprises splitting the Web documents into multiple subsets of Web documents and allocating each different subset to a different computer process.

19. The system of claim 17, wherein the first output comprises associated first values, wherein each first value is a count of occurrence in the textual input of an ngram of the associated key, and wherein processing the first output comprises processing only key and value pairs having a count that meets a threshold.

20. The system of claim 17, wherein identifying a potential paraphrase pair from a second value set of middle portions comprises identifying combinations of pairs of middle portions within the second value set of middle portions.

21. The system of claim 17, wherein the processing steps are performed using a distributed architecture of multiple computers.

22. The system of claim 17, wherein each third value is used to determine a quality of an associated third key potential paraphrase pair, wherein the quality is based at least in part on a number of distinct anchors in the third value set of anchors associated with the potential paraphrase pair.

23. The system of claim 17, wherein all identical first keys are processed by a same reduce process that generates the first output.

24. The system of claim 17, wherein each ngram occurs once in the first output.