TRANSLITERATION DECODING USING A TREE STRUCTURE

• US 20180173689A1
• Filed: 12/21/2016
• Published: 06/21/2018
• Est. Priority Date: 12/21/2016
• Status: Active Grant

• Current Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Original Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Inventors: Pino, Juan Miguel, Funiak, Stanislav, Malpani, Mridul, Lochan, Guarav
• Granted Patent: US 10,394,960 B2
• Time in Patent Office: Days
• CPC Class Codes: G06F 40/129 Handling non-Latin characters, e.g. kana-to-kanji conversion
• CPC Class Codes: G06F 40/44 Statistical methods, e.g. probability models

Abstract

Embodiments are disclosed for transliteration decoding using a tree structure. A method according to some embodiments includes steps of: generating a tree structure for an input string in a first script system, the tree structure including nodes representing segments of the input string; identifying segmentation candidates for the input string based on paths of the tree structure, the segmentation candidates segmenting the input string into character groups; selecting a segmentation candidate based on probabilities of the segmentation candidates predicted by a probabilistic model; segmenting the input string into character groups that correspond to characters in a second script system; decoding the character groups in the first script system into the characters in the second script system, the characters forming a word or a word prefix in the second script system; and outputting the word or the word prefix in the second script system.

Claims

1. A method for transliteration decoding using a tree structure, comprising:

generating a tree structure for an input string in a first script system, the tree structure including nodes representing segments of the input string;

identifying segmentation candidates for the input string based on paths of the tree structure, the segmentation candidates segmenting the input string into character groups;

selecting a segmentation candidate based on probabilities of the segmentation candidates predicted by a probabilistic model;

segmenting the input string into character groups that correspond to characters in a second script system;

decoding the character groups in the first script system into the characters in the second script system, the characters forming a word or a word prefix in the second script system; and

outputting the word or the word prefix in the second script system.

2. The method of claim 1, wherein the generating comprises:

generating a tree structure for an input string in a first script system, the tree structure including nodes representing phonemes of the input string;

3. The method of claim 1, wherein the identifying comprises:

identifying segmentation candidates for the input string based on paths of the tree structure, the segmentation candidates segmenting the input string into phonemes.

4. The method of claim 1, wherein the decoding comprises:

decoding the character groups in the first script system that is a Latin script system into the characters in the second script system that is a non-Latin script system, the characters forming a word or a word prefix in the second script system.

5. The method of claim 1, wherein the generating comprises:

identifying first-level nodes of the tree structure, the first-level nodes representing candidates of a first character group of the input string.

6. The method of claim 5, wherein the generating comprises:

identifying second-level nodes of the tree structure, the second-level nodes representing candidates of a second character group that follows the first character group in the input string.

7. The method of claim 1, wherein the generating comprises:

generating a tree structure for an input string in a first script system, the tree structure including paths that start at a root node of the tree structure and end at leaf nodes of the tree structure, the paths representing the segmentation candidates that segment the input string into character groups.

8. The method of claim 1, wherein the identifying comprises:

identifying segmentation candidates for the input string by exploring paths of the tree structure, the paths starting at a root node of the tree structure and ending at leaf nodes of the tree structure, the segmentation candidates segmenting the input string into character groups.

9. The method of claim 1, wherein the generating comprises:

generating a tree structure for an input string in a first script system, the tree structure including branches that start at a root node of the tree structure and end at nodes of the tree structure, the branches representing candidates of a prefix of the input string.

10. The method of claim 9, further comprising:

determining that a branch represent a specific prefix candidate of the input string having no transliteration possibility; and

abandoning paths associated with the branch for identifying segmentation candidates.

11. The method of claim 10, wherein the determining comprises

determining that a branch represent a specific prefix candidate of the input string and that no existing word in the second transcript system starts with a prefix that is a transliteration of the specific prefix candidate.

12. The method of claim 1, further comprising:

for a specific branch of the tree structure that starts at a root node of the tree structure and ends at a specific node, the specific branch representing a specific prefix of the input string, generating a probability that the specific prefix is segmented into character groups represented by nodes of the specific branch and the character groups are transliterated into another prefix in the second script system.

13. The method of claim 12, further comprising:

assigning the probability to the specific node of the tree structure.

14. The method of claim 13, further comprising:

for a second specific node that follows the specific node and locates at one level below the specific node, generating a probability assigned to the second specific node incrementally based on the probability assigned to the specific node.

15. The method of claim 12, further comprising:

assigning multiple probabilities to the specific node of the tree structure, the probabilities correspond to scenarios that the specific prefix is transliterated into different prefixes in the second script system.

16. The method of claim 15, further comprising:

ignoring some of the multiple probabilities by keeping a predetermined number of top candidates of scenarios having highest probabilities.

17. A computing device, comprising:

a processor; and

a memory storing instructions which, when executed by the processor, cause the computing device to perform a process including;

generating a tree structure for an input string in a first script system, the tree structure including nodes representing segments of the input string;

identifying segmentation candidates for the input string based on paths of the tree structure, the segmentation candidates segmenting the input string into character groups;

selecting a segmentation candidate based on probabilities of the segmentation candidates predicted by a probabilistic model;

segmenting the input string into character groups that correspond to characters in a second script system;

decoding the character groups in the first script system into the characters in the second script system, the characters forming a word or a word prefix in the second script system; and

outputting the word or the word prefix in the second script system.

18. The computing device of claim 17, wherein the memory stores the tree structure, and the tree structure including paths that start at a root node of the tree structure and end at leaf nodes of the tree structure, the paths representing the segmentation candidates that segment the input string into character groups.

19. The computing device of claim 17, wherein the process further comprises:

assigning the probabilities to specific nodes of the tree structure.

20. A non-transitory machine-readable storage medium comprising a program containing a set of instructions for causing a machine to execute procedures for transliteration decoding, the procedures comprising:

generating a tree structure for an input string in a first script system, the tree structure including nodes representing segments of the input string;

identifying segmentation candidates for the input string based on paths of the tree structure, the segmentation candidates segmenting the input string into character groups;

selecting a segmentation candidate based on probabilities of the segmentation candidates predicted by a probabilistic model;

segmenting the input string into character groups that correspond to characters in a second script system;

decoding the character groups in the first script system into the characters in the second script system, the characters forming a word or a word prefix in the second script system; and

outputting the word or the word prefix in the second script system.