Patent ID: 7672830

Claim:
A method for aligning words of natural language sentences which ensures a proper N:M alignment between source and target words by satisfying coverage and transitive closure, comprising: receiving a corpus of aligned source sentences f=f 1 . . . f i . . . f l composed of source words f 1 , . . . f l , and target sentences e=e 1 . . . e j . . . e J composed of target words e 1 , . . . e J ; the source sentences being in a first natural language and the target sentences being in a second natural language; with a processor producing a translation matrix M with association measures m ij ; each association measure m ij in the translation matrix providing a valuation of association strength between each source word f i and each target word e j ; producing one or more of an alignment matrix A and cepts that link aligned source and target words, including performing orthogonal non-negative matrix factorization of the translation matrix M, ensuring that the one or more of the alignment matrix and cepts defines a proper N:M alignment between source and target words by satisfying coverage and transitive closure; wherein coverage is satisfied when each source word is aligned with at least one target word and each target word is aligned to at least one source word; and wherein transitive closure is satisfied if when source word f i is aligned to target words e j and e l , and source word f k is aligned to target word e l , then source word f k is also aligned to target word e j .