Apparatus and method for linguistic expression processing

• US 4,771,401 A
• Filed: 03/31/1986
• Issued: 09/13/1988
• 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: Kaufman, Ilia, Kucera, Henry
• Primary Examiner(s): NOT, DEFINED
• Application Number:
  US06/846,366
• Time in Patent Office: 897 Days
• Field of Search: 364/200 MS File, 364/900 MS File, 364/419
• US Class Current: 715/206
• 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

An apparatus and method for linguistic expression processing provides features for spelling verification, correction, and dictionary database storage. The system utilizes a linguistically salient word skeleton-forming process to correct both typrographic and cognitive spelling errors. The system also uses a suspect expression modification sequence to recognize and correct typographical spelling errors. A linguistic expression database includes a master lexicon having expression blocks arranged in accord with respective collation ranges of skeletons of expressions contained therein. In one preferred embodiment, these linguistically salient word skeletons corresponding to the master lexicon expressions are not retained in the database.

Claims

1. A digital data processing apparatus for storing digitally encoded linguistic information, said apparatus comprising

A. input means for accepting a signal representative of linguistic expression,

B. database storage means for storing a linguistic expression database,

said database storage means including master lexicon storage means for storing digitally encoded information representative of plural linguistic expressions and including plural addressable lexicon storage blocks, each said block storing one or more lexicon entries, each said lexicon entry storing signals representative of a linguistic expression, each said expression including at least one alphanumeric character,

C. database access means connected with said input means and with said database storage means for accessing information stored in said linguistic expression database,

said database access means including master lexicon access means for addressably accessing each said lexicon storage block according to its skeletal collation range, said skeletal collation range being defined by upper and lower bounds of a collation sequence of linguistically salient word skeletons of said one or more linguistic expressions represented within a lexicon storage block, and

D. output means connected with said database access means for generating a signal representative of linguistic information.

2. A digital data processing apparatus according to claim 1 wherein a first said lexicon entry, which represents a first linguistic expression, comprises differential encoding means for representing a difference in character content between said first expression and a second linguistic expression represented within a second said lexicon entry.

3. A digital data processing apparatus according to claim 1 wherein a first said lexicon entry, which represents a first linguistic expression, comprises differential encoding means for representing a difference in character content between said first expression and a second linguistic expression represented within a second said lexicon entry, said first and second lexicon entries being stored in a common lexicon storage block.

4. A digital data processing apparatus according to claim 2 wherein said differential encoding means comprises at least one of

A. explicit differential encoding means for explicitly representing an alphanumeric character of said first linguistic expression, and

B. indirect differential encoding means for representing an alphanumeric character sequence common to said first linguistic expression and to a third linguistic expression represented within a third said lexicon entry.

5. A digital data processing apparatus according to claim 1 wherein at least one said lexicon entry comprises at least one of

A. suffix encoding means for representing a suffix pattern of a linguistic expression,

B. hyphenation encoding means for representing a hyphenation pattern of a linguistic expression, and

C. capitalization encoding means for representing a capitalization pattern of a linguistic expression.

6. A digital data processing apparatus according to claim 1 wherein said linguistic expression database comprises common expression verification table means for storing digitally encoded information representative of plural commonly used linguistic expressions and including plural common-expression entries, each said common-expression entry including means for storing a first hash code of a first common linguistic expression, and wherein said database access means comprises means for addressably accessing each said common-expression entry according to a first selected index.

7. An apparatus according to claim 1 wherein said linguistic expression database comprises modified suspect expression verification table means for storing digitally encoded information representative of substantially all of the linguistic expressions represented in the master lexicon storage means and including plural addressable suspect-expression entries, each said suspect-expression entry including means for storing a second hash code of a common linguistic expression, and wherein said database access means comprises means for addressably accessing each said suspect expression entry according to a second index.

8. An apparatus according to claim 1 wherein said linguistic expression database comprises user expression table means for storing digitally encoded information representative of one or more user-defined expressions and including one or more user-expression entries, each said user-expression entry including means for storing a signal representative of a user-defined expression, and wherein said database access means comprises means for addressably accessing each said user-expression entry.

