Digital data processing method and means for word classification augmented by ending analysis

Claim 3

A method according to claim 1 comprising the step of separating from the rest of the candidate words representations of those candidate words which have said at least one predetermined acceptable relation.

Claim 4

A method according to claim 1 wherein the step of comparing and finding candidate words which are acceptable and nonacceptable spelling matches comprises the additional step of, at least for each of those candidate words which is an acceptable spelling match, forming a match class indication representing a value corresponding to any one of a plurality of classes in which the acceptable match may be included; and wherein the step of determining an ending portion in each of individual candidate words comprises the additional step of utilizing the acceptable match class indication for each of individual candidate words to determine the position of said ending portion of the corresponding candidate word.

Claim 5

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 a stem portion in a query word comprises the step of forming a representation of the number of characters in the located stem portion of the query word, and wherein the step of determining the ending portion of a candidate word comprises the step of 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 ending portion in the candidate word.

Claim 6

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.

Claim 7

A method according to claim 3, 4 or 5 wherein the classes for an acceptable spelling match comprise at least: a) a single character transposition; b) a single character deletion; and c) a single character insertion between the stem of the query word and beginning characters of the candidate word.

Claim 8

A method according to claim 6 wherein the nonacceptable spelling match between the stem of the query word and beginning characters of a candidate word comprises at least multiple errors in the characters.

Claim 9

A method according to claim 6 wherein the classes for an acceptable spelling match comprise an exact match.

Claim 10

A method according to claim 1 wherein the step of selecting a representation of at least one acceptable suffix for candidate words comprises the steps of: a) 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 b) using each of said one or more acceptable suffix indications to access stored suffix values, to thereby derive a representation of at least one acceptable suffix for each of said acceptable suffix indications.

Claim 11

1Q. A method according to claim 1 wherein the step of forming a suffix class indication comprises the step of utilizing representations of at least characters at the end of the query word after the stem portion to determine and form said acceptable suffix classification indication.

Claim 12

A method according to claim 10 wherein the step of forming a suffix class indication comprises, in addition, the step of selectively using representations of the stem portion of the query word to determine and form said acceptable suffix class indication.

Claim 13

A method according to claim 10 wherein the step of determining the stem portion of the query word comprises the steps of: a) forming representations of characters in acceptable suffixes; bl comparing the representations of characters in acceptable suffixes with characters in the ending of the query word; cl controlling the data processing means so as to sequence the order in which the representations of characters in acceptable suffixes are compared and, upon finding a match between characters and the order thereof, forming a suffix class indication for the query word under comparison.

Claim 14

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 a suffix of the query word and at least one of the characters in the query word preceding the suffix to form at least one indication of the context of the characters preceding the suffix in the query word; and b) utilizing the particular 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.

Claim 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 steps of determining a stem portion and forming a suffix class indication comprising the steps of: 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; 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 suffix class; the step of determining a stem portion of the query word comprising the step of: selectively stripping a representation of at least one character from the ending of the query word and wherein the stripping selectively takes place or does not take place, controlled at least in part on a value represented by the representation of an action item; the step of forming a suffix class indication utilizing values represented by the representation of a suffix classification in forming the suffix class indication.

Claim 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 steps of utilizing the suffix class indication to select a representation of at least one acceptable suffix 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.

Claim 17

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 to select a representation of at least one acceptable suffix comprising the steps of: utilizing representations of the suffix class indications to access and to derive from a first one of the tables a representation of an acceptable suffix list, the acceptable suffix list corresponding to'a value of the suffix class indication; utilizing representations of the at least one acceptable suffix list to access and to derive from a second one of the tables a representation of the at least one acceptable suffix, the at least one acceptable suffix corresponding to a value of the acceptable suffix list.

Claim 18

A method according to claim 16 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 to select a representation of at least one acceptable suffix comprising the steps of: utilizing representations of the suffix class indications to access and to derive from a third one of the tables a representation of an acceptable suffix list, the acceptable suffix list corresponding to a value of the suffix class indication; utilizing representations of the at least one acceptable suffix list to access and to derive from a fourth one of the tables a representation of the at least one acceptable suffix, the at least one acceptable suffix corresponding to a value of the acceptable suffix list.

Claim 19

Program controlled 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 being represented by machine readable coded signals and comprising one or more characters, comprising: a) programmed digital processing means for locating a suffix portion of a query word and for forming a suffix class indication of any one of a plurality of classes in which the located suffix portion of the query word may be included; b) programmed digital data processing means for comparing the located query word stem with ending portions of such candidate words for finding either an acceptable or a nonacceptable spelling match and, at least for an acceptable spelling match, operative for forming an acceptable spelling class indication representing a value for any one of a plurality of classes in which the acceptable match may be included; c) programmed digital data processing means utilizing the acceptable spelling class indication for individual candidate words to identify an ending portion, if any, in the corresponding candidate word; dl programmed digital data processing means for utilizing the suffix class indication for the query word to select a representation of at least one acceptable suffix for individual candidate words having an acceptable spelling match; and el programmed digital data processing means for comparing a representation of said at least one selected acceptable suffix with the located ending portions of individual candidate words to thereby determine predetermined acceptable relations therebetween.

