Data processing: speech signal processing – linguistics – language – Linguistics – Natural language
Reexamination Certificate
1998-12-16
2001-10-23
Edouard, Patrick N. (Department: 2644)
Data processing: speech signal processing, linguistics, language
Linguistics
Natural language
Reexamination Certificate
active
06308149
ABSTRACT:
FIELD OF THE INVENTION
The invention relates to grouping words, some of which include equivalent substrings.
BACKGROUND AND SUMMARY OF THE INVENTION
Some conventional techniques group related words using some type of manual choice. For example, Debili, F.,
Analyse Syntaxico-Semantique Fondee Sur Une Acquisition Automatique de Relations Lexicales-Semantiques
, Doctoral Thesis, Univ. Paris XI, Jan. 26, 1982, pp. 174-223, discloses such a technique to obtain families of words. The Debili thesis discloses that each word is truncated by removing suffixes (and possibly prefixes) to obtain a stem (“radical”). Binary correlation matrices of suffixes are created by examining an automatically produced correlation matrix of suffixes and manually produced compatibility and incompatibility matrices of suffixes, and are corrected by inserting a zero for suffixes that are not compatible. The suffix matrices and the stems can then be used to automatically obtain families of words, with certain manual corrections.
In contrast, other conventional techniques automatically group words without manual intervention. Adamson, G., and Boreham, J., “The use of an Association Measure Based on Character Structure to Identify Semantically Related Pairs of Words and Document Titles”,
Information Storage and Retrieval
, Vol. 10, 1974, pp. 253-260, disclose such an automatic word classification technique based on comparison of pairs of consecutive characters, called digrams. The technique computes a similarity coefficient between pairs of words based on the number of digrams common to the words and on the sum of the total numbers of digrams in the words, to obtain a matrix of similarity coefficients for all pairs of words. The matrix is then used to cluster the words by the method of single linkage, to produce a numerically stratified hierarchy of clusters.
Lennon, M., Peirce, D.S., Tarry, B.D., and Willett, P., “An evaluation of some conflation algorithms for information retrieval”,
Journal of Information Science
, Vol. 3, 1981, pp. 177-183, describe stemming algorithms that reduce all words with the same root to a single form by stripping each word of its derivational and inflectional affixes. If prefixes are not removed, the procedure conflates all words with the same stem. Lennon et al. describe an evaluation to determine whether the reduction in implementation costs for machine processing algorithms is achieved at the expense of a decrease in conflation performance, when compared to algorithms based on manual evaluation of possible suffixes. They conclude that there is relatively little difference despite the different ways algorithms are developed, and that simple, fully automated methods perform as well for English language information retrieval as procedures which involve a large degree of manual involvement in their development.
The invention addresses a basic problem that arises in grouping related words. Conventional techniques exhibit a tension between accuracy and speed: Manual techniques can be used to group words very accurately, but are complex and tedious. Automatic techniques, on the other hand, can be very fast, but produce groupings that are not as generally accurate as can be obtained manually.
The invention is based on the discovery of a new automatic technique for grouping words that alleviates the tension between accuracy and speed. The new technique automatically obtains suffix relation data indicating a relation value for each of a set of relationships between suffixes that occur in a natural language; the relation value for a relationship could, for example, be its frequency of occurrence in a set of words from the natural language. The new technique then performs automatic clustering of a set of words using the relation values from the suffix relation data, to obtain groups of words, where two or more words in a group have suffixes as in one of the relationships and, preceding the suffixes, equivalent substrings.
The new technique can be implemented for pairwise relationships between suffixes, with the relation value of each suffix pair being the number of pairs of words that are related to each other by the pair of suffixes. Automatic clustering can then be performed with the pairwise similarity between words being the greatest relation value of the suffix pairs, if any, that relate the words to each other. Complete link clustering can be used. The new technique can be implemented using a lexicon, such as an inflectional lexicon, to automatically obtain a word list and then to use the word list in automatically obtaining suffix pair data. The suffix pair data can indicate pairs of suffixes that relate words to each other and, for each pair of suffixes, a relation value indicating a number of times the suffix pair occurs in the word list. The suffix pair data can further indicate, for each suffix in a pair, a part of speech, and the relation value can accordingly indicate the number of times the suffixes in the suffix pair occur in the word list with the indicated parts of speech.
A representative for each group of words indicated by the group data can also be automatically obtained, such as the shortest word in the group. Further, a data structure, such as a finite state transducer (FST), can be automatically produced that can be accessed with a word in a group to obtain the group's representative. The data structure can also be accessed with a group's representative to obtain a list of the words in the group.
The new technique can further be implemented in a system that includes memory and a processor that automatically obtains the suffix relation data and automatically clusters the set of words to obtain the group data, storing the suffix is relation data and the group data in memory. The processor can also automatically produce a data structure as described above and provide it to a storage medium access device for storage on a storage medium or to another machine over a network.
In comparison with conventional techniques for grouping words with manual choice or other manual involvement, the new technique is advantageous because it is automatic and therefore can be performed quickly. In addition, with appropriate clustering techniques, the new technique can approach the accuracies obtainable with manual techniques.
In comparison with conventional automatic techniques for grouping words, the new technique is significantly more accurate. Indeed, when applied to the problem of stemming, the new technique is also more accurate than conventional semi-automatic stemmers that rely on a list of suffixes, a set of rules, and a list of exceptions.
The new technique is also advantageous because it can be readily applied to additional languages for which inflectional lexicons are available. A language's inflectional lexicon can be used to automatically obtain suffix pairs with relation values.
The new technique is also advantageous because it can be implemented to use complete words as group representatives. In comparison with techniques that use substrings to represent groups, this is advantageous because it avoids ambiguous representatives that could represent more than one group.
The following description, the drawings, and the claims further set forth these and other aspects, objects, features, and advantages of the invention.
REFERENCES:
patent: 4342085 (1982-07-01), Glickman et al.
patent: 4799188 (1989-01-01), Yoshimura
patent: 4864501 (1989-09-01), Kucera et al.
patent: 5099425 (1992-03-01), Kanno Yuji et al.
patent: 5237503 (1993-08-01), Bedecarrax et al.
patent: 5323310 (1994-06-01), Robinson
patent: 5442778 (1995-08-01), Pedersen et al.
patent: 5500796 (1996-03-01), Black, Jr.
patent: 5559693 (1996-09-01), Anick et al.
patent: 5594641 (1997-01-01), Kaplan et al.
patent: 5625554 (1997-04-01), Cutting et al.
patent: 5708829 (1998-01-01), Kadashevich et al.
patent: 5794177 (1998-08-01), Carus et al.
patent: 5835888 (1998-11-01), Kanevsky et al.
patent: 5911140 (1999-06-01), Turkey et al.
patent: 5924105 (1999-07-01), Punch, III et al.
patent: 5940624 (1999-08-
Chanod Jean-Pierre
Gaussier Eric
Grefenstette Gregory
Edouard Patrick N.
Xerox Corporation
LandOfFree
Grouping words with equivalent substrings by automatic... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Grouping words with equivalent substrings by automatic..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Grouping words with equivalent substrings by automatic... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2551290