Methods and systems for identifying paraphrases from an index of information items and associated sentence fragments

• US 8,280,893 B1
• Filed: 05/02/2011
• Issued: 10/02/2012
• Est. Priority Date: 03/23/2005
• Status: Expired due to Fees

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Pasca, Alexandru Marius, Dienes, Peter Szabolcs
• Primary Examiner(s): TRUONG, CAM Y T
• Application Number:
  US13/098,669
• Time in Patent Office: 519 Days
• Field of Search: 707/999.03, 707/730, 707749-750, 707/753, 707/999.05
• US Class Current: 707/750
• CPC Class Codes: G06F 40/247 Thesauruses; Synonyms

Abstract

Methods and systems for identification of paraphrases from an index of information items and associated sentence fragments are described. One method described comprises identifying a pair of sentence fragments each having a same associated information item from an index, wherein the index comprises a plurality of information items and associated sentence fragments, and identifying a paraphrase pair from the pair of sentence fragments.

Claims

1. A system comprising:

one or more computers programmed to implement a paraphrase engine to create an index of paraphrases, paraphrases being groups of one or more words in a same language, the groups having a same or a similar meaning but not being identical, the paraphrase engine to perform operations including;

identifying a first sentence fragment and a second sentence fragment that, in text of one or more electronic documents, are both associated with a same date or entity name, the first sentence fragment and the second sentence fragment each comprising two or more like-words found in both the first sentence fragment and the second sentence fragment and one or more dissimilar-words found in only one of the first sentence fragment or the second sentence fragment;

aligning the like-words in the first sentence fragment with the like-words in the second sentence fragment;

determining that the alignment satisfies a threshold frequency value; and

in response to determining that the alignment satisfies the threshold frequency value, extracting the dissimilar-words from the first sentence fragment and the dissimilar-words from the second sentence fragment; and

outputting the index of paraphrases after the extracting, the index identifying the dissimilar-words from the first sentence fragment as paraphrasing the dissimilar-words from the second sentence fragment.

2. The system of claim 1, wherein the one or more computers are programmed to implement a search engine to perform operations, the operations comprising:

receiving web search queries that include the dissimilar-words from the second sentence fragment;

accessing the index of paraphrases;

determining, from the index of paraphrases, that the dissimilar-words from the first sentence fragment paraphrase the dissimilar-words from the second sentence fragment; and

searching for electronic documents responsive to the web search queries using at least the dissimilar-words from the first sentence fragment paraphrase.

3. The system of claim 2, further comprising client devices programmed to submit the web search queries to the search engine.

4. The system of claim 1, wherein the first sentence fragment and the second sentence fragment are identified using one or more lexico-syntactic extraction patterns.

5. The system of claim 4, wherein the lexico-syntactic extraction patterns are set up to identify sentence fragments containing verbs.

6. The system of claim 1, wherein the one or more computers are further programmed to summarize a text or a document, including identifying duplicative sentences that say a same thing but in a different way.

7. The system of claim 1, wherein the operations further comprise determining that the alignment satisfies a criterion that embodies a likelihood that the dissimilar-words in the first sentence fragment are paraphrases of the dissimilar-words in the second sentence fragment.

8. The system of claim 7, wherein the criterion is a threshold requirement that at least three non-stop dissimilar-words in the first sentence fragment are aligned with three non-stop dissimilar-words in the second sentence fragment.

9. The system of claim 1, wherein the index of paraphrases further comprises a frequency of occurrence value that characterizes how often the dissimilar-words from the first sentence fragment paraphrase the dissimilar-words from the second sentence fragment.

10. The system of claim 1, wherein operations performed by the paraphrase engine further comprise:

generating a list of potential paraphrase pairs by repeatedly identifying sentence fragments that, in the text of one or more electronic documents, are both associated with a same date or entity name, aligning like-words in the sentence fragments, determining that the alignment satisfies the threshold frequency value, and, in response to determining that the alignment satisfies the threshold frequency value, extracting dissimilar-words from the sentence fragments;

determining a frequency at which the dissimilar-words extracted from the sentence fragments appear in the list of potential paraphrase pairs; and

discarding dissimilar-words that do not meet a threshold frequency value.

11. The system of claim 10, wherein the dissimilar-words extracted from the sentence fragments are ranked in the index of paraphrases according to the frequency at which the dissimilar-words extracted appear in the list of potential paraphrase pairs.

12. The system of claim 1, wherein the operations further comprise parsing the identified sentences fragments into words.

