System and method of providing machine translation from a source language to a target language

1. A method comprising:

selecting, via a processor using a lexical classifier, a bag of target language n-grams associated with a source language sentence, wherein the bag of target language n-grams comprises a beginning n-gram having a start token in a first word position, and an ending n-gram having an end token in a second word position, the end token connecting a history node to a final state node;

combining the bag of target language n-grams to yield an n-gram network;

ranking N strings in the n-gram network using a language model to yield an n-best list of target sentences; and

generating, via the processor, a target sentence based on the n-best list.

2. The method of claim 1 , wherein the lexical classifier generates a classification score for each of a plurality of n-grams in a set of training data.

3. The method of claim 2 , wherein the N strings are represented by a finite state acceptor composed with the language model.

4. The method of claim 3 , wherein the finite state acceptor generates the n-best list of target sentences by combining the classification score for each of the plurality of n-grams and a respective language model score.

5. The method of claim 3 , wherein the finite state acceptor comprises two nodes, wherein each of the two nodes is connected to another node with an edge that represents an n-gram.

6. The method of claim 5 , wherein each of the two nodes represents an n−1 length word history, and wherein the edge is labeled with a word that follows the n−1 length word history.

7. The method of claim 6 , wherein a lower order-gram is used to connect the two nodes.

8. The method of claim 7 , wherein the edge indicates what order n-gram it represents.

9. A system comprising:

a processor; and

a computer readable storage medium storing instructions which, when executed by the processor, cause the processor to perform a method comprising:

receiving a source language sentence;

selecting, via a lexical classifier, a set of target language n-grams associated with the source language sentence, wherein the bag of target language n-grams comprises a beginning n-gram having a start token in a first word position, and an ending n-gram having an end token in a second word position, the end token connecting a history node to a final state node;

combining the set of target language n-grams to yield an n-gram network;

ranking N strings in the n-gram network using a language model to yield an n-best list of target sentences; and

generating a target sentence based on the n-best list.

10. The system of claim 9 , wherein the lexical classifier generates a classification score for each of a plurality of n-grams in a set of training data.

11. The system of claim 10 , wherein the N strings are represented by a finite state acceptor composed with the language model, and wherein the finite state acceptor generates the n-best list of target sentences by combining the classification score for each of the plurality of n-grams and a respective language model score.

12. The system of claim 11 , further comprising generating the n-best list of target sentences by combining the classification score for each of the plurality of n-grams and a plurality of language model scores generated by the language model used to compose the finite state acceptor.

13. The system of claim 11 , wherein the finite state acceptor comprises two nodes, wherein each of the two nodes is connected to another node with an edge that represents an n-gram.

14. The system of claim 13 , wherein each of the two nodes represents an n−1 length word history, and wherein the edge is labeled with a word that follows the n−1 length word history.

15. The system of claim 14 , wherein a lower order-gram is used to connect the two nodes.

16. The system of claim 15 , wherein the edge indicates what order n-gram it represents.

17. A computer-readable storage device having instructions stored which, when executed by a computing device, causes the computing device to perform operations comprising:

receiving a source language sentence;

selecting, via a lexical classifier, a bag of target language n-grams associated with the source language sentence, wherein the bag of target language n-grams comprises a beginning n-gram having a start token in a first word position, and an ending n-gram having an end token in a second word position, the end token connecting a history node to a final state node;

combining the bag of target language n-grams to yield an n-gram network;

ranking N strings in the n-gram network using a language model to yield an n-best list of target sentences; and

generating a target sentence based on the n-best list.

18. The computer-readable storage device of claim 17 , wherein the lexical classifier generates a classification score for each of a plurality of n-grams in a set of training data.

19. The computer-readable storage device of claim 18 , wherein the N strings are represented by a finite state acceptor composed with the language model.

20. The computer-readable storage device of claim 19 , further comprising generating the n-best list of target sentences by combining the classification score for each of the plurality of n-grams and a respective language model score.

21. The computer-readable storage device of claim 19 , wherein the finite state acceptor comprises two nodes, wherein each of the two nodes is connected to another node with an edge that represents an n-gram.

22. The computer-readable storage device of claim 21 , wherein each of the two nodes represents an n−1 length word history, and wherein the edge is labeled with a word that follows the n−1 length word history.

23. The computer-readable storage device of claim 22 , wherein a lower order-gram is used to connect the two nodes.

24. The computer-readable storage device of claim 23 , wherein the edge indicates what order n-gram it represents.