Efficient Implementation of Morphology for Agglutinative Languages

• US 20080243478A1
• Filed: 03/28/2007
• Published: 10/02/2008
• Est. Priority Date: 03/28/2007
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Mazel, Victoria, Magdalen, Josemina Marcella, Dayan, Yigal Shai, Cohen, Daniel
• Granted Patent: US 9,218,336 B2
• Time in Patent Office: Days
• US Class Current: 704/9
• CPC Class Codes: G06F 40/268 Morphological analysis

Abstract

A method for constructing an automaton for automated analysis of agglutinative languages, the method including constructing an affix automaton for each of a plurality of affix types of an agglutinative language, where each of the affix types is associated with one or more affixes associated with a morphological concept, combining any of the affix automatons to form a plurality of template automatons, where each of the template automatons is patterned after any of a plurality of agglutination templates of any of the affix types for the language, and combining the template automatons into a master automaton.

Claims

1. A method for constructing an automaton for automated analysis of agglutinative languages, the method comprising:

constructing an affix automaton for each of a plurality of affix types of an agglutinative language, wherein each of said affix types is associated with one or more affixes associated with a morphological concept;

combining any of said affix automatons to form a plurality of template automatons, where each of said template automatons is patterned after any of a plurality of agglutination templates of any of said affix types for said language; and

combining said template automatons into a master automaton.

2. A method according to claim 1 wherein said constructing an affix automaton step comprises constructing any of said affix automatons from the union of a plurality of said affixes associated with one of said morphological concepts.

3. A method according to claim 1 wherein said constructing an affix automaton step comprises constructing any of said affix automatons starting with the last letter of each of said affixes and continuing towards the beginning of each of said affixes.

4. A method according to claim 1 wherein said constructing an affix automaton step comprises breaking down any of said affixes into its constituent letters prior to construction of its associated affix automaton.

5. A method according to claim 1 wherein said combining any of said affix automatons step comprises combining where each of said agglutination templates defines an order in which said affixes may agglutinate to a stem word.

6. A method according to claim 1 wherein said combining any of said affix automatons step comprises combining any subset of said affix types indicated in any of said agglutination templates, provided that said subset maintains the same relative order as in said agglutination template.

7. A method according to claim 1 wherein said combining any of said affix automatons step comprises combining any of said affix types selected from a head section of any selected one of said agglutination templates, a gerund affix type of said selected agglutination template, and any of said affix types selected from a tail section of said selected agglutination template, wherein said agglutination template has a gerund separator.

8. A method according to claim 1 wherein said combining any of said affix automatons step comprises combining any of said affix automatons in the order in which their corresponding affix types appear in any selected one of said agglutination templates.

9. A method according to claim 8 wherein said combining any of said affix automatons step comprises combining starting with the starting with the last affix type in said selected agglutination template.

10. A system for analyzing words of agglutinative languages comprising:

a master automaton formed by

constructing an affix automaton for each of a plurality of affix types of an agglutinative language, wherein each of said affix types is associated with one or more affixes associated with a morphological concept,

combining any of said affix automatons to form a plurality of template automatons, where each of said template automatons is patterned after any of a plurality of agglutination templates of any of said affix types for said language, and

combining said template automatons; and

computer-implemented means for analyzing a word using said master automaton.

11. A system according to claim 10 wherein said means for analyzing is operative to perform a letter-by-letter traversal of said master automaton using the letters of a word, where each letter of said word is tested by a transition function of said automaton.

12. A system according to claim 11 wherein said means for analyzing is operative to record each successfully-traversed affix type within said automaton until no more valid affixes are discovered for said word.

13. A system according to claim 10 wherein said means for analyzing is operative to indicate an expected part of speech based on which of said agglutination templates were traversed within said automaton.

14. A system according to claim 10 wherein said means for analyzing is operative to perform a dictionary look-up of a portion of said word beyond the letter corresponding to the last valid affix found during said traversal of said automaton to determine the part of speech for said word.

15. A system according to claim 10 wherein said means for analyzing is operative to compare the part of speech indicated for said word by said automaton with the part of speech indicated for said word by said dictionary look-up to determine whether said parts of speech match.

16. A system for constructing an automaton for automated analysis of agglutinative languages, the system comprising:

means for constructing an affix automaton for each of a plurality of affix types of an agglutinative language, wherein each of said affix types is associated with one or more affixes associated with a morphological concept;

means for combining any of said affix automatons to form a plurality of template automatons, where each of said template automatons is patterned after any of a plurality of agglutination templates of any of said affix types for said language; and

means for combining said template automatons into a master automaton.

17. A system according to claim 16 wherein said means for constructing an affix automaton is operative to construct any of said affix automatons from the union of a plurality of said affixes associated with one of said morphological concepts.

18. A system according to claim 16 wherein said means for constructing an affix automaton is operative to construct any of said affix automatons starting with the last letter of each of said affixes and continuing towards the beginning of each of said affixes.

19. A system according to claim 16 wherein said means for constructing an affix automaton is operative to break down any of said affixes into its constituent letters prior to construction of its associated affix automaton.

20. A system according to claim 16 wherein said means for combining any of said affix automatons is operative to combine where each of said agglutination templates defines an order in which said affixes may agglutinate to a stem word.

21. A system according to claim 16 wherein said means for combining any of said affix automatons is operative to combine any subset of said affix types indicated in any of said agglutination templates, provided that said subset maintains the same relative order as in said agglutination template.

22. A system according to claim 16 wherein said means for combining any of said affix automatons is operative to combine any of said affix types selected from a head section of any selected one of said agglutination templates, a gerund affix type of said selected agglutination template, and any of said affix types selected from a tail section of said selected agglutination template, wherein said agglutination template has a gerund separator.

23. A system according to claim 16 wherein said means for combining any of said affix automatons is operative to combine any of said affix automatons in the order in which their corresponding affix types appear in any selected one of said agglutination templates.

24. A system according to claim 23 wherein said means for combining any of said affix automatons is operative to combine starting with the starting with the last affix type in said selected agglutination template.

25. A computer program embodied on a computer-readable medium, the computer program comprising:

a first code segment operative to construct an affix automaton for each of a plurality of affix types of an agglutinative language, wherein each of said affix types is associated with one or more affixes associated with a morphological concept;

a second code segment operative to combine any of said affix automatons to form a plurality of template automatons, where each of said template automatons is patterned after any of a plurality of agglutination templates of any of said affix types for said language; and

a third code segment operative to combine said template automatons into a master automaton.