Graphic word spelling correction using automated dictionary comparisons with phonetic skeletons

• US 4,580,241 A
• Filed: 02/18/1983
• Issued: 04/01/1986
• Est. Priority Date: 02/18/1983
• Status: Expired due to Term

• Current Assignee: Vantage Technology Holdings LLC
• Original Assignee: Houghton Mifflin Harcourt Publishing Company (Houghton Mifflin Harcourt Co. (Private Equity))
• Inventors: Kucera, Henry
• Primary Examiner(s): Thomas, James D.
• Assistant Examiner(s): Williams, A.
• Application Number:
  US06/467,834
• Time in Patent Office: 1,138 Days
• Field of Search: 364/200 MS File, 364/900 MS File, 364/300, 364/418, 381/41-44, 434/176, 434/178, 434/157, 434/167, 400/63, 400/83, 400/98, 400/100, 400/102, 400/109, 400/110
• US Class Current: 715/257
• CPC Class Codes: G06F 16/3335 Syntactic pre-processing, e.g. stopword elimination, stemming
• CPC Class Codes: G06F 40/232 Orthographic correction, e.g. spell checking or vowelisation

Abstract

Automated spelling correction converts, by prescribed linguistic procedures, each word to be corrected to a skeleton, and compares that skeleton with a data base of skeletons derived by identical linguistic procedures from a dictionary of correctly spelled words. In the event of a match between the two skeletal terms, the correctly spelled word (or words) associated with the matched skeleton is presented for replacement of the misspelled word. In the event the comparison does not yield a correct match, the skeletal form of the misspelled word is repeatedly modified and each modified form is compared with the data base of skeletons.

Claims

1. A process for the automated spelling correction of a graphic word, said process comprising the steps of

A. converting each graphic word of a machine-stored and machine-readable dictionary set of correctly spelled words to a specified linguistically salient word skeleton and storing also the resultant set of word skeletons,

B. converting a designated word from a conventional graphic representation to said specified linguistically salient word skeleton and storing the resultant word skeleton,

each said converting step comprising the steps of

(i) omitting from the word skeleton produced thereby a selected alpha set, if any, of the word being converted which lacks isomorphy with a phonetic representation of that selected set, and

(ii) replacing with a different linguistic symbol another selected alpha set, if any, of the word being converted which lacks isomorphy with a phonetic representation of that other selected set,

C. comparing said skeleton of said designated word with said dictionary set of word skeletons,

D. responding to a match from said comparison of word skeletons and producing from the matching skeleton of said dictionary set a corrective set of one or more corresponding grapic words of said dictionary set, and

E. producing a visual display of said corrective word set.

2. A process according to claim 1 in which each said converting step produces a word skeleton having lesser linguistic discrepancy from a phonetic representation of the word being converted than the graphic form of that word has.

3. A process according to claim 1 comprising the further steps of

A. responding to the absence of a selected match from said comparison of word skeletons and modifying said skeleton of said designated word,

B. comparing said modified skeleton with said dictionary set of word skeletons, and

C. repeating said modifying step and said modified-skeleton comparing step selectively in response to the continued absence of said selected match.

4. A process according to claim 1 in which said converting steps include the steps of selectively providing a four-way vocalic distinction in the skeleton of a short word and selectively providing only a two-way vocalic distinction in the skeleton of a long word.

5. A process according to claim 4 in which said converting steps include the further step of classifying a word having only a single set of one or more contiguous vowels, other than a silent final vowel, as a short word.

15. A process according to claim 1 in which each said converting step further comprises the steps of

(i) converting to an alpha set "s", an alpha set consisting of a character "c" followed immediately by any one of the characters "e", "i", and "y",

(ii) converting to an alpha set "s", a non-word-initial alpha set "z",

(iii) converting to an alpha set "kw", an alpha set "qu", and

(vi) converting to an alpha set "r", a word-initial alpha set "wr".

16. A process according to claim 15 in which each said converting step further comprises sequential steps selected from the sequential steps of

(i) converting to an alpha set "w", an alpha set "wh" which is followed immediately by any one of the characters "e", "i", "a", and "y",

(ii) converting to an alpha set "kh", an alpha set "tch",

(iii) converting to an alpha set "kh", an alpha set "tu" which

(a) is followed by a single occurrence of any one of the characters "r", "n", "m", and "l" which, in turn, is followed by any one of the characters "e", "a", "i", "o", and "y", and

(b) does not begin in character position one or in character position two of the word,

(iv) converting to an alpha set "kho", an alpha set which

(a) consists of a character sequence "tu" followed by any one of the characters "o", "a", and "e", and

(b) which does not begin in character position one or character position two of the word being converted,

