Automatic extraction of transfer mappings from bilingual corpora

• US 7,734,459 B2
• Filed: 07/05/2001
• Issued: 06/08/2010
• Est. Priority Date: 06/01/2001
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Menezes, Arul A., Richardson, Stephen D.
• Primary Examiner(s): Vo; Huyen X.
• Application Number:
  US09/899,554
• Publication Number:
  US 20030061023A1
• Time in Patent Office: 3,260 Days
• Field of Search: 704 1- 10, 704/277, 707 1- 10
• US Class Current: 704/5
• CPC Class Codes: G06F 40/45 Example-based machine translation; Alignment

Abstract

A method of aligning nodes of dependency structures obtained from a bilingual corpus includes a two-phase approach wherein a first phase comprises associating nodes of the dependency structures to form tentative correspondences. The nodes of the dependency structures are then aligned as a function of the tentative correspondences and structural considerations. Mappings are obtained from the aligned dependency structures. The mappings can be expanded with varying types and amounts of local context in order that a more fluent translation can be obtained when translation is performed.

Claims

1. A computer-implemented method of associating dependency structures from two different languages on a tangible computer readable medium, wherein the dependency structures comprise nodes organized in a hierarchical parent/child structure, the computer-implemented method comprising:

associating nodes of the dependency structures with a computer to form tentative correspondences on the tangible medium, wherein associating includes forming tentative correspondences comprising translations of morphological bases and derivations;

aligning nodes of the dependency structures as a function of at least one of eliminating at least one of the tentative correspondences and structural considerations on the tangible medium, wherein aligning does not require beginning with either a top or bottom node of the hierarchical parent/child structure of the dependency structures; and

providing an output from the computer indicative of the alignment of the dependency structures.

2. The computer-implemented method of claim 1 wherein associating includes forming tentative correspondences comprising direct translations.

3. The computer-implemented method of claim 1 wherein associating includes forming tentative correspondences comprising bases and derived forms of translations.

4. The computer-implemented method of claim 1 wherein associating includes forming tentative correspondences between nodes wherein one of the nodes comprises more lexical elements than the other node.

5. The computer-implemented method of claim 4 wherein said one of the nodes is a single word in one of the languages and said other node comprises at least two words in the other language.

6. The computer-implemented method of claim 1 wherein aligning pursuant to structural considerations comprises aligning nodes as a function of a set of rules.

7. The computer-implemented method of claim 6 wherein each of the rules of the set of rules are applied to the dependency structures in a selected order.

8. The computer-implemented method of claim 7 wherein each of the dependency structures comprise a set of unaligned nodes and wherein each of the rules are applied successively to the set of unaligned nodes until a set of aligned nodes is identified, then the nodes of the set of aligned nodes are removed from the set of unaligned nodes and each of the rules of the set of rules is again applied successively to the set of unaligned nodes.

9. The computer-implemented method of claim 7 wherein one rule of the set of rules comprises aligning a set of nodes if a bidirectionally unique translation exists.

10. The computer-implemented method of claim 7 wherein one rule of the set of rules comprises aligning a pair of parent nodes, one from each dependency structure having a tentative correspondence to each other, if each child node of each respective parent node is already aligned to a child of the other parent node.

11. The computer-implemented method of claim 7 wherein one rule of the set of rules comprises aligning a pair of child nodes, one from each dependency structure, if a tentative correspondence exists between them and if a parent node of each respective child node is already aligned to a corresponding parent node of the other child.

12. The computer-implemented method of claim 7 wherein one rule of the set of rules comprises aligning a pair of nodes, one from each dependency structure, if respective parent nodes of the nodes under consideration are aligned with each other and respective child nodes are also aligned with each other.

13. The computer-implemented method of claim 7 wherein one rule of the set of rules comprises aligning a first verb node and an associated child node that is not a verb node from one dependency structure to a second verb node of the other dependency structure if the associated child node is already aligned with the second verb node, and either the second verb node has no aligned parent nodes, or the first verb node and the second verb node have associated child nodes aligned with each other.

