# US 8,280,893 B1 · Methods and systems for identifying paraphrases from an index of information items and associated sentence fragments

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 8,280,893 B1
- Document ID: US8280893B1
- Status: Granted
- Kind: B1
- Application number: 13/098,669
- Filed: 2011-05-02
- Granted: 2012-10-02
- Earliest claimed: 2005-03-23
- Assignees: Google Inc.
- Inventors: Alexandru Marius Pasca; Peter Szabolcs Dienes
- Web page: https://patentgrep.com/patent/US8280893B1

## CPC

- G06F 40/247: Thesauruses; Synonyms
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## 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

### Claim 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.

### Claim 2 (depends on 1)

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.

### Claim 3 (depends on 2)

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

### Claim 4 (depends on 1)

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.

### Claim 5 (depends on 4)

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

### Claim 6 (depends on 1)

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.

### Claim 7 (depends on 1)

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.

### Claim 8 (depends on 7)

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.

### Claim 9 (depends on 1)

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.

### Claim 10 (depends on 1)

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.

### Claim 11 (depends on 10)

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.

### Claim 12 (depends on 1)

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

### Claim 13 (depends on 1)

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.

### Claim 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.

### Claim 15 (depends on 14)

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.

### Claim 16 (depends on 14)

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.

### Claim 17 (depends on 16)

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

### Claim 18 (depends on 14)

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.

### Claim 19 (depends on 14)

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.

### Claim 20 (depends on 19)

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.

### Claim 21 (depends on 14)

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.

### Claim 22 (depends on 14)

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.

### Claim 23 (depends on 14)

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

### Claim 24 (depends on 14)

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.

### Claim 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.

### Claim 26 (depends on 25)

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.

### Claim 27 (depends on 25)

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.

### Claim 28 (depends on 25)

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.

### Claim 29 (depends on 28)

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

### Claim 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.

### Claim 31 (depends on 30)

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.

### Claim 32 (depends on 30)

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.

### Claim 33 (depends on 30)

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.

### Claim 34 (depends on 33)

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

### Claim 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.

### Claim 36 (depends on 35)

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.

### Claim 37 (depends on 35)

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.

### Claim 38 (depends on 35)

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.

### Claim 39 (depends on 38)

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

### Claim 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.

### Claim 41 (depends on 40)

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.

### Claim 42 (depends on 40)

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.

### Claim 43 (depends on 42)

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

### Claim 44 (depends on 40)

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.

### Claim 45 (depends on 40)

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.

### Claim 46 (depends on 45)

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.

### Claim 47 (depends on 40)

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.

### Claim 48 (depends on 40)

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.

### Claim 49 (depends on 48)

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.

### Claim 50 (depends on 40)

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

### Claim 51 (depends on 40)

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.
