Efficient implementation of morphology for agglutinative languages

• US 9,218,336 B2
• Filed: 03/28/2007
• Issued: 12/22/2015
• Est. Priority Date: 03/28/2007
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Cohen, Daniel, Dayan, Yigal Shai, Magdalen, Josemina Marcella, Mazel, Victoria
• Primary Examiner(s): Serrou, Abdelali
• Application Number:
  US11/692,228
• Publication Number:
  US 20080243478A1
• Time in Patent Office: 3,191 Days
• Field of Search: 704/1, 704 7- 10
• US Class Current: 1/1
• CPC Class Codes: G06F 40/268 Morphological analysis

Abstract

Constructing an automaton for automated analysis of agglutinative languages comprises: 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 an agglutinative language, the method comprising:

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

combining, using the processor of the computer, 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 agglutinative language;

combining, using the processor of the computer, said template automatons into a master automaton;

receiving, by the processor of the computer, a word in the agglutinative language as an input for analysis;

executing the master automaton to perform a morphological analysis of the received word, using the processor of the computer; and

responsive to the executing, producing an output that indicates an expected part of speech for the word based on which of said template automatons were traversed within said master automaton during the executing.

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

3. The method according to claim 1, wherein said constructing an affix automaton comprises constructing any of said affix automatons by starting with a last letter of each of said affixes and continuing towards a beginning letter of each of said affixes.

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

5. The method according to claim 1, wherein said combining any of said affix automatons comprises combining the affix automatons according to an order defined in the agglutination template.

6. The method according to claim 1, wherein said combining any of said affix automatons comprises combining ones of the affix automatons constructed for any subset of said affix types indicated in any of said agglutination templates, provided that said subset maintains a same relative order in a result of the combining as in said agglutination template.

7. The method according to claim 1, wherein said combining any of said affix automatons comprises combining, for any selected one of the agglutination templates which includes a gerund separator, the affix automatons constructed for any of said affix types selected from a head section of the selected one of said agglutination templates, the affix automaton constructed for a gerund affix type of said selected one of the agglutination templates, and the affix automatons constructed for any of said affix types selected from a tail section of said selected one of the agglutination templates.

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

9. The method according to claim 8, wherein said combining any of said affix automatons in an order comprises combining the any affix automatons starting with the affix automaton constructed for a last affix type in said selected agglutination template.

25. The method according to claim 1, further comprising sending the output to at least one of a natural-language query processor or a search engine for use therein.

10. A system for analyzing words of an agglutinative language, comprising:

a computer comprising a processor and a memory;

a master automaton stored in the memory, the master automaton formed by;

constructing an affix automaton for each of a plurality of affix types of the 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 agglutinative language; and

combining said template automatons into a master automaton; and

instructions which are executable, using the processor, for analyzing a word in the agglutinative language using said master automaton, further comprising;

receiving a word in the agglutinative language;

executing the master automaton to perform the analysis of the received word; and

responsive to the executing, producing an output that indicates an expected part of speech for the word based on which of the template automatons were traversed within the master automaton during the executing.

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

12. The system according to claim 11, wherein the executing the master automaton is operative to record each successfully-traversed affix type traversed within said master automaton until no more valid affixes are discovered for said word using the master automaton.

13. The system according to claim 10, wherein the executing the master automaton is operative to perform a dictionary look-up of a portion of said word beyond a letter corresponding to a last valid affix found when traversing the master automaton, the dictionary look-up determining a part of speech for said word.

14. The system according to claim 13, wherein the executing the master automaton is operative to compare the expected part of speech indicated for said word by said master automaton with the part of speech determined for said word by said dictionary look-up to determine whether said parts of speech match.

15. A system for constructing an automaton for automated analysis of an agglutinative language, the system comprising:

a computer comprising a processor; and

instructions which are executable, using the processor, to implement functions comprising;

constructing an affix automaton for each of a plurality of affix types of the 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 agglutinative language;

combining said template automatons into a master automaton, the master automation operable for analyzing a word in the agglutinative language;

receiving a word in the agglutinative language as an input for analysis;

executing the master automaton to perform the analysis of the received word; and

responsive to the executing, producing an output that indicates an expected part of speech for the word based on which of the template automatons were traversed within the master automaton during the executing.

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

17. The system according to claim 15, wherein the constructing an affix automaton is operative to construct any of said affix automatons by starting with a last letter of each of said affixes and continuing towards a beginning letter of each of said affixes.

18. The system according to claim 15, wherein the 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.

19. The system according to claim 15, wherein the combining any of said affix automatons is operative to combine the affix automatons according to an order defined in the agglutination template.

20. The system according to claim 15, wherein the combining any of said affix automatons is operative to combine ones of the affix automatons constructed for any subset of said affix types indicated in any of said agglutination templates, provided that said subset maintains a same relative order in a result of the combining as in said agglutination template.

21. The system according to claim 15, wherein the combining any of said affix automatons is operative to combine, for any selected one of the agglutination templates which includes a gerund separator, the affix automatons constructed for any of said affix types selected from a head section of the selected one of said agglutination templates, the affix automaton constructed for a gerund affix type of said selected one of the agglutination templates, and the affix automatons constructed for any of said affix types selected from a tail section of said selected one of the agglutination templates.

22. The system according to claim 15, wherein the combining any of said affix automatons is operative to combine, for any selected one of the agglutination templates, any of said affix automatons in an order in which their corresponding affix types appear in the selected one of said agglutination templates.

23. The system according to claim 22, wherein the combining any of said affix automatons in an order is operative to combine the any affix automatons starting with the affix automaton constructed for a last affix type in said selected agglutination template.

24. A computer program embodied on a non-transitory computer-readable medium, the computer program comprising program segments which, when executed by a computer, perform:

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 agglutinative language;

combining said template automatons into a master automaton, the master automation operable for analyzing a word in the agglutinative language;

receiving a word in the agglutinative language as an input for analysis;

executing the master automaton to perform the analysis of the received word; and

responsive to the executing, producing an output that indicates an expected part of speech for the word based on which of the template automatons were traversed within the master automaton during the executing.