14. The computer-implemented method of claim 7 wherein one rule of the set of rules comprises aligning a pair of nodes, one from each dependency structure, comprising the same part-of-speech, if there are no unaligned sibling nodes, and respective parent nodes are aligned, and linguistic relationships between the set of nodes under consideration and their respective parent nodes are the same.

15. The computer-implemented method of claim 7 wherein one rule of the set of rules comprises aligning a pair of nodes, one from each dependency structure, comprising the same part-of-speech, if respective child nodes are aligned with each other and the linguistic relationship between the set of nodes under consideration and their respective child nodes are the same.

16. The computer-implemented method of claim 7 wherein one rule of the set of rules comprises if an unaligned node of one of the dependency structures having immediate neighbor nodes comprising respective parent nodes, if any, and respective child nodes, if any, all aligned, and if exactly one of the immediate neighbor nodes is a non-compound word aligned to a node comprising a compound word, then align the unaligned node with the node comprising the compound word.

17. The computer-implemented method of claim 7 wherein one rule of the set of rules comprises aligning a pair of nodes, one from each dependency structure, comprising pronouns if respective parents are aligned with each other and neither of the nodes have unaligned siblings.

18. The computer-implemented method of claim 7 wherein one rule of the set of rules comprises aligning a pair of nodes, one from each dependency structure, comprising nouns if respective parents comprise nouns are aligned with each other and neither of the nodes have unaligned siblings, and where a linguistic relationship between each of the nodes and the respective parents comprise either a modifier relationship or a prepositional relationship.

19. The computer-implemented method of claim 7 wherein one rule of the set of rules comprises aligning a first verb node of one dependency structure to a second verb node of the other dependency structure if the first verb node has no tentative correspondences and a single associated child verb node that is already aligned to the second verb node.

20. The computer-implemented method of claim 7 wherein one rule of the set of rules comprises aligning a first verb node and a single, respective parent node of one dependency structure to a second verb node of the other dependency structure if the first verb node has no tentative correspondences and the single parent verb node is aligned with the second verb node, where the single parent verb node has no unaligned verb child nodes besides the first verb node, and the second verb node has no unaligned verb child nodes.

21. The computer-implemented method of claim 7 wherein one rule of the set of rules comprises aligning a first node comprising a pronoun of one dependency structure to a second node of the other dependency structure, if a parent node of the first node is aligned with the second node and the second node has no unaligned child nodes.

22. The computer-implemented method of claim 7 wherein one rule of the set of rules comprises aligning a first verb node and a respective parent node of one dependency structure to a second verb node of the other dependency structure if the first verb node has no tentative correspondences and the parent verb node is aligned with the second verb node and where the relationship between the first verb node and the parent verb node comprises a modal relationship.

23. A computer-implemented method of associating dependency structures from two different languages stored on a tangible computer readable medium, wherein the dependency structures comprise nodes organized in a parent/child structure, the computer-implemented method comprising:

aligning nodes of the dependency structures with correspondences on the tangible medium with a computer as a function of a set of rules comprising at least three different rules, wherein the dependency structures comprise a set of unaligned nodes and wherein after each of the rules are applied any aligned nodes are removed from the set of unaligned nodes before applying another rule, and wherein aligning does not require beginning with either a top or bottom node of the hierarchical parent/child structure of the dependency structures, and wherein aligning is not based on top-down processing or bottom-up processing of nodes; and

providing an output from the computer indicative of the alignment of the dependency structures.

24. The computer-implemented method of claim 23 wherein each of the rules of the set of rules are applied to the dependency structures in a selected order.

25. The computer-implemented method of claim 24 wherein the set of rules is applied successively to the set of unaligned nodes.

26. The computer-implemented method of claim 23 wherein later rule applications use an alignment created by an earlier rule application as a reference point that is used to disambiguate between competing alignments.

27. The computer-implemented method of claim 23 wherein one rule of the set of rules comprises aligning a set of nodes if a bidirectionally unique translation exists.

