Locating digital coded words which are both acceptable misspellings and acceptable inflections of digital coded query words

• US 4,499,553 A
• Filed: 09/30/1981
• Issued: 02/12/1985
• Est. Priority Date: 09/30/1981
• Status: Expired due to Term

• Current Assignee: Unisys Corporation
• Original Assignee: Burroughs Corp (Unisys Corporation)
• Inventors: Galie, Louis M., Snow, Craig A., Dickinson, Robert V.
• Primary Examiner(s): NOT, DEFINED
• Application Number:
  US06/307,571
• Time in Patent Office: 1,231 Days
• Field of Search: 340/146.3EP,146.3WD,146.3SG 364/2MSFile,9MSFile,300,419,513
• US Class Current: 715/257
• CPC Class Codes: G06F 16/90344 by using string matching techniques
• CPC Class Codes: G06F 40/232 Orthographic correction, e.g. spell checking or vowelisation
• CPC Class Codes: G06F 40/247 Thesauruses; Synonyms

Abstract

A method is disclosed using a digital data processing means for determining from a plurality of candidate words at least one which is both an acceptable spelling and an acceptable inflection of a query word. The words are represented by machine readable coded signals and comprise plural characters. The steps are as follows: Determine a stem portion of such query word. Form a suffix class indication for any one of a plurality of classes in which the query word may be included. Compare the determined query stem with characters in the beginning of such candidate words for finding acceptable and nonacceptable spelling matches. Determine an ending portion, if any, in each individual candidate words which is an acceptable spelling match. Utilize the suffix class indication to select a representation of at least one acceptable suffix for the candidate words. Compare a representation of the at least one selected acceptable suffix and the determined ending portions in the individual candidate words which are acceptable spelling matches to determine at least one predetermined acceptable relation therebetween.

Claims

1. A method using a digital data processing means for locating from a plurality of digital coded candidate words at least one candidate word which is both an acceptable misspelling and an acceptable inflection of a digital coded query word, the candidate and query words each comprising plural characters, the method comprising the steps of:

determining characters forming a stem portion and an ending portion of such query word;

forming a suffix class indication for any one of a plurality of classes in which the query word may be included;

comparing the characters forming the stem portion with characters starting at the beginning of each of a plurality of such candidate words for finding candidate words having acceptable misspelling matches and those with nonacceptable misspelling matches;

determining characters forming an ending portion, if any, in each of individual ones of the candidate words;

utilizing the suffix class indication to select, from among other suffixes, a representation of characters forming at least one acceptable suffix for the candidate words; and

comparing, character by character, the characters of said at least one acceptable suffix with the characters in the ending portion of each of individual ones of the candidate words for finding candidate words having acceptable ending portions;

the first and second recited steps of comparing thereby locating the candidate words which are both an acceptable misspelling match and an acceptable inflection of the query word.

2. A method according to claim 1 comprising the step of separating from the rest of the candidate words each of individual ones of the candidate words which have been found to have both a stem portion with the acceptable misspelling match and the acceptable ending portion.

3. A method according to claim 1 wherein the step of comparing the characters forming the determined query word stem portion for acceptable misspelling matches comprises the additional step of forming a match class indication representing one of a plurality of classes in which each of the acceptable misspelling matches may be included;

and wherein the step of determining characters forming an ending portion comprises the additional step of utilizing the acceptable match class indication for each of individual candidate words to determine the position of an ending portion in each of individual candidate words.

4. A method according to claim 3 wherein the suffixes of different ones of the candidate words and the acceptable suffixes have different numbers of characters therein, and

wherein the step of determining characters forming a stem portion and an ending portion comprises the step of forming a representation of the number of characters in the stem portion of the query word, and

wherein the step of determining characters forming an ending portion comprises the step of adjusting the representation of the number of characters in the stem portion of the query word as a function of the value represented by the match class indication to thereby form an indication of the position of the ending portion in the candidate word.

5. A method according to claim 4 wherein the step of adjusting comprises the steps of modifying the representation of the number of characters in the stem portion of the query word up one unit, down one unit, or not at all, in accordance with the value represented by said acceptable match class indication.

6. A method according to claims 3, 4 or 5 wherein the classes for an acceptable misspelling match comprise at least:

(a) a single character transposition;

(b) a single character deletion; and

(c) a single character insertion between the characters of the stem of the query word and beginning characters of each of the candidate words.

