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

• US 7,937,396 B1
• Filed: 03/23/2005
• Issued: 05/03/2011
• 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:
  US11/087,446
• Time in Patent Office: 2,232 Days
• Field of Search: 707/6
• 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 machine-implemented method comprising:

identifying, in a machine-readable index, a first sentence fragment and a second sentence fragment that are both associated with a same first information item, wherein the first information item is one of a date, an entity name, and a concept, wherein the index comprises a plurality of information items and sentence fragments associated with respective of the information items;

in response to identifying that the first sentence fragment and the second sentence fragment are both associated with the same first information item, identifying a paraphrase pair in the first and second sentence fragments;

repeating the identifying of the first sentence fragment and the second sentence fragment and the identifying of the paraphrase pair to identify a plurality of paraphrase pairs; and

determining a frequency of occurrence value for each of the paraphrase pairs, wherein the frequency of occurrence value embodies the frequency at which each paraphrase pair appears in the plurality of paraphrase pairs,

wherein

the paraphrase pair comprises a first paraphrase and a second paraphrase,

the first paraphrase comprises a proper subset of the words in the first sentence fragment,

the second paraphrase comprises a proper subset of the words in the second sentence fragment,

the first paraphrase and the second paraphrase are in a same language, have a same or a similar meaning, and are not identical, and

the first and second sentence fragments and the paraphrase pair are identified by one or more data processors that perform actions under the instruction of computer-readable instructions.

2. The method of claim 1, wherein the first information item is an entity name.

3. The method of claim 2, wherein the entity name comprises at least one of a name of a person, a name of a place, and a name of an organization.

4. The method of claim 1, wherein:

the first sentence fragment and the second sentence fragment each comprises a plurality of tokens; and

identifying the paraphrase pair comprises;

aligning the first sentence fragment and the second sentence fragment to match tokens in the first sentence fragment with tokens in the second sentence fragment;

identifying one or more tokens in the first sentence fragment that are dissimilar to one or more tokens in the second sentence fragment; and

identifying the paraphrase pair from the dissimilar tokens.

5. The method of claim 1, further comprising:

identifying a subset of the plurality of paraphrase pairs having a frequency of occurrence value above a threshold; and

adding the subset of the plurality of paraphrase pairs to a machine-readable data collection.

6. A machine-implemented method comprising:

identifying a collection of paraphrase pairs from a machine-readable index that associates information items and sentence fragments, wherein the information items are each one of a date, an entity name, and a concept;

determining a frequency of occurrence value for a first paraphrase pair of the collection of paraphrase pairs, wherein the frequency of occurrence value embodies the frequency at which the first paraphrase pair appears in the collection; and

adding the first paraphrase pair to the machine-readable index based at least in part on the frequency of occurrence value meeting a criterion,

wherein

each paraphrase pair comprises a first paraphrase and a second paraphrase,

the first paraphrase comprises a proper subset of the words in a first sentence fragment,

the second paraphrase comprises a proper subset of the words in a second sentence fragment,

each of the first paraphrase and the second paraphrase in a paraphrase pair are in a same language, have a same or a similar meaning, and are not identical, and

the collection of paraphrase pairs are identified, the frequency of occurrence value is determined, and the first paraphrase pair is added to the machine-readable index by one or more data processors that perform actions under the instruction of computer-readable instructions.

7. The method of claim 6, wherein:

the sentence fragments each comprise a plurality of tokens; and

identifying the collection of paraphrase pairs comprises;

aligning a first sentence fragment and a second sentence fragment to match tokens in the first sentence fragment with tokens in the second sentence fragment;

identifying one or more tokens in the first sentence fragment that are dissimilar to one or more tokens in the second sentence fragment; and

identifying the paraphrase pair from the dissimilar tokens.

8. The method of claim 6, further comprising:

determining a second frequency of occurrence value for a second paraphrase pair; and

adding the second paraphrase pair to the machine-readable index based at least in part on the frequency of occurrence value meeting the criterion.

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

identifying, in a machine-readable index, a first sentence fragment and a second sentence fragment that are both associated with a same first information item, wherein the first information item is one of a date, an entity name, and a concept, wherein the index comprises a plurality of information items and sentence fragments associated with respective of the information items;

in response to the identifying that the first sentence fragment and the second sentence fragment are both associated with the same first information item, identifying a paraphrase pair in the first and second sentence fragments;

repeating the identifying of the first sentence fragment and the second sentence fragment and the identifying of the paraphrase pair to identify a plurality of paraphrase pairs; and

