Patent Document ID: 9460086
Application ID: 14759209

Base Claim:
1. A method for performing bilingual word alignment on source and target text in bilingual documents, the method comprising: computing probability gains of adding a link between any pair of source and target words in the source and target text; applying a greedy algorithm to iteratively search for a plurality of word alignments that satisfy an inversion transduction grammar constraint, wherein applying the greedy algorithm includes: initializing a pending list; generating a local list by performing an expanding operation to each word alignment in the pending list, and adding to the local list new word alignments that satisfy the inversion transduction grammar constraint; determining whether to update the lists after each iteration according to whether the pending list is empty; and outputting the best alignment from the word alignments in the local list; and outputting a best word alignment among the plurality as a final alignment result.

---

Claim 6:
6. The method claim 1 , wherein outputting the best word alignment includes measuring quality of a word alignment as a product of (a) all probability values Π(j,i) p(f j , e i ) that are members of set a, and for any pair of f j and e i that have a link between them, and (b) all probability values Π(i) p(ε, e i ) that are not members of set a, and for any source word that is not aligned to any word, and (c) all probability values Π(j) p(f j , ε) that are not members of set a, for any target word that is not aligned to any word, where p(f j , e i ) is a probability of e i that is aligned to f j ; p(ε, e i ) is a probability of e i that is not aligned to any word; and p(f j , ε) is a probability of f j that is not aligned to any word, whereby ∏ ( j , i ) ∈ a ⁢ p ⁡ ( f j , e i ) × ∏ i ∉ a ⁢ p ⁡ ( ε , e i ) × ∏ j ∉ a ⁢ p ⁡ ( f j ❘ ε ) .