9. An apparatus according to claim 1 wherein said database access means comprises block index means for storing digitally encoded information representative of collation sequences of lexicon blocks and including plural addressable block-index entries, each said block-index entry including means for storing a signal representative of at least one of a collation sequence lower bound and a collation sequence upper bound.

10. An apparatus accoding to claim 1 wherein said master lexicon is substantially free of digitally encoded information explicitly representative of linguistically salient word skeletons.

11. A digital data processing apparatus for electronic spelling verification comprising

A. input means for accepting a signal representative of a suspect linguistic expression,

B. database storage means for storing a linguistic expression database,

said database storage means including master lexicon storage means for storing digitally encoded information representative of plural linguistic expressions and including plural addressable lexicon storage blocks, each said block storing one or more lexicon entries, each said lexicon entry storing signals representative of a linguistic expression, each said expression including at least one alphanumeric character,

C. database access means connected with said input means and with said database storage means for accessing information stored in said linguistic expression database,

said database access means including master lexicon access means for addressably accessing each said lexicon storage block according to its skeletal collation range, said skeletal collation range being defined by upper and lower bounds of a collation sequence of linguistically salient word skeletons of said one or more linguistic expressions represented within a lexicon storage block, and

D. database verification means connected with said database access means for locating within said linguistic expression database a linguistic expression matching suspect expression,

said database verification means including master lexicon verification means for matching said suspect expression with a linguistic expression represented within said master lexicon means, and

E. output means connected with said database verification means for generating a signal indicative of the success of locating a matching database expression.

12. An apparatus according to claim 11 wherein said master lexicon verification means comprises binary search means for identifying a candidate master lexicon block likely to contain an entry representing an expression matching said suspect expression.

13. An apparatus according to claim 12 wherein said binary search means comprises means for generating a linguistically salient word skeleton of said suspect expression.

14. An apparatus according to claim 11 wherein said master lexicon verification means comprises differential decoding means responsive to a differential coding of a first lexicon entry for generating a signal representative of a linguistic expression, said differential encoding being representative of a difference in character content between the linguistic expression represented in said first lexicon entry and a second linguistic expression represented in a second said lexicon entry.

15. An apparatus according to claim 14 wherein said differential decoding means comprises means responsive to at least one of

i. a differential coding which coding is explicitly representative of an alphanumeric character of said first linguistic expression, and

ii. a differential coding which is indirectly representative of a character sequence of said first linguistic expression, said character sequence being common to said first linguistic expression and a third linguistic expression represented in a third lexicon entry for generating signals representative of a character sequence of said first expression.

16. An apparatus according to claim 11 wherein said database verification means comprises common expression verification means of identifying said suspect expression as being a commonly used linguistic expression.

17. An apparatus according to claim 15 wherein said common expression verification means comprises means for generating a first hash code representative of said suspect expression.

18. An apparatus according to claim 11 wherein said database verification means comprises user expression verification means for identifying said suspect expression as being a user-defined expression.

19. An digital data processing apparatus for electronic spelling correction comprising

A. input means for accepting a signal representative of a suspect linguistic expression,

B. database storage means for storing a linguistic expression database,

said database storage means including master lexicon storage means for storing digitally encoded informaticn representative of plural linguistic expressions and including plural addressable lexicon storage blocks, each said block storing one or more lexicon entries, each said lexicon entry storing signals representative of a linguistic expression, each said expression including at least one alphanumeric character,

C. database access means connected with said input means and with said database storage means for accessing information stored in said linguistic expression database,

said database access means including master lexicon access means for addressably accessing each said lexicon storage block according to its skeletal collation range, said skeletal collation range being defined by upper and lower bounds of a collation sequence of linguistically salient word skeletons of said one or more linguistic expressions represented within a lexicon storage block, and

D. database verification means connected with said input means for locating within said linguistic expression database an expression substitutable for said suspect linguistic expression,

said database matching means including master lexicon matching means for identifying a master lexicon expression substitutable for said suspect expression, and

E. output means connected with said database matching means for generating a signal indicative of the success of locating within the database an expression substitutable for the suspect expression.

20. An apparatus according to claim 19 wherein said master lexicon matching means comprises means for generating a linguistically salient word skeleton of said suspect expression and a linguistically salient word skeleton of at least one said master lexicon expression, and for comparing said skeletons to generate a signal indicative of a match thereof.

