Conversion of input text strings

• US 10,133,737 B2
• Filed: 08/26/2011
• Issued: 11/20/2018
• Est. Priority Date: 08/26/2010
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google LLC (Alphabet Inc.)
• Inventors: Brawer, Sascha B, Jansche, Martin, Sproat, Richard, Takenaka, Hiroshi, Terashima, Yui
• Primary Examiner(s): Tzeng, Forrest F
• Application Number:
  US13/818,869
• Publication Number:
  US 20140163952A1
• Time in Patent Office: 2,643 Days
• Field of Search: 704 2, 704 9
• CPC Class Codes: G06F 40/129 Handling non-Latin characters, e.g. kana-to-kanji conversion
• 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/42 Data-driven translation
• CPC Class Codes: G06F 40/55 Rule-based translation
• CPC Class Codes: G06F 40/58 Use of machine translation, e.g. for multi-lingual retrieval, for server-side translation for client devices or for real-time translation

Abstract

Methods, systems, and apparatus, including computer programs encoded on a computer storage medium, for transforming text strings. In general, one aspect of the subject matter described in this specification can be embodied in methods that include the actions of receiving input string having a plurality of terms, the input string being in a first form; transforming the input string from the first form to a second form including: applying one or more rules to the input string to identify one or more terms for translation, the one or more identified terms being fewer than the plurality of terms, translating the identified one or more terms to one or more translated terms in the second form, and transliterating the remaining terms of the plurality of terms into transliterated terms in the second form; and concatenating the translated and transliterated terms to form a hybrid output string in the second form.

Claims

1. A method performed by data processing apparatus, the method comprising:

receiving, with one or more processors at a server, an input string having a plurality of terms, the input string being in a first form, wherein a given sequence of the plurality of terms refers to a geographic feature, wherein the given sequence is annotated with a geographic-feature type selected from a plurality of geographic-feature types each indicating a characteristic of an entity in the physical world corresponding to the geographic feature, and wherein the given sequence is stored in an annotated format with the geographic-feature type in a database of geographic labels prior to receiving the input string;

transforming, with one or more processors, the input string from the first form to a second form, the transforming including;

applying one or more rules to the input string to identify one or more terms for translation, the one or more identified terms being fewer than the plurality of terms, wherein at least some of the rules are applied in response to a match between a feature type of the respective rule and the geographic-feature type with which the given sequence is annotated to indicate the characteristic of the corresponding entity in the physical world,

translating the identified one or more terms to one or more translated terms in the second form, and

transliterating at least some of the remaining terms of the plurality of terms into transliterated terms in the second form, including selecting one or more transliteration rules for application in accordance with the indicated characteristic of the entity, wherein when the given sequence of the plurality of terms is annotated with a first geographic-feature type of the plurality of geographic-feature types, a first rule of the one or more rules identifies a specific term in the input string for translation in response to a match between a first feature type of the first rule and the first geographic-feature type, and when the given sequence of the plurality of terms is annotated with a second geographic-feature type of the plurality of geographic-feature types, a second rule of the one or more rules identifies the same specific term in the input string for transliteration in response to a match between a second feature type of the second rule and the second geographic-feature type, wherein the specific term is translated or transliterated to a term having the same grammatical form as the specific term;

the method further comprising;

concatenating, with one or more processors, at least the translated and transliterated terms to form a hybrid output string in the second form; and

storing the hybrid output string in the database of geographic labels; and

when a map of a geographic region including the entity is requested for display;

(i) retrieving the hybrid output string from the database and (ii) providing, via a network interface, the hybrid output string along with map data for presenting the map with the hybrid output string at a client device.

2. The method of claim 1, wherein the first form and the second form are a first writing system and a second writing system respectively.

3. The method of claim 1, wherein the first form and the second form are a first natural language and a second natural language respectively.

4. The method of claim 1, wherein applying one or more rules to the input string comprises:

for rules that match the geographic-feature type of the given sequence, determining whether the input string matches a string pattern of the respective one or more matching rules.

5. The method of claim 1, wherein each rule includes a number of respective rule outputs for respective output forms, the respective rule outputs including translated forms of terms identified by the respective rules.

6. The method of claim 1, wherein a matching rule among the one or more rules identifies a first portion of the given sequence to be translated and a second portion of the given sequence to be transliterated.

7. The method of claim 1, wherein transliterating the remaining terms includes:

tokenizing the string into a plurality of tokens;

transliterating each token from the first form to a second form; and

concatenating at least the transliterated tokens in the second form to form a transliterated output string in the second form.

15. The method of claim 1, wherein:

the geographic-feature type comprises a given type of geographic political region;

applying one or more rules to the input string comprises;

determining that the given type of geographic political region corresponds to a hierarchy of rules relating to geographic political regions;

determining that the given type of geographic political region corresponds to a sub-type of geographic political regions within the hierarchy of rules; and

