Method and System for Building and Contracting a Linguistic Dictionary

• US 20060293880A1
• Filed: 12/27/2005
• Published: 12/28/2006
• Est. Priority Date: 06/29/2005
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Greevy, Edel, Elshishiny, Hisham Emad, Hsiao, Pai-Fang Franny, Troussov, Alexander, Nevidomskiy, Alexey, Volkov, Pavel
• Granted Patent: US 8,090,571 B2
• Time in Patent Office: Days
• US Class Current: 704/10
• CPC Class Codes: G06F 16/374 Thesaurus
• CPC Class Codes: G06F 40/242 Dictionaries

Abstract

A method for building and contracting a linguistic dictionary, the linguistic dictionary comprising a list of surface forms and a list of normalized forms, each normalized form being associated with a surface form, the method comprising the steps of: comparing each character of a surface form with each character of the surface form'"'"'s normalized form; in response to the comparing step, determining an edit operation for each character compared; and generating a transform code from the set of the edit operations in order to transform the surface form to its normalized form.

Claims

1. A method for building and contracting a linguistic dictionary, the linguistic dictionary comprising a list of surface forms and a list of normalized forms, each normalized form being associated with a surface form, the method comprising the steps of:

comparing each character of a surface form with each character of the surface form'"'"'s normalized form;

in response to the comparing step, determining an edit operation for each character compared; and

generating a transform code from the set of the edit operations for transforming the surface form to its normalized form.

2. A method as claimed in claim 1 wherein the edit operation comprises deleting a character, retaining a character, inserting a character or replacing a character within the surface form for deriving the normalized form from the surface form.

3. A method as claimed in claim 1 further comprising determining a global frequency for each of the generated transform codes.

4. A method as claimed in claim 3 further comprising the step of calculating whether a surface form comprises more than one transform code.

5. A method as claimed in claim 3 further comprising the step of identifying, for each surface form having more than one transform code, whether at least one of the transform codes as having a higher global frequency than the other transform codes.

6. A method as claimed in claim 5 wherein the transform code with the higher global frequency replaces the transform code having a lower global frequency.

7. A method as claimed in claim 6 wherein the transform code having the higher global frequency is shared across surface forms.

8. A method as claimed in claim 1 wherein the linguistic dictionary comprises a trie-based data structure.

9. A method as claimed in claim 1 wherein the surface forms and normalized forms comprise Arabic surface forms and normalized forms.

10. A method as claimed in claim 7 further comprising the step of calculating a usage rate of the highest occurring transform codes and selecting the transform code with the highest usage rate as the preferred transform code for storing.

11. A method as claimed in claim 1 further comprising the steps of stemming the surface forms to derive a normalized form and applying a pruning algorithm.

12. A method as claimed in claim 11 wherein the stemming step comprises generating a trie-based index for an information retrieval application.

13. A method as claimed in claim 11 wherein the pruning step comprises populating a trie-based data structure with a surface form and generating a generic rule for applying to the surface form.

14. A method as claimed in claim 13 wherein the generic rule describes how the surface form is to be processed.

15. A method as claim in claim 14 wherein the pruning step further comprises traversing the trie-based structure from node to node until a generic rule is found, comparing the generic rule with a most frequently occurring rule and if the generic rule is identical to the most frequently occurring rule removing the nodes associated with the generic rule.

16. A method as claimed in claim 15 wherein only the exceptions to the generic rule are stored in the trie-based data structure.

17. A system for building and contracting a linguistic dictionary, the linguistic dictionary comprising a list of surface forms and a list of normalized forms, each normalized form being associated with a surface form, the method comprising the steps of:

a parsing component configured to compare each character of a surface form with each character of the surface form'"'"'s normalized form; and

an edit operation component configured to determine an edit operation for each character compared;

wherein the edit operation component is configured to generate a transform code from the set of the edit operations for transforming the surface form to its normalized form.

18. A system as claimed in claim 17 wherein the edit operation comprises deleting a character, retaining a character, inserting a character or replacing a character in the surface form for deriving the normalized form of the surface form.

19. A system as claimed in claim 17 wherein the system further comprises a determining component configured to determine a global frequency for each of the generated transform codes.

20. A system as claimed in claim 17 further comprising means for calculating whether a surface form comprises more than one transform code.

21. A system as claimed in claim 19 further comprising means for identifying, for each surface form having more than one transform code, whether at least one of the transform codes is determined as having a higher global frequency than the other transform codes.

22. A system as claimed in claim 21 wherein the transform code with the higher global frequency replaces the transform code having a lower global frequency.

23. A system as claimed in claim 22 wherein the transform code having the higher global frequency is shared across surface forms.

24. A system as claimed in claim 17 wherein the linguistic dictionary comprises a trie-based data structure.

25. A system as claimed in claim 17 wherein the surface forms and normalized forms comprise Arabic surface forms and normalized forms.

26. A system as claimed in claim 23 further comprising means for calculating a usage rate of the highest occurring transform codes and means for selecting the transform code with the highest usage rate as the preferred transform code for storing.

27. A system as claimed in claim 17 further comprising a stemming algorithm for stemming the surface form to derive a normalized form and means for applying a pruning algorithm.

28. A system as claimed in claim 27 wherein the stemming algorithm comprises means for generating a trie-based index for information retrieval applications.

29. A system as claimed in claim 27 further comprising means for populating a trie-based data structure with a surface form and means for generating a generic rule for applying to the surface form.

30. A system as claimed in claim 29 wherein the generic rule describes how the surface form is to be processed.

31. A system as claimed in claim 27 wherein the pruning algorithm further comprises means for traversing the trie-based structure from node to node until a generic rule is found, means for comparing the generic rule to a most frequently occurring rule and if the generic rule is identical to the most frequently occurring rule means for removing the nodes associated with the generic rule.

32. A system as claimed in claim 31 wherein only the exceptions to the generic rule are stored in the trie-based data structure.

33. A computer program product loadable into the internal memory of a digital computer and executable by a digital computer, said computer program product having a plurality of code sections comprising:

code for comparing each character of a surface form with each character of the surface form'"'"'s normalized form;

code for, in response to the comparisons, determining an edit operation for each character compared; and

code for generating a transform code from the set of the edit operations for transforming the surface form to its normalized form.