7. A method according to claim 6 wherein the nonacceptable misspelling matches between the stem of the query word and the characters starting at the beginning of the candidate words comprise at least multiple errors in the characters.

8. A method according to claim 6 wherein the step of comparing the characters forming the determined query word stem portion and finding acceptable misspelling matches comprises the added step of finding exact spelling matches.

9. A method according to claim 1 wherein the step of utilizing the suffix class indication comprises the steps of:

(a) using the suffix class indication for the query word to access stored acceptable suffix indications and to thereby obtain from the stored acceptable suffix indications one or more acceptable suffix indications; and

(b) using each of said one or more acceptable suffix indications to access stored suffix values, to thereby select a representation of at least one acceptable suffix, having one or more characters, for each of said acceptable suffix indications.

10. A method according to claim 1 wherein the step of forming a suffix class indication comprises the step of utilizing at least characters in the ending portion of the query word to select from other suffix classes, a suffix class in which the query word is included and forming a corresponding suffix class indication.

11. A method according to claim 10 wherein the step of using characters of at least the ending portion comprises the step of additionally and selectively using representations of characters of the stem portion of the query word to select a suffix class and form said corresponding suffix class indication.

12. A method according to claim 10 wherein the steps of determining characters forming a stem portion and an ending portion and the step of forming a suffix class indication comprise the steps of:

(a) forming representations of characters in any one of a plurality of possible suffixes;

(b) comparing the representations of characters in the possible suffixes with characters in the ending portion of the query word;

(c) controlling the data processing means so as to sequence the order in which the representations of characters in possible suffixes are so compared and, upon finding a match between such characters and the order thereof, selecting a suffix class and forming a suffix class indication for the query word.

13. A method according to claim 1 wherein the step of forming a suffix class indication comprises the steps of:

(a) inspecting representations of the characters of the suffix of the query word and at least one of the characters in the stem of the query word to form an indication of the context of the characters preceding the suffix in the query word; and

(b) utilizing the characters in the suffix of the query word and the indication of the context of at least one character preceding the suffix to form the suffix class indication for the query word.

14. A method according to claim 3 wherein the digital data processing means comprises a plurality of stored tables each having digitally coded representations of possible suffixes therein, the step of determining characters forming a stem portion and an ending portion and the step of forming a suffix class indication comprising the steps of:

(a) utilizing representations of at least one character in the ending of the query word to access and to derive from a first one of the stored tables a representation of at least one character type corresponding to the at least one character;

(b) utilizing the representation of the at least one character type derived from the first table to access and derive from a second one of the stored tables a representation of an action item and a representation of a possible suffix class;

(c) selectively stripping a representation of at least one character from the ending of the query word, the stripping selectively taking place or not taking place, controlled at least in part on representation of an action item; and

(d) utilizing values represented by the representation of a possible suffix class in forming the suffix class indication.

15. A method according to claim 3 wherein the digital data processing means comprises a plurality of stored tables each having digitally coded representations therein, the step of utilizing the suffix class indication comprising the step of utilizing the suffix class indication to access and to derive from a first one of the tables a representation of at least one acceptable suffix for the candidate words.

16. A method according to claim 3 wherein the digital data processing means comprises a plurality of stored tables each having digitally coded representations therein, the step of utilizing the suffix class indication comprising the steps of:

(a) utilizing representations of the suffix class indications to access and to derive from a first one of the tables a representation of a list of acceptable suffixes, the acceptable suffix list corresponding to a value represented by the suffix class indication;

(b) utilizing representations of the at least one of the plural suffix lists to access and to derive from a second one of the tables a representation of the characters forming the at least one acceptable suffix.

17. A method according to claim 1 comprising the step of stripping the ending portion from the stem portion of the query word before the step of comparing the characters forming the query word stem.

18. Program controlled digital data processing means for locating from a plurality of digital coded candidate words at least one candidate word which is both an acceptable misspelling and an acceptable inflection of a digital coded query word, the query word and each of a plurality of the query words comprising plural characters, the data processing means comprising:

(a) programmed digital data processing means for determining characters forming a stem portion and an ending portion of such query word and for determining and forming a suffix class indication of any one of a plurality of classes in which the query word may be included;

(b) programmed digital data processing means for comparing the characters forming the stem portion of the query word with characters starting at the beginning of each of a plurality of such candidate words for finding candidate words having beginning portions with acceptable misspelling matches and those with nonacceptable misspelling matches and, for each of individual ones of those candidate words having an acceptable misspelling match, operative for forming an acceptable misspelling class indication representing a value for any one of a plurality of classes in which the acceptable misspelling match for such candidate word may be included;