21. An apparatus according to claim 20 wherein said master lexicon matching means comprises target modification means responsive to the absence of a match of skeletons for

A. selectively modifying said suspect word skeleton by replacing one set of one or more skeleton symbols with a different set of such symbols,

B. comparing said modified suspect skeleton with a linguistically salient word skeleton of at least one said database alternate expression, and

C. selectively repeating said modifying step and said comparing step in response to the continued absence of a match of skeletons.

22. An apparatus according to claim 19 further comprising suspect expression modification means for generating a modified form of said suspect expression and for locating a database expression matching said modified suspect expression.

23. An apparatus according to claim 22 wherein said suspect expression modification means comprises means for at least one of

i. generating a signal representative of an expression having a transposed character sequence,

ii. generating a signal representative of an expression having a deleted character,

iii. generating a signal representative of an expression having an added character, and

iv. generating a signal representative of an expression having a replaced character.

24. An apparatus according to claim 22 wherein said suspect expression modification comprises means for identifying said modified expression as a potentially valid linguistic expression.

25. An apparatus according to claim 24 wherein said suspect expression modification means comprises means for generating a linguistically salient word skeleton of said modified suspect expression, and further comprises binary search means for identifying a candidate master lexicon block likely to contain an entry representing an expression matching said modified suspect expression.

26. An apparatus according to claim 19 wherein said master lexicon matching means comprises differential decoding means responsive to a differential coding of a first lexicon entry for generating a signal representative of a linguistic expression, said differential encoding being representative of a difference in character content between the linguistic expression represented in said first lexicon entry and a second linguistic expression represented in a second said lexicon entry.

27. An apparatus according to claim 26 wherein said differential decoding means comprises means responsive to at least one of

i. a differential coding which coding is explicitly representative of an alphanumeric character of said first linguistic expression, and

ii. a differential coding which is indirectly representative of a character sequence of said first linguistic expression, said character sequence being common to said first linguistic expression and a third linguistic expression represented in a third lexicon entry for generating signals representative of a character sequence of said first expression.

28. An apparatus according to claim 19 further comprising user expression verification means for identifying a suspect expression or modification thereof as matching a user defined expression.

29. A method for storing digitally-encoded linguistic information in a digital data processing apparatus, said method comprising the steps of

A. inputting plural linguistic expressions, each said linguistic expression including alphanumeric characters,

B. generating signals representing plural master lexicon entries, each said entry representing an input linguistic expression,

C. forming plural master lexicon blocks, each said block being formed by the steps of

(i) generating a linguistically salient word skeleton for each linguistic expression in the block,

(ii) collating said block linguistically salient word skeletons and determining therefrom a block skeletal collation range, and

(iii) storing in a storage medium one or more said master lexicon entries,

D. forming a master lexicon wherein said blocks are arranged in an addressable sequence determined in accord with their respective skeletal collation ranges.

30. A method according to claim 29 wherein said master lexicon entry-forming step comprises the step of generating a digital code representing a difference in character content between a first input expression represented in a first master lexicon entry and a second input expression represented in a second master lexicon entry.

31. A method according to claim 29 wherein said master lexicon entry-forming step comprises the step of generating a digital code representing a difference in character content between a first input expression represented in a first master lexicon entry and a second input expression represented in a second master lexicon entry, and wherein said block forming step comprises storing said first and second master lexicon entries in a common block.

32. A method according to claim 30 wherein said character differential code generating step comprises at least one step selected from the steps of

A. generating an explicit differential code for explicitly representing an alphanumeric character of said first linguistic expression, and

B. generating an indirect differential code for representing an alphanumeric character sequence common to said first linguistic expression and to a third linguistic expression represented in a third said lexicon entry.

33. A method according to claim 29 wherein said master lexicon entry-forming step comprises at least one step selected from the steps of

A. generating a suffix code for representing a suffix pattern of a linguistic expression,

B. generating a hyphenation code for representing a hyphenation pattern of a linguistic expression, and

C. generating a capitalization code for representing a capitalization pattern of a linguistic expression.

34. A method according to claim 29 comprising the further step of forming a common expression verification table having digitally encoded information representative of plural common linguistic expressions, said common expression verification table-forming step including the steps of