28. The computer-implemented method of claim 23 wherein one rule of the set of rules comprises aligning a pair of parent nodes, one from each dependency structure having a tentative correspondence to each other, if each child node of each respective parent node is already aligned to a child of the other parent node.

29. The computer-implemented method of claim 23 wherein one rule of the set of rules comprises aligning a pair of child nodes, one from each dependency structure, if a tentative correspondence exists between them and if a parent node of each respective child node is already aligned to a corresponding parent node of the other child.

30. The computer-implemented method of claim 23 wherein one rule of the set of rules comprises aligning a pair of nodes, one from each dependency structure, if respective parent nodes of the nodes under consideration are aligned with each other and respective child nodes are also aligned with each other.

31. The computer-implemented method of claim 23 wherein one rule of the set of rules comprises aligning a first verb node and an associated child node that is not a verb node from one dependency structure to a second verb node of the other dependency structure if the associated child node is already aligned with the second verb node, and either the second verb node has no aligned parent nodes, or the first verb node and the second verb node have associated child nodes aligned with each other.

32. The computer-implemented method of claim 23 wherein one rule of the set of rules comprises aligning a pair of nodes, one from each dependency structure, comprising the same part-of-speech, if there are no unaligned sibling nodes, and respective parent nodes are aligned, and linguistic relationships between the set of nodes under consideration and their respective parent nodes are the same.

33. The computer-implemented method of claim 23 wherein one rule of the set of rules comprises aligning a pair of nodes, one from each dependency structure, comprising the same part-of-speech, if respective child nodes are aligned with each other and the linguistic relationship between the set of nodes under consideration and their respective child nodes are the same.

34. The computer-implemented method of claim 23 wherein one rule of the set of rules comprises if an unaligned node of one of the dependency structures having immediate neighbor nodes comprising respective parent nodes, if any, and respective child nodes, if any, all aligned, and if exactly one of the immediate neighbor nodes is a non-compound word aligned to a node comprising a compound word, then align the unaligned node with the node comprising the compound word.

35. The computer-implemented method of claim 23 wherein one rule of the set of rules comprises aligning a pair of nodes, one from each dependency structure, comprising pronouns if respective parents are aligned with each other and neither of the nodes have unaligned siblings.

36. The computer-implemented method of claim 23 wherein one rule of the set of rules comprises aligning a pair of nodes, one from each dependency structure, comprising nouns if respective parents comprise nouns are aligned with each other and neither of the nodes have unaligned siblings, and where a linguistic relationship between each of the nodes and the respective parents comprise either a modifier relationship or a prepositional relationship.

37. The computer-implemented method of claim 23 wherein one rule of the set of rules comprises aligning a first verb node of one dependency structure to a second verb node of the other dependency structure if the first verb node has no tentative correspondences and a single associated child verb node that is already aligned to the second verb node.

38. The computer-implemented method of claim 23 wherein one rule of the set of rules comprises aligning a first verb node and a single, respective parent node of one dependency structure to a second verb node of the other dependency structure if the first verb node has no tentative correspondences and the single parent verb node is aligned with the second verb node, where the single parent verb node has no unaligned verb child nodes besides the first verb node, and the second verb node has no unaligned verb child nodes.

39. The computer-implemented method of claim 23 wherein one rule of the set of rules comprises aligning a first node comprising a pronoun of one dependency structure to a second node of the other dependency structure, if a parent node of the first node is aligned with the second node and the second node has no unaligned child nodes.

40. The computer-implemented method of claim 23 wherein one rule of the set of rules comprises aligning a first verb node and a respective parent node of one dependency structure to a second verb node of the other dependency structure if the first verb node has no tentative correspondences and the parent verb node is aligned with the second verb node and where the relationship between the first verb node and the parent verb node comprises a modal relationship.

41. A computer-implemented method of associating dependency structures from two different languages stored on a tangible computer readable medium, wherein the dependency structures comprise nodes organized in a hierarchical parent/child structure, the computer-implemented method comprising:

