KR20010015113A - An expression method of names of places, a recognition method of names of places and a recognition apparatus of names of places - Google Patents

Abstract

Even when there are many notations in the name representation, it is possible to create a name dictionary that covers all names strings with little effort, and to enable fast collation processing.

The present invention extends the BNF technique known as one of the expressions of the generation rule of the context-free grammar to be suitable for the notation of the name, and expresses the name notation of the name.

According to the generation rule, a set of typical notation names, for example, "ヶ", "KE" and "が" can be defined simply as one syntax category. In addition, by using a selection symbol employed in the BNF technique, it is possible to express a notation of a place name more concisely. The processing is to express the notation of a place name with a production rule (102), and perform the recognition process 104 using a network obtained from the production rule. For this reason, it is possible to easily create a dictionary describing all sets of various notations.

Description

NAME EXPRESSION METHOD OF NAMES OF PLACES, A RECOGNITION METHOD OF NAMES OF PLACES AND A RECOGNITION APPARATUS OF NAMES OF PLACES}

BACKGROUND OF THE INVENTION Field of the Invention [0001] The present invention relates to a method for expressing a name group, a method for recognizing a name string, and a device for recognizing a name group, and a name string suitable for applying to a name string storage means and a matching means used in particular for a device for reading a name described on a document. A recognition method and apparatus are provided.