(i) generating a first hash code representing a common linguistic expression, and

(ii) storing said first hash code for addressable access in accord with a first index value.

35. A method according to claim 29 comprising the further step of forming a modified suspect expression verification table having digitally encoded information representative of said input linguistic expressions stored in said master lexicon, said modified suspect expression verification table-forming step including the steps of

(i) generating a second hash code representative of one or more said input linguistic expressions,

(ii) storing said second hash code for addressable access in accord with a second index value.

36. A method according to claim 29 comprising the further step of forming a user expression table having digitally encoded information representative of one or more user-defined expressions, said user expression table-forming step comprising the steps of

(i) inputting a user-defined expression, and

(ii) storing said user-defined expression for addressable access according to a third index value.

37. A method according to claim 29 further comprising the step of forming a block index table having digitally encoded information representative of collation ranges of plural master lexicon blocks, said block index table forming step including the step of storing, for each master lexicon block, a digital code representative of a skeletal collation range of each said block.

38. A method for spelling verification in a digital data processing apparatus, said method comprising the steps of

A. inputting plural linguistic expressions, each said linguistic expression including alphanumeric characters,

B. generating signals representing plural master lexicon entries, each said entry representing an input linguistic expression,

C. forming plural master lexicon blocks, each said block being formed by the steps of

(i) generating a linguistically salient word skeleton for each linguistic expression in the block,

(ii) collating said block linguistically salient word skeletons and determining therefrom a block skeletal collation range,

(iii) storing in a storage medium one or more master lexicon entries,

D. forming a master lexicon wherein said blocks are arranged in an addressable sequence determined in accord with their respective skeletal collation ranges,

E. inputting a signal representative of a suspect linguistic expression,

F. matching said suspect expression with an expression represented in said master lexicon, and

G. generating a signal indicative of the success of said matching step.

39. A method according to claim 38 wherein said matching step comprises the step of identifying a candidate master lexicon block likely to include an entry matching said suspect expression.

40. A method according to claim 39 wherein said identifying step comprises the step of generating a linguistically salient word skeleton of said suspect expression.

41. An method according to claim 38 wherein said matching step comprises the step of responding to a differential coding of a first lexicon entry for generating a signal representative of a first linguistic expression, said differential encoding being representative of a difference in character content between the linguistic expression represented in said first lexicon entry and a second linguistic expression represented in a second said lexicon entry.

42. A method according to claim 41 wherein said responding step includes the steps of

A. generating an alphanumeric character in response to an explicit differential coding representative of an alphanumeric character of said first linguistic expression, and

B. generating an alphanumeric character sequence in response to an indirect differential code, said indirect differential code representing a character sequence common to said first linguistic expression and to a third linguistic expression represented in a third lexicon entry.

43. A method according to claim 38 further comprising the step of identifying said suspect expression in a digitally encoded table of common linguistic expressions.

44. A method according to claim 43 wherein said common expression identification step comprises the step of generating a first hash code representative of said suspect expression.

45. A method according to claim 38 further comprising the step of identifying said suspect expression as matching an entry in a digitally encoded table of user-defined expressions.

46. A method for electronic spelling correction in a digital data processing apparatus, said method comprising the steps of

A. inputting plural linguistic expressions for storage, each said linguistic expression including alphanumeric characters,

B. generating signals representing plural master lexicon entries, each said entry representing an input linguistic expression,

C. forming plural master lexicon blocks, each said block being formed by the steps of

(i) generating a linguistically salient word skeleton for each linguistic expression in the block, wherein said skeleton includes skeletal symbols,

(ii) collating said block linguistically salient word skeletons and determining therefrom a block skeletal collation range, and

(iii) storing in a storage medium one or more master lexicon entries,

D. forming a master lexicon wherein said blocks are arranged in an addressable sequence determined in accord with their respective skeletal collation range thereof,

E. inputting a signal representative of a suspect linguistic expression,

F. locating within said master lexicon an entry representing an expression substitutable for said suspect expression, and

G. generating a signal indicative of the success of said locating step.

47. A method according to claim 46 wherein said master lexicon expression locating step comprises the steps of

