Method and apparatus for analyzing character strings

Abstract

A method for automatically identifying and correcting errors in electronically stored character strings input from handwritten character strings is disclosed. The input character strings are compared to a predetermined list of correct character strings by dividing the input character string and each of the correct character strings into at least one character string fragment. Each character string fragment or set of character string fragments is formed by applying at least one different fragmentation submethod to the character string. The corresponding fragments from the input character string and the correct character strings are then compared in turn. The correct character string producing a unique lowest comparison value is determined to be the correct character string intended by the input character string. Accordingly, the determined correct character string is output in place of the input character string.

What is claimed is: 
     
       1. A method of analyzing an uncorrected character string generated by an input device, comprising the steps of: dividing the uncorrected character string into at least one set of uncorrected character string fragments by use of at least one predetermined submethod;   successively selecting at least one correct character string from a predetermined list of correct character strings as at least one current correct character string,   comparing, for each current correct character string and each set of uncorrected character string fragments, a predetermined set of correct character string fragments to the corresponding set of uncorrected character string fragments to generate an error value for each predetermined set of correct character string fragments, wherein each predetermined set of correct character string fragments is generated by one predetermined submethod;   selecting, for each current correct character string, a lower error value from the generated error values as a corresponding total value for the current correct character string;   storing at least one current correct character string and the corresponding total value to a storage means; and   transferring the contents of the storage device to an appropriate output device upon reaching an end of the list of correct character strings;   wherein characters in the correct and uncorrected character string fragments are placed in a predetermined order without regard to ordering of the characters in the correct and uncorrected character strings, respectively.   
     
     
       2. The method of claim 1, wherein the step of transferring at least one correct string further comprises the steps of: selecting one correct character string from the predetermined list of correct character strings which has a unique and a lowest total value; and   transferring the selected correct character string to the output device for the uncorrected character string when the total value of the selected correct character string is below a predetermined threshold value.   
     
     
       3. A method of analyzing an uncorrected character string generated by an input device, comprising the steps of: dividing the uncorrected character string into at least one set of uncorrected character string fragments by use of at least one predetermined submethod;   successively selecting at least one correct character string from a predetermined list of correct character strings as at least one current correct character string,   comparing, for each current correct character string and each set of uncorrected character string fragments, a predetermined set of correct character string fragments to the corresponding set of uncorrected character string fragments to generate an error value for each predetermined set of correct character string fragments, wherein each predetermined set of correct character string fragments is generated by one predetermined submethod;   selecting, for each current correct character string, a lowest error value from the generated error values as a corresponding total value for the current correct character string;   storing at least one current correct character string and the corresponding total value to a storage means; and   transferring the contents of the storage device to an appropriate output device upon reaching an end of the list of correct character strings, wherein the corrected and uncorrected character strings are divided into no more than a predetermined number character string fragments.   
     
     
       4. A method of analyzing an uncorrected character string generated by an input device, comprising the steps of: dividing the uncorrected character string into at least one set of uncorrected character string fragments by use of at least one predetermined submethod;   successively selecting at least one correct character string from a predetermined list of correct character strings as at least one current correct character string,   comparing, for each current correct character string and each set of uncorrected character string fragments, a predetermined set of correct character string fragments to the corresponding set of uncorrected character string fragments to generate an error value for each predetermined set of correct character string fragments, wherein each predetermined set of correct character string fragments is generated by one predetermined submethod;   selecting, for each current correct character string, a lowest error value from the generated error values as a corresponding total value for the current correct character string;   storing at least one current correct character string and the corresponding total value to a storage means; and   transferring the contents of the storage device to an appropriate output device upon reaching an end of the list of correct character strings, wherein duplicate characters are added to a character string until a specified number of characters comprise the character string.   
     
     
       5. A method of analyzing an uncorrected character string generated by an input device, comprising the steps of: dividing the uncorrected character string into at least one set of uncorrected character string fragments by use of at least one predetermined submethod;   successively selecting at least one correct character string from a predetermined list of correct character strings as at least one current character string,   comparing, for each current correct character string and each set of uncorrected character string fragments, a predetermined set of correct character string fragments to the corresponding set of uncorrected character string fragments to generate an error value for each predetermined set of correct character string fragments, wherein each predetermined set of correct character string fragments is generated by one predetermined submethod;   selecting, for each current correct character string, a lowest error value from the generated error values as a corresponding total values for the current correct character string;   storing at least one current correct character string and the corresponding total value to a storage means; and   transferring the contents of the storage device to an appropriate output device upon reaching an end of the list of correct character strings, wherein one predetermined submethod comprises the steps of:   generating a first character string fragment by including all the characters of the character string up to but excluding a first consonant;   generating a next character string fragment by including the consonant and all subsequent characters of the character string up to but excluding a next consonant; and   repeating the next character string fragment generating step until the first of all the characters being included in a character string fragment and a predetermined number of character string fragments being generated occurs.   
     
     
       6. The method of claim 5, further comprising the step of deleting all characters duplicated within a single character string fragment. 
     
     
       7. A method of analyzing an uncorrected character string generated by an input device, comprising the steps of: dividing the uncorrected character string into at least one set of uncorrected character string fragments by use of at least one predetermined submethod;   successively selecting at least one correct character string from a predetermined list of correct character strings as at least one current correct character string,   comparing, for each current correct character string and each set of uncorrected character string fragments, a predetermined set of correct character string fragments to the corresponding set of uncorrected character string fragments to generate an error value for each predetermined set of correct character string fragments, wherein each predetermined set of correct character string fragments is generated by one predetermined submethod;   selecting, for each current correct character string, a lowest error value from the generated error values as a corresponding total value for the current correct character string;   storing at least one current correct character string and the corresponding total value to a storage means; and   transferring the contents of the storage device to an appropriate output device upon reaching an end of the list of correct character strings, wherein one predetermined submethod comprises the steps of:   generating a first character string fragment by including all the characters of the character string up to but excluding a first vowel;   generating a next character string fragment by including the vowel and all subsequent characters up to but excluding a next vowel; and   repeating the next character string fragment generating step until the first of all the characters being included in a character string fragment and a predetermined number of character string fragments being generated occurs.   
     
     
       8. The method of claim 7, further comprising the step of deleting all characters duplicated within a single character string fragment. 
     
     
       9. A method of analyzing an uncorrected character string generated by an input device, comprising the steps of: dividing the uncorrected character string into at least one set of uncorrected character string fragments by use of at least one predetermined submethod;   successively selecting at least one correct character string from a predetermined list of correct character strings as at least one current correct character string,   comparing, for each current correct character string and each set of uncorrected character string fragments, a predetermined set of correct character string fragments to the corresponding set of uncorrected character string fragments to generate an error value for each predetermined set of correct character string fragments, wherein each predetermined set of correct character string fragments is generated by one predetermined submethod;   selecting, for each current correct character string, a lowest error value from the generated error value as a corresponding total value for the current correct character string;   storing at least one current correct character string and the corresponding total value to a storage means; and   transferring the contents of the storage device to an appropriate output device upon reaching an end of the list of correct character strings, wherein one predetermined submethod comprises the steps of:   generating a first character string fragment by including all the characters of the string up to a first vowel-consonant combination;   including the vowel in the current fragment;   generating a next character string fragment by including the consonant in the next fragment and all subsequent characters up to a next vowel-consonant combination; and   repeating the including and next character string fragment generates steps until the first of all the character string of the characters string being included in a character string fragment and a predetermined number of character string fragments being generated occurs.   
     
     
       10. The method of claim 9, further comprising the step of deleting all characters duplicated within a single character string fragment. 
     
     
       11. A method of analyzing an uncorrected character string generated by an input device, comprising the steps of: dividing the uncorrected character string into at least one set of uncorrected character string fragments by use of at least one predetermined submethod;   successively selecting at least one correct character string from a predetermined list of correct character strings as at least one current correct character string,   comparing, for each current correct character string and each set of uncorrected character string fragments, a predetermined set of correct character string fragments to the corresponding set of uncorrected character string fragments to generate an error value for each predetermined sep of correct character string fragments, wherein each predetermined set of correct character string fragments is generated by one predetermined submethod;   selecting, for each current correct character string, a lowest error value from the generated error values as a corresponding total value for the current correct character string;   storing at least one current correct character string and the corresponding total value to a storage means; and   transferring the contents of the storage device to an appropriate output device upon reaching an end of the list of correct character strings, wherein one predetermined submethod comprises the steps of:   generating a first character strings fragment by including all the characters of the string up to a first consonant-vowel combination;   including the consonant in the current fragment;   generating a next character string fragment by including the vowel in the next fragment and all subsequent characters up to a next consonant-vowel combination; and   repeating the including and next character string fragment generating steps until the first of all the characters of the character string being included in a character string fragment and a predetermined number of character string fragments being generated occurs.   
     
     
       12. The method of claim 11, further comprising the step of deleting all characters duplicated within a single character string fragment. 
     
     
       13. A method of analyzing an uncorrected character string generated by an input device, comprising the steps of: dividing the uncorrected character string into at least one set of uncorrected character string fragments by use of at least one predetermined submethod;   successively selecting at least one correct character string from a predetermined list of correct character strings as at least one current correct character string,   comparing, for each current correct character string and each set of uncorrected character string fragments, a predetermined set of correct character string fragments to the corresponding set of uncorrected character string fragments to generate an error value for each predetermined set of correct character string fragments, wherein each predetermined set of correct character string fragments is generated by one predetermined submethod;   selecting, for each current correct character string, a lowest error value from the generated error values as a corresponding total value for the current correct character string;   storing at least one current correct character string and the corresponding total value to a storage means; and   transferring the contents of the storage device to an appropriate output device upon reaching an end of the list of correct character strings, wherein one predetermined submethod comprises the steps of:   generating a first digraph character by including a first character and a next character of the character string;   generating a next digraph character by including the next character and a next plus one character of the character string; and   repeating the next digraph character generating step until all the characters of the character string are in at least one digraph character.   
     
     
       14. The method of claim 13, further comprising the step of enhancing, prior to generating the first digraph character, character strings by appending a beginning or end of word symbol to the beginning and end of the character string. 
     
     
       15. A method of analyzing an uncorrected character string generated by an input device, comprising the steps of: dividing the uncorrected character string into at least one set of uncorrected character string fragments by use of at least one predetermined submethod;   successively selecting at least one correct character string from a predetermined list of correct character string as at least one current correct character string,   comparing, for each current correct character string and each set of uncorrected character string fragments, a predetermined set of correct character string fragments to the corresponding set of uncorrected character string fragments to generate an error value for each predetermined set of correct character string fragments, wherein each predetermined set of correct character string fragments is generated by one predetermined submethod;   selecting, for each current correct character string, a lowest error value from the generated error values as a corresponding total value for the current correct character string;   storing at least one current correct character string and the corresponding total value to a storage means; and   transferring the contents of the storage device to an appropriate output device upon reaching an end of the list of correct character strings, wherein one predetermined submethod comprises the steps of:   of eliminating duplicate characters from the character strings and;   reordering the characters of each of the character strings in alphabetical order.   
     
     
       16. A method of analyzing an uncorrected character string generated by an input device, comprising the steps of: dividing the uncorrected character string into at least one set of uncorrected character string fragments by use of at least one predetermined submethod;   successively selecting at least one correct character string from a predetermined list of correct character strings as at least one current correct character string,   comparing, for each current correct character string and each set of uncorrected character string fragments, a predetermined set of correct character string fragments to the corresponding set of uncorrected character string fragments to generate an error value for each predetermined set of correct character string fragments, wherein each predetermined set of correct character string fragments is generated by one predetermined submethod;   selecting, for each current correct character string, a lowest error value from the generated error values as a corresponding total value for the current correct character string;   storing at least one current correct character string and the corresponding total value to a storage means; and   transferring the contents of the storage device to an appropriate output device upon reaching an end of the list of correct character strings; and further comprising the steps of:   selecting another predetermined submethod to preselect most probable correct character strings;   performing the comparison and selection steps on the list of predetermined correct character strings, using the selected submethod to determine the most probable correct character strings;   storing the most probable correct character strings as a new list of predetermined correct character strings; and   using the new list in place of the original list for remaining submethods.   
     
     
       17. A method of analyzing an uncorrected character string generated by an input device, comprising the steps of: dividing the uncorrected character string into at least one set of uncorrected character string fragments by use of at least one predetermined submethod;   successively selecting at least one correct character string from a predetermined list of correct character strings as at least one current correct character string,   comparing, for each current correct character string and each set of uncorrected character string fragments, a predetermined set of correct character string fragments to the corresponding set of uncorrected character string fragments to generate an error value for each predetermined set of correct character string fragments, wherein each predetermined set of correct character string fragments is generated by one predetermined submethod;   selecting, for each current correct character string, a lowest error value from the generated error values as a corresponding total value for the current correct character string;   storing at least one current correct character string and the corresponding total value to a storage means; and   transferring the contents of the storage device to an appropriate output device upon reaching an end of the list of correct character strings, wherein the step of comparing the sets of correct and uncorrect character string fragments comprises the steps of:   loading all of the correct character string fragments into a first input data plane of a processor plane of 1-bit parallel processors;   loading all of the uncorrected character string fragments into a second input data plane of the processor plane;   outputting results from at least one logical combination of corresponding locations on the first and second input data planes to an output data plane of the processor plane; and   parallely summing the results of the output data plane for each logical combination.   
     
     
       18. The method of claim 17, wherein the at least one logical operation is at least one of a logical XOR operation and a logical AND operation. 
     
     
       19. A method of analyzing an uncorrected character string, comprising the steps of: scanning a hand-completed form with a scanner;   outputting signals from the scanner to an optical character recognition system;   converting the scanner signals to an uncorrected string of character data;   storing the uncorrected character string in a memory;   dividing the uncorrected character string into at least one set of uncorrected character string fragments by use of at least one predetermined submethod;   successively selecting at least one correct character string from a predetermined list of correct character strings as at least one current correct character string,   comparing, for each current correct character string and each set of uncorrected character string fragments, a predetermined set of correct character string fragments to the corresponding set of uncorrected character string fragments to generate an error value for each predetermined set of correct character string fragments, wherein each predetermined set of correct character string fragments is generated by one predetermined submethod;   selecting, for each current correct character string, a lowest error value from the generated error values as a corresponding total value for the current correct character string;   storing at least one current correct character string and the corresponding total value to a storage means;   transferring the contents of the storage device to an appropriate output device upon reaching an end of the list of correct character strings.   
     
     
       20. The method of claim 1, wherein the predetermined order is alphabetical order. 
     
     
       21. The method of claim 3, wherein the predetermined number of character string fragments is 4.