(c) programmed digital data processing means utilizing the acceptable misspelling class indication for each of individual ones of the candidate words to identify an ending portion, if any, in the corresponding candidate word;

(d) programmed digital data processing means for utilizing the suffix class indication for the query word to select from among other suffixes a representation of at least one acceptable suffix for the candidate words; and

(e) programmed digital data processing means for comparing the characters of said at least one acceptable suffix with the characters of the ending portion in each of individual ones of the candidate words for finding candidate words having acceptable ending portions.

19. Programmed digital data processing means according to claim 18 comprising means for separating from the rest of the candidate words each of individual ones of those candidate words found by previously recited programmed digital processing means as having both a beginning portion with the acceptable misspelling match and the acceptable ending portion.

20. Digital data processing means for locating from a plurality of digital coded candidate words at least one which is both an acceptable misspelling and an acceptable inflection of a digital coded query word, the query word and each of a plurality of the candidate words comprising plural characters, the means comprising:

(a) first programmable digital data processing means comprising first control program means, the first programmable digital data processing means, at least in part under control of the first control program means, being operative for processing characters of the query word for thereby determining characters of the query word forming a stem portion and characters forming an ending portion and for additionally determining a suffix class indication for the characters of the query word;

(b) second programmable digital data processing means comprising second control program means, the second programmable digital data processing means, at least in part under control of the second control program means, being operative for comparing the stem portion of the query word with characters at the beginning of each of a plurality of said candidate words for determining those candidate words which have acceptable misspelling matches with the stem portion of the query word; and

(c) third programmable digital data processing means comprising third control program means, the third programmable digital data processing means, at least in part under control of the third control program means, being operative for using the suffix indication to select from other suffixes an acceptable suffix composed of one or more characters and for comparing characters forming an ending portion, after said characters at the beginning, of each of individual ones of the candidate words with the selected suffixes to thereby determine those candidate words which have an acceptable ending;

(d) the second and third programmable digital data processing means thereby determining candidate words having both acceptable misspellings and acceptable inflections of the query word.

21. Digital data processing means according to claim 20 wherein the second programmable digital data processing means additionally comprises means operative for forming a match type class indication corresponding to any one of a plurality of types of misspelling matches between the beginnings of the candidate words and the stem of the query word, and wherein the third digital data processing means additionally comprises means operative for utilizing the match type class indication to determine the number of characters in the ending portions of the candidate words for use in comparing with the suffix representations.

22. Digital data processing means for locating from a plurality of digital coded candidate words at least one which is both an acceptable misspelling and an acceptable inflection of a digital coded query word, the query word and each of a plurality of the candidate words each comprising plural characters, the processing means comprising:

data processing means for determining a stem portion and an ending portion of such query word and for forming an indication of the size of one of said portions;

data processing means for determining and forming a suffix class indication of at least one of a plurality of classes in which the query word may be included;

first memory means for storing representations of a data base comprising said candidate words;

means for deriving from the data base in the first memory means representations of said candidate words;

means for comparing representations of the stem portion of the query word with representations of the characters at the beginning of each of individual ones of the candidate words which are derived from the data base for finding either an acceptable misspelling match or a nonacceptable misspelling match and, for the acceptable misspelling match, determining and forming an acceptable misspelling match class indication representing any one of a plurality of classes in which the acceptable misspelling match may be included;

means for utilizing the acceptable misspelling match class indication for modifying representations of the indication of size to determine the characters forming an ending portion, if any, in the candidate words;

second memory means for storing representations of a plurality of acceptable suffixes, each acceptable suffix comprising one or more characters, the acceptable suffixes being arranged in groups and representations of each group being selectable from the other groups in the second memory means in accordance with one of the suffix class indications;

means for utilizing the suffix class indication for the query word to select from the second memory means, representations of at least one of the groups of acceptable suffixes; and

means for comparing representations of the acceptable suffixes which have been selected with representations of the ending portions of individual ones of the candidate words for acceptable relations therebetween;

those candidate words having both the acceptable misspelling match and the acceptable relation to the acceptable suffixes being both the acceptable misspelling and the acceptable inflection of the query word.

23. A digital data processing means for locating from a plurality of digital coded candidate words at least one which is both an acceptable misspelling and an acceptable inflection of a digital coded query word, the query word and each of plural ones of the candidate words comprising plural characters, the means comprising:

