System and method for improved string matching under noisy channel conditions

• US 6,687,697 B2
• Filed: 07/30/2001
• Issued: 02/03/2004
• Est. Priority Date: 07/30/2001
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Schweizer, Charles B., Collins-Thompson, Kevyn
• Primary Examiner(s): Corrielus, Jean M.
• Application Number:
  US09/918,791
• Publication Number:
  US 20030028522A1
• Time in Patent Office: 918 Days
• Field of Search: 358/474, 358/497, 710/1, 707/3, 707/6, 707/5, 382/164, 382/166, 382/176, 382/187, 382/219, 382/229, 704/260, 704/269, 704/276
• US Class Current: 1/1
• CPC Class Codes: G06F 16/90344 by using string matching techniques
• CPC Class Codes: G06F 40/216 using statistical methods
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/12 Detection or correction of errors, e.g. by rescanning the pattern
• CPC Class Codes: G06V 30/268 Lexical context
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

Described is a system and method for improving string matching in a noisy channel environment. The invention provides a method for identifying string candidates and analyzing the probability that the string candidate matches a user-defined string. In one implementation, a find engine receives a query string, converts an image file into a textual file, and identifies each instance of the query string in the textual file. The find engine identifies candidates within the textual file that may match the query string. The find engine refers to a confusion table to help identify whether candidates that are near matches to the query string are actually matches to the query string but for a common recognition error. Candidates meeting a probability threshold are identified as matches to the query string. The invention further provides for analysis options including word heuristics, language models, and OCR confidences.

Claims

1. A computer-readable medium having computer-executable components for locating a query string in a document image file, comprising:

a search component in communication with an image file and being configured to transform the image file into a textual file, the textual file including textual data corresponding to graphical representations of the textual data within the image file; and

a confusion table identifying errors that could occur during the transformation of the image file to the textual file, each error in the confusion table having an associated likelihood that the error would occur,

wherein the search component is configured to locate instances of a query string within the textual file by comparing the query string to a candidate string in the textual file and determining a probability that the candidate string matches the query string and using the confusion table.

2. The computer-readable medium of claim 1, wherein the search component further comprises a dialog box component for receiving the query string from a user.

3. The computer-readable medium of claim 1, wherein the search component further comprises a dialog box component for receiving a threshold value that includes a value that must be satisfied to identify the candidate string matches the query string.

4. The computer-readable medium of claim 3, wherein the mechanism includes an optical character recognition engine.

5. The computer-readable medium of claim 3, wherein the mechanism includes a handwriting recognition engine.

6. The computer-readable medium of claim 1, wherein the search component further comprises a dialog box component for receiving an error rate that identifies an average number of errors that are permitted between the query string and any string in the textual file while still considering the string in the textual file the candidate string.

7. The computer-readable medium of claim 1, wherein the search component further comprises a mechanism to transform the image file into the textual file, and wherein that mechanism performs the transformation through a noisy process.

8. The computer-readable medium of claim 1, wherein a recognition engine produces confidence data during the transformation of the image file to the textual file, the confidence data identifying a probability that the textual file is an accurate representation of the image file.

9. The computer-readable medium of claim 1, wherein the identified errors in the confusion table include string-to-string edits corresponding to likely errors in recognizing graphical representations of text.

10. The computer-readable medium of claim 9, wherein the string-to-string edits comprise a table including correct edit strings with each edit string having a corresponding incorrect edit string wherein a difference between the correct edit string and the incorrect edit string is a result of a noisy process for transforming image files to text files, and wherein correct/incorrect edit string pair further includes a probability of occurrence of the difference.

11. The computer-readable medium of claim 1, further comprising a candidate table including candidates, wherein each candidate is generated by a parsing of the text file to identify strings within the textual file that are similar to the query string.

12. The computer-readable medium of claim 11, wherein each candidate differs from the query string by not more than a predetermined factor.

13. A computer-readable medium, having computer executable-instructions for performing steps, comprising:

receiving a request to locate instances of a query string in a document image file;

transforming the document image file into a document text file using a recognition process;

parsing the document text file to identify a candidate data string that differs from the query string by less than a predetermined factor; and

analyzing the candidate data string to identify a probability that the candidate data string matches the query string.

14. The computer-readable medium of claim 13, wherein parsing the document text file includes performing a fast approximate string match.

15. The computer-readable medium of claim 13, wherein analyzing the candidate data string comprises performing a noisy channel analysis.

16. The computer-readable medium of claim 15, wherein analyzing the candidate data string comprises:

comparing a portion of the candidate data string to a table associating error strings with correct strings, wherein the error strings result from the recognition process misrecognizing the correct strings; and

if the portion of the candidate data string corresponds to an error string, determining if replacing the portion with the correct string corresponding to the error string increases the probability that the candidate data string matches the query string, and if so, identifying the candidate data string as a match.

17. The computer-readable medium of claim 16, wherein each error string/correct string pair has an associated probability that describes a likelihood that the correct string was misrecognized as the error string, and wherein determining if replacing the portion increases the probability that the candidate matches the query string is based on the likelihood that the correct string was misrecognized as the error string.

18. The computer-readable medium of claim 16, wherein analyzing the candidate data string further comprises evaluating whether a confidence value associated with the portion of the candidate data string affects the probability that the candidate data string matches the query string, the confidence value quantifying a confidence that characters in the document text file are an accurate representation of the corresponding characters in the document image file.

19. The computer-readable medium of claim 16, wherein analyzing the candidate data string further comprises including word heuristics in the analysis.

20. The computer-readable medium of claim 16, wherein analyzing the candidate data string further comprises including process language models in the analysis.

21. A computer-implemented method for locating strings in a document, comprising:

receiving a request to locate instances of a query string in a document image file;

transforming the document image file into a document text file using a recognition process;

performing a fast approximate string match on the document text file to identify a candidate data string that differs from the query string by less than a predetermined factor; and

analyzing the candidate data string to identify a probability that the candidate data string matches the query string.

22. The computer-implemented method of claim 21, wherein analyzing the candidate data string comprises:

comparing a portion of the candidate data string to a confusion table that associates error strings with correct strings, wherein the error strings result from the recognition process misrecognizing the correct strings, and further wherein each error string/correct string pair has an associated probability that describes a likelihood that the correct string was misrecognized as the error string; and

if the portion of the candidate data string corresponds to an error string, determining if replacing the portion with the correct string corresponding to the error string increases the probability that the candidate data string matches the query string, and if so, identifying the candidate data string as a match.

23. The computer-implemented method of claim 21, wherein analyzing the candidate data string comprises evaluating whether a confidence value associated with the portion of the candidate data string affects the probability that the candidate data string matches the query string, the confidence value quantifying a confidence that characters in the document text file are an accurate representation of the corresponding characters in the document image file.

24. The computer-readable medium of claim 21, wherein analyzing the candidate data string comprises including word heuristics in the analysis.

25. The computer-readable medium of claim 21, wherein analyzing the candidate data string comprises including process language models in the analysis.