A. generating a linguistically salient word skeleton of said suspect expression and a linguistically salient word skeleton of at least one said master lexicon expression, and

B. comparing said skeletons to generate a signal indicative of a match thereof.

48. A method according to claim 47 wherein said master lexicon expression locating step comprises the step of responding to the absence of a match of skeletons for executing the steps of

A. selectively modifying said suspect expression skeleton by replacing one set of one or more skeletal symbols with a different set of such symbols,

B. comparing said modified suspect expression skeleton with a linguistically salient word skeleton of at least one said master lexicon expression, and

C. selectively repeating said modifying step and said comparing step in response to the continued absence of a match of skeletons.

49. A method according to claim 46 further comprising the step of generating a signal representative of a modified form of said suspect expression and for locating a linguistic expression matching said modified suspect expression.

50. A method according to claim 49 wherein said suspect expression modification step comprises at least one step selected from the steps of

i. generating a signal representative of an expression having a transposed character sequence,

ii. generating a signal representative of an expression having a deleted character,

iii. generating a signal representative of an expression having an added character, and

iv. generating a signal representative of an expression having a replaced character.

51. A method according to claim 49 wherein said suspect expression modification step includes the step of identifying said modified expression as being a valid linguistic expression.

52. A method according to claim 51 wherein said suspect expression modification step comprises the steps of

A. generating a linguistically salient word skeleton of said modified suspect expression, and

B. identifying a candidate master lexicon block likely to contain an entry representing an expression matching said modified suspect expression.

53. A method according to claim 49 wherein said suspect expression modification step comprises the step of matching said modified suspect expression with a table of user-defined expressions.

54. A method according to claim 46 wherein said matching step comprises the step of responding to a differential coding contained in a first lexicon entry for generating a signal representative of a first linguistic expression, said differential encoding being representative of a difference in character content between the linguistic expression represented in said first lexicon entry and a second linguistic expression represented in a second said lexicon entry.

55. A method according to claim 53 wherein said responding step includes the steps of

A. generating an alphanumeric character in response to an explicit differential coding representative of an alphanumeric character of said first linguistic expression, and

B. generating an alphanumeric character sequence in response to an indirect differential code representative of a character sequence of said first linguistic expression, said character sequence being common to said first linguistic expression and a third linguistic expression represented in in a third lexicon entry.

56. In a digital data processing apparatus having a data storage means for storing a linguistic expression database, said data storage means including plural entry means, each for storing a signal representative of a linguistic expression, each expression including at least one alphanumeric character, said digital data processing apparatus further having data access means for accessing linguistic expression information stored in said database, the improvement wherein said data storage means comprises

differential encoding means for storing a differential coding representative of differences between a first linguistic expression stored in a first entry means and a second linguistic expression stored in a second entry means, said differential encoding means including

i. explicit differential encoding means for storing a first digital coding pattern explicitly representative of at least one alphanumeric character of said first linguistic expression, and

ii. indirect differential encoding means for storing a second digital coding pattern representative of an alphanumeric character sequence common to said first linguistic expression and a third linguistic expression stored in a third said entry means of said database.

57. In an apparatus according to claim 56 the further improvement wherein said data access means comprises means responsive to said differential dcoding for generating a signal representative of a linguistic expression character sequence.

58. In an apparatus according to claim 56 the futher improvement wherein each of said indirect differential encoding means and said explicit differential encoding means comprises at least one of

A. suffix encoding means for storing a digital coding representative of a suffix pattern of a linguistic expression,

B. hyphenation encoding means for storing a digital coding representative of a hyphenation pattern of a linguistic expression, and

C. capitalization encoding means for storing a digital coding representative of a capitalization pattern of a linguistic expression.

59. In an apparatus according to claim 58, the further improvement wherein said indirect differential encoding means comprises decompression table means for storing signals representative of linguistic expression information, said decompression table means comprising at least one of

i. first decompression coding means for storing addressable digital codes representative of linguistic expression hyphenation and suffix patterns, and

ii. second decompression coding means for storing addressable digital codes representative of linguistic expression alphanumeric character sequences.

60. In a method for storing digitally encoded information forming a linguistic expression database of the type used in a digital data processing apparatus, said method having steps including inputting digital signals representative of plural linguistic expressions, each said expression including alphanumeric characters, and storing each said expression-representative signal to form a database entry, the improvement whereby said storing step includes the steps of