means for determining the characters forming a stem portion and an ending portion of such query word;

means for forming a suffix class indication for any one of a plurality of classes in which the query word may be included;

means for comparing the characters of the stem portion of the query word with characters in the beginning of such candidate words for finding candidate words with acceptable misspelling matches and candidate words with nonacceptable misspelling matches;

means for determining characters forming an ending portion, if any, in each of individual ones of the candidate words;

means for utilizing the suffix class indication to select from among other suffixes a representation of characters forming at least one acceptable suffix for the candidate words; and

means for comparing character by character the characters of said at least one selected acceptable suffix with the characters in the ending portion in each of the individual ones of the candidate words for finding acceptable ending portions, the first and second recited means thereby locating candidate words which are both an acceptable misspelling and an acceptable inflection of the query word.

24. Means according to claim 23 comprising the means for separating from the rest of the candidate words each of individual ones of the candidate words which have both a stem portion having the acceptable misspelling match and an ending having the acceptable ending portion.

25. Means according to claim 23 wherein the means for comparing characters of the stem portion comprises means, at least for each of those candidate words which is an acceptable misspelling match, for forming a match class indication representing a value corresponding to any one of a plurality of classes in which the acceptable misspelling match may be included;

and

wherein the means for determining characters forming an ending portion comprises additional means for utilizing the acceptable match class indication for each of individual ones of the candidate words to determine the position of the characters of said ending portion in each such candidate word.

26. Means according to claim 25 wherein the suffixes of different ones of the candidate words and the acceptable suffixes have different numbers of characters therein, and

wherein the means for determining the characters forming the stem portion comprises means for forming a representation of the number of characters in the stem portion of the query word, and

wherein the means for determining the ending portion of a candidate word comprises means for adjusting representations of the number of characters in the stem portion of the query word as a function of the value represented by the match class indication to thereby form an indication of the position of the characters of the ending portion in the candidate word.

27. Means according to claim 26 wherein the means for adjusting comprises means modifying the representation of the number of characters in the stem portion of the query word up one unit, down one unit, or not at all, in accordance with the value represented by said acceptable match class indication.

28. Means according to claim 25, 26 or 27 wherein the classes for an acceptable misspelling match comprise at least:

(a) a single character transposition;

(b) a single character deletion; and

(c) a single character insertion between the characters in the stem of the query word and the beginning characters of the candidate word.

29. Means according to claim 28 wherein the nonacceptable misspelling match between the stem of the query word and beginning characters of one of the candidate words comprises at least multiple errors in the characters.

30. Means according to claim 28 wherein the classes for an acceptable misspelling match comprise an exact match.

31. Means according to claim 23 wnerein the means for utilizing the suffix class indication comprises:

means for using the suffix class indication for the query word to access stored acceptable suffix indications and to thereby obtain one or more acceptable suffix indications; and

means for using individual ones of said one or more acceptable suffix indications to access stored suffix values, to thereby derive a representation of at least one of the acceptable suffixes for each of said acceptable suffix indications.

32. Means according to claim 23 wherein the means for forming a suffix class indication comprises means for utilizing at least characters in the ending portion of the query word to select, from other suffix classes, a suffix class in which the query word is included and for forming a corresponding suffix class indication.

33. Means according to claim 32 wherein the means for forming a suffix class indication comprises, in addition, means for selectively using representations of the stem portion of the query word to select and to form said suffix class indication.

34. Means according to claim 32 wherein the means for determining characters forming the stem portion and an ending portion and the means for utilizing characters of the query comprise:

(a) means for forming representations of characters in acceptable suffixes of the query;

(b) means for comparing the representations of characters in acceptable suffixes of the query with characters in the ending portion of the query word;

(c) means for controlling the data processing means so as to sequence the order in which the representations of characters in acceptable suffixes of the query are compared and, upon finding a match between characters and the order thereof, forming the suffix class indication for the query word under comparison.

35. Means according to claim 23 wherein the means for forming a suffix class indication comprises:

(a) means for inspecting representations of the characters of the ending portion of the query word and at least one of the characters in the query word preceding the ending portion to form at least one indication of the context of the characters in the stem portion in the query word; and

(b) means for utilizing the particular ending portion of the query word and the indication of the context to form the suffix class indication for the query word.

36. Means according to claim 23 wherein the digital data processing means comprises at least one memory for storing a plurality of tables each having digitally coded representations therein, the means for determining the characters forming a stem portion and the means for forming a suffix class indication comprising:

