Patent EA-003619-B1 (EA)
Title: System and method for searching electronic documents created with optical character recognition
IPC: G06F17/30
Filed: 1999-03-26
Abstract: 1. A computer based method for association documents with optical character recognition with an alphanumeric search request by generating variant words, the method comprising: receiving an alphanumeric search request; forming at least one variant word associated with the alphanumeric search request according to predefined optical character recognition substitution data, the optical character recognition substitution data including a set of optical character recognition substitutions and a probability of occurrence corresponding to each optical character recognition substitution, wherein the variant word is different from the alphanumeric search request; and identifying any electronic documents in the database having at least one generated variant word. 2. The method of Claim 1, wherein generating at least one variant word comprises: determining a candidate variant word segment, each candidate variant word segment comprising at least a portion of a word; determining whether the candidate variant word segment has a probability of occurrence above a predetermined threshold of probability; and if the candidate variant word segment does not have a probability of occurrence above the predetermined threshold of probability, excluding the candidate variant word segment from said at least one variant word. 3. The method of Claim 2, wherein determining whether the candidate variant word segment has a probability of occurrence above a predetermined threshold of probability comprises: determining a plurality of optical character recognition substitutions corresponding to the candidate variant word segment according to the predefined optical character recognition substitution data; combining the probability of occurrence corresponding to each optical character recognition substitutions corresponding to the candidate variant word segment to determine a probability of occurrence corresponding to the candidate variant word segment; and comparing the probability of occurrence corresponding to the candidate variant word segment with the predetermined threshold of probability. 4. The method of Claim 1, further comprising: determining a plurality of optical character recognition substitutions corresponding to the alphanumeric search request according to the predefined optical character recognition substitution data; and combining the plurality of optical character recognition substitutions to create a candidate variant word segment. 5. The method of Claim 1, further comprising: creating a tree data structure having a plurality of substitution nodes, each substitution node corresponding to an element of an optical character recognition substitution corresponding to the alphanumeric search request, the tree data structure having a root node and at least one leaf node, each leaf node linked to the root node by a path corresponding to the leaf node; and combining the optical character recognition substitutions corresponding to each substitution node on the path corresponding to one of said leaf nodes to create the variant word. 6. The method of Claim 5, further comprising: determining, for each substitution node, a corresponding probability of occurrence according to the predefined optical character recognition substitution data; and determining, for each substitution node, whether the corresponding probability of occurrence is above a predetermined threshold ; and in the event that the probability of occurrence corresponding to a substitution node is not above the predetermined threshold, excluding the variant word corresponding to the substitution node from said at least one variant word. 7. The method of Claim 5, further comprising: creating a branch node in the tree data structure, the branch node corresponding to a delineation of a character during optical character recognition of the alphanumeric search request; creating at least one substitution node that is a child node of the branch node, the child node corresponding to an optical character recognition substitution for the character corresponding to the branch node. 8. The method of Claim 7, wherein the optical character recognition substitution corresponding to the substitution node comprises two characters. 9. The method of Claim 7, wherein the optical character recognition substitution corresponding to the substitution node represents zero characters. 10. The method of Claim 1, wherein determining at least one variant word comprises determining a plurality of variant words, and searching the database occurs after determining the plurality of variant words. 11. A computer based method for searching a database of electronic documents, tangibly embodying a program of instructions executable by the machine to perform method steps for searching a document database, the document database comprising documents created by the use of optical character recognition, the method steps comprising: receiving a search request comprising a target alphanumeric word; determining a plurality of optical character recognition substitutions corresponding to the target alphanumeric word; generating at least one variant word corresponding to the target alphanumeric word, wherein the at least one variant word is different from the target alphanumeric word and is based upon the plurality of optical character recognition substitutions corresponding to the target alphanumeric word; and identifying the documents in the document database having at least one generated variant word. 12. The method of Claim 11, wherein the method steps further comprise: determining a possible optical character recognition substitution corresponding to the target alphanumeric word; determining a probability of occurrence corresponding to the possible optical character recognition substitution; determining whether the probability of occurrence corresponding to the possible optical character recognition substitution is above a threshold of probability; selectively including the possible optical character recognition substitution in the plurality of optical character recognition substitutions, based upon the probability of occurrence relative to the threshold of probability. 13. The method of Claim 11, wherein the method steps further comprise: specifying a plurality of substitution nodes, each substitution node corresponding to an optical character recognition substitution, the plurality of substitution nodes forming a hierarchical tree structure; and forming a variant word by including the substitutions corresponding to a set of substitution nodes forming a path between a root node and a leaf node in the hierarchical tree structure. 14. The method of Claim 11, wherein the method steps further comprise specifying a plurality of branch nodes within the hierarchical tree structure, each branch node representing a delineation of a character during optical character recognition of the target alphanumeric word. 15. A computer based method for searching a database of electronic documents created by the use of optical character recognition, the method comprising: receiving an alphanumeric search request; determining at least one variant word associated with the alphanumeric search request according to predefined optical character recognition substitution data, the optical character recognition substitution data including a set of optical character recognition substitutions and a probability of occurrence corresponding to each optical character recognition substitution, wherein the variant word is different from the alphanumeric search request; creating a tree data structure having a plurality of substitution nodes, each substitution node corresponding to an element of an optical character recognition substitution corresponding to the alphanumeric search request, the tree data structure having a root node and at least one leaf node, each leaf node linked to the root node by a path corresponding to the leaf node; and combining the optical character recognition substitutions corresponding to each substitution node on the path corresponding to one of said leaf nodes to create the variant word; and searching the database of electronic documents according to said at least one determined variant word. 16. The method of Claim 15, further comprising: determining, for each substitution node, a corresponding probability of occurrence according to the predefined optical character recognition substitution data; and determining, for each substitution node, whether the corresponding probability of occurrence is above a predetermined threshold; and in the event that the probability of occurrence corresponding to a substitution node is not above the predetermined threshold, excluding the variant word corresponding to the substitution node from said at least one variant word. 17. The method of Claim 15, further comprising: creating a branch node in the tree data structure, the branch node corresponding to a delineation of a character during optical character recognition of the alphanumeric search request; creating at least one substitution node that is a child node of the branch node, the child node corresponding to an optical character recognition substitution for the character corresponding to the branch node. 18. The method of Claim 17, wherein the optical character recognition substitution corresponding to the substitution node comprises two characters. 19. The method of Claim 17, wherein the optical character recognition substitution corresponding to the substitution node represents zero characters. 20. The method of Claim 1, wherein further performs rejection of variant words not identified in the database. 21. The method of Claim 11, wherein further performs rejection of variant words not identified in the document database.