storing a differential coding representative of differences between a first linguistic expression stored in a first entry and a second linguistic expression stored in a second entry, said differential coding storing step including the steps of

i. generating a first digital coding pattern explicitly representative of at least one alphanumeric character of said first linguistic expression, and

ii. generating a second digital coding pattern representative of an alphanumeric character sequence common to at least two linguistic expressions stored in said database.

61. In a method according to claim 60 the further improvement whereby each of said indirect differential coding step and said explicit differential coding step comprise at least one of the steps of

A. generating a digital coding representative of a suffix pattern of a linguistic expression,

B. generating a digital coding representative of a hyphenation pattern of a linguistic expression, and

C. generating a digital coding representative of a capitalization pattern of a linguistic expression.

62. In a method according to claim 61, the further improvement whereby said indirect differential coding step comprises at least one of the steps of

i. generating and storing addressable digital codes representative of common linguistic expression hyphenation and suffix pattern, and

ii. generating and storing addressable digital codes representative of common linguistic expression alphanumeric character sequences.

63. A digital data processing apparatus for electronic spelling correction, said apparatus comprising

A. input means for accepting a signal representative of a suspect linguistic expression,

B. database storage means for storing signals representative of a set of valid linguistic expressions,

C. means for converting at least one said valid linguistic expression to a linguistically salient word skeleton, and for converting said suspect linguistic expression, or a modified form thereof, to a linguistically salient word skeleton, said converting means comprising

i. means for eliminating from the word skeleton produced thereby a selected alpha set, if any, of the expression being converted which lacks 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 expression being converted which lacks isomorphy with a phonetic representation of that other selected set,

D. means for comparing said suspect expression skeleton with at least one said valid expression skeleton, and

E. means for responding to a match from said comparison of word skeletons to generate a signal representative of a valid linguistic expression corresponding to a matching skeleton.

64. An apparatus according to claim 63 comprising target modification means for

A. selectively modifying said suspect word skeleton by replacing one set of one or more skeleton symbols with a different set of such symbols,

B. comparing said modified suspect skeleton with a linguistically salient word skeleton of at least one said database linguistic expression, and

C. selectively repeating said modifying step and said comparing step in response to the continued absence of a match of skeletons.

65. An apparatus according to claim 64 comprising means for generating from said input suspect expression a modified form thereof said modified suspect expression-generating means comprising at least one of

i. means for generating a signal representative of an expression having a transposed character sequence,

ii. means for generating a signal representative of an expression having a deleted character,

iii. means for generating a signal representative of an expression having an added character, and

iv. means for generating a signal representative of an expression having a replaced character.

66. A method of electronic spelling correction in a digital data processing apparatus having a database for storing signals representative of a set of valid linguistic expressions, said method comprising the steps of

A. accepting a signal representative of a suspect linguistic expression,

B. converting at least one said valid linguistic expression to a linguistically salient word skeleton and for converting said suspect linguistic expression, or a modified form thereof, to a linguistically salient word skeleton, each said converting step comprising the steps of

i. eliminating from the word skeleton produced thereby a selected alpha set, if any, of the expression 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 expression being converted which lacks isomorphy with a phonetic representation of that other selected set,

C. comparing said suspect expression skeleton with at least one said database expression skeleton, and

D. responding to a match from said comparison of word skeletons to generate a signal representative of a database expression corresponding to a matching skeleton.

67. A method according to claim 66 comprising the steps of

A. selectively modifying said suspect word skeleton by replacing one set of one or more skeleton symbols with a different set of such symbols,

B. comparing said modified suspect skeleton with a linguistically salient word skeleton of at least one said database expression, and

C. selectively repeating said modifying step and said comparing step in response to the continued absence of a match of skeletons.

68. A method according to claim 66 comprising the step of generating from said input suspect expression a modified form thereof said modified suspect expression-generating step comprising at least one of the steps of

i. generating a signal representative of an expression having a transposed character sequence,

ii. generating a signal representative of an expression having a deleted character,

iii. generating a signal representative of an expression having an added character, and

iv. generating a signal representative of an expression having a replaced character.