Determining language for character sequence

• US 7,139,697 B2
• Filed: 03/27/2002
• Issued: 11/21/2006
• Est. Priority Date: 03/28/2001
• Status: Expired due to Fees

• Current Assignee: WSOU Investments, LLC (WSOU Holdings, LLC)
• Original Assignee: Nokia Mobile Phones UK Limited (Nokia Corporation)
• Inventors: Hakkinen, Juha, Mettala, Markku
• Primary Examiner(s): Smits, Talivaldis Ivars
• Assistant Examiner(s): Serrou, Abdelali
• Application Number:
  US10/108,661
• Publication Number:
  US 20020184003A1
• Time in Patent Office: 1,700 Days
• Field of Search: 704/9, 704/277, 704/8
• US Class Current: 704/9
• CPC Class Codes: G06F 40/216 using statistical methods
• CPC Class Codes: G06F 40/263 Language identification
• CPC Class Codes: G06F 40/289 Phrasal analysis, e.g. finite state techniques or chunking

Abstract

A method for selecting the language for a character sequence fed into a data processing device, wherein decision trees are trained for different characters on the basis of lexicons of predetermined languages. The decision trees describe language probabilities on the basis of characters in the environments of the characters. The decision trees for at least some of the characters of the character sequence fed into the data processing device are traversed, thus obtaining a probability of at least one language for each character. The language for the character sequence is selected on the basis of the probabilities obtained.

Claims

1. A method for selecting the language for a character sequence fed into a data processing device, the method comprising:

storing in the data processing device character-specific decision trees to describe probabilities for at least two different languages on the basis of characters in the environments of the characters,

traversing the decision trees for at least some of the characters of the character sequence fed into the data processing device, thus obtaining a probability of at least one language for each character, and

selecting the language for the character sequence on the basis of said language probabilities.

2. A method as claimed in claim 1, the method further comprising:

training the decision trees on the basis of predetermined lexicons of at least two languages.

3. A method as claimed in claim 1, wherein the decision trees comprise nodes and leaves which comprise probabilities of different languages, the nodes comprise questions concerning the characters located to the right and/or to the left of the character, and the decision tree for the character of the character sequence is traversed by answering the questions set forth in the nodes of the decision tree until a leaf determining the language probabilities is found or there is no way to proceed from a node, the character thus being provided with a probability of at least one language on the basis of said leaf or node.

4. A method as claimed in claim 1, wherein at least two languages are shown to a user to select from that are the most probable languages for the character sequence,

the selection made by the user is read, and

the language selected by the user is selected as the language of the character sequence.

5. A method as claimed in claim 1, wherein the language which occurs most frequently as the most probable language in the characters of the character sequence is selected automatically as the language of the character sequence.

6. A method as claimed in claim 1, wherein the probabilities of languages for different characters are added up, and

the language for which the total sum of probabilities is greatest is selecting automatically as the language of the character sequence.

7. A method as claimed in claim 1, wherein the data processing device is a mobile station in a mobile communication system,

the method is used for selecting the language for a character sequence fed into the contact data of a mobile station supporting multilingual speech recognition, the decision trees being formed on the basis of lexicons comprising substantially proper names,

a phoneme sequence is formed for the character sequence according to the language selected therefor,

in response to at least the speech information supplied by the user of the mobile station, a phoneme sequence substantially according to the speech information supplied by the user is selected, and

a character sequence according to said phoneme sequence is selected from the contact data.

8. A method as claimed in claim 1, wherein the lexicons to be used of at least two languages are selected, the lexicons comprising character sequences and languages associated therewith,

the lexicons are combined into one training lexicon,

questions concerning the characters in the environment of a character are formed on the basis of the training lexicon,

said questions are compared with each other,

the questions maximizing the information gain are added to the nodes of the decision tree of the character,

the decision tree is grown using the nodes until a predetermined ending criterion is met,

leaves are added to the decision tree, the leaves comprising a probability of at least one language, and

the decision trees are stored in a data processing device.

9. A method as claimed in claim 8, wherein the ending criterion consists of restricting the decision tree to a predetermined size or depth or the fact that the information gain obtained by adding a node remains below a predetermined amount.

10. A method for training a decision tree in a data processing device, the method comprising:

selecting lexicons to be used of at least two languages which comprise character sequences and language tags associated therewith,

combining the lexicons into one training lexicon, and

forming decision trees for different characters to be used for selecting the language for a character sequence by taking the following steps of;

forming questions concerning characters in the environment of the selected character on the basis of the training lexicon,

comparing said questions with each other,

adding nodes to the decision tree of the character, the nodes comprising questions, in order to maximize the information gain,