In general, a character string (hereinafter referred to as the name string) consisting of an array of names words such as the name of 都 道 府縣 (Japan's administrative division), the name of the municipality, and the character (one of the terminal administrative divisions of Japan) is included in the image. The character recognition device to read,

(1) extract the character pattern (character extraction),

(2) identify the character type (character code) of each character pattern (character identification),

(3) The identification result of the character is matched with the column of the place word which has been memorized in advance (string collation), and three functions are provided.

As a conventional technique related to the method of character string matching, for example, a method by Kagawa et al. (Information Processing Society, Vol. 35, No. 6, "Error Correction Algorithm for Recognizing Handwritten Chinese Character Address") and the like are known. In addition, as a conventional technique for a method of integrating character extraction, recognition, and contrast, a method based on a Hidden Markov model (OE Agazzi, et al., "Connected And Degraded Text Recognition using Planar Hidden Markov Models," Proceedings of International Conference on Acoustics, Speech, and Signal Processing), a method known as exploratory string recognition (Koga, et al., “Lexical Search Approach for Character-String Recognition" Third International Association for Pattern Recognition Workshop on Document Analysis Systems 1998) have.

The above-described prior art requires a name string dictionary and a means for storing a named string that can appear in advance for the string matching process. Incidentally, there are three kinds of names string dictionaries as shown below.

(1) "Dictionary source file" saved in file

This is a "name designation rule file" described later, and the like must be editable for new creation or modification.

(2) "dictionary table" stored in memory

This is the "name designation network" described later, and the contents of the dictionary file are expanded on the memory in a format suitable for collation processing.

(3) "dictionary binary file" which is an intermediate step between (1) and (2) described above.

This is a result of storing a part of the development process in advance in a file in order to facilitate development on the memory.

The format of the dictionary source file used in the prior art is often not clear. However, the prior art is based on the premise that all names strings that can appear in the dictionary table are stored in advance. Therefore, a text file that lists all the names strings that can appear in advance is a dictionary source file. It is thought that it is used as.

In the above-described prior art, it is necessary to prepare a dictionary for character string matching processing, but in Japanese, there are many double letters representing the same region in different character strings, and it is difficult to register all the names strings that can appear in advance. The problem is that it is virtually impossible to write a complete dictionary for this.

In the Japanese place name notation, there are two notations in accordance with the difference in the letters used, two notations in which the word is omitted, two notations in accordance with additional character strings, and two notations in the notation of road names. Hereinafter, examples of these two notations will be described.

(1) Dual notation according to the difference in the letters used

There are also "小澤", "市 ヶ 谷", "市 ケ 谷" and "市 が 谷".

(2) two-letter notation

There are two different symbols to omit the name of 都 道 府縣, and two symbols that omit "大字" and "字" (both 大字 and characters). The abbreviation for omits the name of the city is often seen in the case of mail recipients. For example, there are two types of names, such as 埼 玉 縣 川 越 市 大字 小 ヶ 谷 and 과 玉 縣 川 越 市 小 ヶ 谷. In addition, examples of omitting "大字" and "字" include, for example, "埼 玉 埼 川 越 市 大字 小 ヶ 谷" and "埼 玉 縣 川 越 市 小 ヶ 谷".

(3) two-letter notation according to additional character strings

Unnecessary strings are added to the original address, such as the name of the Chinese character, to make the name. For example, there are two characters, such as "埼 玉 縣 川 越 市 大字 小 ヶ 谷" and "埼 玉 縣 川 越 市 大字 小 ヶ 谷 字 東 關".

(4) Marking notation according to street name notation

There are many things that can be seen in Tokyo, such as 京 都市 下 京 區 大 政 所 町 and 烏丸 通 佛光 寺 下 る.

As mentioned above, there are various kinds of names notation, but, for example, taking the name of "Jami Yumi River" as an example, and examining the notation corresponding to this, as listed below, It can be seen that there are a plurality of notations.

「埼 玉 縣 川 越 市 小 ヶ 谷」

「埼 玉 縣 川 越 市 小 ケ 谷」

「埼 玉 縣 川 越 市 小 が 谷」

「埼 玉 縣 川 越 市 大字 小 ヶ 谷」

「埼 玉 縣 川 越 市 大字 小 ケ 谷」

「埼 玉 縣 川 越 市 大字 小 が 谷」

川川 市 小 ヶ 谷

川川 市 小 ケ 谷

川川 市 小 が 谷

`` Kawazai City Character ''

`` Kawazai City Character ''

`` Kawazai City Character ''

In the above-described example, there may be cases in which small characters are used together, such as "埼 玉 縣 川 越 市 小 ヶ 谷 東 田", "埼 玉 縣 川 越 市 小 ヶ 谷 東 關", "埼 玉 縣 川 越 市 小小 谷 谷 西 關", In consideration of the combination with the 12 double letters mentioned above, there are 84 different double letters.

In the prior art, it is necessary to register all the combinations of the various notations as described above in the dictionary file by hand, and therefore, there is a problem that the dictionary file creation takes a lot of trouble. In addition, in the case of many cities such as Tokyo, where the sum of the names of neighborhoods and street names in the city has reached hundreds of thousands, it was virtually impossible to create a complete dictionary by hand.

It is a first object of the present invention to provide a place name notation method that can solve the above-described problems and facilitate the registration of various double-word notation in the character string dictionary.

As described above, when there are many notations in the designation of a place name, even if the notation can be described in advance without any omission, the prior art has a large storage capacity and the processing time also increases with the number of notations. Will cause problems.

As a technique capable of solving the above-described problem, a technique that allows the prior storage capacity to be made smaller and the collation processing can be made faster according to a data format called Trie (Koga, et al., “ Lexical Search Approach for Character-String Recognition "and the Third International Association for Pattern Recognition Workshop on Document Analysis Systems 1998." This technique is known as a tree-type data that diverges only portions that vary in notation. Notation, making it easy to automatically generate a Trie from a set of strings.

The above-mentioned technique is, for example, from the three notations of "埼 玉 縣 川 越 市 小 ヶ 谷 東 田", "埼 玉 縣 川 越 市 小小 谷 谷 東 關", and "埼 玉 縣 川 越 市 小小 谷 谷 西 ヶ" as follows. Trie can be easily generated.

In the following description, a network representing the concatenation of characters in a name string is referred to as a place name notation network.

However, if there is a difference in a part of a character string, such a trie-type name representation network must treat them as completely different character strings and create another branch. Thus, for example, Trie corresponding to the heterologous notation becomes large as shown next.

(Omit below)

As described above, even when trying to express this notation by a method using a Trie-type geographical name notation network, there arises a problem that both the preliminary capacity and the processing time are greatly increased.

Accordingly, an object of the present invention is to provide a name expression method, a name string recognition method and apparatus having a memory format for use in a name dictionary for recognizing a variety of different notations and having a small-capacity and fast collation process. It is in doing it.

According to the present invention, the above object is a geographical name representation method in which a geographical name represents a set of geographical names strings having a plurality of double letters represented by an array of words representing different regions but the same region. For each substring constituting some or all, it is achieved by defining an array of characters or syntax categories, and representing the named string by a syntax category consisting of an array of characters or a finished syntax category.

The above object is also achieved by expressing the named string using a substitution symbol indicating which character or phrase category string the syntax category is replaced with, and a name symbol indicating which syntax category indicates a specific region.

In addition, the above object is that the substring of the input string defines an array of characters or syntax categories for each substring constituting part or all of the named string, which is previously given, and consists of an array of characters or delimited syntax categories. This is accomplished by matching a place name in the input string by determining whether it matches one of the place name strings indicated by the syntax category.

The above object is also to define an array of characters or syntax categories for each substring constituting part or all of the names string, and to store the names string indicated by the syntax category consisting of the array of characters or syntax categories that have been defined. And a storage means, an input means for inputting a character string, means for collating whether or not the input character string is a named character string stored in the storage means, and means for outputting a result of the collation.

Moreover, the said objective is equipped with the character reading means which reads the character described on the document by making into an image the image obtained by converting the shade of the surface of a document into an electrical signal, and the said input means reads the said character. This is accomplished by entering a string from the means.

Specifically, in order to achieve the above object, the present invention expresses a noun name using a generation rule of a context free grammar. The context-free grammar indicates, by generation rules, which sentence elements (syntax categories) are replaced by columns of which other syntax categories ("Introduction to Natural Language Processing", Modern Science History, ISBN4-7649-0143-9). This invention uses the extended BNF technique which extended the BNF technique (Backus-Naur-Form) known as one of the expressions of a generation rule (Middle "compiler" ISBN4-7828-5057-3) to be suitable for expression of a place name. .

According to the generation rule described above, a pattern of typical notation, for example, "ヶ", "ケ", and "が" can be defined as one syntax category, and the set of notation of place names can be expressed concisely. . In addition, by using a selection symbol employed in the BNF technique, it is possible to express a notation of a place name more concisely. For this reason, according to the present invention, it is possible to easily create a dictionary in which all sets of various notations are described.

The BNF technique is a technique for expressing the generation rule of the context free grammar using symbols such as substitution, options, and selection, and uses the following symbols.

:: = substitution. This means that the syntax category on the left side can be replaced with the syntax category or the array of characters on the right side.

[ ] option. It means that there is no need to have the description in [].

| Selection. It means either the right side or the left side.

As an example, the example which expressed the generation | occurrence | production rule of the above notation of "埼 玉 縣 川 越 市 小 ヶ 谷" by the BNF technique is shown below.

<w ヶ> :: = ヶ | ケ | が

<埼 玉 縣 川 越 市 小 ヶ 谷> :: = [埼 玉 縣] 川 越 市 [大字] 小 <w ヶ> 谷 [[字] 東 田 | 東 關 | 西 關]

In addition, by using the above-described notation format, it becomes possible to miniaturize the place name notation network. In the above-described notation format, the difference between the substrings is expressed using the symbols "[]" and "|". For this reason, when the difference between the substrings can be present in this notation, a path for bypassing the substring can be easily set on the network. For example, the notation of the BNF technique described above may be replaced by a dense network as shown below. It was difficult to generate such a dense network from the conventional string sequence.

BRIEF DESCRIPTION OF THE DRAWINGS Fig. 1 is a flowchart for explaining an example of a processing of a name string recognition according to an embodiment of the present invention.

FIG. 2 is a diagram showing an example of notation of a place name expressed according to the edited place name generation rule and an example of listing this notation without using a generation rule; FIG.

3 is a diagram schematically illustrating a place name notation network created from an example of a generation rule.

Fig. 4 is a diagram for explaining a data format when the name representation network is mounted on a calculator.

5 is a flowchart for explaining a process for generating a name representation network from a name string generation rule.

FIG. 6 is a view for explaining an example of a syntactic tree generated. FIG.

Fig. 7 is a flowchart for explaining a processing operation by a function proc that generates a name-notation network from a name-notation generation rule.

FIG. 8 is a diagram for explaining a process of generating a place name network by the function proc (No. 1). FIG.

FIG. 9 is a view for explaining a process of generating a place name notation network by the function Proc (No. 2). FIG.

FIG. 10 is a diagram illustrating a place name network group generated from a place name generation rule. FIG.

Fig. 11 is a flowchart for explaining a processing sequence for generating a place name notation network using the related art.

FIG. 12 is a diagram for explaining an example of a generation process of a place name notation network generated by the prior art; FIG.

FIG. 13 shows an example of a place name notation network created by the prior art. FIG.

FIG. 14 is a flowchart for explaining a processing operation in the name recognition processing shown in FIG. 1; FIG.

FIG. 15 is a flowchart for explaining a processing operation in the character string matching process shown in FIG. 14; FIG.

Fig. 16 is a flowchart for explaining processing operation of function srch.

Fig. 17 is a block diagram showing an example of the configuration of a system to which the name string recognition processing is applied according to the embodiment of the present invention.

Fig. 18 is a block diagram showing the construction of a designated character string generation rule editing apparatus.

Fig. 19 is a block diagram showing the construction of another embodiment of the present invention.

20 is a diagram illustrating an example of a screen displayed on a display.

<Explanation of symbols for main parts of the drawings>

101: handle editing the name string generation rule

102: Name string generation rule file

103: name generation network generation processing

104: name recognition processing

1404: String collation processing

1701: Postal Separator

1702: Scanner

1703: delay line

1704: sorter

1705: place name recognition device

1706: interface for input

1707: arithmetic processing unit

1708: processing unit for output

1710: memory

1711: network interface

1712: hard disk

1713: removable media storage

1714: editing device for generating names strings

1718: network

1801: mouse

1802: Keyboard

1803: Display

1804: program for editing names string generation rules

1805: String Matching Program

1806: place name network display program

1807: naming string generation rules file

1808: place name network generator

1809: place name network data

1810: communication device

1811: removable media storage

1812: Computer

1901: Mouse

1902: keyboard

1903: display

1904: Printer

1905: input file

1906: output file

1907: Nominations Program

1908: place name additional information file

1909: nomination string generation rules file

1910: communication module

1911: interface module

1912: place name data

1913: place name sort module

1914: Geographical Information Search Module

1915: place name generation module

1916: string matching module

1917: place name development module

1918: place name network generator

1919: place name network data

Hereinafter, embodiments of a place name notation method and a place name character string recognition method according to the present invention will be described in detail with reference to the accompanying drawings.

Fig. 1 is a flowchart for explaining a processing example of name string recognition according to an embodiment of the present invention. First, this flow will be described. In addition, the flowchart used by the following description was expressed according to the Gain-Sarson technique. For this technique, see "J. Martin and C. McClure, "Software Structured Techniques", History of Modern Science, "ISBN4-7649-0124-2 C3050 P5562E."

(1) First, prior to the recognition of the name, the name string generation rule editing process (step 101) creates a generation rule of the name string based on the case of the name notation, and sets this generation rule as the name string generation rule file. Save to 102. The nomenclature character string generation rule editing process of step 101 can be implemented by human editing work by a calculator.

(2) Next, the place name notation network generation process (step 103) reads the place name character string generation rule file 102, and generates the place name notation network which is a dictionary for the place name recognition 104. FIG. The name notation network generation process of step 103 can be realized as a program on a calculator.

(3) Next, the name recognition processing (step 104) reads the name string in the input image with reference to the name representation network. The name recognition processing 104 of step 104 can be realized as a program on a calculator.

The name string generation rule file 102 expresses a group of two names in a name by the generation rule of the context free grammar using the "extended BNF technique" according to the present invention. The extended BNF technique is an extension of a symbol such as combined with the BNF technique, and uses a symbol as described below.

:: = substitution. This means that the syntax category on the left side can be replaced with the syntax category on the right side or an array of characters.

[ ] option. Means that the description in [] may be omitted.

| Selection. It means either the right or left side of this symbol.

<W string> syntax category

<N number> A phrase category that represents a family of names in a place name string that represents a particular region. The number is an identifier for the name. Use an integer greater than zero.

And the symbol mentioned above is evaluated according to the following priority.

(1) Definition of variable names of <W string> and <N number>

(2) Types of parentheses in [] and (). When using parentheses with two or more boxes, the inner parentheses are evaluated first.

(3) |

(4) :: =

Fig. 2 is a diagram showing an example of notation of a place name expressed according to the place name character string generation rule edited by the editing process according to the above-described step 101 and an example of listing this notation.

An example of a place name represented according to the place name character string generation rule shown in Fig. 2A is, for example, "埼 玉 縣 川 越 市 大字 小 ヶ 谷" ("東 田", "東 關", "西 關"). , "표 玉 이 川 越 市 大字 笠 幡" ("久保", 河南 "is a small letter) and" 埼 玉 縣 川 越 市 下 廣 谷 "are examples of using the extended BNF technique according to the present invention. In this way, a place name containing a large number of two notations can be expressed very simply by using a symbol introduced according to the present invention. On the other hand, the example in which two notations are listed without using the generation rule shown in Fig. 2B only lists a plurality of notations, so that the notation generated from the notation of the four lines shown in Fig. 2A is shown. The number is 106. The part shown in FIG. 2 (B) is a part thereof.

The name string generation rule file 102 is a normal text file, and as a means for realizing the step 101 of the name string generation rule editing process, a general text editor can be applied.

FIG. 3 is a diagram schematically showing a place name notation network created from the example of the generation rule in FIG. 2A, which will be described below.

The place name notation network is a directional graph in which each vertex is a substring, with each vertex corresponding to a boundary of the substring. The direction of each side coincides in the order of the characters in the string. In Fig. 3, the side recorded as NULL indicates that the NULL transition, that is, the string may have nothing at that location. The circle | round | yen 301 which the line entered in the lower right in FIG. 3 shows the starting position of a place name character string. Further, circles 302 to 304 with slanted lines in the center indicate the end positions of the designated character strings.

FIG. 4 is a diagram for explaining a data format when the name representation network is mounted on a calculator, which will be described below. In addition, when the name representation network is mounted on a calculator, the name representation network has a data format as shown in FIG. 4 (left-child. Right-sibling representation, T. Colmen et al. 201-202). This data type expresses the concatenation of characters as child pointers and branches of the place name network as sibling pointers.

Fig. 4A shows the components of each data record, and each data record consists of three data items of data items c401, b402 and d403. Data item c is a character code and data item b is a sibling pointer. In addition, the data item d is a pointer. A branch from a data record is represented by a sibling pointer and a character string in a list form connected by a pointer. For example, if the place name representation network shown in Fig. 3 is represented in the form of a list by the above-described data record, it becomes as shown in Fig. 4B.

In the geographical name notation network expressed in the list form shown in Fig. 4B, from the data record 404 '(corresponding to the character code "small") to the data records 404 to 406, the data record ( 404 'to 404 are connected by means of a pointer and data records 404, 405 and 406 are connected by sibling pointers. In addition, the character string "埼 玉 로" is shown by the data records 407, 408, and 409 connected by the pointer. In addition, when a data record corresponds to NULL transition, a NULL character is stored in the character code c401 of the data record, and it means that the data record which branches off from the data code which stored this NULL character may be abbreviate | omitted. In addition, after the data record corresponding to the last character of the designated character string, one extra data record is provided, as indicated by the data record 410, and a null pointer is provided in the pointer d of the data record 410. Is stored, indicating that it is the end of the network, and the identifier of the place name is stored in the sibling pointer b.

The geographical name notation network shown in FIG. 4 (B) in the format representation as described above can be regarded as a graph in which each data record corresponds to a node, and each of the geographical name notation networks schematically shown in FIG. Variations, here, are represented by the number of nodes.

FIG. 5 is a flowchart for explaining a process of generating a place name notation network from the place name character string generation rule in step 103 of FIG. 1, FIG. 6 is a view for explaining an example of a syntax item to be generated, and these are described below.

First, in the control loop 501, for each row that begins with the generation rule of each name string in the name representation generation rule file 102, e.g., <N number> after the second row from Fig. 2A. One by one. For each line, first in step 502, the syntax of the character strings in the line is parsed, and a syntactic head as shown in FIG. Next, in step 503, an end node t _i of the place name notation network corresponding to the place name notation group is generated. Hereinafter, unless there is a problem in particular, the "node on the place name designation network" shall represent the data record of the format of FIG. The character code c in t _i stores NULL, the pointer d, NULL, and the sibling pointer b stores the place name identifier of the place name notation. Next, in step 504, a place name notation network corresponding to the place name notation group is generated using the function proc described below. After finishing processing all the names string generation rules, the names representation network generated in step 505 merges the duplicated portions.

The process of generating a syntactic tree from a naming string generation rule is, for example, a transition network according to the generation rule described in "Introduction to Natural Language Processing" (Modern Scientific History, ISBN4-7649-0143-9, pp.19-30). Can be used to generate the method. An example of the syntax tree generated by the process of step 502 shown in FIG. 6 is an example of the syntax tree generated from the second line of FIG. 2 (A). In Fig. 6, circles marked with "+" indicate concatenation of character strings, circles with "[]" indicate options, circles with "|" indicate selection, and squares indicate character strings. In the extended BNF technique, parentheses "(", ")" are also used, but the syntax used in the embodiments of the present invention is that the order of operations determined by the parentheses is provided without installing a node corresponding to the parenthesis. The structure of the neck should reflect to itself.

The function proc is a function used to generate a name-notation network from syntax. It takes two arguments, p and a. The argument p specifies the value taken by the pointer d of the node at the end of the name-notation network to be created. In addition, the argument a indicates the most significant node of the syntax item to be processed. If argument a is specified for any node, all nodes below argument a are processed recursively.

7 is a flowchart illustrating a processing operation by a function proc, FIGS. 8 and 9 illustrate a process in which a name representation network is generated by a function Proc, and FIG. 10 is a name representation network generated from a name representation generation rule. It is a figure which shows a group, and it demonstrates below. In Fig. 7, p, q, and r shown in the figure are variables representing addresses of data records in the format shown in Fig. 4, and the symbol &quot;-&quot; indicates data items in the data records. In addition, the process of the flow shown in FIG. 7 performs four cases separately according to the kind of node a of a syntax tree.

(1) The type of node a in the syntax item is determined, and the type is determined as one of "+", "|", "[]", and "string" (step 701).

(2) In the judgment in step 701, if the node a of the syntax item is "+", that is, a combination, first, the argument p is copied to the variable q. That is, the address of the end node of the partial network generated by this process is copied (step 702).

(3) Subsequently, the child node n _i (number of 1 ≦ _i ≦ child nodes) of the syntactic head is processed by the function proc () in order from the right side to generate a partial network of the named place network. At that time, the argument is passed so that the end point of the partial network generated by the function proc () becomes q. The pointer of the starting point of the generated partial network is substituted into q again, and the end point of the partial network to be generated is subsequently set. In this way, as the function proc () is repeatedly called, partial networks of the name-notation network generated from the child node of the syntax "+" are sequentially connected (steps 703 and 704).

(4) When processing of all child nodes is finished, q is returned at the time q, that is, the head of the partial network as a return value (step 705).

(5) In the determination in step 701, if the node a of the syntax item is "1", that is, the first node is generated from the partial node 1 n ₁ , and the first address of the obtained partial network is set to the variable q. Is substituted into (step 706).

(6) Subsequently, the value of q is substituted into the variable r, and a partial network generated from other child nodes n _i (2 ≦ _i ≦ number of child nodes) is generated in order. The head address of the generated partial network is stored in the sibling pointer b of r. In addition, the head address of the generated partial network is substituted into r, and the same process is repeated below (steps 707 to 710).

(7) When the processing of all the child nodes is finished, q is returned as the return value of the address q of the head of the partial network generated first (step 711).

(8) If the type of node a in the syntax tree is "[]", that is, the option in step 701, first, a partial network corresponding to the child node of the syntax tree is generated, and the first address is stored in the variable q. do. At that time, a parameter is specified such that the terminal of the generated partial network is p (step 712).

(9) Next, a node corresponding to the NULL transition is created using the function newNd (), and the address is stored in the sibling pointer b of q. NewNd () is a function for newly securing a new storage area of the data record of the format shown in Fig. 4, and a NULL pointer is set in the data item b of the secured data record (step 713).

(10) Subsequently, NULL is substituted into the character code c of the node corresponding to the NULL transition, and p is set in the child node pointer d of the node corresponding to the NULL transition (steps 714 and 715).

(11) The address q at the head of the last generated partial network is returned as a return value (step 716).

(12) In the determination in step 701, when the type of the node a in the syntax item is a character string, the value of p is first substituted into the variable q (step 717).

(13) Next, the following processing is repeated for each character C _i (1 ≦ _i ≦ string length) in the character string in order at the end of the character string, and one node corresponding to each character is generated. In this case, first, a storage area of a node is secured by the function newNd (). Subsequently, C _i is substituted into the character code c of the newly created node. Subsequently, the value of q is substituted into the child node d of the newly created node. Subsequently, the value of q is replaced with the address of the newly generated node (steps 718 to 722).

(14) After the above-described processing is executed for each character C _i , the address q of the newly generated partial network is returned as a return value (step 723).

In Figs. 8 and 9 illustrating the process of generating a place name notation network by the function Proc, reference numeral 801 generates an end node in the process of step 503 of the flow shown in Fig. 5, and designates an identifier "3501104". It is saved. Then, according to the process of each step of the flow shown in FIG. 7, the place name notation network is produced | generated as shown from the top to the bottom of the figure shown in FIG. 8, FIG. When the node 603 of the syntax item shown in FIG. 6 is processed by the function proc, first, a partial network corresponding to the node 602 is generated as the function proc, and as shown by reference numeral 802, the node 603 is generated. A partial network corresponding to 602 is created. Subsequently, a partial network corresponding to node 604 is created with the function proc. In this case, p stores the address of node 804, and the generated partial network is connected to node 804, as shown by reference numeral 803.

By the control loop 501 of the flow shown in FIG. 5, a separate name representation network is generated for each generation rule of the name string. As a result, the place name notation network group generated from the place name notation generation rule in FIG. 2 is generated as shown in FIG. 10, and further, in accordance with the process of step 505, a portion where these network groups are duplicated, for example, Incorporating parts of Matsukawa City, the name place network as described by FIG. 3 is created.

11 is a flowchart for explaining a processing procedure for generating a name representation network using the prior art, FIG. 12 is a view for explaining an example of a process for generating a name representation network generated by the prior art, and FIG. A diagram showing an example of a name-notation network generated by the present invention. Hereinafter, a method of generating a name-notation network when a generation rule is not used will be described with reference to these drawings.

The reason why the prior art is explained here is that only a conventional name representation network having a tree structure called Trie can be generated from a conventional name representation string, and the name representation network generated from the representation method of the present invention is used for storage capacity and matching. This is because all of the required processing times are excellent. A technique for expressing a notation of a place name according to the prior art is an arrangement of a place name string as shown in FIG. 2 (B), and the flow described by FIG. 11 is a procedure for generating a place name notation network from such an arrangement of words. to be. In FIG. 2B, the k-th character string is S _k , the length is L _k , and the i-th character of each character string is C _i . It is also assumed that an identifier corresponding to each character string is stored separately. The place name notation network to be generated is realized in the data format shown in FIG.

(1) First, the node rr which becomes the virtual route of the place name notation network is created. NULL is set in the child node d of this node (steps 1101 and 1102).

(2) The loop 1103 processes all strings S _k by one.

(3) First, the address of the root is substituted into the variable p. Then, for every one of the characters in the string, the subroutine SrchNxt is called. The subroutine SrchNxt is a processing procedure for determining whether a node corresponding to each character has already been generated and, if not, to add a new node, which will be described later (steps 1104 to 1106).

(4) When you have finished processing the characters in the string with the subroutine SrchNxt, create a new child node with the function newNd (), store the identifier of the string in the area of pointer b, and further address the new child node's address. Assign to p's child pointer d. The child node of rr at the end of the loop 1103 becomes the root of the name-notation network (steps 1107 to 1110).

Next, the processing of the subroutine SrchNxt will be described.

(1) First, the value of the child node d of p is substituted into the variable q, and then looped to scan all the child nodes of p by the variable q, and if the corresponding character code, i.e., the data item c, is equal to C _i. Investigate whether or not. If it is the same, it is assumed that a node corresponding to C _i has already been generated, and the pointer p advances to the node q to end (steps 1111, 1113 to 1115, and loop 1112).

(2) In step 1113, if the data item c is not equal to C _i , the value of the sibling pointer of q is substituted for q, and the looping process is repeated until q becomes NULL (step 1116).

(3) If the node corresponding to C _i is not found even after the loop processing ends, create a new node with the function newNd (), set C _i to the character code c of the new node, and NULL to the child node d. Assigns the value of the child node pointer d of p to the sibling pointer b, assigns the address of this new node to the child node pointer d of p, and assigns the address of the new child node to pointer p. The process ends (steps 1117 to 1122).

FIG. 12 illustrates a process of generating a place name notation network according to the above-described process sequence of FIG. 11. An example here is the process of processing three rows above FIG. 2 (B). First, a place name notation network corresponding to "Kawazu City Kobe-ya" is first generated (1201). Subsequently, although "Kawazu City" is processed, since the part of "Kawazu City" is already generated by reference numeral 1201, a new node is not created. However, when the pointer p reaches the position indicated by the reference number 1202, and the character of "笠" is processed, the node corresponding to "笠" does not exist in the child node of "city". Thus, as a sibling node of "small", a node corresponding to "small" is newly created. Hereinafter, the node corresponding to the remaining character "幡" is connected as a child node of the newly created node (1203). In the case of "川 越 市 下 廣 谷", the process is similarly performed, and a node for "下" is newly created as a brother of "小" and "笠" (1204), and nodes corresponding to subsequent characters are connected (1205). .

Although FIG. 13 schematically shows a part of the place name notation network generated from the group of two notations shown in FIG. 2 (B), this example is different from the case shown in FIG. 3, but the place name notation network generated from the conventional notation method is , Tree form, that is, once branched, does not join again. This is a representation format of data known as Trie. Compared with FIG. 3, it can be seen that there are many overlapping parts.

For example, the partial network corresponding to "東 田", "東 關", and "西 關" is repeated 6 times. This means that the required storage capacity is increased, and in the case of a calculator having a hierarchical memory configuration, when the memory space to be accessed becomes large, access is delayed due to a miss hit of the cache, and further, the string matching process described later. This will be late.

In accordance with the present invention, being able to create a less redundant name representation network as shown in FIG. 3 is an inherent advantage of name word representation in accordance with the creation rules. By using this generation rule, it is possible to clearly express the duplicated points. For example, in the example shown in FIG. 2 (A), there are three different notations in "의" of "小 ヶ 谷", but the same character strings after "ヶ" are represented by the extended BNF technique. For this reason, as shown in FIG. 3, a network with three paths is generated only between "small" and "谷".

On the other hand, in the conventional notation method of the name-name string as shown in FIG. 2 (B), it is not possible to detect whether the two-letter group after "ケ" is equivalent, and generate only the network as shown in FIG. Can not.

FIG. 14 is a flowchart for explaining a processing operation in the name recognition processing 104 shown in FIG. 1, which will be described below.

(1) First, an image of a portion of a character line is extracted from the input image in accordance with the character line extraction process (step 1401).

(2) Next, according to the character extraction process, the pattern considered to be a character, ie, a candidate pattern, is extracted from a character line image. If the boundary of the character cannot be determined uniquely in this step, the character pattern attempts extraction based on the hypotheses of the plurality of boundaries, and outputs candidate patterns corresponding to the respective hypotheses (step 1402).

(3) Next, according to the character recognition process, it recognizes what character each extracted candidate pattern is, and outputs it as a candidate character string. When the extraction method of the character is based on a plurality of hypotheses, and when a plurality of candidate characters are output for one pattern as a result of the character recognition, the character recognition processing is performed in response to the combination of each extraction method and the candidate character. The candidate character string is outputted (step 1403).

(4) Finally, according to the string matching process, whether each candidate string is a correct name string or not is compared with reference to the place name notation network. The candidate character string repaired by matching is used as the name recognition result (step 1404).

15 is a flowchart for explaining the processing operation in the above-described character string matching processing 1404, which will be described below. This process is a process that takes one character string as an input, determines whether at least a part of the input string can be repaired as a named string, and obtains an identifier of the corresponding name notation if it can be repaired. Here, the length of the input string is L, and the i-th character of the string is C _i .

(1) First, steps 1502 and 1503 are repeated by the loop 1501 while changing the starting point s of the control from 1 to L. FIG.

(2) The address of the root of the place name notation network is set in the variable p indicating the node. Then call the function srch with the arguments p and s. The function srch finds a path that matches the input string in the name-notation network and returns the address of the node at its end. If the return value of srch is not a NULL pointer, the matching is considered to be successful, and the identifier stored in the node indicated by the return value of the function srch is output (steps 1502 to 1504).

(3) If the matching is not successful even if s reaches L, the character string matching processing has failed, and the processing ends (step 1505).

In the above-described process, the function srch is also called recursively from itself, searching for depth-first paths that match input strings in the name-notation network. The function srch takes two arguments, the arguments p and i. The argument p indicates the node that starts the search. In addition, the argument i is an integer and shows which character of the input string is the thing to be noticed by the current process. If a string to be repaired is found, the function srch returns the address of the node at the end of the string, or a NULL pointer if no string to be repaired was found.

Fig. 16 is a flowchart for explaining the processing operation of the function srch in the above-described processing, which will be described below.

(1) First, check whether the argument p points to a string termination node. If the character string end node is indicated, the input character string is considered to be repaired, and p is returned as the return value to terminate the process (step 1601).

(2) Then, it is determined whether or not it has already finished processing all the characters. If i is greater than L and finishes processing all characters, and p does not reach the end of the name-notation network, NULL is returned (step 1602).

(3) Then, it is checked whether the data item c of p matches the i-th character C _i of the character string. If there is a match, the function srch is called recursively, with the child node p-> d of p as the starting point of the search and processing the string from the i + 1 th. If this return value r is not NULL, it is assumed that the character string has been repaired, and the process ends with r as the return value (step 1603).

(4) Next, it is checked whether p is a node corresponding to a NULL transition. If so, then the function srch is called recursively, with p's child node p-> d as the starting point of the search and processing the string from the i th. If this return value r is not NULL, it is assumed that the character string has been repaired, and the process ends with r as the return value (step 1604).

(5) Then, it is examined whether sibling node p-> b is connected to p. If it is connected, the sibling node p-> b of p is the starting point of the search, and the function srch is called recursively to process the string from the i th, and this return value is returned to the upper level (step 1605).

(6) If any of the above-described processes do not correct the input character string, no further search is possible, and the process ends with NULL as the return value (step 1606).

Although the embodiments of the present invention described above have been described in that character extraction, character recognition, and character string matching are performed sequentially, the present invention, Gong et al., &Quot; Method for recognizing separators and character strings such as recipient reading device and mail item &quot; 10-28077 can be easily extended by feeding back the string matching result to the character extraction.

Fig. 17 is a block diagram showing a configuration example of a system to which the name string recognition processing is applied according to the embodiment of the present invention. Fig. 18 is a block diagram showing the configuration of a device for editing a name string generation rule. This system example is an example in which the present invention is applied to a mail classification system. 17 and 18, reference numeral 1701 denotes a mail separator, reference numeral 1702 is a scanner, reference numeral 1703 is a delay line, reference numeral 1704 is a sorter, and reference numeral 1705 is a name recognition. Device, reference number 1706 for an input interface, reference number 1707 for an arithmetic processing device, reference number 1708 for an output processing device, reference number 1710 for a memory, reference number 1711 for a network interface, reference The number 1712 is a hard disk, the reference number 1713 is a media removable storage device, the reference number 1714 is a designation string generation rule editing device, the reference number 1718 is a network, the reference number 1801 is a mouse, and the like. Number 1802 is a keyboard, reference number 1803 is a display, reference number 1804 is a name string generation rule editing program, reference number 1805 is a string matching program, reference number 1806 is a name designation network display program, Reference number (1807) is the nomination string A generation rule file, reference number 1808 denotes a name designation network generating program, reference number 1809 denotes a name designation network data, reference number 1810 indicates a communication device, reference number 1811 indicates a media removable storage device, and reference number 1812 is a computer.

In the system shown in FIG. 17, one or more postal separators 1701 and one or more designated character string generation rule editing apparatuses 1714 are connected by a network 1718. The mail separator 1701 is composed of a scanner 1702, a delay line 1703, a sorter 1704, and a name recognition device 1705. The name recognition device 1705 further includes an input interface 1706, an arithmetic processing unit 1707, an output processing unit 1708, a memory 1710, a network interface 1711, a hard disk 1712, and a removable media. It is composed of a possible memory device 1713. Moreover, the thick line in a figure shows the flow of a postal matter.

In the system shown in FIG. 17, image information of a place name described in a mail item input from the scanner 1702 is transmitted to the place name recognition device 1705. While the postal matter carries the delay line 1703, the name recognition apparatus 1705 recognizes the place name described in the postal matter and transmits the recognition result to the sorter 1704. The sorter 1704 classifies mails according to the recognition result.

As a preparation step for sorting mail items, the name recognition device 1705 reads the name representation network generation program file from the hard disk 1712 into the memory 1710 and starts the operation device 1707. Under the control of the place name notation network generation program, the place name recognition device 1705 inputs the place name character generation rule from the place name character generation rule editing device 1714 through the network interface 1711, and creates a place name notation network file to be hard. The disk 1712 is stored.

Alternatively, the name string generation rule may be read from a media removable storage device 1713 such as a floppy disk drive, instead of inputting from the name string generation rule editing device 1714 over a network.

The name recognition apparatus 1705 reads the recognition program file and the name representation network file from the hard disk 1712 into the memory 1710 and executes it by the computing device 1807 when classifying mail items. Then, under the control of the recognition program, the name recognition apparatus 1705 inputs an image from the input interface 1706, recognizes the name described in the mail, and outputs the recognition result via the output interface 1708.

The name string generation rule editing apparatus 1714 stores a mouse 1801, a keyboard 1802, a display 1803, and a name string generation rule file 1807 in the computer 1812, as shown in FIG. The disk device, the communication device 1810, and the media removable storage device 1811 are connected to each other. The editing operation is executed by editing the name string generation rule file 1807 through the name string generation rule editing program 1804 operating on the computer 1812. The designated character string generation rule file 1807 is a text file, and an ordinary text editor can be used for editing. In addition, the name representation network generation program 1808 may be executed on the computer 1812, and the name representation network 1809 may be generated from the name string generation rule file 1807.

The named character string generation rule editing apparatus 1714 can confirm whether the named word generation rule during editing is grammatically correct according to the above-described function, and is a program 1805 that is equivalent to the character string matching 1404 in the recognition process. Then, it is possible to check whether the test string input from the keyboard 1803 is repaired.

In addition, the computer 1812 executes the place name notation network display program 1806 for displaying the place name notation network 1809 in a format as shown in FIG. 3, for example, so that the operator can visually display the editing results. You can check with The name string generation rule file 1807 of the edited result is transmitted to the name recognition device 1705 via the communication device 1810, or the removable storage medium such as a floppy disk by the media removable storage device 1811. May be copied to the mail separator 1701 by a storage medium.

19 is a block diagram showing the structure of another embodiment of the present invention, and FIG. 20 is a view for explaining an example of a screen displayed on a display. This example is a directory register for retrieving information on a place name from a character string representing a place name by using a method for representing a place name and a place name matching method according to the present invention. In Fig. 19, reference numeral 1901 denotes a mouse, reference numeral 1902 denotes a keyboard, reference numeral 1901 denotes a display, reference numeral 1904 denotes a printer, reference numeral 1905 denotes an input file, and reference numeral 1906. Is an output file, reference number 1907 is a directory program, reference number 1908 is a name side information file, reference number 1909 is a name string generation rule file, reference number 1910 is a communication module, reference number 1911 ) Is an interface module, reference number 1912 is a name list data, reference number 1913 is a name list sort module, reference number 1914 is a name information search module, reference number 1915 is a name list generation module, and reference number 1916 is a character string matching module, reference numeral 1917 is a name designation expansion module, reference numeral 1918 is a name designation network generating program, and reference number 1919 is a name designation network data.

The apparatus shown in FIG. 19 provides the following services.

(1) Displays or prints the standard form of the place name string entered from the keyboard.

(2) Display or print a double-sided representation of the place name string entered from the keyboard.

(3) Display or print local information (zip code, etc.) corresponding to the place name character string input from the keyboard.

(4) Convert the name string inputted from the file into information unique to the area, such as standard form or postal code, and output it as a file.

(5) Convert the name string inputted from the network into information unique to the relevant area such as standard type or postal code and output it to the network.

In the above description, the standard type refers to a formal character string indicating an area determined by administrative division, for example.

The embodiment shown in FIG. 19 is based on a directory register program 1907 executed on a calculator, including a mouse 1901, a keyboard 1902, a display 1903, a printer 1904, an input file 1905, and an output file ( 1906, the name addition information file 1908, and the name string generation rule file 1909 are connected to each other. Display and input / output are performed through the interface module 1911. When the character string to be searched is input, the name information retrieval module 1914 calls the character string matching module 1916. The string matching module 1916 is a module that is in charge of processing equivalent to the string matching processing 1404 in FIG. 14, and is generated by the geographical name notation network generation program 1918 from the geographical name notation generation rule file 1909. Refer to the notation network data (1919) and examine which identifier's place name notation corresponds to the input string.

The name information retrieval module 1914 retrieves additional information such as a canonical form and a postal code from the name additional information file 1908 with the obtained identifier. In addition, the place name notation development module 1917 enumerates all possible notation names from the place name notation network data 1919. The obtained notation group is stored in the place name list data 1912 and output through the interface module 1911 as necessary. The name list sorting module 1913 rearranges and outputs the order of the two notation groups according to the operator's instructions. The input for such processing may be performed through any one of the keyboard 1901, the input file 1905, and the communication module 1910. The output may be performed through any one of the display 1904, the output file 1906, and the communication module 1910.

In the screen example shown on the display 1903 of the embodiment of FIG. 19 shown in FIG. 20, in the example shown in FIG. 20A, an operator inputs a character string "川 越 市 小 ヶ 谷" and executes a search. Is an example of the screen displayed on the display 1903 when the display is performed. The input character string is input in the field 2005, and a search is performed by clicking the button 2006 with a mouse. As a result of the search, a character string that corresponds to the input character string is displayed in the window 2007. The "standard" item of each line indicates whether or not the character string is a standard type. The item "name" displays the string. In the item "zip code", a postal code corresponding to the character string is displayed, but additional information of other regions may be displayed.

The frames of "standard", "name", and "zip code" listed in the area 2004 become buttons, and by clicking each button with a mouse, the rearrangement of the rows based on the respective items is instructed. The window 2008 is for specifying an option of a search. Here, it is specified whether to display only the standard form, to display the notation group based on characters, large characters, etc., or to display the notation group based on a generic name ("** complex", etc.). The button 2002 is a button for instructing the printing of the display contents, and the button 2001 is a button for switching to a mode for inputting / outputting a file instead of the keyboard and the display. The button 2003 is a button for instructing the end of the program.

The window 2009 opened in FIG. 20B is a window that displays detailed information such as how to read a place name, a Chinese character, a postal code, and the like obtained as a result of the verification. This window 2009 is activated by clicking on a search result displayed on the window 2007 with a mouse.

In addition, the place name character strings written according to the notation method according to the embodiment of the present invention can be stored and provided as a place name dictionary in a storage medium such as FD, MO, DVD, or the like.

As described above, according to the present invention, even if most names are represented in place names, it is possible to prepare a place name dictionary that covers all possible place name strings with little effort. In addition, it is possible to easily create a dictionary of names in a network format capable of fast collation processing.

Claims (9)

In a place name expression method in which a place name representing a region represents a set of place names strings having a plurality of double letters represented by an array of words representing different regions but the same region, For each substring constituting part or all of the name string, an array of character or syntax categories is defined, and the name representation method is represented by a syntax category consisting of an array of the above-described character or syntax categories. . The method of claim 1, And the name string is written using a substitution symbol indicating which other character or phrase category string of the syntax category is replaced, and a name symbol indicating which syntax category indicates a specific region. In the name string matching method, A place name represented by a syntax category, in which the substring of the input string defines an array of character or syntax categories for each substring that constitutes some or all of the named string in advance, and consists of an array of characters or pre-defined syntax categories. A geographical name string matching method, characterized in that the geographical name is matched among input strings by judging whether or not it matches one of the character strings. In the named string matching device, Storage means for defining an array of character or syntax categories for each substring constituting part or all of the name string, and storing the name string represented by the syntax category consisting of the array of characters or the finished syntax category; Input means for entering a string, Means for checking whether or not the inputted character string is a named character string stored in the storage means; and Means for outputting the result of said collation Name string matching device, characterized in that provided with. In the name string recognition device, Character reading means for reading a character described on the document as an input of an image obtained by converting the color tone of the surface of the document into an electrical signal, The place name string matching means of Claim 4 is provided, And an input means in the name string matching means inputs a character string from the character reading means. In the mail classification system, A postal matter classification system, wherein the designated name character string recognition apparatus according to claim 5 is used to recognize a designated name string among the recipients of the postal matter, classify the postal matter, or print the recognition result on the postal matter. In the designated character string recording medium, Each name of a place name having a plurality of double notations represented by an array of words representing different regions but representing the same region, for each substring that forms part or all of the names string, Define an array, A designated character string recording medium characterized by being represented by a syntax category consisting of the above-described character or an array of defined syntax categories. A character reading device that reads a character described on a document by using an image obtained by converting a light and shade of the surface of a document into an electrical signal, wherein the name string is stored using the name expression method according to claim 1. Means, and means for recognizing a place name as an arrangement of partial pictures in the input image, wherein each partial image is found to be similar to each character included in one of the place name strings represented by the place name representation. Name string recognition device. In a place name expression method in which a place name representing a region represents a set of place names strings having a plurality of double letters represented by an array of words representing different regions but the same region, A method of presenting a geographical name, characterized in that it is expressed according to a rule for generating a substring consisting of a word or a part of a word.