means for utilizing representations of at least one character in the ending portion of the query word to access and to derive, from a first one of the stored tables, a representation of at least one character type corresponding to the at least one character;

means for utilizing the representation of the at least one character type derived from the first table to access and derive from a second one of the stored tables a representation of an action item and a representation of a possible suffix class;

means for selectively stripping a representation of at least one character from the ending portion of the query word, the stripping selectively taking place or not taking place, controlled at least in part on a value represented by the representation of an action item; and

means for utilizing the values represented by the representation of a possible suffix class in forming the suffix class indication.

37. Means according to claim 23 wherein the digital data processing means comprises at least one store for storing a plurality of tables each having digitally coded representations therein, the means for utilizing the suffix class indication comprising:

means for utilizing the suffix class indication to access and to derive from a first one of the tables a representation of at least one acceptable suffix for the candidate words.

38. Means according to claim 23 wherein the digital data processing means comprises at least one memory for storing a plurality of tables each having digitally coded representations therein, the means for utilizing the suffix class indication comprising:

means for utilizing representations of the suffix class indications to access and to derive from a first one of the tables a representation of a list of acceptable suffixes, the acceptable suffix list corresponding to a value represented by the suffix class indication; and

means for utilizing representations of the acceptable suffix list to access and to derive from a second one of the tables a representation of the characters of at least one acceptable suffix.

39. Means according to claim 23 comprising means for stripping the ending portion from the stem portion of the query word, and wherein the means for comparing the characters of the stem portion compare the stem portion from which the ending has been stripped.

40. A method using a program controlled digital data processing means for locating from a plurality of digital coded candidate words at least one candidate word which is both an acceptable misspelling and an acceptable inflection of a digital coded query word, the query word and each of a plurality of the query words comprising plural characters, the method comprising the steps of:

(a) determining characters forming a suffix portion and an ending portion of such query word and for determining and forming a suffix class indication of any one of a plurality of classes in which the query word may be included;

(b) comparing the characters forming the stem portion of the query word with characters starting at the beginning of each of a plurality of such candidate words for finding candidate words having stem portions with acceptable misspelling matches and those with nonacceptable misspelling matches and, for each of individual ones of those candidate words having an acceptable misspelling match, forming an acceptable misspelling class indication representing a value for any one of a plurality of classes in which the acceptable misspelling match for such candidate word may be included;

(c) utilizing the acceptable misspelling class indication for each of individual ones of the candidate words to identify an ending portion, if any, in the corresponding candidate word;

(d) utilizing the suffix class indication for the query word to select from among other suffixes a representation of at least one acceptable suffix for the candidate words; and

(e) comparing the characters of said at least one acceptable suffix, character by character, with the characters of the ending portion in each of individual ones of the candidate words for finding candidate words having acceptable ending portions.

41. A method according to claim 40 comprising the step of for separating from the rest of the candidate words each of individual ones of those candidate words found having both a stem portion with the acceptable misspelling match and the acceptable ending portion.

42. A method using a digital data processing means for locating from a plurality of digital coded candidate words at least one candidate word which is both an acceptable misspelling and an acceptable inflection of a digital coded query word, the query word and each of plural ones of the candidate words comprising plural characters, the method comprising the steps of:

determining characters forming a stem portion and an ending portion of such query word;

comparing the characters forming the stem portion with characters starting at the beginning of each of a plurality of such candidate words for finding candidate words having acceptable misspelling matches and those with nonacceptable misspelling matches;

determining characters forming an ending portion, if any, in each of individual ones of the candidate words;

utilizing the characters of at least the ending portion of the query word to select, from among other suffixes, a representation of characters forming at least one acceptable suffix for the candidate words; and

comparing, character by character, the characters of said at least one acceptable suffix with the characters in the ending portion of each of individual ones of the candidate words for finding candidate words having acceptable ending portions;

the first and second recited steps of comparing thereby locating the candidate words which are both an acceptable misspelling match and an acceptable inflection of the query word.

43. A method according to claim 42 comprising the step of separating from the rest of the candidate words each of individual ones of the candidate words which have been found to have both a stem portion with the acceptable misspelling match and the acceptable ending portion.

44. A method according to claim 42 wherein the step of utilizing at least the characters in the ending portion of the query word comprises the additional step of selectively using representations of characters of the stem portion of the query word to select, from among other suffixes, the representation of characters forming at least one acceptable suffix for the candidate words.