Multi-lingual word hyphenation using inductive machine learning on training data

• US 8,996,994 B2
• Filed: 01/16/2008
• Issued: 03/31/2015
• Est. Priority Date: 01/16/2008
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Alonichau, Siarhei, Shahani, Ravi, Powell, Kevin
• Primary Examiner(s): Shah, Paras D
• Application Number:
  US12/015,489
• Publication Number:
  US 20090182550A1
• Time in Patent Office: 2,631 Days
• Field of Search: 704/8, 704/9, 704/10, 715/255, 715/256, 715/258
• US Class Current: 715/258
• CPC Class Codes: G06F 40/191 Automatic line break hyphenation

Abstract

Tools and techniques are described for providing multi-lingual word hyphenation using inductive machine learning on training data. Methods provided by these techniques may receive training data that includes hyphenated words, and may inductively generate hyphenation patterns that represent substrings of these words. The hyphenation patterns may include the substrings and hyphenation codes associated with characters occurring in the substrings. The methods may receive induction parameters applicable to generating the hyphenation patterns, and may store the hyphenation patterns into a language-specific lexicon file. These methods may also receive requests to hyphenate input words that occur in a human language, and may evaluate how to process the request based on the language. The methods may search for hyphenation patterns occurring in the input words, with the hyphenation patterns being stored in the lexicon file. Finally, the methods may respond to the request, indicating whether the hyphenation patterns occurred in the input words.

Claims

1. A method comprising:

receiving training data at a server computer system that include a plurality of hyphenated words;

inductively generating hyphenation patterns at the server computer system from the received training data, via machine learning, comprising substrings occurring within the plurality of hyphenated words, and hyphenation codes identifying hyphenation points within the hyphenation patterns and associated respectively with characters occurring in the substrings, the hyphenation codes each corresponding to an action to be performed after a given input character occurs within a word, the action being selected from at least one of

deleting a letter before the hyphen,

adding a specified letter before the hyphen,

changing the letter before the hyphen to some specified letter,

changing a letter after the hyphen to some other specified letter, or

deleting the letter before the hyphen and changing the letter after the hyphen to another specified letter;

building at least one data structure at the server computer system comprising representations of the individual characters appearing within the substrings, wherein the data structure indicates how many times the substrings occur with the training data;

receiving, at the server computer system, at least one induction parameter applicable to generating the hyphenation patterns, wherein the at least one induction parameter specifies a precision applicable to generating the hyphenation patterns, wherein the precision is related to a lower bound on accuracy with which input words not included in the training data may be hyphenated;

storing at least one inductively generated hyphenation pattern at the server computer system comprising the substrings and the hyphenation codes as entries into a language-specific lexicon file; and

receiving at least one request from a client computer system to hyphenate at least one input word occurring in a human language based on the stored at least one inductively generated hyphenation pattern.

2. The method of claim 1, wherein receiving training data includes receiving training data that includes at least some correctly-hyphenated words, wherein the hyphenation codes identify at least one hyphenation point where hyphenation is permitted, wherein the hyphenation codes identify at least one hyphenation point where hyphenation is not permitted.

3. The method of claim 1, further comprising merging at least one automatically generated hyphenation pattern with at least one manually created hyphenation pattern.

4. The method of claim 1, wherein generating hyphenation patterns includes generating hyphenation codes that include don'"'"'t care codes.

5. The method of claim 1, wherein generating hyphenation patterns includes generating hyphenation codes that do not include don'"'"'t care codes.

6. The method of claim 1, wherein building the data structure includes building a data structure that includes respective states corresponding to the individual characters, and includes representations of orders in which the characters occur within the substrings.

7. The method of claim 1, wherein building the data structure includes building a data structure that includes representations of sequences of hyphenation codes as associated respectively with sequences of the individual characters, wherein the hyphenation codes indicate whether hyphenation is permitted within an input word after occurrences of the individual characters.

8. The method of claim 7, wherein building the data structure includes building a data structure that includes respective states corresponding to sequences of the individual characters and respective states corresponding to sequences of the hyphenation codes, and includes representations of orders in which the characters and hyphenation codes occur within the substrings.

9. The method of claim 1, further comprising selecting at least one non-overlapping subset of the hyphenation patterns, wherein the subset of the hyphenation patterns performs similarly to the hyphenation patterns.

10. The method of claim 1, further comprising decompounding at least one compound word occurring in the training data into a plurality of segment boundaries, and further comprising merging a plurality of hyphenation points defined in the hyphenation codes with the segment boundaries.

11. The method of claim 1, wherein receiving training data includes receiving representations of a plurality of words hyphenated according to a first human language, and further comprising:

receiving further training data including a further plurality of words hyphenated according to a further human language;

inductively generating further hyphenation patterns that represent further substrings occurring within the further words, wherein the further hyphenation patterns include at least the further substrings and further hyphenation codes associated respectively with further characters occurring in the further substrings;

receiving at least one further induction parameter applicable to generating the further hyphenation patterns; and

storing at least the further substrings and the further hyphenation codes as entries into a further lexicon file specific to the further human language.

