US4471459A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Digital data processing method and means for word classification by pattern analysis
Assignee: Unisys Corp
•
Filing: 1981-09-30
•
Granted: 1984-09-11
•
Expires: 2001-09-30
Abstract
Abstract Digital data processing means employing a method for separating acceptable spellings of words from nonacceptable spellings wherein each word comprises characters assigned positions. The character positions in each word are assigned increasing values from one end of the word to the other, positions of the same number of characters from the same end of each word being assigned the same value. Two words to be compared are called a query word and a candidate word. The method includes the following steps. A representation of a character in a given position of the query word is compared with representations of characters in the next lower position, the same position, and the next higher position in the candidate word and a compare type indication is formed representing a match or a mismatch between each query word character and the candidate word characters under comparison. The given position of the query word under comparison is changed to the next higher valued position of the query word and the preceding step is repeated to form another compare type indication. The compare type indications are processed to thereby form a spelling classification indication for one of the words under comparison representing an acceptable spelling or a nonacceptable spelling with respect to the other.
Inventors
- 👤 Robert V. Dickinson
- 👤 Louis M. Galie
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-27 07:39
CPC Classifications
G; G06; G06F; G06F40/00; G06F40/20; G06F40/232
Claims Analysis
Total Claims: 36
Claim 1
Independent Claim
225 words
A method using a digital data processing means for separating words with acceptable spellings from words with nonacceptable spellings wherein each word comprises characters assigned character positions, character position in each word being assigned increasing values from one end of the word to the other, characters at the same number of positions from one end of each word being assigned the same value, the two words to be compared being called a query word and a candidate word, the method comprising the steps of: (a) comparing representation of a character in a given character position of the query word with representations of characters in the next lower character position, the same character position, and the next higher character position in the candidate word, and forming a compare type indication representing a match or a mismatch between such query word character and each of such candidate word characters under comparison; (b) changing the given character position of the query word under comparison in the preceding step of comparing to the next higher valued character position of the query word and repeating the preceding step of comparing at least once to form another compare type indication; and (c) processing and utilizing said compare type indications to thereby form a spelling classification indication for one of the words under comparison representing an acceptable spelling or a nonacceptable spelling.
Claim 2
Independent Claim
225 words
A method using a digital data processing means for separating words with acceptable spellings from words with nonacceptable spellings wherein each word comprises characters assigned character positions, character position in each word being assigned increasing values from one end of the word to the other, characters at the same number of positions from one end of each word being assigned the same value, the two words to be compared being called a query word and a candidate word, the method comprising the steps of: (a) comparing representation of a character in a given character position of the query word with representations of characters in the next lower character position, the same character position, and the next higher character position in the candidate word, and forming a compare type indication representing a match or a mismatch between such query word character and each of such candidate word characters under comparison; (b) changing the given character position of the query word under comparison in the preceding step of comparing to the next higher valued character position of the query word and repeating the preceding step of comparing at least once to form another compare type indication; and (c) processing and utilizing said compare type indications to thereby form a spelling classification indication for one of the words under comparison representing an acceptable spelling or a nonacceptable spelling.
Claim 3
Dependent Claim
93 words
A method according to claim 1 comprising the steps of: repeating the preceding step of comparing, the step of changing and the step of processing and utilizing, for each of a plurality of different candidate words, to thereby form a spelling classification indication, for each of said plurality of candidate words; and utilizing the spelling classification indication for each of said plurality of candidate words for physically separating representations of those candidate words indicated to be acceptable spellings from representations of those candidate words indicated to be nonacceptable spellings of the query word.
Claim 4
Dependent Claim
38 words
A method according to claim 2 comprising the step of combining a representation of each of said plurality of candidate words which are indicated to be an acceptable spelling with a representation of the corresponding spelling classification indication.
Claim 5
Dependent Claim
28 words
A method according to claim 3 wherein the step of physically separating comprises the step of physically transferring the combined representations of candidate words and acceptable spelling classifications.
Claim 6
Dependent Claim
137 words
A method according to claim 1 wherein the step of comparing and forming a compare type indication comprises the additional steps of: forming for a query character under comparison a compare type representation comprising a lower storage position, a same storage position, and a next higher storage position which correspond respectively to such next lower character position, the same character position, and the next higher character position in the candidate word, forming in each binary storage position a binary representation of a first value when the comparison with the candidate character in the corresponding character position of the candidate word results in an equality, and forming in each storage position a binary representation of a second value when the comparison with the candidate character in the corresponding character position of the candidate word results in an inequality.
Claim 7
Dependent Claim
91 words
A method according to claim 1 wherein first and second compare type indications are formed using, respectively, a query character in a first character position and a second query character in a second higher valued character position of the query word, the steps of processing and utilizing comprising the steps of: utilizing at least the first compare type indication for forming a first tentative spelling classification indication; and utilizing at least the second compare type indication and the first tentative spelling classification indication for forming a second tentative spelling classification indication.
Claim 8
Dependent Claim
23 words
A method according to claim 6 including the step of utilizing the second tentative spelling classification indication in forming said spelling classification indication.
Claim 9
Dependent Claim
21 words
A method according to claim 1 comprising the step of forming a digitally coded signal representative of the spelling classification indication.
Claim 10
Dependent Claim
52 words
A method according to claim 1 comprising the step of forming a spelling classification indication comprising a digitally coded signal identifying any one of at least the following acceptable spelling errors between the query word and the candidate word: a character insertion error, a character deletion error, and a character transposition error.
Claim 11
Dependent Claim
29 words
A method according to claim 9 wherein the acceptable spelling errors include equality and inequality between the characters and their order in the candidate word and the query word.
Claim 12
Dependent Claim
38 words
A method according to claim 1 wherein the step of processing and utilizing said compare type indications to form a spelling classification indication is partially performed following the formation of each compare type indication for each query character.
Claim 13
Dependent Claim
50 words
A method according to claim 1 comprising the additional step of accumulating the compare type indications in a store, and wherein the step of processing and utilizing said compare type indications comprises the step of processing and utilizing the compare type indications after they have been accumulated in the store.
Claim 14
Independent Claim
237 words
A method using a digital data processing means for separating words with acceptable spellings from words with nonacceptable spellings wherein each word comprises characters assigned character positions, character positions in each word being assigned increasing values from one end of the word to the other, character at the same number of positions from one end of each word being assigned the same value, two words to be compared being called a query word and a candidate word, the method comprising the steps of: (a) comparing representations of each of plural given characters in each of different given character positions of the query word with representations of characters in the candidate word; (b) forming representations of a plurality of compare type indications, a different compare type indication for each of said plural given characters of the query word, each compare type indication representing whether a match was found in the step of comparing between one of the given characters of the query word and the three characters of the candidate word located in the next lower character position than, the same character position as, and the next higher character position than, such given character of the query word; and (c) processing and utilizing said compare type indications in order of the corresponding given characters of the query to form a spelling classification indication for one of the words under comparison representing an acceptable spelling or a nonacceptable spelling.
Claim 15
Independent Claim
237 words
A method using a digital data processing means for separating words with acceptable spellings from words with nonacceptable spellings wherein each word comprises characters assigned character positions, character positions in each word being assigned increasing values from one end of the word to the other, character at the same number of positions from one end of each word being assigned the same value, two words to be compared being called a query word and a candidate word, the method comprising the steps of: (a) comparing representations of each of plural given characters in each of different given character positions of the query word with representations of characters in the candidate word; (b) forming representations of a plurality of compare type indications, a different compare type indication for each of said plural given characters of the query word, each compare type indication representing whether a match was found in the step of comparing between one of the given characters of the query word and the three characters of the candidate word located in the next lower character position than, the same character position as, and the next higher character position than, such given character of the query word; and (c) processing and utilizing said compare type indications in order of the corresponding given characters of the query to form a spelling classification indication for one of the words under comparison representing an acceptable spelling or a nonacceptable spelling.
Claim 16
Dependent Claim
48 words
A method according to claim 13 wherein the digital data processing means is programmable and comprising the steps of: initiating the execution of a compare procedure enabling the data processing means to perform such steps of comparing representations and forming representations of a plurality of compare type indications.
Claim 17
Dependent Claim
98 words
A method according to claim 14 comprising the steps of initiating the operation of a branching procedure for performing the step of processing and utilizing said compare type indications, said branching procedure having a plurality of nodal junctions, each nodal junction having plural branches therefrom to one or more other nodal junctions, a different one of the plurality of nodal junctions being reached for each of said compare type indications, the particular branch which is taken from one nodal junction to another being conditioned upon the value represented by a compare type indication and the one nodal junction.
Claim 18
Dependent Claim
236 words
Digital data processing means for separating words with acceptable spellings from words with nonacceptable spellings wherein each word comprises characters assigned character positions, character positions in each word being assigned increasing values from one end of the word to the other, characters at the same number of positions from one end of each word being assigned the same value, two words to be compared being called a query word and a candidate word, comprising: (a) means operative for comparing a representation of a character in a given character position of the query word with representations of characters in the next lower character position, the same character position, and the next higher character position in the candidate word, and for forming a compare type indication representing a match or a mismatch between such query word character and each of such candidate word characters under comparison; (b) means for changing the given character position of the query word under comparison by the means for comparing to the next higher valued character position of the query word, the means for comparing comprising means operative for repeating the recited operation using the next higher valued character position of the query word to form another compare type indication; and (c) means for processing and utilizing said compare type indications to thereby form a spelling classification indication for one of the words under comparison representing an acceptable spelling or a nonacceptable spelling.
Claim 19
Dependent Claim
236 words
Digital data processing means for separating words with acceptable spellings from words with nonacceptable spellings wherein each word comprises characters assigned character positions, character positions in each word being assigned increasing values from one end of the word to the other, characters at the same number of positions from one end of each word being assigned the same value, two words to be compared being called a query word and a candidate word, comprising: (a) means operative for comparing a representation of a character in a given character position of the query word with representations of characters in the next lower character position, the same character position, and the next higher character position in the candidate word, and for forming a compare type indication representing a match or a mismatch between such query word character and each of such candidate word characters under comparison; (b) means for changing the given character position of the query word under comparison by the means for comparing to the next higher valued character position of the query word, the means for comparing comprising means operative for repeating the recited operation using the next higher valued character position of the query word to form another compare type indication; and (c) means for processing and utilizing said compare type indications to thereby form a spelling classification indication for one of the words under comparison representing an acceptable spelling or a nonacceptable spelling.
Claim 20
Dependent Claim
101 words
Digital data processing means according to claim 16 comprising: means for enabling a repeat of the recited operation for the comparing means, for the means for changing and for the means for processing for each of a plurality of different candidate words to thereby form a spelling classification indication for each of said plurality of candidate words; and means for utilizing the spelling classification indication for each of said plurality of candidate words for physically separating representations of those candidate words indicated to be acceptable spellings from representations of those candidate words indicated to be nonacceptable spellings of the query word.
Claim 21
Dependent Claim
39 words
Digital data processing means according to claim 17 comprising means for combining a representation of each of said plurality of candidate words which are indicated to be an acceptable spelling with a representation of the corresponding spelling classification indication.
Claim 22
Dependent Claim
29 words
Digital data processing means according to claim 18 wherein the means for physically separating comprises means for physically transferring the combined representations of candidate words and acceptable spelling classifications.
Claim 23
Dependent Claim
140 words
Digital data processing means according to claim 16 wherein the means for comparing and forming a compare type indication comprises: means for forming for a query character under comparison a compare type representation comprising a lower storage position, a same storage position, and a next higher storage position corresponding, respectively, to such next lower character position, the same character position, and the next higher character position in the candidate word, and means for forming in each storage position a binary representation of a first value when the comparison with the candidate character in the corresponding character position of the candidate word results in an equality, and means for forming in each storage position a binary representation of a second value when the comparison with the candidate character in the corresponding character position of the candidate word results in an inequality.
Claim 24
Dependent Claim
91 words
Means according to claim 16 wherein the first and second compare type indications are formed using a query character in a first character position and a second query character in a second higher valued character position of the query word, the means for processing and utilizing comprising: means for utilizing at least the first compare type indication for forming a first tentative spelling classification indication; and means for utilizing at least the second compare type indication and the first tentative spelling classification indication for forming a second tentative spelling classification indication.
Claim 25
Dependent Claim
21 words
Means according to claim 21 comprising means for utilizing the second tentative spelling classification indication in forming said spelling classification indication.
Claim 26
Dependent Claim
19 words
Means according to claim 16 comprising means for forming a digitally coded signal representative of the spelling classification indication.
Claim 27
Dependent Claim
50 words
Means according to claim 16 comprising means for forming a spelling classification indication comprising a digitally coded signal identifying any one of at least the following acceptable spelling errors between the query word and the candidate word: a character insertion error, a character deletion error, and a character transposition error.
Claim 28
Dependent Claim
29 words
Digital data processing means according to claim 34 wherein the acceptable spelling errors include equality between the characters and their order in the candidate word and the query word.
Claim 29
Dependent Claim
42 words
Digital data processing means according to claim 16 wherein the operation of the means for processing and utilizing said compare type indications to form spelling classification indications is partially performed following the formation of each compare type indication for each query character.
Claim 30
Dependent Claim
51 words
Digital data processing means according to claim 16 comprising a store, means for accumulating the compare type indications in the store, and wherein the means for processing and utilizing said compare type indications comprises means for processing and utilizing the compare type indications after they have been accumulated in the store.
Claim 31
Dependent Claim
234 words
Digital data processing means for separating words with acceptable spellings from words with nonacceptable spellings wherein each word comprises characters assigned character positions, character positions in each word being assigned increasing values from one end of the word to the other, characters at the same number of positions from one end of each word being assigned the same value, two words to be compared being called a query word and a candidate word, comprising: (a) means operative for comparing representations of each of plural given characters in each of different given character positions of the query word with representations of characters in the candidate word; (b) means for forming representations of a plurality of compare type indications, a different compare type indication for each of said plural given characters of the query word, each compare type indication representing whether a match was found by the comparing means between one of the given characters of the query word and the three characters of the candidate word located in the next lower character position than, the same character position as, and the next higher character position than, such given character of the query word; and (c) means for processing and utilizing said compare type indications in order of the corresponding given characters of the query to form a spelling classification indication for one of the words under comparison representing an acceptable spelling or a nonacceptable spelling.
Claim 32
Dependent Claim
234 words
Digital data processing means for separating words with acceptable spellings from words with nonacceptable spellings wherein each word comprises characters assigned character positions, character positions in each word being assigned increasing values from one end of the word to the other, characters at the same number of positions from one end of each word being assigned the same value, two words to be compared being called a query word and a candidate word, comprising: (a) means operative for comparing representations of each of plural given characters in each of different given character positions of the query word with representations of characters in the candidate word; (b) means for forming representations of a plurality of compare type indications, a different compare type indication for each of said plural given characters of the query word, each compare type indication representing whether a match was found by the comparing means between one of the given characters of the query word and the three characters of the candidate word located in the next lower character position than, the same character position as, and the next higher character position than, such given character of the query word; and (c) means for processing and utilizing said compare type indications in order of the corresponding given characters of the query to form a spelling classification indication for one of the words under comparison representing an acceptable spelling or a nonacceptable spelling.
Claim 33
Dependent Claim
47 words
Means according to claim 28 wherein the digital data processing means is programmable and comprising: means for initiating the execution of a compare procedure enabling the digital data processing means to perform such steps of comparing representations and forming representations of a plurality of compare type indications.
Claim 34
Dependent Claim
96 words
Means according to claim 29 comprising means for initiating the operation of a branching procedure for performing the step of processing and utilizing said compare type indications, said branching procedure having a plurality of nodal junctions, each nodal junction having plural branches therefrom to one or more other nodal junctions, a different one of the plurality of nodal junctions being reached for each of said compare type indications, the particular branch which is taken from one nodal junction to another being conditioned upon the value represented by a compare type indication and the one nodal junction.
Claim 35
Independent Claim
290 words
A method using a digital data processing means for separating words with acceptable spellings from words with nonacceptable spellings wherein each word comprises characters assigned character positions, character positions in each word being assigned increasing values from one end of the word to the other, characters at the same number of positions from one end of each word being assigned the same value, the two words to be compared being called a query word and a candidate word, the method comprising the steps of: (a) storing the query word in a store in the processing means; (b) storing candidate words in a store in the processing means; (c) enabling the data processing means to operatively compare a representation of a character in a given character position of the stored query word with representations of characters in the next lower character position, the same character position, and the next higher character position in each of the stored candidate words, and form a compare type indication representing a match or a mismatch between such query word character and each of such candidate word characters under comparison; (d) enabling the processing means to change the given character position of the stored query word in the preceding operation of comparing in sequence to higher valued character positions of the stored query word and for each such character position repeat the preceding step of comparing to form a plurality of compare type indications for each of the stored candidate words; and (e) enabling the processing means to process and utilize the plurality of compare type indications formed for each of the stored candidate words to thereby form a spelling classification indication for each of the candidate words representing an acceptable spelling or a nonacceptable spelling.
Claim 36
Independent Claim
290 words
A method using a digital data processing means for separating words with acceptable spellings from words with nonacceptable spellings wherein each word comprises characters assigned character positions, character positions in each word being assigned increasing values from one end of the word to the other, characters at the same number of positions from one end of each word being assigned the same value, the two words to be compared being called a query word and a candidate word, the method comprising the steps of: (a) storing the query word in a store in the processing means; (b) storing candidate words in a store in the processing means; (c) enabling the data processing means to operatively compare a representation of a character in a given character position of the stored query word with representations of characters in the next lower character position, the same character position, and the next higher character position in each of the stored candidate words, and form a compare type indication representing a match or a mismatch between such query word character and each of such candidate word characters under comparison; (d) enabling the processing means to change the given character position of the stored query word in the preceding operation of comparing in sequence to higher valued character positions of the stored query word and for each such character position repeat the preceding step of comparing to form a plurality of compare type indications for each of the stored candidate words; and (e) enabling the processing means to process and utilize the plurality of compare type indications formed for each of the stored candidate words to thereby form a spelling classification indication for each of the candidate words representing an acceptable spelling or a nonacceptable spelling.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1987-09-11 | 1988-03-12 | 1988-09-11 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1991-09-11 | 1992-03-12 | 1992-09-11 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 1995-09-11 | 1996-03-12 | 1996-09-11 | $7700.00 | Window Closed / Lapsed |