(v) converting to a first non-alpha symbol, a word-final alpha set "y" which does not form a portion of a word having a character length less than three,

(vi) converting to said first symbol, a word-final alpha set "ie" which does not form a portion of a word having a character length less than four,

(vii) converting to said first symbol, a word-final alpha set "i" which does not form a portion of a word having a character length less than three,

(viii) converting to said first symbol, an alpha set which

(a) consists of either of the characters "i" or "y", and

(b) is both preceded and followed by any one of the characters "e", "i", "o", "a", and "u",

(ix) converting to an alpha set "i", an alpha set "y" which is immediately preceded by a consonant,

(x) converting to an alpha set "sh", an alpha set which

(a) consists of either of the character sequences "si" or "ti",

(b) is followed immediately by any one of the characters "a", "o", and "u", and

(c) does not begin in character position one or character position two of the word,

(xi) converting to an alpha set "ge", a word-final alpha set "gue" which does not begin in character position one or character position two of the word,

(xii) converting to an alpha set "oo", an alpha set "ue",

(xiii) converting to an alpha set "oo", an alpha set which consists of any one of the characters "e", "a", and "o" followed by either of the characters "u" or "w", and which

(a) is followed by a consonant, or

(b) is word-final,

(xiv) converting to a trace symbol, a word-final alpha set which

(a) consists of either of the character sequences "ea" or "ia", and

(b) does not form a portion of a word having a character length less than four,

(xv) converting to a trace symbol, a word-initial alpha set consisting of one or more occurrences any of the characters "a", "e", "i", "o", and "u",

(xvi) converting to an alpha set "g", an alpha set "dg",

(xvii) converting to an alpha set "k", an alpha set "c",

(xviii) converting an alpha set consisting of either of a doubly-adjacent or triply-adjacent occurrence of a single consonant to an alpha set being said single consonant,

(xix) converting to an alpha set "x", an alpha set "ks",

(xx) converting to an alpha set "xhon", a non-word-initial alpha set "xion",

(xxi) converting to an alpha set "s", a word-initial alpha set "ps",

(xxii) converting to an alpha set "r", an alpha set "rh",

(xxiii) converting to an alpha set "te", a non-word-initial alpha set "ght",

(xxiv) converting to an alpha set "f", an alpha set "ph",

(xxv) converting to an alpha set "n", an alpha set "gn",

(xxvi) converting to an alpha set "n", a word-initial alpha set which consists of either of the character sequences "kn" or "pn", and

(xxvii) converting to an alpha set "x", an alpha set "xs".

17. A process according to claim 16 in which each said converting step further comprises sequential steps selected from the sequential steps of

(i) converting to a second non-alpha symbol, an alpha set which consists of any one of the characters "e", "i", and "a" and which is preceded by

(a) exclusively consonants, or

(b) a trace symbol, resulting from a prior-executed conversion step, which is followed exclusively by consonants,

(ii) converting to a third non-alpha symbol, an alpha set which consists of either of the characters "o" or "u" and which is preceded by

(a) exclusively consonants, or

(b) a trace symbol, resulting from a prior-executed conversion step, which is followed exclusively by consonants,

(iii) converting to said third symbol, a non-word-initial second symbol which results from a prior conversion step, and which is followed by a singly-occurring character "r" which

(1) is followed by a consonant not a character "r", or

(2) is word-final,

(iv) converting to said third symbol, a word-final alpha set "o" which forms a portion of a word having a character length of two or more,

(v) converting to said third symbol, a word-final alpha set "oe" which forms a portion of a word having a character length of two or more,

(vi) converting to a fourth non-alpha symbol, a second symbol which results from a prior conversion step, and which is followed exclusively by consonants, and

(vii) converting to a fifth non-alpha symbol, a third symbol which results from a prior conversion step, which is followed exclusively by consonants,

(viii) deleting a non-word-initial alpha set consisting of one or more occurrences of any of the characters "a", "e", "i", "o", "u", and "y".

6. In a process for automated spelling correction by the comparison of a graphic word to be corrected with a dictionary set of correctly spelled words to produce a corrective set of one or more dictionary words selectively matching the designated word, the improvement comprising the steps of

A. producing from the designated word in conventional graphic representation, by a first transformation, a designated-word skeleton representing linguistically-salient phonetic features of that word, said transformation comprising the steps of

(i) omitting from the skeleton produced thereby a selected alpha set, if any, of the word being converted which lacks isomorphy with a phonetic representation of that selected set, and p2 (ii) replacing with a different linguistic symbol another seleted alpha set, if any, of the word being converted which lacks isomorphy with a phonetic representation of that other selected set,

