MULTI-LINGUAL WORD HYPHENATION USING INDUCTIVE MACHINE LEARNING ON TRAINING DATA

• US 20090182550A1
• Filed: 01/16/2008
• Published: 07/16/2009
• Est. Priority Date: 01/16/2008
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Powell, Kevin, Alonichau, Siarhei, Shahani, Ravi
• Granted Patent: US 8,996,994 B2
• Time in Patent Office: Days
• US Class Current: 704/8
• 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 that include a plurality of hyphenated words;

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

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

storing at least the substrings and the hyphenation codes into a language-specific lexicon file.

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, wherein at least one of the induction parameters 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 are hyphenated, and 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 generating hyphenation patterns includes building at least one data structure that includes representations of individual characters appearing within the substrings, wherein the data structure indicates how many times at least part of the substrings occur within the training data.

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

8. The method of claim 6, 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.

9. The method of claim 8, 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.

10. 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.

11. 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.

12. 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 into a further lexicon file specific to the further human language.

13. At least one computer-readable storage medium 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 to hyphenate at least one input word occurring in a human language;

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

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

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

14. The computer-readable storage medium of claim 13, further comprising instructions for calculating zero or more hyphenation points or hyphenation types in response to the evaluating.

15. The computer-readable storage medium of claim 14, 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.

16. The computer-readable storage medium of claim 15, further comprising instructions for converting the segment boundaries into hyphenation points.

17. The computer-readable storage medium of claim 15, further comprising instructions for merging the at least one hyphenation point with a plurality of segment boundaries resulting from decompounding the compound input word.

18. The computer-readable storage medium of claim 13, 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 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.

19. A word hyphenation system comprising:

a least one server adapted to;

receive training data that includes a plurality of hyphenated words;

based on at least one induction parameter, inductively generate hyphenation patterns that represent substrings occurring within the words, wherein the 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 hyphenation patterns; and

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

wherein the server is further adapted to;

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

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

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

respond to the request, wherein the response at least indicates whether the at least one hyphenation pattern occurred in the input word, wherein the server may achieve complete accuracy in hyphenating input words that occur within the training data, and wherein the server may achieve at least a lower bound on accuracy in hyphenating input words that do not occur in the training data; and

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

20. The word hyphenation system of claim 19, 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 raining 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;

wherein the server is further adapted to;

receive at least one further request to hyphenate at least 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 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.