Claim 20

Program controlled 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 being represented by machine readable coded signals and comprising one or more characters, comprising: a) programmed digital processing means for locating a suffix portion of a query word and for forming a suffix class indication of any one of a plurality of classes in which the located suffix portion of the query word may be included; b) programmed digital data processing means for comparing the located query word stem with ending portions of such candidate words for finding either an acceptable or a nonacceptable spelling match and, at least for an acceptable spelling match, operative for forming an acceptable spelling class indication representing a value for any one of a plurality of classes in which the acceptable match may be included; c) programmed digital data processing means utilizing the acceptable spelling class indication for individual candidate words to identify an ending portion, if any, in the corresponding candidate word; dl programmed digital data processing means for utilizing the suffix class indication for the query word to select a representation of at least one acceptable suffix for individual candidate words having an acceptable spelling match; and el programmed digital data processing means for comparing a representation of said at least one selected acceptable suffix with the located ending portions of individual candidate words to thereby determine predetermined acceptable relations therebetween.

Claim 21

Programmed.digital data processing means according to claim 18 comprising means for separating from the rest of the candidate words representations of those candidate words which have said predetermined acceptable relation with the at least one selected acceptable suffix.

Claim 22

2Q. 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 query and candidate words being represented by machine readable coded signals and comprising one or more characters comprising: 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 causing the query word to be processed for determining a stem portion and an acceptable suffix class indication for the query word; 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 determined stem portion of the query word with the beginning characters of each of a plurality of said candidate words for determining those candidate words which have acceptable spelling matches with. the stem portion of the query word; and 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 determining and comparing representations of an ending portion of those individual candidate words having acceptable spelling matches with suffix representations corresponding to said suffix class indication and to thereby determine those candidate words which have both an acceptable spelling match and an acceptable ending.

Claim 23

2Q. 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 query and candidate words being represented by machine readable coded signals and comprising one or more characters comprising: 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 causing the query word to be processed for determining a stem portion and an acceptable suffix class indication for the query word; 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 determined stem portion of the query word with the beginning characters of each of a plurality of said candidate words for determining those candidate words which have acceptable spelling matches with. the stem portion of the query word; and 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 determining and comparing representations of an ending portion of those individual candidate words having acceptable spelling matches with suffix representations corresponding to said suffix class indication and to thereby determine those candidate words which have both an acceptable spelling match and an acceptable ending.

Claim 24

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

Claim 25

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 comprising one or more characters, comprising: data processing means for determining at least a stem 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 determined query word stem with representations of characters at the beginnings of the candidate words derived from the data base for finding either an acceptable or a nonacceptable spelling match and, at least for an acceptable spelling match, forming an acceptable spelling match class indication having a value corresponding to any one of a plurality of classes in which the acceptable spelling match may be included; providing a size representation for each of the candidate words having an acceptable spelling match; means for utilizing the acceptable spelling match class indications for modifying the size representations and for using the modified size representations to determine an ending portion, if any, in the corresponding candidate words; second memory means for storing representations of a plurality of acceptable suffixes, the acceptable suffixes being arranged in groups and representations of each group being selectable from the memory means in accordance with a value represented by each suffix class indication; means for utilizing the suffix class indication for the query word to derive from the second memory means a representation of at least one acceptable suffix from the group corresponding to such suffix class indication; and means for comparing the representation of the at least one selected acceptable suffix and the determined ending portions of individual candidate words for acceptable relations therebetween.

Claim 26

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 comprising one or more characters, comprising: data processing means for determining at least a stem 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 determined query word stem with representations of characters at the beginnings of the candidate words derived from the data base for finding either an acceptable or a nonacceptable spelling match and, at least for an acceptable spelling match, forming an acceptable spelling match class indication having a value corresponding to any one of a plurality of classes in which the acceptable spelling match may be included; providing a size representation for each of the candidate words having an acceptable spelling match; means for utilizing the acceptable spelling match class indications for modifying the size representations and for using the modified size representations to determine an ending portion, if any, in the corresponding candidate words; second memory means for storing representations of a plurality of acceptable suffixes, the acceptable suffixes being arranged in groups and representations of each group being selectable from the memory means in accordance with a value represented by each suffix class indication; means for utilizing the suffix class indication for the query word to derive from the second memory means a representation of at least one acceptable suffix from the group corresponding to such suffix class indication; and means for comparing the representation of the at least one selected acceptable suffix and the determined ending portions of individual candidate words for acceptable relations therebetween.

