FUZZY MATCHING AND SCORING BASED ON DIRECT ALIGNMENT

• US 20120143593A1
• Filed: 12/07/2010
• Published: 06/07/2012
• Est. Priority Date: 12/07/2010
• Status: Abandoned Application

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Wu, Enyuan, Michael, Alan K., Oh, Beom Seok, Uehara, Shusuke, O'Donnell, Kevin S.
• Application Number:
  US12/961,878
• Publication Number:
  US 20120143593A1
• Time in Patent Office: Days
• US Class Current: 704/2
• CPC Class Codes: G06F 40/47 Machine-assisted translation, e.g. using translation memory

Abstract

Various embodiments provide a translation memory system that utilizes sentence-level fuzzy matching and a scoring algorithm based on direct alignment. In one or more embodiments, a fuzzy match scoring formula includes use of an edit operation definition to define various deductions that are computed as part of an overall score, an overall scoring algorithm, and word-level scoring and partial match definitions. A direct alignment algorithm finds a computed alignment between two sentences using a pair-wise difference matrix associated with a primary sentence and a comparison sentence. An overall algorithm identifies editing operations such as replacements, position swaps and adjustments for a final score calculation. Once final scores are calculated between the primary sentence and multiple comparison sentences, a primary/comparison sentence pair can be selected, based on the score, to serve as a basis for translating the primary sentence.

Claims

1. A computer-implemented method comprising:

conducting a direct alignment operation to ascertain anchor points between a primary sentence for which a translation is sought and a comparison sentence for which a translation exists;

finding changes between anchor points in the primary and comparison sentences;

finding moves between the primary and comparison sentences, wherein changes and moves constitute deductions that are utilized to calculate a final score for the primary and comparison sentences; and

using the changes and the moves to calculate an overall score for the primary and comparison sentences.

2. The computer-implemented method of claim 1, wherein the primary and comparison sentences are comprised of tokens, wherein tokens comprise the following token types:

word, tag, number, punctuation marks, or delimiter.

3. The computer-implemented method of claim 1, wherein conducting the direct alignment operation comprises utilizing a two-dimensional array to store edit differences for token pairs associated with the primary and comparison sentences, and at least to find said anchor points.

4. The computer-implemented method of claim 1, wherein conducting the direct alignment operation comprises utilizing a two-dimensional array to store edit differences for token pairs associated with the primary and comparison sentences, and at least to find said anchor points, wherein the two-dimensional array is configured to have entries associated with partial matches between the primary and comparison sentences.

5. The computer-implemented method of claim 1, wherein conducting the direct alignment operation comprises utilizing a two-dimensional array to store edit differences for token pairs associated with the primary and comparison sentences, and at least to find said anchor points, wherein the two-dimensional array is configured to have entries associated with partial matches between the primary and comparison sentences, and wherein the partial matches can comprise a 50% partial match or a 70% partial match between the primary and comparison sentences.

6. The computer-implemented method of claim 1, wherein conducting the direct alignment operation comprises:

utilizing a two-dimensional array to store edit differences for token pairs associated with the primary and comparison sentences, and at least to find said anchor points; and

finding a path from an upper left corner of the two-dimensional array to the lower right corner of the two-dimensional array, said path constituting a least token-to-token comparison.

7. The computer-implemented method of claim 1, wherein conducting the direct alignment operation comprises:

utilizing a two-dimensional array to store edit differences for token pairs associated with the primary and comparison sentences, and at least to find said anchor points; and

finding a path through the two-dimensional array, said path constituting a least token-to-token comparison, wherein a default direction for the path is a diagonal direction.

8. The computer-implemented method of claim 1, wherein using the changes and moves to calculate an overall score comprises calculating an overall score in accordance with the following formula:

Overall score=(total token count—

total deductions)/(total token count),

where “

total token count”

is the total token count for the primary sentence and “

total deductions”

takes into account at least the number of moves and the number of changes.

9. The computer-implemented method of claim 1, wherein using the changes and moves to calculate an overall score comprises calculating an overall score in accordance with the following formula:

Overall score=(total token count−

total deductions)/(total token count),

where “

total token count”

is the total token count for the primary sentence and “

total deductions”

takes into account at least the number of moves, the number of changes, word inserts and punctuation inserts.

10. The computer-implemented method of claim 1, wherein the primary and comparison sentences both comprise English sentences.

11. One or more computer readable storage media embodying computer readable instructions which, when executed, implement a method comprising:

building a two-dimensional array that is to serve as a basis for token-to-token comparison between a primary sentence for which a translation is sought and a comparison sentence for which a translation exists, wherein the two-dimensional array includes individual values associated with matches between tokens of the primary and comparison sentences; and

finding a path through the array with a least token-to-token comparison, wherein said path defines one or more anchor points between tokens of the primary and comparison sentences.

12. The one or more computer readable storage media of claim 11, wherein tokens comprise one of the following token types:

word, tag, number, punctuation marks, or delimiter.

13. The one or more computer readable storage media of claim 11, wherein the two-dimensional array is configured to have entries associated with partial matches between the primary and comparison sentences.

14. The one or more computer readable storage media of claim 11 further comprising finding one or more changes between anchor points in the primary and comparison sentences and assigning deductions for any found changes.

15. The one or more computer readable storage media of claim 11 further comprising finding one or more moves between the primary and comparison sentences, and assigning deductions for any found moves.

16. The one or more computer readable storage media of claim 11 further comprising calculating an overall score for the primary and comparison sentences in accordance with the following formula:

Overall score=(total token count−

total deductions)/(total token count),

where “

total token count”

is the total token count for the primary sentence and “

total deductions”

takes into account deductions associated with edit actions between the primary and comparison sentences.

17. The one or more computer readable storage media of claim 11 further comprising calculating an overall score for the primary and comparison sentences in accordance with the following formula:

Overall score=(total token count−

total deductions)/(total token count),

where “

total token count”

is the total token count for the primary sentence and “

total deductions”

takes into account deductions associated with edit actions between the primary and comparison sentences, wherein edit actions include insert actions.

18. The one or more computer readable storage media of claim 11 further comprising calculating an overall score for the primary and comparison sentences in accordance with the following formula:

Overall score=(total token count−

total deductions)/(total token count),

where “

total token count”

is the total token count for the primary sentence and “

total deductions”

takes into account deductions associated with edit actions between the primary and comparison sentences, wherein edit actions include insert actions, wherein edit actions include change actions.

19. The one or more computer readable storage media of claim 11 further comprising calculating an overall score for the primary and comparison sentences in accordance with the following formula:

Overall score=(total token count−

total deductions)/(total token count),

where “

total token count”

is the total token count for the primary sentence and “

total deductions”

takes into account deductions associated with edit actions between the primary and comparison sentences, wherein edit actions include insert actions, wherein edit actions include move actions.

20. The one or more computer readable storage media of claim 11 further comprising calculating an overall score for the primary and comparison sentences in accordance with the following formula:

Overall score=(total token count−

total deductions)/(total token count),

where “

total token count”

is the total token count for the primary sentence and “

total deductions”

takes into account deductions associated with edit actions between the primary and comparison sentences, wherein edit actions include insert actions, wherein edit actions include insert actions, change actions and move actions.