B. effecting said comparison by comparing said designated-word skeleton with a set of dictionary-word skeletons, each skeleton of which corresponds to one said correctly-spelled word and which represents linguistically-salient features of that word according to said same first transformation, and

C. selecting from said dictionary set of words the one or more words which correspond to the dictionary-word skeleton which exactly matches the designated-word skeleton, thereby to produce said corrective set of words.

7. In automated spelling according to claim 6, the further improvement comprising the steps of

A. selectively modifying, in response to the absence of an acceptable match of skeletons, said designated-word skeleton by replacing one set of one or more skeleton symbols with a different set of such symbols,

B. repeating said comparing step with the midified skeleton, and

C. selectively repeating said modifying step and said compare-repeating step in response to the continued absence of an acceptable match of skeletons.

8. In apparatus for automated spelling correction by the comparison of a graphic word to be corrected with a dictionary set of correctly spelled words to produce a corrective set of one or more dictionary words selectively matching the designated word, the improvement comprising,

A. means for producing from the designated word in conventional graphic representation, by a first transformation, a designated-word skeleton representing linguistically-salient phonetic features of that word, said transformation means comprising means for

(i) omitting from the skeleton produced thereby a selected alpha set, if any, of the word being converted which lacks isomorphy with a phonetic representation of that selected set, and

(ii) replacing with a different linguistic symbol another seleted alpha set, if any, of the word being converted which lacks isomorphy with a phonetic representation of that other selected set,

B. means for effecting said comparison by comparing said designated-word skeleton with a set of dictionary-word skeletons, each skeleton of which corresponds to one said correctly-spelled word and which represents linguistically-salient features of that word according to said same first transformation, and

C. means for selecting from said dictionary set of words the one or more words which correspond to the dictionary-word skeleton which exactly matches the designated-word skeleton, thereby to produce said corrective set of words.

9. In apparatus for automated spelling according to claim 8, the further improvement comprising

A. means for selectively modifying, in response to the absence of an exact match of skeletons, said designated-word skeleton by replacing one set of one or more skeleton symbols with a different set of such symbols,

B. means for repeating said comparing step with the modified skeleton, and

C. means for selectively repeating said modifying step and said compare-repeating step in response to the continued absence of an exact match of skeletons.

18. In apparatus according to claim 8, the further improvement in which said transformation means further comprises means for

(i) converting to an alpha set "s", an alpha set consisting of a character "c" followed immediately by any one of the characters "e", "i", and "y",

(ii) converting to an alpha set "s", a non-word-initial alpha set "z",

(iii) converting to an alpha set "kw", an alpha set "qu", and

(iv) converting to an alpha set "r", a word-initial alpha set "wr".

19. In apparatus according to claim 18, the further improvement in which said transformation means further comprises means for executing sequential operations selected from the sequential operations of

(i) converting to an alpha set "w", an alpha set "wh" which is followed immediately by any one of the characters "e", "i", "a", and "y",

(ii) converting to an alpha set "kh", an alpha set "tch",

(iii) converting to an alpha set "kh", an alpha set "tu" which

(a) is followed by a single occurrence of any one of the characters "r", "n", "m", and "l" which, in turn, is followed by any one of the characters "e", "a", "i", "o", and "y", and

(b) does not begin in character position one or in character position two of the word,

(iv) converting to an alpha set "kho", an alpha set which

(a) consists of a character sequence "tu" followed by any one of the characters "o", "a", and "e", and

(b) which does not begin in character position one or character position two of the word being converted,

(v) converting to a first non-alpha symbol, a word-final alpha set "y" which does not form a portion of a word having a character length less than three,

(vi) converting to said first symbol, a word-final alpha set "ie" which does not form a portion of a word having a character length less than four,

(vii) converting to said first symbol, a word-final alpha set "i" which does not form a portion of a word having a character length less than three,

(viii) converting to said first symbol, an alpha set which

(a) consists of either of the characters "i" or "y", and

(b) is both preceded and followed by any one of the characters "e", "i", "o", "a", and "u",

(ix) converting to an alpha set "i", an alpha set "y" which is immediately preceded by a consonant,

(x) converting to an alpha set "sh", an alpha set which

(a) consists of either of the character sequences "si" or "ti",

(b) is followed immediately by any one of the characters "a", "o", and "u", and

(c) does not begin in character position one or character position two of the word,

(xi) converting to an alpha set "ge", a word-final alpha set "gue" which does not begin in character position one or character position two of the word,

(xii) converting to an alpha set "oo", an alpha set "ue",

(xiii) converting to an alpha set "oo", an alpha set which consists of any one of the characters "e", "a", and "o" followed by either of the characters "u" or "w", and which