determining which parts of the given sequence to translate and which parts of the given sequence to transliterate based on a rule associated with the sub-type of geographic political regions.

16. The method of claim 1, wherein transliterating at least some of the remaining terms of the plurality of terms comprises:

transliterating at least some of the remaining terms into an intermediate phonetic representation; and

transliterating the intermediate phonetic representation into the second form.

17. The method of claim 1, wherein transliterating at least some of the remaining terms of the plurality of terms comprises:

tokenizing the remaining terms to produce tokens;

transliterating a given one of the tokens based on a transliteration rule, wherein the transliteration rule transliterates the given one of the tokens based on an at least part of an adjacent token.

20. The method of claim 1, wherein transliterating at least some of the remaining terms of the plurality of terms into transliterated terms in the second form includes:

in response to determining that the indicated characteristic is a population count of a city, wherein the city is the entity in the physical world, selecting a certain transliteration rule when the city is of a certain size, and not selecting the transliteration rule when the city is less than the certain size.

21. The method of claim 1, wherein transliterating at least some of the remaining terms of the plurality of terms into transliterated terms in the second form includes:

in response to determining that the indicated characteristic is a height a building, wherein the building is the entity in the physical world, selecting a certain transliteration rule when the building is a certain height, and not selecting the transliteration rule when the building is less than the certain height.

22. The method of claim 1, wherein transliterating at least some of the remaining terms of the plurality of terms into transliterated terms in the second form includes transliterating a term in the input string based on context of other terms in the input string and based on the first and second forms.

8. A system comprising:

one or more computers operable to interact to perform operations comprising;

receiving an input string having a plurality of terms, the input string being in a first form, wherein a given sequence of the plurality of terms refers to a geographic feature, wherein the given sequence is annotated with a geographic-feature type selected from a plurality of geographic-feature types each indicating a characteristic of an entity in the physical world corresponding to the geographic feature, and wherein the given sequence is stored in an annotated format with the geographic-feature type in a database of geographic labels prior to receiving the input string;

transforming the input string from the first form to a second form, the transforming including;

applying one or more rules to the input string to identify one or more terms for translation, the one or more identified terms being fewer than the plurality of terms, wherein at least some of the rules are applied in response to a match between a feature type of the respective rule and the geographic-feature type with which the given sequence is annotated to indicate the characteristic of the corresponding entity in the physical world,

translating the identified one or more terms to one or more translated terms in the second form, and

transliterating at least some of the remaining terms of the plurality of terms into transliterated terms in the second form, including selecting one or more transliteration rules for application in accordance with the indicated characteristic of the entity, wherein when the given sequence of the plurality of terms is annotated with a first geographic-feature type of the plurality of geographic-feature, a first rule of the one or more rules identifies a specific term in the input string for translation in response to a match between a first feature type of the first rule and the first geographic-feature type, and when the given sequence of the plurality of terms is annotated with a second geographic-feature type of the plurality of geographic-feature types, a second rule of the one or more rules identifies the same specific term in the input string for transliteration in response to a match between a second feature type of the second rule and the second geographic-feature type, wherein the specific term is translated or transliterated to a term having the same grammatical form as the specific term;

concatenating at least the translated and transliterated terms to form a hybrid output string in the second form; and

storing the hybrid output string in the database of geographic labels; and

when map data for a geographic region including the entity is requested for display;

(i) retrieving the hybrid output string from the database and (ii) providing, via a network interface, the hybrid output string along with the requested map data for display at a client device.

9. The system of claim 8, wherein the first form and the second form are a first writing system and a second writing system respectively.

10. The system of claim 8, wherein the first form and the second form are a first natural language and a second natural language respectively.

11. The system of claim 8, wherein applying one or more rules to the input string comprises:

for rules that match the geographic-feature type of the given sequence, determining whether the input string matches a string pattern of the respective one or more matching rules.

12. The system of claim 8, wherein each rule includes a number of respective rule outputs for respective output forms, the respective rule outputs including translated forms of terms identified by the respective rules.

13. The system of claim 8, wherein a matching rule among the one or more rules identifies a first portion of the given sequence to be translated and a second portion of the given sequence to be transliterated.

14. The system of claim 8, wherein transliterating the remaining terms includes:

tokenizing the string into a plurality of tokens;

transliterating each token from the first form to a second form; and

concatenating at least the transliterated tokens in the second form to form a transliterated output string in the second form.

18. The system of claim 8, wherein transliterating at least some of the remaining terms of the plurality of terms comprises:

transliterating at least some of the remaining terms into an intermediate phonetic representation; and

transliterating the intermediate phonetic representation into the second form.

19. The system of claim 8, wherein transliterating at least some of the remaining terms of the plurality of terms comprises:

tokenizing the remaining terms to produce tokens;

transliterating a given one of the tokens based on a transliteration rule, wherein the transliteration rule transliterates the given one of the tokens based on an at least part of an adjacent token.