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.