(a) is followed by a consonant, or

(b) is word-final,

(xiv) converting to a trace symbol, a word-final alpha set which

(a) consists of either of the character sequences "ea" or "ia ", and

(b) does not form a portion of a word having a character length less than four,

(xv) converting to a trace symbol, a word-initial alpha set consisting of one or more occurrences any of the characters "a", "e", "i", "o", and "u",

(xvi) converting to an alpha set "g", an alpha set "dg",

(xvii) converting to an alpha set "k", an alpha set "c",

(xviii) converting an alpha set consisting of either of a doubly-adjacent or triply-adjacent occurrence of a single consonant to an alpha set being said single consonant,

(xix) converting to an alpha set "x", an alpha set "ks",

(xx) converting to an alpha set "xhon", a non-word-initial alpha set "xion",

(xxi) converting to an alpha set "s", a word-initial alpha set "ps",

(xxii) converting to an alpha set "r", an alpha set "rh",

(xxiii) converting to an alpha set "te", a non-word-initial alpha set "ght",

(xxiv) converting to an alpha set "f", an alpha set "ph",

(xxv) converting to an alpha set "n", an alpha set "gn",

(xxvi) converting to an alpha set "n", a word-initial alpha set which consists of either of the character sequences "kn" or "pn", and

(xxvii) converting to an alpha set "x", an alpha set "xs".

20. In apparatus according to claim 19, the further improvement in which said transformation means further comprises means for executing sequential operations selected from the sequential operations of

(i) converting to a second non-alpha symbol, an alpha set which consists of any one of the characters "e", "i", and "a" and which is preceded by

(a) exclusively consonants, or

(b) a trace symbol, resulting from a prior-executed conversion step, which is followed exclusively by consonants,

(ii) converting to a third non-alpha symbol, an alpha set which consists of either of the characters "o" or "u" and which is preceded by

(a) exclusively consonants, or

(b) a trace symbol, resulting from a prior-executed conversion step, which is followed exclusively by consonants,

(iii) converting to said third symbol, a non-word-initial second symbol which results from a prior conversion step, and which is followed by a singly-occurring character "r" which

(1) is followed by a consonant not a character "r", or

(2) is word-final,

(iv) converting to said third symbol, a word-final alpha set "o" which forms a portion of a word having a character length of two or more,

(v) converting to said third symbol, a word-final alpha set "oe" which forms a portion of a word having a character length of two or more,

(vi) converting to a fourth non-alpha symbol, a second symbol which results from a prior conversion step, and which is followed exclusively by consonants, and

(vii) converting to a fifth non-alpha symbol, a third symbol which results from a prior conversion step, which is followed exclusively by consonants,

(viii) deleting a non-word-initial alpha set consisting of one or more occurrences of any of the characters "a", "e", "i", "o", "u", and "y".

10. Apparatus for the automated spelling correction of a graphic word, said apparatus comprising

A. means for converting each graphic word of a machine-stored and machine-readable dictionary set of correctly spelled words to a specified linguistically salient word skeleton and for storing also the resultant set of word skeletons, and for convertins a designated word from conventional graphic representation to said specified linguistically salient word skeleton and for storing the resultant word skeleton, said converting means comprising

(i) means for elimating from the word skeleton produced thereby a selected alpha set, if any, of the word being converted which lack isomorphy with a phonetic representation of that selected set, and

(ii) means for replacing with a different linguistic symbol another selected alpha set, if any, of the word being converted which lacks isomorphy with a phonetic representation of that other selected set,

B. means for comparing said skeleton of said designated word with said dictionary set of word skeletons,

C. means for responding to a match from said comparison of word skeletons and for producing from the matching skeleton of said dictionary set a corrective set of one or more corresponding graphic words of said dictionary set, and

D. means for producing a visual display of said corrective word set.

11. Apparatus according to claim 10 in which said converting means includes means for producing a word skeleton having lesser linguistic discrepancy from the phonetic representation of a word being converted than the graphic form of that word has.

12. Apparatus according to claim 10 further comprising

A. means for responding to the absence of a match from said comparison of word skeletons and for modifying said skeleton of said designated word,

B. means for comparing said modified skeleton with said dictionary set of word skeletons, and

C. means for repeating said modifying operation and said modified-skeleton comparing operation selectively in response to the continued absence of said selected match.

13. Apparatus according to claim 10 in which said converting means includes means for selectively providing a four-way vocalic distinction in the skeleton of a short word and selectively providing only a two-way vocalic distinction in the skeleton of a long word.

14. Apparatus according to claim 13 in which said converting means includes means for classifying a word having only a single set of one or more contiguous vowels, other than a silent final vowel, as a short word.