13. The system of claim 1, wherein the operations further comprise aligning special characters or punctuation marks in the first sentence fragment with special characters or punctuation marks in the second sentence fragment.

14. A method implemented by a system of one or more computers, the method comprising:

identifying, by the system, a first sentence fragment and a second sentence fragment that, in text of one or more electronic documents, are both associated with a same date or entity name, the first sentence fragment and the second sentence fragment each comprising two or more like-words found in both the first sentence fragment and the second sentence fragment and one or more dissimilar-words found in only one of the first sentence fragment or the second sentence fragment;

aligning, by the system, the like-words in the first sentence fragment with the like-words in the second sentence fragment;

determining, by the system, that the alignment satisfies a threshold frequency value; and

in response to determining that the alignment satisfies the threshold frequency value, extracting, by the system, the dissimilar-words from the first sentence fragment and the dissimilar-words from the second sentence fragment; and

outputting, to memory, the index of paraphrases after the extracting, the index identifying the dissimilar-words from the first sentence fragment as paraphrasing the dissimilar-words from the second sentence fragment.

15. The method of claim 14, further comprising:

receiving web search queries that include the dissimilar-words from the second sentence fragment;

accessing the index of paraphrases;

determining, from the index of paraphrases, that the dissimilar-words from the first sentence fragment paraphrase the dissimilar-words from the second sentence fragment; and

searching for electronic documents responsive to the web search queries using at least the dissimilar-words from the first sentence fragment.

16. The method of claim 14, wherein the first sentence fragment and the second sentence fragment are identified using one or more lexico-syntactic extraction patterns.

17. The method of claim 16, wherein the lexico-syntactic extraction patterns are set up to identify sentence fragments containing verbs.

18. The method of claim 14, further comprising summarize a text or a document, including identifying duplicative sentences that say a same thing but in a different way.

19. The method of claim 14, wherein the method further comprises determining, by the system, that the alignment satisfies a criterion that embodies a likelihood that the dissimilar-words in the first sentence fragment are paraphrases of the dissimilar-words in the second sentence fragment.

20. The method of claim 19, wherein the criterion is a threshold requirement that at least three non-stop dissimilar-words in the first sentence fragment are aligned with three non-stop dissimilar-words in the second sentence fragment.

21. The method of claim 14, further comprising:

generating a list of potential paraphrase pairs by repeatedly identifying sentence fragments that, in the text of one or more electronic documents, are both associated with a same date or entity name, aligning like-words in the sentence fragments, determining that the alignment satisfies the threshold frequency value, and, in response to determining that the alignment satisfies the threshold frequency value, extracting dissimilar-words from the sentence fragments;

determining a frequency at which the dissimilar-words extracted from the sentence fragments appear in the list of potential paraphrase pairs; and

discarding dissimilar-words that do not meet a threshold frequency value.

22. The method of claim 14, further comprising ranking the dissimilar-words extracted from the sentence fragments in the index of paraphrases according to the frequency at which the dissimilar-words extracted appear in the list of potential paraphrase pairs.

23. The method of claim 14, further comprising parsing the identified sentences fragments into words.

24. The method of claim 14, further comprising aligning special characters or punctuation marks in the first sentence fragment with special characters or punctuation marks in the second sentence fragment.

25. A method implemented by a system of one or more computers, the method comprising:

identifying, by the system, different sentence fragments in different electronic documents, wherein the sentence fragments each comprise two or more words that are alike and are all associated within the different electronic documents with a same date, with a same entity name, or with a same concept, and wherein the sentence fragments further comprising words that are dissimilar and not found in all the sentence fragments;

aligning, by the system, the different sentence fragments based on positioning of the words that are alike within the different sentence fragments;

determining, by the system, that some of the alignments of the words that are alike satisfy a criterion;

in response to determining that some of the alignments of the words that are alike satisfy the criterion, extracting, by the system, the words that are dissimilar from the at least some of the different sentence fragments;

determining, by the system, frequencies at which the words that are dissimilar appear between the words that are alike within the different sentence fragments;

determining, by the system, that some of the words that are dissimilar satisfy a threshold frequency value;

in response to the determining that at least some of the words that are dissimilar satisfy the threshold frequency value, adding, by the system, the words that are dissimilar and that satisfy the threshold frequency value to an index of paraphrases; and

outputting, by the system, the index of paraphrases after the adding, the index identifying that the words that are dissimilar and that satisfy the threshold frequency value are paraphrases, wherein paraphrases are groups of one or more words in a same language, the groups having a same or a similar meaning but not being identical.

