Input method editor

• US 9,026,426 B2
• Filed: 03/19/2009
• Issued: 05/05/2015
• Est. Priority Date: 03/19/2009
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Wu, Genqing, Duan, Xiaotao, Huang, Tai-Yi
• Primary Examiner(s): Shah, Paras D
• Application Number:
  US13/141,958
• Publication Number:
  US 20120016658A1
• Time in Patent Office: 2,238 Days
• Field of Search: 704/1, 704/2, 704/4, 704/8, 704/9, 704/10, 715/257, 715/261, 715/262, 715/264
• US Class Current: 704/8
• CPC Class Codes: G06F 3/018 Input/output arrangements for oriental characters
• CPC Class Codes: G06F 3/0233 Character input methods
• CPC Class Codes: G06F 40/40 Processing or translation of natural language natural language analysis G06F40/20; semantic analysis G06F40/30
• CPC Class Codes: G06F 40/53 Processing of non-Latin text kana-to-kanji conversion G06F40/129; vowelisation G06F40/232

Abstract

Methods, systems, and apparatus, including computer program products, in which an input method editor receives graphemes in a first writing system and identifies lexical items in a second writing system based on the graphemes in the first writing system. In one implementation, a method is provided. The method includes receiving a first grapheme in a first writing system; using a grapheme graph of graphemes in the first writing system to identify a first n-gram representation in the first writing system of a first morpheme in a second writing system; using the first n-gram representation to locate one or more first nodes in a morpheme graph; selecting a first lexical item from the one or more first lexical items based on a first score associated with each of the one or more first lexical items; and providing the first lexical item for display on a user device.

Claims

1. A computer-implemented method comprising:

receiving a first grapheme in a first writing system, the first grapheme representing only a portion of a first syllable in a second writing system;

using a grapheme graph of graphemes in the first writing system to identify a first n-gram representation in the first writing system of a first morpheme in the second writing system, wherein the first n-gram representation includes the first grapheme;

using the first n-gram representation to locate one or more first nodes in a morpheme graph, wherein each located first node in the morpheme graph represents one or more first lexical items in the second writing system, each of the one or more first lexical items represented by the first n-gram representation;

receiving a second grapheme in the first writing system, the second grapheme representing only a portion of a second syllable in the second writing system, wherein the first grapheme represents only a portion of a third morpheme that is different from a fourth morpheme represented only in part by the second grapheme, wherein the first and second graphemes are distinct characters separated by a space in an input string;

using the grapheme graph of graphemes in the first writing system to identify a second n-gram representation in the first writing system of a second morpheme in the second writing system, wherein the second n-gram representation includes the second grapheme;

using the second n-gram representation to locate one or more second nodes in the morpheme graph, wherein each located second node in the morpheme graph represents one or more second lexical items in the second writing system, each of the one or more second lexical items represented by the second n-gram representation;

generating one or more permutations of a third lexical item and a fourth lexical item, wherein the third lexical item is selected from the one or more first lexical items, and the fourth lexical item is selected from the one or more second lexical items;

selecting a permutation from the one or more permutations based on a second score associated with each of the one or more permutations, wherein the selected permutation includes the third lexical item followed by the fourth lexical item; and

providing the selected permutation for display on a user device.

2. The method of claim 1, wherein the grapheme graph includes a plurality of nodes, each node representing a grapheme in the first writing system, and wherein each node in a proper subset of the plurality of nodes corresponds to a full syllable, each corresponding full syllable including the graphemes of its corresponding node and of the nodes from which the corresponding node descends.

3. The method of claim 2, wherein the first n-gram representation represents a full syllable that corresponds to one of the nodes in the proper subset of nodes.

4. The method of claim 1, wherein the morpheme graph includes a plurality of nodes, each node representing one or more morphemes in the second writing system, and wherein each node in a proper subset of the plurality of nodes corresponds to a lexical item, each corresponding lexical item including the morphemes of its corresponding node and of the nodes from which the corresponding node descends.

5. The method of claim 4, wherein each morpheme corresponds to a Hanzi character.

6. The method of claim 1, wherein the first n-gram representation is representative of a full Pinyin syllable and each of the one or more lexical items is a Hanzi term.

7. The method of claim 1, wherein using the first n-gram representation to locate one or more nodes in a morpheme graph includes:

selecting an identifier of a first node in the grapheme graph that corresponds to the first n-gram representation; and

locating a second node in the morpheme graph that is associated with the identifier.

8. A computer-implemented method, comprising:

receiving a first input of a first Roman character;

using the first Roman character to locate a first Pinyin syllable node in a Pinyin input graph, the Pinyin input graph including a plurality of Pinyin syllable nodes, each Pinyin syllable node corresponding to a Roman character, wherein each Pinyin syllable node in a proper subset of the plurality of Pinyin syllable nodes corresponds to a Pinyin syllable, each corresponding Pinyin syllable including the first Roman character and other Roman characters of its corresponding Pinyin syllable node and the Pinyin syllable nodes from which the corresponding Pinyin syllable node descends;