growing the decision tree using the nodes until a predetermined ending criterion is met,

adding leaves to the decision tree, the leaves comprising a probability of at least one language.

11. A method as claimed in claim 10, wherein the ending criterion consists of restricting the decision tree to a predetermined size or depth or the fact that the information gain obtained by adding a node remains below a predetermined amount.

12. A method as claimed in claim 10, wherein a number is determined for each of said questions by using the language tags, the number describing the information gain achieved by adding that question to the decision tree, said questions are compared on the basis of the numbers, and a node with a question having the largest information gain is added to the decision tree.

13. A data processing device comprising a language selector block for determining the language from a character sequence fed into the device and memory for storing character-specific decision trees determined on the basis of lexicons of at least two languages, the decision trees describing language probabilities on the basis of characters in the environment of the characters, wherein said language selector block is arranged to retrieve the character-specific decision trees from the memory in response to the character sequence fed into the data processing device,

said language selector block is arranged to traverse character-specific decision trees for at least some of the characters of the character sequence until a language can be assigned to each character, and

said language selector block is arranged to select the language for the character sequence on the basis of the languages assigned to the characters.

14. A data processing device as claimed in claim 13, wherein said data processing device is further arranged to show at least two languages to a user to select from that are the most probable languages for the character sequence,

said data processing device is arranged to read the choice made by the user, and

said language selector block is arranged to select the language selected by the user as the language of the character sequence.

15. A data processing device as claimed in claim 13, wherein the decision trees comprise nodes and leaves which comprise probabilities of different languages, the nodes comprising questions concerning characters located to the right and/or to the left of a character, and

said language selector block is arranged to examine the decision tree for the character of the character sequence by answering the questions set forth in the nodes of the decision tree until a leaf to determine the language probabilities is found or there is no way to proceed from a node, the character thus being provided with a probability of at least one language on the basis of said leaf or node.

16. A data processing device as claimed in claim 13, wherein said data processing device is a mobile station in a mobile communication system, and said language selector block is used for selecting the language of the character sequence fed into the contact data of the mobile station supporting multilingual speech recognition, and the decision tree is formed from lexicons comprising substantially proper names,

a phoneme sequence is formed for the character sequence according to the language selected therefor, and,

in response to at least the speech information supplied by the user of the mobile station, a phoneme sequence substantially according to the speech information supplied by the user is selected, and, further, a character sequence according to said phoneme sequence is selected from the contact data.

17. A data processing device as claimed in claim 13, wherein the data processing device is arranged to select automatically as the language of the character sequence the language that occurs most frequently as the most probable language in the characters of the character sequence.

18. A data processing device as claimed in claim 13, wherein the data processing device is arranged to add up the probabilities of languages for different characters, and

the data processing device is arranged to automatically select the language for which the total sum of probabilities is greatest as the language of the character sequence.

19. A computer program product stored on a computer readable medium for controlling a data processing device processing a character sequence, said computer program product comprising program code causing the data processing device to

retrieve character-specific decision trees stored in the memory of the data processing device that describe probabilities for at least two languages on the basis of characters in the environments of the characters,

traverse the decision trees for at least some of the characters of the character sequence fed into the data processing device, thus obtaining a probability of at least one language for each character, and

select the language for the character sequence on the basis of said language probabilities.

20. A computer program product as claimed in claim 19, said computer program product comprising program code for causing the data processing device to select automatically as the language of the character sequence the language which occurs most frequently as the most probable language in the characters of the character sequence.

21. A computer program product as claimed in claim 19, said computer program product comprising program code for causing the data processing device to add up the probabilities of languages for different characters, and automatically select the language for which the total sum of probabilities is greatest as the language of the character sequence.

22. A computer program product stored on a computer readable medium for controlling a data processing device, said computer program product comprising program code causing the data processing device to

select lexicons to be used of at least two languages, the lexicons comprising character sequences and language tags associated therewith,

combine the lexicons into one training lexicon, and

form decision trees for different characters to be used for selecting the language for a character sequence by taking the following steps of:

producing questions concerning characters in the environment of the selected character on the basis of the training lexicon,

comparing said questions with each other,

adding nodes to the decision tree of the character, the nodes comprising questions, in order to maximize the information gain, growing the decision tree using the nodes until a predetermined ending criterion is met.

23. A computer program product as claimed in claim 22, said computer program product comprising program code for causing the data processing device to determined a number for each of said questions by using the language tags, the number describing the information gain achieved by adding that question to the decision tree, compared said questions on the basis of the numbers, and add a node with a question having the largest information gain to the decision tree.