Digital data processing method and means for word classification by pattern analysis

• US 4,471,459 A
• Filed: 09/30/1981
• Issued: 09/11/1984
• Est. Priority Date: 09/30/1981
• Status: Expired due to Term

• Current Assignee: Unisys Corporation
• Original Assignee: System Development Incorporated
• Inventors: Galie, Louis M., Dickinson, Robert V.
• Primary Examiner(s): Smith; Jerry
• Assistant Examiner(s): Fleming; Michael R.
• Application Number:
  US06/307,631
• Time in Patent Office: 1,077 Days
• Field of Search: 364/200,900,419
• US Class Current: 715/202
• CPC Class Codes: G06F 40/232 Orthographic correction, e.g. spell checking or vowelisation

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.

Claims

1. 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.

2. 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.

3. 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.

4. 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.

5. 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.

6. 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.

7. A method according to claim 6 including the step of utilizing the second tentative spelling classification indication in forming said spelling classification indication.

8. A method according to claim 1 comprising the step of forming a digitally coded signal representative of the spelling classification indication.

9. 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.

10. 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.

11. 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.

12. 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.

13. 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.

14. 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.

15. 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.

16. 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.

17. 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.

18. 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.

19. 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.

20. 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.

21. 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.

22. Means according to claim 21 comprising means for utilizing the second tentative spelling classification indication in forming said spelling classification indication.

23. Means according to claim 16 comprising means for forming a digitally coded signal representative of the spelling classification indication.

24. 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.

26. 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.

27. 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.

25. 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.

28. 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.

29. 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.

30. 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.

31. 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.