using the located Pinyin syllable node to locate one or more first Hanzi character nodes in a Pinyin syllable graph, the Pinyin syllable graph including a plurality of Hanzi character nodes, each Hanzi character node corresponding to a Pinyin syllable, wherein each Hanzi character node in a proper subset of the plurality of Hanzi character nodes corresponds to one or more first Hanzi terms, each corresponding one or more first Hanzi terms including Hanzi characters that correspond to Pinyin syllables of its corresponding Hanzi character node and the Hanzi character nodes from which the corresponding Hanzi character node descends;

receiving a second input of a second Roman character, wherein the first and second inputs collectively represent an input string and the first and second Roman characters are distinct characters represented by a space in the input string;

using the second Roman character to locate a second Pinyin syllable node in the Pinyin input graph, wherein the second Pinyin syllable node represents a Pinyin syllable that includes the second Roman character input;

using the second located Pinyin syllable node to locate one or more second Hanzi character nodes in the Pinyin syllable graph, wherein each located second Hanzi character node corresponds to one or more second Hanzi terms; and

generating one or more permutations of a third Hanzi term and a fourth Hanzi term, wherein the third Hanzi term is selected from the one or more first Hanzi terms, and the fourth Hanzi term is selected from the one or more second Hanzi items; and

selecting a permutation from the one or more permutations based on a second score associated with each of the one or more permutations for output to a user device, wherein the selected permutation includes the third Hanzi term followed by the fourth Hanzi term.

9. The method of claim 8, wherein using the located Pinyin syllable node to locate one or more Hanzi character nodes includes:

selecting an identifier of the located Pinyin syllable node; and

locating a first Hanzi character node in the Pinyin syllable graph that is associated with the identifier.

10. The method of claim 8, wherein the Pinyin syllable graph is a Patricia trie.

11. A computer-implemented method, comprising:

receiving, at a computing system having one or more processors, first and second characters in a first language, the first and second characters being distinct characters separated by a space in an input;

determining, by the computing system, possible first syllables in a second language that begin with the first character, the second language being a transliteration of the first language;

determining, by the computing system, possible second syllables in the second language that begin with the second character, wherein determining the possible first and second syllables each comprises (i) utilizing a grapheme graph and the respective first or second characters to identify a respective n-qram representation of a respective morpheme in the second language and (ii) utilizing a morpheme graph and the respective n-qram representation to identify the respective possible first or second syllables;

determining, by the computing system, permutations of the possible first and second syllables, each permutation representing a possible word in the second language;

selecting, by the computing system, a most likely permutation to obtain a selected word in the second language; and

outputting, from the computing system, the selected word, wherein receipt of the selected word causes the selected word to be displayed.

12. The computer-implemented method of claim 11, further comprising obtaining, by the computing system, scores for the permutations, each score being indicative of a likelihood that the input corresponds to a specific possible word represented by a specific permutation, wherein selecting the most likely permutation includes selecting a permutation having a highest score.

13. The computer-implemented method of claim 11, wherein determining the first and second possible words and the selected includes utilizing, by the computing system, at least two graphs.

14. The computer-implemented method of claim 13, wherein the at least two graphs include (i) a grapheme graph having nodes relating specific characters in the first language and words in the first language that begin with the specific characters and (ii) a morpheme graph having nodes relating specific syllable permutations in the first language and words in the second language, wherein determining the first and second possible words includes utilizing, by the computing system, the grapheme graph, and wherein selecting the selected word includes utilizing, by the computing system, the morpheme graph.

15. The computer-implemented method of claim 11, wherein the first language is Pinyin and the second language is Chinese.

20. The computing system of claim 11, wherein the first language is Pinyin and the second language is Chinese.

16. A computing system including a memory having instructions stored thereon and one or more processors configured to execute the instructions, which causes the one or more processors to perform operations comprising:

receiving first and second characters in a first language, the first and second characters being distinct characters separated by a space in an input to the computing device;

determining possible first syllables in a second language that begin with the first character, the second language being a transliteration of the first language;

determining possible second syllables in the second language that begin with the second character, wherein determining the possible first and second syllables each comprises (i) utilizing a grapheme graph and the respective first or second characters to identify a respective n-qram representation of a respective morpheme in the second language and (ii) utilizing a morpheme graph and the respective n-qram representation to identify the respective possible first or second syllables;

determining permutations of the possible first and second syllables, each permutation representing a possible word in the second language;

selecting a most likely permutation to obtain a selected word in the second language; and

outputting the selected word, wherein receipt of the selected word causes the selected word to be displayed at the computing device.

17. The computing system of claim 16, wherein the operations further comprise obtaining scores for the permutations, each score being indicative of a likelihood that the input corresponds to a specific possible word represented by a specific permutation, wherein selecting the most likely permutation includes selecting a permutation having a highest score.

18. The computing system of claim 16, wherein determining the first and second possible words and the selected includes utilizing at least two graphs.

19. The computing system of claim 18, wherein the at least two graphs include (i) a grapheme graph having nodes relating specific characters in the first language and words in the first language that begin with the specific characters and (ii) a morpheme graph having nodes relating specific syllable permutations in the first language and words in the second language, wherein determining the first and second possible words includes utilizing the grapheme graph, and wherein selecting the selected word includes utilizing the morpheme graph.