12. One of an optical storage device, a semiconductor storage device or a magnetic storage device having computer-executable instructions stored thereon which, when executed by a computer, cause the computer to perform a method comprising:

receiving at least one request from a client computer system to hyphenate at least one input word occurring in a human language;

evaluating at a server computer system how to process the request based at least in part on the human language;

searching, at the server computer system, for a least one hyphenation pattern comprising a substring occurring in the at least one input word and at least one hyphenation code identifying hyphenation points within the at least one hyphenation pattern and associated respectively with characters occurring in the substrings, the at least one hyphenation code corresponding to an action to be performed after a given input character occurs within a word, the action being selected from at least one of

deleting a letter before the hyphen,

adding a specified letter before the hyphen,

changing the letter before the hyphen to some specified letter,

changing a letter after the hyphen to some other specified letter, or

deleting the letter before the hyphen and changing the letter after the hyphen to another specified letter,

wherein at least the one hyphenation pattern is stored in a language-specific lexicon file that is created inductively, via machine learning at the server computer system, based on training data; and

responding from the server computer system to the at least one request from the client computer system, wherein the response at least indicates whether the at least one hyphenation pattern occurred in the at least one input word.

13. The optical storage device, semiconductor storage device or magnetic storage device of claim 12, further comprising instructions for calculating zero or more hyphenation points or hyphenation types in response to the evaluating.

14. The optical storage device, semiconductor storage device or magnetic storage device of claim 13, wherein the instructions for receiving at least one request include instructions for receiving a request to hyphenate at least one compound input word, and further comprising decompounding the compound input word into a plurality of segment boundaries.

15. The optical storage device, semiconductor storage device or magnetic storage device of claim 14, further comprising instructions for converting the segment boundaries into hyphenation points.

16. The optical storage device, semiconductor storage device or magnetic storage device of claim 14, further comprising instructions for merging the at least one hyphenation point with a plurality of segment boundaries resulting from decompounding the compound input word.

17. The optical storage device, semiconductor storage device or magnetic storage device of claim 12, further comprising instructions for:

receiving at least a further request to hyphenate at least a further input word occurring in a further human language;

evaluating how to process the request based at least in part on the further human language;

searching for a least a further hyphenation pattern comprising a further substring occurring in the further input word, wherein at least the further hyphenation pattern is stored in a further lexicon file that is specific to the further human language and that is created inductively based on further training data; and

responding to the further request, wherein the further response at least indicates whether the at least one further hyphenation pattern occurred in the further input word.

18. A word hyphenation system comprising:

a least one server adapted to;

receive training data that includes a plurality of hyphenated words;

receive at least one induction parameter applicable to generating hyphenation patterns;

based on the at least one induction parameter, inductively generate the hyphenation patterns, from the training data via machine learning, comprising substrings occurring within the plurality of hyphenated words, and hyphenation codes identifying hyphenation points within the hyphenation patterns and associated respectively with characters occurring in the substrings, the hyphenation codes each corresponding to an action to be performed after a given input character occurs within a word, the action being selected from at least one of

deleting a letter before the hyphen,

adding a specified letter before the hyphen,

changing the letter before the hyphen to some specified letter,

changing a letter after the hyphen to some other specified letter, or

deleting the letter before the hyphen and changing the letter after the hyphen to another specified letter; and

store at least the substrings and the hyphenation codes as entries into a language-specific lexicon file specific to a human language;

wherein the server is further adapted to;

receive at least one request to hyphenate of an input word occurring in the human language;

determine the human language in the context of the at least one request;

evaluate how to process the at least one request based at least in part on the human language;

search for at least one hyphenation pattern occurring in the input word, wherein a substring of at least one hyphenation pattern is stored in the language-specific lexicon file; and

respond to the at least one request, the response at least indicates based in part by determining whether the substring of the at least one hyphenation pattern occurred in the input word, wherein the at least one server may achieve complete accuracy in hyphenating input words that occur within the training data, and wherein the at least one server may achieve at least a lower bound on accuracy in hyphenating input words that do not occur in the training data, wherein the lower bound is based on a precision applicable to generating the hyphenation patterns; and

at least one client system adapted to send the request and to receive the response thereto.

19. The word hyphenation system of claim 18, further comprising at least a further lexicon file that is specific to a least a further human language, and wherein the server is adapted to:

receive further training data that includes a further plurality of hyphenated words in the further human language;

inductively generate further hyphenation patterns that represent substrings occurring within the words, wherein the further hyphenation patterns include at least the substrings and hyphenation codes associated respectively with characters occurring in the substrings;

receive at least one induction parameter applicable to generating the further hyphenation patterns;

store at least the substrings and the hyphenation codes into the further lexicon file;

receive at least one further request to hyphenate one further input word occurring in the further human language;

evaluate how to process the further request based at least in part on the further human language;

search for the substring of the a least one further hyphenation pattern occurring in the further input word, wherein at least the further hyphenation pattern is stored in the further lexicon file; and

respond to the further request, wherein the further response at least indicates whether the at least one further hyphenation pattern occurred in the further input word.