US6308149B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Grouping words with equivalent substrings by automatic clustering based on suffix relationships
Assignee: Xerox Corp
•
Filing: 1998-12-16
•
Granted: 2001-10-23
•
Expires: 2018-12-16
Abstract
Abstract A set of words of a natural language is grouped by automatically obtaining suffix relation data that indicate a relation value for each of a set of relationships between suffixes that occur in the natural language, and, then, by automatically clustering the words in the set using the relation values from the suffix relation data, to obtain group data indicating groups of words. Two or more words in a group have suffixes as in one of the relationships and, preceding the suffixes, equivalent substrings. The relationships can be pairwise relationships, and the relation value can indicate the number of occurrences of a suffix pair. The suffix relation data can be obtained using an inflectional lexicon. Complete link clustering can be used.
Inventors
- 👤 Eric Gaussier
- 👤 Gregory Grefenstette
- 👤 Jean-Pierre Chanod
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-07 18:48
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/30; G06F16/33; G06F16/3331; G06F16/334; G06F16/3344; G06F40/00; G06F40/20; G06F40/268
Claims Analysis
Total Claims: 21
Claim 1
Independent Claim
90 words
A method of grouping a set of words that may occur in a natural language set, comprising: automatically obtaining suffix relation data indicating a relation value for each of a set of relationships between suffixes that occur in the natural language set; and automatically clustering the words in the set of words using the relation values from the suffix relation data, to obtain group data indicating groups of words; two or more words in a group having suffixes as in one of the relationships and, preceding the suffixes, equivalent substrings.
Claim 2
Independent Claim
90 words
A method of grouping a set of words that may occur in a natural language set, comprising: automatically obtaining suffix relation data indicating a relation value for each of a set of relationships between suffixes that occur in the natural language set; and automatically clustering the words in the set of words using the relation values from the suffix relation data, to obtain group data indicating groups of words; two or more words in a group having suffixes as in one of the relationships and, preceding the suffixes, equivalent substrings.
Claim 3
Dependent Claim
18 words
The method of claim 1 in which the relation value for a relationship is its frequency of occurrence.
Claim 4
Dependent Claim
14 words
The method of claim 1 in which the relationships between suffixes are pairwise relationships.
Claim 5
Dependent Claim
35 words
The method of claim 3 in which the relation value of each pairwise relationship is the number of pairs of words that are related to each other by the pair of suffixes in the relationship.
Claim 6
Dependent Claim
61 words
The method of claim 3 in which the act of automatically clustering the words comprises: obtaining, for each of a set of pairs of words, a pairwise similarity value based on the relation value of a suffix pair, if any, that relates the words to each other; and performing automatic clustering using the pairwise similarity values for the pairs of words.
Claim 7
Dependent Claim
17 words
The method of claim 5 in which the act of performing automatic clustering performs complete link clustering.
Claim 8
Dependent Claim
38 words
The method of claim 5 in which the pairwise similarity value for a pair of words is equal to the greatest relation value of the relationships between suffixes that relate the words in the pair to each other.
Claim 9
Dependent Claim
95 words
The method of claim 3 in which the natural language set includes one natural language and the act of automatically obtaining suffix relation data comprises: using a lexicon for the language to obtain a word list indicating the set of words; using the word list to obtain suffix pair data indicating pairs of suffixes that relate words in the set of words to each other; and for each pair of suffixes indicated by the suffix pair data, obtaining a relation value indicating a number of times the suffix pair occurs in the set of words.
Claim 10
Dependent Claim
16 words
The method of claim 8 in which the lexicon is an inflectional lexicon for the language.
Claim 11
Dependent Claim
49 words
The method of claim 8 in which the suffix pair data further indicate, for each suffix in a pair, a part of speech; the relation value indicating the number of times the suffixes in the suffix pair occur in the set of words with the indicated parts of speech.
Claim 12
Dependent Claim
43 words
The method of claim 1 , further comprising: automatically obtaining, for each group of words indicated by the group data, a representative; and automatically producing a data structure that can be accessed with a word in a group to obtain the group's representative.
Claim 13
Dependent Claim
24 words
The method of claim 11 in which the act of automatically obtaining a representative selects the shortest word in a group as the representative.
Claim 14
Dependent Claim
27 words
The method of claim 11 in which the data structure can also be accessed with a group's representative to obtain a list of words in the group.
Claim 15
Dependent Claim
17 words
The method of claim 11 in which the data structure is a finite state transducer data structure.
Claim 16
Independent Claim
118 words
A system for grouping a set of words that occur in a natural language, comprising: memory for storing data; and a processor connected for accessing the memory; the processor operating to: automatically obtain suffix relation data indicating a relation value for each of a set of relationships between suffixes that occur in the natural language; the processor storing the suffix relation data in memory; and automatically cluster the words in the set using the relation values from the suffix relation data, to obtain group data indicating groups of words; two or more words in a group having suffixes as in one of the relationships and, preceding the suffixes, equivalent substrings; the processor storing the group data in memory.
Claim 17
Independent Claim
118 words
A system for grouping a set of words that occur in a natural language, comprising: memory for storing data; and a processor connected for accessing the memory; the processor operating to: automatically obtain suffix relation data indicating a relation value for each of a set of relationships between suffixes that occur in the natural language; the processor storing the suffix relation data in memory; and automatically cluster the words in the set using the relation values from the suffix relation data, to obtain group data indicating groups of words; two or more words in a group having suffixes as in one of the relationships and, preceding the suffixes, equivalent substrings; the processor storing the group data in memory.
Claim 18
Dependent Claim
28 words
The system of claim 15 , further comprising: an inflectional lexicon stored in memory; the processor, in automatically obtaining suffix relation data, accessing the inflectional lexicon in memory.
Claim 19
Dependent Claim
55 words
The system of claim 15 in which the processor further operates to: automatically obtain, for each group of words indicated by the group data, a representative; and automatically produce a data structure that can be accessed with a word in a group to obtain the group's representative; the processor storing the data structure in memory.
Claim 20
Dependent Claim
59 words
The system of claim 17 , further comprising a storage medium access device for accessing a storage medium; the processor being connected for providing data to the storage medium access device; the processor further operating to provide the data structure to the storage medium access device; the storage medium access device storing the data structure on the storage medium.
Claim 21
Dependent Claim
45 words
The system of claim 17 , in which the processor is further connected for establishing connections with machines over a network; the processor operating to: establish a connection to a machine over the network; and transfer the data structure to the machine over the network.
References Cited (Backward Citations)
US4342085A
Cited
US4799188A
Cited
US4864501A
Cited
US5099425A
Cited
US5237503A
Cited
US5940624A
Cited
US5708829A
Cited
US5323310A
Cited
US5559693A
Cited
US5442778A
Cited
US5594641A
Cited
US5625554A
Cited
US5500796A
Cited
US5794177A
Cited
US5911140A
Cited
US5835888A
Cited
US5924105A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2004-10-22 | 2005-04-23 | 2005-10-23 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2008-10-22 | 2009-04-23 | 2009-10-23 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2012-10-22 | 2013-04-23 | 2013-10-23 | $7700.00 | Window Closed / Lapsed |