26. The method of claim 25, wherein the method further comprises:

determining, by the system, that some of the words that are dissimilar fail to satisfy the threshold frequency value; and

discarding, by the system, the some of the words that are dissimilar and that fail to satisfy the threshold frequency value.

27. The method of claim 25, further comprising:

receiving, by the system, web search queries that include words;

accessing, by the system, the index of paraphrases;

determining, by the system and from the index of paraphrases, that some of the words in the web search queries appear in the index of paraphrases; and

searching for electronic documents responsive to the web search queries using other words that are identified in the index of paraphrases as paraphrasing the some of the words appearing in the web search queries.

28. The method of claim 25, wherein identifying the different sentence fragments in the different electronic documents comprises identifying the different sentence fragments using one or more lexico-syntactic extraction patterns.

29. The method of claim 28, wherein the lexico-syntactic extraction patterns are set up to identify sentence fragments containing verbs.

30. A system comprising:

one or more computers programmed to implement a paraphrase engine to create an index of paraphrases, paraphrases being groups of one or more words in a same language, the groups having a same or a similar meaning but not being identical, the paraphrase engine to perform operations including;

identifying different sentence fragments in different electronic documents, wherein the sentence fragments each comprise two or more words that are alike and are all associated within the different electronic documents with a same date, with a same entity name, or with a same concept, and wherein the sentence fragments further comprising words that are dissimilar and not found in all the sentence fragments;

aligning the different sentence fragments based on positioning of the words that are alike within the different sentence fragments;

determining that some of the alignments of the words that are alike satisfy a criterion;

in response to determining that some of the alignments of the words that are alike satisfy the criterion, extracting the words that are dissimilar from the at least some of the different sentence fragments;

determining frequencies at which the words that are dissimilar appear between the words that are alike within the different sentence fragments;

determining that some of the words that are dissimilar satisfy a threshold frequency value;

in response to the determining that at least some of the words that are dissimilar satisfy the threshold frequency value, adding the words that are dissimilar and that satisfy the threshold frequency value to an index of paraphrases; and

outputting the index of paraphrases after the adding, the index identifying that the words that are dissimilar and that satisfy the threshold frequency value are paraphrases, wherein paraphrases are groups of one or more words in a same language, the groups having a same or a similar meaning but not being identical.

31. The system of claim 30, wherein the operations further comprise:

determining that some of the words that are dissimilar fail to satisfy the threshold frequency value; and

discarding the some of the words that are dissimilar and that fail to satisfy the threshold frequency value.

32. The system of claim 30, wherein the one or more computers are further programmed to implement a search engine, the search engine to perform operations including:

receiving web search queries that include words;

accessing the index of paraphrases;

determining, from the index of paraphrases, that some of the words in the web search queries appear in the index of paraphrases; and

searching for electronic documents responsive to the web search queries using other words that are identified in the index of paraphrases as paraphrasing the some of the words appearing in the web search queries.

33. The system of claim 30, wherein identifying the different sentence fragments in the different electronic documents comprises identifying the different sentence fragments using one or more lexico-syntactic extraction patterns.

34. The system of claim 33, wherein the lexico-syntactic extraction patterns are set up to identify sentence fragments containing verbs.

35. An article comprising one or more computer-readable data storage media storing program code operable to cause one or more machines to perform operations, the operations comprising:

identifying different sentence fragments in different electronic documents, wherein the sentence fragments each comprise two or more words that are alike and are all associated within the different electronic documents with a same date, with a same entity name, or with a same concept, and wherein the sentence fragments further comprising words that are dissimilar and not found in all the sentence fragments;

aligning the different sentence fragments based on positioning of the words that are alike within the different sentence fragments;

determining that some of the alignments of the words that are alike satisfy a criterion;

in response to determining that some of the alignments of the words that are alike satisfy the criterion, extracting the words that are dissimilar from the at least some of the different sentence fragments;

determining frequencies at which the words that are dissimilar appear between the words that are alike within the different sentence fragments;

determining that some of the words that are dissimilar satisfy a threshold frequency value;

in response to the determining that at least some of the words that are dissimilar satisfy the threshold frequency value, adding the words that are dissimilar and that satisfy the threshold frequency value to an index of paraphrases; and

outputting the index of paraphrases after the adding, the index identifying that the words that are dissimilar and that satisfy the threshold frequency value are paraphrases, wherein paraphrases are groups of one or more words in a same language, the groups having a same or a similar meaning but not being identical.

