Identifying a group of words using modified query words obtained from successive suffix relationships

• US 6,430,557 B1
• Filed: 12/16/1998
• Issued: 08/06/2002
• Est. Priority Date: 12/16/1998
• Status: Expired due to Term

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Gaussier, Eric, Chanod, Jean-Pierre, Grefenstette, Gregory
• Primary Examiner(s): Trammell, James P.
• Assistant Examiner(s): CHEUNG, MARY DA ZHI WANG
• Application Number:
  US09/212,662
• Time in Patent Office: 1,329 Days
• Field of Search: 707/1-7, 704/1-10, 704/205
• US Class Current: 1/1
• CPC Class Codes: G06F 16/3338 Query expansion
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

A query word is used to identify one of a number of word groups, by first determining whether the query word is in any of the word groups. If not, attempts to modify the query word are made in accordance with successive suffix relationships in a sequence until a modified query word is obtained that is in one of the word groups. The sequence of suffix relationships, which can be pairwise relationships, can be defined by a list ordered according to the frequencies of occurrence of the suffix relationships in a natural language. If a modified query word is obtained that is in one of the word groups, information identifying the word group can be provided, such as a representative of the group or a list of words in the group.

Claims

1. A method of using a query word to identify one of a number of word groups;

the method comprising;

(A) determining whether the query word is in any of the word groups; and

(B) if the query word is not in any of the word groups, attempting to modify the query word in accordance with successive suffix relationships by changing a suffix in a sequence until a modified query word is obtained that is in one of the word groups, wherein the successive suffix relationships are ordered in a list according to their frequencies of occurrence in a natural language so as to attempt to modify the query word first in accordance with a suffix relationship that has the highest frequency of occurrence in the natural language.

2. The method of claim 1 in which the sequence of suffix relationships is defined by an ordered list of the suffix relationships and in which (B) comprises:

attempting to modify the query word in accordance with each relationship in the ordered list of suffix relationships until a modified query word is obtained that is in one of the groups.

3. The method of claim 2 in which the suffix relationships are pairwise relationships.

4. The method of claim 3 in which (B) further comprises attempting to modify the query word by following each pairwise relationship in both directions.

5. The method of claim 2 in which the suffix relationships are ordered in the list according to their frequencies of occurrence in a natural language and in which (B) further comprises:

attempting to modify the query word first in accordance with the suffix relationship that has the highest frequency of occurrence in the natural language.

6. The method of claim 2, further comprising, prior to (A):

automatically producing a word group data structure that indicates the word groups;

the ordered list of suffix relationships being automatically obtained in producing the word group data structure.

7. The method of claim 1 in which (B) comprises a series of iterations, each for one of the suffix relationships in the sequence;

each iteration comprising;

(B1) attempting to modify the query word in accordance with the iteration'"'"'s suffix relationship; and

(B2) if (B1) successfully modifies the query word to obtain a modified query word, determining whether the modified query word is in any of the word groups.

8. The method of claim 1, further comprising:

(C) upon obtaining a modified query word that is in one of the word groups, providing information identifying the word group.

9. The method of claim 8 in which each of the word groups has a representative and in which (C) returns the representative of the word group.

10. The method of claim 8 in which (C) returns a list of words in the word group.

11. A system for using a query word to identify one of a number of word groups, comprising:

a query word; and

a processor;

the processor operating to;

determine whether the query word is in any of the word groups; and

if not, attempt to modify the query word in accordance with successive suffix relationships by changing a suffix in a sequence until a modified query word is obtained that is in one of the word groups, wherein the successive suffix relationships are ordered in a list according to their frequencies of occurrence in a natural language so as to attempt to modify the query word first in accordance with a suffix relationship that has the highest frequency of occurrence in the natural language.

12. The system of claim 11, further comprising:

stored word group data indicating the word groups;

the processor, upon obtaining a modified query word, operating to access the stored word group data to determine whether the modified query word is in one of the word groups.

13. The system of claim 12 in which the word group data are an FST data structure.

14. The system of claim 11, further comprising:

stored suffix relationship sequence data indicating the sequence of suffix relationships;

the processor, in attempting to modify the query word, operating to access the suffix relationship sequence data to obtain a next suffix relationship.

15. An article of manufacture for use in a system for using a query word to identify one of a number of word group;

the system including;

the query word;

a storage medium access device; and

a processor connected for receiving data accessed on a storage medium by the storage medium access device;

the article of manufacture comprising;

a storage medium; and

instruction data stored by the storage medium;

the instruction data indicating instructions the processor can execute;

the processor, in executing the instructions;

determining whether the query word is in any of the word groups; and

if not, attempting to modify the query word in accordance with successive suffix relationships by changing a suffix in a sequence until a modified query word is obtained that is in one of the word groups, wherein the successive suffix relationships are ordered in a list according to their frequencies of occurrence in a natural language so as to attempt to modify the query word first in accordance with a suffix relationship that has the highest frequency of occurrence in the natural language.

16. The article of claim 15, further comprising:

word group data indicating the word groups;

the processor, in executing the instructions, further;

upon obtaining a modified query word, operating to access the stored word group data to determine whether the modified query word is in one of the word groups.

17. The article of claim 16 in which the word group data are an FST data structure.

18. The article of claim 15, further comprising:

suffix relationship sequence data stored by the storage medium;

the suffix relationship sequence data indicating the sequence of suffix relationships;

the processor, in executing the instructions, further;

in attempting to modify the query word, operating to access the suffix relationship sequence data to obtain a next suffix relationship.

19. A method of operating a first machine to transfer data to a second machine over a network, the second machine including a memory and a processor connected for accessing the memory;

the memory being for storing instruction data;

the method comprising;

establishing a connection between the first and second machines over the network; and

operating the first machine to transfer instruction data to the memory of the second machine;

the instruction data indicating instructions the processor can execute;

the processor, in executing the instructions, using a query word to identify one of a number of word groups;

the processor operating to;

determine whether the query word is in any of the word groups; and

if not, attempt to modify the query word in accordance with successive suffix relationships by changing a suffix in a sequence until a modified query word is obtained that is in one of the word groups, wherein the successive suffix relationships are ordered in a list according to their frequencies of occurrence in a natural language so as to attempt to modify the query word first in accordance with a suffix relationship that has the highest frequency of occurrence in the natural language.

20. A method of using a query word to identify one of a number of word group;

the method comprising;

(A) determining whether the query word is in any of the word groups; and

(B) if the query word is not in any of the word group, attempting to modify the query word in accordance with each suffix relationship in an ordered list of suffix relationship until a modified query word is obtained that is in one of the group, wherein the suffix relationships are ordered in a list according to their frequencies of occurrence in a natural language so as to modify the query word first in accordance with the suffix relationship that has the highest frequency of occurrence in the language.