Automated word-form transformation and part of speech tag assignment

• US 20080208566A1
• Filed: 02/23/2007
• Published: 08/28/2008
• Est. Priority Date: 02/23/2007
• Status: Abandoned Application

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Alonichau, Siarhei
• Application Number:
  US11/710,189
• Publication Number:
  US 20080208566A1
• Time in Patent Office: Days
• US Class Current: 704/9
• CPC Class Codes: G06F 40/268 Morphological analysis
• CPC Class Codes: G06F 40/284 Lexical analysis, e.g. tokenisation or collocates

Abstract

A method of creating a data structure for use with a morphological algorithm is discussed. The method includes creating a data structure having a plurality of paths. The data structure maps a plurality of words into a set of classes. The method further includes modifying the data structure to remove a portion of one or more of the paths that is not necessary to unambiguously map the words to the set of classes and storing the data structure on a tangible computer readable medium.

Claims

1. A method of creating a data structure for use with a morphological algorithm, comprising:

creating a data structure having a plurality of paths that maps a plurality of words into a set of classes;

modifying the data structure to remove a portion of one or more of the paths that is not necessary to unambiguously map the words to the set of classes; and

storing the data structure on a tangible computer readable medium.

2. The method of claim 1, wherein creating a data structure includes creating paths having at least one node and wherein a node at an end of the path is associated with data related to the set of classes.

3. The method of claim 1, wherein creating a data structure includes mapping the dictionary into set of classes related to parts of speech.

4. The method of claim 1, wherein creating a data structure includes mapping the dictionary into set of classes related to inflections.

5. The method of claim 2, and further comprising:

modifying the data structure to associate data related to the set of classes to a node not at an end of the path.

6. The method of claim 5, wherein associating data to a node not at the end of path comprises:

associating class data that represents a union of class data associated with at least two other nodes.

7. The method of claim 5, wherein associating data to a node not at the end of path comprises:

associating class data that represents an intersection of class data associated with other nodes.

8. The method of claim 5, wherein associating data to a node not at the end of path comprises:

associating class data based upon a relative frequency of the class data associated with other nodes.

9. The method of claim 1, and further comprising:

processing a word to account for specific language phenomena; and

providing the processed word for the step of creating the data structure.

10. The method of claim 9, wherein processing the word includes accounting for at least one of reduplication, prefixation, and capitalization.

11. A method of providing morphological information to a computer implemented application, comprising:

receiving an input signal indicative of a word;

selecting a piece of morphological class data from the finite state automaton-based data structure that is mapped to a location in the data structure associated with at least a portion of the word; and

providing the piece of morphological class data to the application without accessing a dictionary.

12. The method of claim 11, wherein providing the piece of morphological class data includes providing data indicative of a part of speech.

13. The method of claim 11, wherein providing the piece of morphological data includes providing data indicative of a word-form transformation.

14. The method of claim 13, wherein providing data indicative of a word-form transformation comprises providing data indicative of an inflection.

15. The method of claim 13, wherein providing data indicative of a word-form transformation comprises providing data indicative of a base-form of the word.

16. The method of claim 11, wherein selecting a piece of morphological class data from the finite state automaton-based data structure includes selecting data associated with less than the entire word.

17. The method of claim 11, wherein searching the finite-state automaton-based data structure includes searching a finite-state automaton-based data structure based upon a dictionary of known words and wherein the input received is indicative of a word that is not a known word.

18. A tangible computer medium for storing a system adapted to perform automated morphological operations on an input, comprising:

a first finite state automaton-based data structure having a plurality of paths that maps a dictionary of words into a set of classes, wherein at least one of the paths is shorter than the word that is mapped to it;

a second finite state automaton-based data structure having a plurality of paths that maps a dictionary of words into a set of classes; and

an algorithm configured to access at least one of the first and second data structures to retrieve data related to the sets of classes.

19. The tangible computer medium of claim 18, wherein the first data structure includes paths having at least one node and wherein a node at an end of the path is associated with data related to the set of classes.

20. The tangible computer medium of claim 19, wherein a node not at an end of the path is associated with data related to the set of classes.