36. The article of claim 35, wherein the operations further comprise:

determining, by the system, that some of the words that are dissimilar fail to satisfy the threshold frequency value; and

discarding, by the system, the some of the words that are dissimilar and that fail to satisfy the threshold frequency value.

37. The article of claim 35, wherein the operations further comprise:

receiving web search queries that include words;

accessing, by the system, the index of paraphrases;

determining, by the system and from the index of paraphrases, that some of the words in the web search queries appear in the index of paraphrases; and

searching for electronic documents responsive to the web search queries using other words that are identified in the index of paraphrases as paraphrasing the some of the words appearing in the web search queries.

38. The article of claim 35, wherein identifying the different sentence fragments in the different electronic documents comprises identifying the different sentence fragments using one or more lexico-syntactic extraction patterns.

39. The article of claim 38, wherein the lexico-syntactic extraction patterns are set up to identify sentence fragments containing verbs.

40. An article comprising one or more computer-readable data storage media storing program code operable to cause one or more machines to perform operations implementing a paraphrase engine to create an index of paraphrases, paraphrases being groups of one or more words in a same language, the groups having a same or a similar meaning but not being identical, the operations comprising:

identifying a first sentence fragment and a second sentence fragment that, in text of one or more electronic documents, are both associated with a same date or entity name, the first sentence fragment and the second sentence fragment each comprising two or more like-words found in both the first sentence fragment and the second sentence fragment and one or more dissimilar-words found in only one of the first sentence fragment or the second sentence fragment;

aligning the like-words in the first sentence fragment with the like-words in the second sentence fragment;

determining that the alignment satisfies a threshold frequency value; and

in response to determining that the alignment satisfies the threshold frequency value, extracting the dissimilar-words from the first sentence fragment and the dissimilar-words from the second sentence fragment; and

outputting the index of paraphrases after the extracting, the index identifying the dissimilar-words from the first sentence fragment as paraphrasing the dissimilar-words from the second sentence fragment.

41. The article of claim 40, wherein the operations further implement a search engine, the operations further comprising:

receiving web search queries that include the dissimilar-words from the second sentence fragment;

accessing the index of paraphrases;

determining, from the index of paraphrases, that the dissimilar-words from the first sentence fragment paraphrase the dissimilar-words from the second sentence fragment; and

searching for electronic documents responsive to the web search queries using at least the dissimilar-words from the first sentence fragment.

42. The article of claim 40, wherein the first sentence fragment and the second sentence fragment are identified using one or more lexico-syntactic extraction patterns.

43. The article of claim 42, wherein the lexico-syntactic extraction patterns are set up to identify sentence fragments containing verbs.

44. The article of claim 40, wherein the operations further comprise summarizing a text or a document, including identifying duplicative sentences that say a same thing but in a different way.

45. The article of claim 40, wherein the operations further comprise determining that the alignment satisfies a criterion that embodies a likelihood that the dissimilar-words in the first sentence fragment are paraphrases of the dissimilar-words in the second sentence fragment.

46. The article of claim 45, wherein the criterion is a threshold requirement that at least three non-stop dissimilar-words in the first sentence fragment are aligned with three non-stop dissimilar-words in the second sentence fragment.

47. The article of claim 40, wherein the index of paraphrases further comprises a frequency of occurrence value that characterizes how often the dissimilar-words from the first sentence fragment paraphrase the dissimilar-words from the second sentence fragment.

48. The article of claim 40, wherein operations performed by the paraphrase engine further comprise:

generating a list of potential paraphrase pairs by repeatedly identifying sentence fragments that, in the text of one or more electronic documents, are both associated with a same date or entity name, aligning like-words in the sentence fragments, determining that the alignment satisfies the threshold frequency value, and, in response to determining that the alignment satisfies the threshold frequency value, extracting dissimilar-words from the sentence fragments;

determining a frequency at which the dissimilar-words extracted from the sentence fragments appear in the list of potential paraphrase pairs; and

discarding dissimilar-words that do not meet a threshold frequency value.

49. The article of claim 48, wherein the dissimilar-words extracted from the sentence fragments are ranked in the index of paraphrases according to the frequency at which the dissimilar-words extracted appear in the list of potential paraphrase pairs.

50. The article of claim 40, wherein the operations further comprise parsing the identified sentences fragments into words.

51. The article of claim 40, wherein the operations further comprise aligning special characters or punctuation marks in the first sentence fragment with special characters or punctuation marks in the second sentence fragment.