Longest-common-subsequence detection for common synonyms

• US 8,001,136 B1
• Filed: 07/02/2008
• Issued: 08/16/2011
• Est. Priority Date: 07/10/2007
• Status: Expired due to Fees

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Papachristou, Dimitra, Baker, Steven D.
• Primary Examiner(s): Abel-Jalil; Neveen
• Assistant Examiner(s): MINCEY, JERMAINE A
• Application Number:
  US12/166,700
• Time in Patent Office: 1,140 Days
• Field of Search: None
• US Class Current: 707/758
• CPC Class Codes: G06F 16/36 Creation of semantic tools, e.g. ontology or thesauri

Abstract

One embodiment of the present invention provides a system for identifying synonym candidates. During operation, the system receives a first term and a second term. The system then determines a length of the longer one of the first and second terms, and determines a longest common subsequence of the two terms. The system further produces a result to indicate whether the two terms are synonym candidates based on the length of the longer term and a length of the longest common subsequence of the two terms.

Claims

1. A method for identifying synonym candidates, the method comprising:

receiving a first term and a second term;

identifying, using one or more processors, a longest subsequence that is common to the first term and the second term;

determining which of the first term and the second term are longer;

determining a ratio between a length of the longest subsequence and a length of the longer of the first term and the second term; and

determining that the ratio between the length of the longest subsequence and the length of the longer of the first term and the second term meets a first threshold;

computing an edit distance between the first term and the second term;

comparing the edit distance to a second threshold;

determining that the edit distance meets the second threshold; and

designating the first term and the second term as synonym candidates based on determining that the ratio between the length of the longest subsequence and the length of the longer of the first term and the second term meets the first threshold and based on determining that the edit distance meets the second threshold.

2. The method of claim 1, further comprising:

determining a length of the longer of the first and second terms.

3. The method of claim 1, wherein computing an edit distance between the first term and the second term is based on determining that the ratio between the length of the longest subsequence and the length of the longer of the first term and the second term meets the first threshold.

10. The method of claim 1, wherein the first term and the second term are designated as synonym candidates without determining a ratio between the length of the longest subsequence and the length of the shorter of the first term and the second term.

11. The method of claim 1, wherein the first term and the second term have different lengths.

4. A computer system for identifying synonym candidates, the computer system comprising:

one or more processors; and

a computer-readable storage device storing instructions that, when executed by the one or more processors, cause the one or more processors to perform operations comprising;

receiving a first term and a second term;

identifying a longest subsequence that is common to the first term and the second term;

determining which of the first term and the second term are longer;

determining a ratio between a length of the longest subsequence and a length of the longer of the first term and the second term; and

determining that the ratio between the length of the longest subsequence and the length of the longer of the first term and the second term meets a first threshold;

computing an edit distance between the first term and the second term;

comparing the edit distance to a second threshold;

determining that the edit distance meets the second threshold; and

designating the first term and the second term as synonym candidates based on determining that the ratio between the length of the longest subsequence and the length of the longer of the first term and the second term meets the first threshold and based on determining that the edit distance meets the second threshold.

5. The computer system of claim 4, wherein the operations further comprise:

determining a length of the longer of the first and second terms.

6. The computer system of claim 4, wherein computing an edit-distance between the first term and the second term is based on determining that the ratio between the length of the longest subsequence and the length of the longer of the first term and the second term meets the first threshold.

12. The system of claim 4, wherein the first term and the second term are designated as synonym candidates without determining a ratio between the length of the longest subsequence and the length of the shorter of the first term and the second term.

13. The system of claim 4, wherein the first term and the second term have different lengths.

7. A computer readable storage device storing instructions that, when executed by a computer system, cause the computer system to perform operations comprising:

receiving a first term and a second term;

identifying a longest subsequence that is common to the first term and the second term;

determining which of the first term and the second term are longer;

determining a ratio between a length of the longest subsequence and a length of the longer of the first term and the second term; and

determining that the ratio between the length of the longest subsequence and the length of the longer of the first term and the second term meets a first threshold;

computing an edit distance between the first term and the second term;

comparing the edit distance to a second threshold;

determining that the edit distance meets the second threshold; and

designating the first term and the second term as synonym candidates based on determining that the ratio between the length of the longest subsequence and the length of the longer of the first term and the second term meets the first threshold and based on determining that the edit distance meets the second threshold.

8. The computer readable storage device of claim 7, wherein the operations further comprise:

determining a length of the longer of the first and second terms.

9. The computer readable storage device of claim 7, wherein computing an edit distance between the first term and the second term is based on determining that the ratio between the length of the longest subsequence and the length of the longer of the first term and the second term meets the first threshold.

14. The storage device of claim 7, wherein the first term and the second term are designated as synonym candidates without determining a ratio between the length of the longest subsequence and the length of the shorter of the first term and the second term.

15. The storage device of claim 7, wherein the first term and the second term have different lengths.