aligning nodes of the dependency structures with correspondences on the tangible medium with a computer as a function of a set of rules comprising at least two different rules where aligned nodes are determined based on the parent/child structure, and wherein aligning does not require beginning with either a top or bottom node of the hierarchical parent/child structure of the dependency structures, and wherein an order of aligning nodes is based on linguistic relevance, beginning with aligning nodes having more linguistic relevance than aligning nodes having less linguistic relevance; and

providing an output from the computer indicative of the alignment of the dependency structures.

42. The computer-implemented method of claim 41 wherein the dependency structures comprise a set of unaligned nodes and wherein after each of the rules are applied any aligned nodes are removed from the set of unaligned nodes before applying another rule.

43. The computer-implemented method of claim 41 wherein one rule of the set of rules comprises aligning a set of nodes if a bidirectionally unique translation exists.

44. The computer-implemented method of claim 41 wherein one rule of the set of rules comprises aligning a pair of parent nodes, one from each dependency structure having a tentative correspondence to each other, if each child node of each respective parent node is already aligned to a child of the other parent node.

45. The computer-implemented method of claim 41 wherein one rule of the set of rules comprises aligning a pair of child nodes, one from each dependency structure, if a tentative correspondence exists between them and if a parent node of each respective child node is already aligned to a corresponding parent node of the other child.

46. The computer-implemented method of claim 41 wherein one rule of the set of rules comprises aligning a pair of nodes, one from each dependency structure, if respective parent nodes of the nodes under consideration are aligned with each other and respective child nodes are also aligned with each other.

47. The computer-implemented method of claim 41 wherein one rule of the set of rules comprises aligning a first verb node and an associated child node that is not a verb node from one dependency structure to a second verb node of the other dependency structure if the associated child node is already aligned with the second verb node, and either the second verb node has no aligned parent nodes, or the first verb node and the second verb node have associated child nodes aligned with each other.

48. The computer-implemented method of claim 41 wherein one rule of the set of rules comprises aligning a pair of nodes, one from each dependency structure, comprising the same part-of-speech, if there are no unaligned sibling nodes, and respective parent nodes are aligned, and linguistic relationships between the set of nodes under consideration and their respective parent nodes are the same.

49. The computer-implemented method of claim 41 wherein one rule of the set of rules comprises aligning a pair of nodes, one from each dependency structure, comprising the same part-of-speech, if respective child nodes are aligned with each other and the linguistic relationship between the set of nodes under consideration and their respective child nodes are the same.

50. The computer-implemented method of claim 41 wherein one rule of the set of rules comprises if an unaligned node of one of the dependency structures having immediate neighbor nodes comprising respective parent nodes, if any, and respective child nodes, if any, all aligned, and if exactly one of the immediate neighbor nodes is a non-compound word aligned to a node comprising a compound word, then align the unaligned node with the node comprising the compound word.

51. The computer-implemented method of claim 41 wherein one rule of the set of rules comprises aligning a pair of nodes, one from each dependency structure, comprising pronouns if respective parents are aligned with each other and neither of the nodes have unaligned siblings.

52. The computer-implemented method of claim 41 wherein one rule of the set of rules comprises aligning a pair of nodes, one from each dependency structure, comprising nouns if respective parents comprise nouns are aligned with each other and neither of the nodes have unaligned siblings, and where a linguistic relationship between each of the nodes and the respective parents comprise either a modifier relationship or a prepositional relationship.

53. The computer-implemented method of claim 41 wherein one rule of the set of rules comprises aligning a first verb node of one dependency structure to a second verb node of the other dependency structure if the first verb node has no tentative correspondences and a single associated child verb node that is already aligned to the second verb node.

54. The computer-implemented method of claim 41 wherein one rule of the set of rules comprises aligning a first verb node and a single, respective parent node of one dependency structure to a second verb node of the other dependency structure if the first verb node has no tentative correspondences and the single parent verb node is aligned with the second verb node, where the single parent verb node has no unaligned verb child nodes besides the first verb node, and the second verb node has no unaligned verb child nodes.