Claim 27

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 being represented by machine readable coded signals and comprising plural characters, the means comprising: means for determining a stem 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 determined query word stem with characters in the beginning of such candidate words for finding acceptable and nonacceptable spelling matches; means for determining an ending portion, if any, in each of individual candidate words which is an acceptable spelling match; means for utilizing the suffix class indication to select a representation of at least one acceptable suffix for the candidate words; and means for comparing a representation of said 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.

Claim 28

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 being represented by machine readable coded signals and comprising plural characters, the means comprising: means for determining a stem 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 determined query word stem with characters in the beginning of such candidate words for finding acceptable and nonacceptable spelling matches; means for determining an ending portion, if any, in each of individual candidate words which is an acceptable spelling match; means for utilizing the suffix class indication to select a representation of at least one acceptable suffix for the candidate words; and means for comparing a representation of said 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.

Claim 29

Means according to claim 23 comprising the means for separating from the rest of the candidate words representations of those candidate words which have said at least one predetermined acceptable relation.

Claim 30

Means according to claim 23 wherein the means for comparing and finding candidate words which are acceptable and nonacceptable spelling matches comprises means for, at least for each of those candidate words which is an acceptable spelling match, forming a match class indication representing a value corresponding to any one of a plurality of classes in which the acceptable match may be, included; and wherein means for determining an ending portion in each of individual candidate words comprises the additional means for utilizing the acceptable match class indication for each of individual candidate words to determine the position of said ending portion of the corresponding candidate word.

Claim 31

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 a stem portion in a query word comprises means for forming a representation of the number of characters in the located 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 ending portion in the candidate word.

Claim 32

Means according to claim 26 wherein the means 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.

Claim 33

Means according to claim 25, 26 or 27 wherein the classes for an acceptable spelling match comprise at least: a) a single character transposition; b) a single character deletion; and c) a single character insertion between the stem of the query word and beginning characters of the candidate word.

Claim 34

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

Claim 35

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

Claim 36

Means according to claim 23 wherein the means for selecting a representation of at least one acceptable suffix for candidate words comprises: a) 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 b) means for using each of said one or more acceptable suffix indications to access stored suffix values, to thereby derive a representation of at least one acceptable suffix for each of said acceptable suffix indications.

Claim 37

Means according to claim 23 wherein the means for forming a suffix class indication comprises means for utilizing representations of at least characters at the end of the query word after the stem portion to determine and form said acceptable suffix classification indication.

Claim 38

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 determine and form said acceptable suffix class indication.

Claim 39

Means according to claim 32 wherein the step of determining the stem portion of the query word comprises: a) means for forming representations of characters in acceptable suffixes; b) means for comparing the representations of characters in acceptable suffixes with characters in the ending 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 are compared and, upon finding a match between characters and the order thereof, forming a suffix class indication for the query word under comparison.

Claim 40

Means according to claim 23 wherein the means for forming a suffix class indication comprises: a) means for inspecting representations of the characters of a suffix of the query word and at least one of the characters in the query word preceding the suffix to form at least one indication of the context of the characters preceding the suffix in the query word; and b) means for utilizing the particular 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.

Claim 41

Means according to claim 25 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 a stem portion and forming a suffix class indication comprising: means for 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; 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 suffix class; the means for determining a stem portion of the query word comprising means for selectively stripping a representation of at least one character from the ending of the query word and wherein the stripping selectively takes place or does not take place, controlled at least in part on a value represented by the representation of an action item; the means for forming a suffix class indication utilizing values represented by the representation of a suffix classification in forming the suffix class indication.

Claim 42

Means according to claim 25 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 to select a representation of at least one acceptable suffix 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.

Claim 43

Means according to claim 25 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 to select a representation of at least one acceptable suffix 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 an acceptable suffix list, the acceptable suffix list corresponding to a value of the suffix class indication; and means for utilizing representations of the at least one acceptable suffix list to access and to derive from a second one of the tables a representation of the at least one acceptable suffix, the at least one acceptable suffix corresponding to a value of the acceptable suffix list.

Claim 44

Means according to claim 38 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 to select a representation of at least one acceptable suffix comprising: means for utilizing representations of the suffix class indications to access and to derive from a third one of the tables a representation of an acceptable suffix list, the acceptable suffix list corresponding to a value of the suffix class indication; means for utilizing representations of the at least one acceptable suffix list to access and to derive from a fourth one of the tables a representation of the at least one acceptable suffix, the at least one acceptable suffix corresponding to a value of the acceptable suffix list.