determining a frequency of occurrence value for each of the paraphrase pairs, wherein the frequency of occurrence value embodies the frequency at which each paraphrase pair appears in the plurality of paraphrase pairs,

wherein

the paraphrase pair comprises a first paraphrase and a second paraphrase,

the first paraphrase comprises a proper subset of words in the first sentence fragment,

the second paraphrase comprises a proper subset of words in the second sentence fragment, and

the first paraphrase and the second paraphrase are in a same language, have a same or a similar meaning, and are not identical.

10. The article of claim 9, wherein:

the first sentence fragment and a second sentence fragment each comprises a plurality of tokens; and

identifying the paraphrase pair comprises;

aligning the first sentence fragment and a second sentence fragment to match tokens in the first sentence fragment with tokens in the second sentence fragment;

identifying one or more tokens in the first sentence fragment that are dissimilar to one or more tokens in the second sentence fragment; and

identifying the paraphrase pair from the dissimilar tokens.

11. The article of claim 9, wherein the operations further comprise:

identifying a subset of the plurality of paraphrase pairs having a frequency of occurrence value above a threshold; and

adding the subset of the plurality of paraphrase pairs to a machine-readable data collection.

12. 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 a collection of paraphrase pairs from a machine-readable index that associates information items and sentence fragments, wherein the information items are each one of a date, an entity name, and a concept;

determining a frequency of occurrence value for a first paraphrase pair of the collection of paraphrase pairs, wherein the frequency of occurrence value embodies the frequency at which the first paraphrase pair appears in the collection;

adding the first paraphrase pair to the machine-readable index based at least in part on the frequency of occurrence value meeting a criterion,

wherein

each paraphrase pair comprises a first paraphrase and a second paraphrase,

the first paraphrase comprises a proper subset of words in a first sentence fragment in the index,

the second paraphrase comprises a proper subset of words in a second sentence fragment in the index, and

each of the first paraphrase and the second paraphrase in a paraphrase pair are in a same language, have a same or a similar meaning, and are not identical.

13. A machine-implemented method comprising:

identifying a first sentence fragment and a second sentence fragment, each sentence fragment comprising a plurality of tokens and each sentence fragment associated with a same information item in a machine-readable index;

aligning the first sentence fragment and the second sentence fragment so that tokens in the first sentence fragment match tokens in the second sentence fragment;

determining a number of matched non-stop tokens in the aligned first and second sentence fragments;

determining a number of dissimilar tokens in the aligned first and second sentence fragments; and

identifying a paraphrase pair in the dissimilar tokens based at least in part on the number of matched non-stop tokens and the number of dissimilar tokens, wherein paraphrases in the paraphrase pair are in a same language,

wherein the sentence fragments are identified and aligned, the number of matched non-stop tokens and the number of dissimilar tokens are determined, and the paraphrase pair is identified by one or more data processors that perform actions under the instruction of computer-readable instructions.

14. The method of claim 13, further comprising:

repeating the identifying of the first sentence fragment and the second sentence fragment, the aligning, the determining of the number of matched non-stop tokens, the determining of the number of dissimilar tokens, and the identifying of the paraphrase pair to identify a plurality of paraphrase pairs;

determining a frequency of occurrence value for each of the paraphrase pairs in the plurality of paraphrase pairs, wherein the frequency of occurrence value embodies the frequency at which each paraphrase pair appears in the collection;

identifying a subset of the plurality of paraphrase pairs, wherein each paraphrase pair in the subset has a frequency of occurrence value that is above a criteria; and

adding the subset of the plurality of paraphrase pairs to a machine-readable index.

15. A machine-implemented method comprising:

accessing an index that includes a collection of index entries, wherein each of the index entries comprises a sentence fragment and an associated date;

repeatedly selecting, from the index, first index entries comprising a date and second index entries comprising the same first date;

identifying whether first portions of first sentence fragments from the first index entries paraphrase second portions of second sentence fragments from the second index entries, including

determining a frequency of occurrence value for each first portion and second portion in the selected index entries, wherein the frequency of occurrence value embodies the frequency at which the first portions and the second portions are in the sentence fragments of the selected index entries and

identifying a subset of the first portions and the second portions having a frequency of occurrence value above a threshold; and

in response to identifying that the first portions paraphrase the second portions, storing the first portions and the second portions in a machine-readable data collection,

wherein;

the index is accessed, the index entries are selected, whether the first portions are identified as paraphrasing the second portions, and the first and second portions are stored by one or more data processors that perform actions under instruction of computer-readable instructions; and

paraphrases are in a same language, have a same or a similar meaning, and are not identical.