Pattern string matching apparatus and pattern string matching method

• US 6,978,044 B2
• Filed: 03/30/2004
• Issued: 12/20/2005
• Est. Priority Date: 08/06/1999
• Status: Expired due to Fees

• Current Assignee: Kabushiki Kaisha Toshiba (Toshiba Corporation)
• Original Assignee: Kabushiki Kaisha Toshiba (Toshiba Corporation)
• Inventors: Akagi, Takuma
• Primary Examiner(s): AHMED, SAMIR ANWAR
• Application Number:
  US10/813,526
• Publication Number:
  US 20040184663A1
• Time in Patent Office: 630 Days
• Field of Search: 382/185, 382/186, 382/187, 382/209, 382/217, 382/218, 382/228, 382/229, 382/230, 382/310, 707/2
• US Class Current: 382/187
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/1904 involving a deformation of the sample or reference pattern; Elastic matching
• CPC Class Codes: G06V 30/268 Lexical context

Abstract

This invention is to compare each character of a first character string with each character of a second character string, vote for a matrix having two sides corresponding to the characters of the first character string and the characters of the second character string and calculate values of the voting result for respective components arranged in an oblique direction of the matrix. The matching result is determined based on the calculated values of the voting result. As a result, a high-speed and highly precise matching process which is noise-resistant and takes the character arrangement into consideration can be attained.

Claims

1. A character string matching apparatus for effecting a process for matching between a first character string, which comprises a plurality of characters as a result of a recognition of characters, and a second character string, which comprises a plurality of characters stored in a dictionary in advance, comprising:

a first table comprising a matrix of cells of rows and columns for specifying types of the characters appearing in the first character string and orders of the characters appearing in the first character string;

a second table comprising a one-row memory for voting for each second character sting, in which a calculated value of each of the components of various types of second character strings to be matched with respect to the first character string in the direction of the second character string is stored, the second table is provided with a link for the first table based on the type of each character in the second character string and the orders of appearance and types of the characters specified by the first table, wherein the link indicates the memory address of the voting position in the second table;

voting means for casting a vote to the second table with respect to each of the characters of the first character string which has been input based on a correspondency of the first table with the second table; and

determining means for determining whether or not the first character string and the second character string are matched based on a result of voting to the second table as a result of the voting by said voting by the voting means executed with respect to all of the characters of the first character string.

2. The character string matching apparatus according to claim 1, wherein the first character string has recognized characters each having similarity, the second character string includes characters which are registered in a dictionary, and the voting means casts a vote weighted based on the similarity of each of the recognized characters of the first character string.

3. The character string matching method according to claim 2, wherein the voting means does not cast a vote where the similarity of each the recognized characters of the first character string is lower than a predetermined level.

4. The character sting matching apparatus according to claim 1, wherein the first character string includes character candidates each having the priority order, the second character string includes characters which are registered in a dictionary, and the voting means casts votes weighed based on the priority order of the character candidate of the first character string.

5. A character string matching method for effecting a process for matching between a first character string, which comprises a plurality of characters as a result of a recognition of characters, and a second character string, which comprises a plurality of characters stored in a dictionary in advance, comprising:

specifying types of the characters appearing in the first character string and orders of the characters appearing in the first character string by a first table comprising a matrix of cells of rows and columns;

providing a second table comprising a one-row memory for voting for each second character string, in which a calculated value of each of the components of various types of second character strings to be matched with respect to the first character string in the direction of the second character string is stored, and a link for the first table based on the type of each character in the second character string and the orders of appearance and types of the characters specified by the first table, wherein the link indicates the memory address of the voting position in the second table;

casting a vote to the second table with respect to each of the characters of the first character string which has been input, based on a correspondency of the first table with the second table; and

determining whether or not the first character string and the second character string are matched based on the result of voting to the second table as a result of the voting by said voting by the voting means executed with respect to all of the characters of the first character string.

6. The character string matching method according to claim 5, comprising:

the first character string having recognized characters each having similarity;

the second character string having including characters which are registered in a dictionary; and

the voting means casting votes weighed based on the degree of similarity of the recognized characters of the first character string.

7. The character string matching method according to claim 6, wherein the voting means does not cast a vote where the similarity of each of the recognized characters of the first character string is lower than a predetermined level.

8. The character string matching method according to claim 5, comprising:

the first character string including character candidates each having the priority order;

the second character string including characters which are registered in a dictionary; and

the voting means casting votes weighed based on the priority order of the character candidate of the first character string.