JP2790064B2 - Symbol string reader - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

2. Description of the Related Art A device for reading a one-dimensional symbol string having a higher hierarchy, such as a character string or a phoneme string corresponding to a word string, using analog data as an input, specifically, a mail or a form A device for reading written address,
The present invention relates to an apparatus for reading a sentence in a document, an apparatus for recognizing a continuous utterance voice, and the like.

[0002]

2. Description of the Related Art In a conventional symbol string reading apparatus, analog data (image data corresponding to a character string, acoustic data corresponding to a phoneme string, etc.) is input, and one symbol (character, phoneme, etc.) is first read out of the data. Cut out the segment corresponding to ()). Next, individual symbol recognition is performed for each segment. At this stage, the recognition result of the symbol string may be determined, but in order to perform more accurate recognition, a constraint of a higher hierarchy (such as a word) is used. At that time, the symbol candidate string of the individual recognition result is compared with the dictionary of the upper layer unit to obtain an appropriate symbol string as the arrangement of the upper layer unit.

An example of the flow of the above-described processing for reading an address will be described with reference to FIG. In the case of reading a destination address, the analog data is image data of the destination address, a symbol is a character, and the upper hierarchy means an address element such as a prefecture name, a municipal name, a municipal name, and the like. In FIG. 2, first, a segment 20 corresponding to one character is cut out of the image data 10. Next, each segment 2
The result of character recognition for 0 is a character candidate string 30
It is. At this stage, a plurality of character candidates exist in one segment 20. For example, the character candidates corresponding to the leftmost segment 20 are “west”, “article”, and “dai”.
There are three types. When the character candidate string 30 is compared with the address element dictionary, the combination of the address elements “Shinagawa-ku” and “Nakanobu” corresponds well, and this is the final destination address read result 90.

[0004] Such a conventional address and address reading apparatus is, for example, an automatic mail address reading and sorting machine for the Ministry of Posts and Telecommunications of Japan (= Cited Document 1; Ishikawa et al., NEC Technical Report,
Vol. 44, No. 3, 1991), "Postal Mail Address Automatic Reading and Sorting Machine TR-17" (= Cited Document 2, Torimoto et al., Toshiba Review, Vol. 45, No. 2, 1990) Japanese Unexamined Patent Publication No. Hei 5-324899, "Address Recognition Apparatus Described by Mail" (= Cited Document 3);
For example, it is described in Japanese Patent Publication “Address Recognition Device” (= cited reference 4). A conventional example of an apparatus for reading the text of a document, which is also a kind of symbol string reading apparatus, is described in "Implementation and Evaluation of Post-processing of Japanese Document Reader" (= Cited Document 5, Takao et al. Magazine, No. 30
Vol. 11, No. 1989), "Error Detection and Automatic Correction of Japanese Text Input by OCR" (= Cited Document 6, Ito et al., Transactions of Information Processing Society of Japan, Vol. 33, No. 5, 1992
), "Natural Language Processing in Character Recognition" (= Cited Document 7; Nishino, Information Processing, Vol. 34, No. 10, 199)
(In this case, analog data is image data of a text area in a document, a symbol is a character, and a higher hierarchical unit is a word). Conventional examples of a speech continuous speech recognition apparatus include “speech recognition using a stochastic model” (= Cited Document 8; Nakagawa, IEICE, 1988); and “speech recognition” (= Cited Document 9; Watanabe). Others, NEC Technical Report, Vol. 47, No. 8, 1994
Year), Japanese Patent Publication No. 6-32014, "Word detection method"
(In this case, the analog data is the acoustic data of the continuous speech,
The symbol is a phoneme, and the higher hierarchical unit is a word.)

[0005]

As shown in the example of FIG. 2, since a plurality of symbol candidates usually exist in one segment, the collation between the symbol candidate string and the upper hierarchy unit dictionary is a combination. Become. If specifically described with reference to the example of FIG. 2, "Nishikawa ...
"...""Nishihachi...""Nishiyama...""Shinagawa...""Shinpachi ...
"...""Shinyama...""Taikawa...""Taihachi...""Taiyama..."
.. ”Is searched for in the address element dictionary.

[0006] Furthermore, since the segment is usually cut out in a plurality of ways, the number of combinations of character candidates for matching with the dictionary is further increased. FIG. 3 shows a case where a plurality of types of segment cutting methods are considered for a part of FIG. In the example of FIG. 3, nine segments are originally cut out for two characters “Shinagawa”. Segment position information 21 expressed in units of the segment at the time of the finest division is also shown. The segment position information 21 is [segment head position, segment width]
It is expressed in two terms. In the example of FIG. 3, [1,1]-[2,1]-[3,1]-[4,1]-
[5,1] [1,1]-[2,1]-[3,1]-[4,2] [1,1]-[2,1]-[3,3] [1,1] -[2,2]-[4,1]-[5,1] [1,1]-[2,2]-[4,2] [1,2]-[3,1]-[4, [1]-[5,1] [1,2]-[3,1]-[4,2] [1,2]-[3,3]. Since there are three types of character candidates in each segment, there are 576 combinations of character candidates.

Further, the correct symbol may not be included in the symbol candidate sequence. Particularly when the input analog data is handwritten image data of a postal address, it is quite common that character candidates do not include correct characters. Assuming that the correct candidate symbol is not included in the symbol candidate string as a processing target, incomplete matching (so to speak, insect-eating matching) with the dictionary is required. FIG. 4 is a list of address elements of Shinagawa-ku, Tokyo, which are above the street name. For example, when the address element dictionary having the contents as shown in FIG. 4 is compared with the character candidate string 30 shown in FIG. 2, if the incomplete match is included, the following address elements are searched (all characters). Excluding discrepancies).

Exact match: Shinagawa-ku, Nakanobu, Nishinakanobu 1 character mismatch: Togoshi, Oyama, Yashio, Hiratsuka, Higashishinagawa, Nishishinagawa, Minamishinagawa, Kitashinagawa, Higashinakanobu, 2 characters mismatch: Flag stand, Oyamadai, Nishioi, Nishi-Gotanda 3-character mismatch: Higashi-Gotanda In order to achieve such incomplete matching, simply sorting the items in the upper layer unit in the dictionary does not provide sufficient search efficiency. Assuming that the item does not match at the first character, it may be possible to perform a partial match search with a symbol candidate string for all items in the dictionary. Furthermore, for example, if there are many possible ways to cut out a segment, it is not always possible to assume that the number of mismatched characters matches the number of segments. Taking as an example "Nishi Gotanda" where the two characters do not match, "West" matches in the leftmost segment in FIG.
When is not found, it is hardly possible to specify how many segments “field” may be located from “west”. In the example of FIG. 2, the character candidate at the position skipped by one segment from “west” includes “ta”, and the skipped one segment is divided into two segments depending on the extraction method, and the two segments are “five” and “counter”. Is considered in consideration of the possibility of matching. Considering such a possibility, if it is attempted to extract all patterns at the stage of matching a symbol candidate string with a dictionary in a higher hierarchical unit, the processing amount increases in combination, and becomes complex and enormous. I will.

As can be understood from the above description, in the conventional symbol string reading apparatus, when comparing a symbol candidate string with a dictionary in a unit of a higher hierarchy, a plurality of ways of cutting out a segment and a plurality of symbols of each segment are used. Attempts to handle candidates, incomplete matching, and the like have a problem that the processing amount increases in combination and the processing becomes complicated.

In addition to this problem, the conventional symbol string reading apparatus has a problem of complicated adjustment and maintenance. This problem will be described below.

By collating the symbol candidate sequence with the dictionary in the upper layer unit, a sequence of symbol candidates that can be regarded as corresponding to the upper layer unit is obtained.
It is also necessary to determine the arrangement of the upper layer unit. In the example of FIG. 2, there are three address elements “Shinagawa-ku”, “Nishinakanobu”, and “Nakanobu” as the address elements obtained by perfect matching for the character candidate string 30, but “Shinagawa-ku” and “Nishinakanobu” In the combination, the existence positions overlap. On the other hand, the combination of "Shinagawa-ku" and "Nakanobu" can be determined to be highly reliable because the two address elements are adjacent and satisfy the hierarchical relationship of the addresses.

In the example of FIG. 2, a sequence of highly reliable character candidates that satisfies both the adjacency condition and the hierarchical relationship can be obtained by the arrangement of the completely matching address elements. And must be combined with incomplete matches. At this time, it is necessary to determine the best combination in consideration of both the degree of coincidence between the symbol candidate string and the upper hierarchical element and the suitability of the arrangement of the upper hierarchical elements.

However, in the conventional symbol string reading device,
The above two factors need to be adjusted separately. For example, as described above, the matching considering all the possibilities between the symbol candidate sequence and the dictionary requires a huge amount of processing,
It is assumed that a complete match and a one-character mismatch are taken out of the dictionary. Then, even if the combination of the searched upper-layer elements is determined and it is desired to also determine the two-character mismatch, it is necessary to start over again or to recreate / replace the constituent elements of the apparatus.

Therefore, there is a problem that complicated operations and labor are required for adjustment and maintenance necessary for obtaining more optimum results and performance.

As described above, in the conventional symbol string reading apparatus, if the possibility is to be considered in order to increase the accuracy, the processing amount increases in combination and the processing becomes complicated. In addition, there is a problem that adjustment and maintenance become complicated. SUMMARY OF THE INVENTION It is an object of the present invention to provide a symbol string reading apparatus that eliminates the above-mentioned conventional disadvantages, efficiently obtains an optimum reading result, and is easy to adjust and maintain.

[0016]

According to the present invention, there is provided a symbol string reading apparatus for reading a one-dimensional symbol string corresponding to input analog data, by cutting out a segment corresponding to one symbol from the analog data. An individual recognition unit that performs individual symbol recognition for each segment; a symbol candidate string buffer that stores a result of the individual recognition unit;
For each symbol, at least [Upper hierarchical unit U,
A tag dictionary memory for storing ternary information such as a symbol string length L of U and a position P of the symbol in U, and a symbol candidate in the symbol candidate string buffer corresponding to the symbol candidate from the tag dictionary memory. Item 3. Tag assigning means for retrieving information, a tag information buffer for storing a search result of the tag assigning means, an upper layer constraint memory for describing a connection constraint between upper layer units, For three sets of three-term information [U1, L1, P1] and [U2, L2, P2], the positional relationship between segments corresponding to the three-term information and U1 · L
1. An optimal tag chain search means for determining a one-dimensional symbol string corresponding to the analog data by connecting the relations among 1.P1, U2, L2, and P2 using connection constraints. Is a symbol string reading device.

[0017]

According to the present invention, tagging means 5 does not execute the collation of the cut-out and individual recognition results stored in the symbol candidate string buffer 3 with the upper hierarchy unit dictionary as in the prior art. After tagging the candidates indicating the relationship with the upper layer unit, the optimal tag chain search means 8
To find the best combination of tags.

Conventionally, in reading the address of a postal address, conventionally, first, address elements such as "Shinagawa-ku" and "Nakanobu" were searched from a character candidate string, and a combination of "Shinagawa-ku" and "Nakanobu" was examined. However, in the present invention, “article” is one of “Shinagawa-ku”.
The first character, "river", is tagged with the second character of "Shinagawa-ku".
-Connect with "ku"-"medium"-"nobu".

[0019] Thus, since the upper layer unit constraint and the connection constraint can be handled in the same framework, the adjustment for obtaining the optimum result becomes easier. Further, since it is not necessary to perform collation with a dictionary, the processing can be executed at high speed.

[0020]

FIG. 1 is a block diagram showing the configuration of an embodiment of the present invention.

The data input means 1 inputs analog data. The individual recognizing unit 2 cuts out a segment corresponding to one symbol from the analog data input by the data input unit, and performs individual symbol recognition for each segment. The symbol candidate string buffer 3 stores the result of the individual recognition means 2. The tag dictionary memory 4 stores, for each symbol, at least ternary information of [Upper layer unit U of the symbol, symbol string length L of U, position P of the symbol in U]. The tag assigning means 5 searches the tag dictionary memory 4 for three-term information corresponding to the symbol candidate in the symbol candidate string buffer 3 for the symbol candidate. The tag information buffer 6
The search result of the tag assigning means 5 is stored. The upper layer constraint memory 7 describes connection constraints between upper layer units. The optimal tag chain search means 8 performs the two ternary information [U1, L1, P1] and [U2, L2, P
2], by using the positional relationship of the segment corresponding to the three-term information and the relationship among U1, L1, P1, U2, L2, and P2 as connection constraints, the input analog data Determine the corresponding one-dimensional symbol sequence.
The read result buffer 9 stores the result determined by the optimum tag chain search means 8.

The symbol candidate string buffer 3, tag dictionary memory 4, tag information buffer 6, upper layer constraint memory 7, and read result buffer 9 can be realized by storage devices such as an IC memory and a magnetic disk device. The individual recognizing unit 2, the tag assigning unit 5, and the optimal tag chain searching unit 8 can be realized by a CPU of a computer or a dedicated circuit.

The first embodiment of the present invention is a device for reading an address written on a post or a form. In this embodiment, the analog data indicates image data of an address area of a post or a form, the symbol string indicates a character string, and the upper layer unit indicates an address element such as a prefecture name, a municipal name, a municipal name. The data input means 1 may use an image scanner. The individual recognizing means 2 is a means for cutting out a segment corresponding to one character from the image data and performing character recognition for each segment, and is as described as a known means in Patent Documents 1, 2, and 3 and the like. . The data content written to the symbol candidate string buffer 3 as the processing result of the individual recognizing means 2 can be expressed, for example, in a format as shown in FIGS.

The tag dictionary memory 4 in this embodiment is
For each character used as an address element [Address element U,
Ternary information of a character string length L of U and a position P of the character in U is stored. FIG. 5 shows an example of the contents of the tag dictionary memory 4 for the address element group as shown in FIG. In FIG. 5, the key characters 40 to the left of “:” are the characters appearing in the address element, and the corresponding three-term information is arranged on the right side. For example, if these three items of information are [EBARA, 2,1] corresponding to “EB”, it indicates that the character “EB” is the first of two characters of the address element “EBARA”. ing. Since a certain character may appear in multiple address elements, for example, it corresponds to “Nobu” [Nishinakanobu, 3,
3] [Nakanobu, 2, 2] [Higashinakanobu, 3, 3]
The character "Nobu" is the third character of the three characters of the address element "Nishinakanobu", the second character of the two characters of the address element "Nakanobu", or the three characters of the address element "Higashinakanobu". It expresses that it is the third character. Although the address element U in the ternary information is represented by a character string in the example of FIG. 5, it may be represented by a code value associated with the address element instead of the character string itself.

The tag assigning means 5 includes a symbol candidate string buffer 3
Is searched for the tag dictionary memory 4 using each of the character candidates corresponding to the segment as a key. And the key character 4 of the tag dictionary memory 4
If there is a character corresponding to 0, the ternary information corresponding to the character is read and written to the tag information buffer 6. FIG. 6 shows an example of the result written in the tag information buffer 6 when the tag dictionary memory 4 as shown in FIG. 5 is searched for the character candidate string 30 as shown in FIG.

The upper-level constraint memory 7 stores an upper-lower-order relationship of addresses represented by a tree structure in FIG. That is, in terms of the address structure of Shinagawa-ku in FIG. 4, there is a relationship that "Shinagawa-ku" is below "Tokyo", and "EBARA", "Flag Nodai" and other towns are below that. In the case of an address, in general, a basic superordinate-subordinate relationship is established in the order of a prefecture name, a municipal county name, and a town name, and the town name level is represented by a capital letter name, a character name (or a town name, a town name), or the like. It can be multistage. In the case of an address, the upper-lower relationship of the address elements directly serves as a constraint on the arrangement of the address elements. That is, the address elements are arranged in order from a higher-order address element to a lower-order address element. If the example based on FIG. 4 is described, "Tokyo"-"Shinagawa-ku"-"Nakanobu" is OK, but "Tokyo"-"Nakanobu" or "Nakanobu"-"Flag stand" No lineup is allowed. Such a connection constraint expression method includes, for example, a method of describing whether connection is possible for all combinations of two address elements, and a method of listing address elements that can be connected immediately after or immediately before a certain address element. .

The optimal tag chain search means 8 connects the two pieces of three-term information in the tag information buffer 6 to determine a final one-dimensional symbol string (address reading result in this embodiment). For example, the following can be considered.

The first method of realizing the optimum tag chain search means 8 is that two pieces of ternary information [U1, L
[1, P1] and [U2, L2, P2] Condition 2a: The segment corresponding to [U1, L1, P1] is ahead of the segment corresponding to [U2, L2, P2] Condition 2b: U1 = U2 And P1 <P2 Condition 2c: If U1 can exist before U2, then condition 2a and (condition 2b or condition 2c)
Holds when [U2, L1, P1] is followed by [U2, L1
2, P2] to form all possible combinations, calculate the cost of each combination, and select the best cost combination.

FIG. 7 shows the tag information buffer 6 shown in FIG.
This is an example of a case where tag concatenation by the first realization method is executed based on the above. In FIG. 7, two tags (three-term information stored in the tag information buffer 6) satisfying the above conditions 2a and 2b or 2c are connected by a solid line. For example, although the tag [Shinagawa-ku, 3, 2] of the segment (2, 1) and the tag [Shinagawa-ku, 3, 3] of the segment (3, 1) are connected, the condition between the two tags is 2a and the condition 2b are satisfied. The condition 2a is satisfied because the end position 2 of the segment (2, 1) is ahead of the start position 3 of the segment (3, 1). The satisfaction of the condition 2b means that U1 = U
2 = “Shinagawa Ward”, because P1 = 2 <P2 = 3. In addition, the tag [Shinagawa-ku,
3,2] and tag of segment (4,1) [Hiratsuka, 2,
1] are linked by satisfying the conditions 2a and 2c. Referring to the upper layer constraint memory 7, since U1 = “Shinagawa Ward” is an upper address element of U2 = “Hiratsuka”, the condition 2c
It can be seen that holds.

In the first realization method, after all the tag connections as shown by the solid lines in FIG. 7 are formed, cost calculation is executed for those combinations to select the one with the best cost.

The second method of realizing the optimum tag chain search means 8 is that two pieces of ternary information [U1, L
For [1, P1] and [U2, L2, P2], condition 3a: the segment corresponding to [U1, L1, P1] is immediately adjacent to the segment corresponding to [U2, L2, P2]. Does not hold, but [U1, L1, P
The segment corresponding to [1] is before the segment corresponding to [U2, L2, P2]. Condition 3c: U1 = U2 and P1 + 1 = P2 Condition 3d: U1 = U2 and P1 + 1 <P2 Condition 3e: U1 is immediately before U2 P1 = L1
And P2 = 1 Condition 3f: Condition 3e is not satisfied, but U1 can exist ahead of U2. First, when condition 3a and (condition 3c or condition 3e) are satisfied, [U1, L1, P1] After [U
2, L2, P2] to form a combination, calculate the cost of each combination, and if a combination having a cost value better than the threshold is not obtained, conditions 3b and (condition 3d or condition 3f) are satisfied. [U1, L1,
The combination of [P1] and [U2, L2, P2] is also formed, the cost is calculated again, and the combination with the best cost is selected.

FIG. 8 shows the tag information buffer 6 shown in FIG.
This is an example of a case where tag concatenation by the second realization method is executed based on the above. In FIG. 8, two tags satisfying the above conditions 3a and 3c or 3e are connected by a solid line. For example, the condition 3a and the condition 3c are satisfied between the tag [Nishinakanobu, 3,1] of the segment (3, 1) and the tag [Nishinakanobu, 3, 2] of the segment (4, 1). The condition 3a is satisfied because the end position 3 of the segment (3, 1) is immediately before the start position 4 of the segment (4, 1). The condition 3c is satisfied when U1 = U2 = “Nishinakanobu” and P1 + 1 =
1 + 1 = 2 = P2. In addition, between the tag [Shinagawa-ku, 3, 3] of the segment (3, 1) and the tag [Nakanobu, 2, 1] of the segment (4, 1), the condition 3a
The condition 3e is satisfied. U1 = "Shinagawa-ku" is U2
= Since it is the next higher address element of “Nakanobu”, it can exist immediately before, and since P1 = L1 = 3 and P2 = 1, condition 3
It can be seen that e holds. On the other hand, in FIG.
The tags satisfying the condition 3b and the condition 3d or the condition 3f are connected by a dotted line. The tag connection indicated by the dotted line in FIG. 8 corresponds to the tag connection indicated by the solid line in FIG. 7 except for the tag connection indicated by the solid line in FIG.

In the second realization method, first, only tag combinations as shown by solid lines in FIG. 8 are formed, and cost calculation is performed for those combinations. As a result, when a combination of tag bindings better than a certain threshold is obtained, the tag binding as shown by the dotted line in FIG. 8 is not formed. On the other hand, when a combination better than the threshold is not obtained, the best cost combination is selected after performing tag formation such as a dotted line (in the latter case, the combination selected as a result is the first combination). Implementation method).

A third method of realizing the optimum tag chain search means 8 is as follows. Of the three item information [U, L, P] in the tag information buffer 6, the corresponding segment positions are arranged in order from the front to the rear. U, L, P], for the three-term information [U ', L', P '] ahead of the corresponding segment position, Condition 4a: U' = U and P '<P Condition 4b: U' is located ahead of U When it is assumed that there exists, [U ', L', P '] satisfying the condition 4a or the condition 4b, the one having the best cost value of the combination when [U, L, P] is connected is sequentially determined. The best cost combination is determined by making selections.

The third realization method will be described with reference to the example shown in FIG. In this third realization method, the corresponding segment position is processed in order from the tag in front, so first, in FIG. 9, the tag [Nishi-Gotanda, 4, 1] [Nishioi, 3, 3] corresponding to the segment (1, 1) 1] ... [Oyamadai,
[3, 3] is determined. Next, the cost value of the tag [Nishi-Shinagawa, 3, 3] [Higashi-Shinagawa, 3, 3] ... [Koyamadai, 3, 2] corresponding to the segment (2, 1) is determined. Next, the cost value of the tag [Nishi-Gotanda, 4, 4] [Higashi-Gotanda, 4, 4]... [Shinagawa-ku, 3, 3] corresponding to the segment (3, 1) is determined. . At this time, for example, when determining the cost of [Nakanobu, 2, 1] corresponding to the segment (4, 1), the segments (1, 1) (2,
1) Search for tags satisfying the condition 4a or the condition 4b among the tags corresponding to (3, 1), select the tag having the best cost when combined, and based on the tag combination, The cost of [Nakanobu, 2, 1] is determined. Specifically, [Nakanobu, 2,
1] is [Shinagawa-ku, 3,1] of segment (1,1),
[Shinagawa-ku, 3,2] of segment (2,1) and [Shinagawa-ku, 3,3] of segment (3,1) satisfy the condition,
A combination with [Shinagawa-ku, 3, 3] of the segment (3, 1) can be selected as a combination that provides the best cost value when combined.

The tag connection represented by the dotted line and the solid line in FIG.
Those that satisfy the condition 4a or the condition 4b are shown. For each tag, a solid line shows an example of the tag having the best coupling cost with the tag in front. In this way, the method of deciding the cost value of the tag in order from the previous one accumulates the cost based on the best combination in front of the tag, so-called dynamic programming (Viterbi algorithm) ) Is used to determine the best cost combination.

In the above, an example of the method of connecting the tags in the optimal tag chain search means 8 and determining the final one-dimensional symbol string based on the cost value for the combination has been described. Various definitions are possible for the cost value at that time. For example, the following items can be reflected in costs.

(A) Number of linked tags (number of linked items of ternary information) (B) Number of skipped symbols (logical intervals of tags) (C) Interval of segments corresponding to tags (physical tags) Interval) (D) Difference between logical interval and physical interval of tag (E) Reliability (or distance) in individual recognition of each symbol In the simplest case, when only the above (A) is used for cost,
What is necessary is just to give a fixed cost value every time one tag is connected. The more tags are linked from the beginning, the better the accumulated value of the cost value is, and the combination (3) composed of the largest number of tag connections (the combination with the largest number of linked item information) has the best cost value. The final reading result.

In this case, assuming that, for example, a cost value = −100 points is given to one tag, in the example of the optimal tag chain search of FIGS. It is judged to be the best at -500 points.

[Shinagawa-ku, 3,1]-[Shinagawa-ku, 3, 2]-[Shinagawa-ku, 3, 3]-[Nakanobu, 2, 1]-[Nakanobu, 2, 2] ... (1) However, with only (A), a plurality of combinations having the best cost value often occur. For example, in the example of FIG. 7, the following combinations are possible, and the cost value of the tie is -500 points.

[Shinagawa-ku, 3,1]-[Shinagawa-ku, 3, 2]-[Shinagawa-ku, 3, 3]-[Nishinakanobu, 3, 2]-[Nishinakanobu, 3, 3] ... (2) In order to make a more precise judgment, the above (B) and (C)
Items such as (D) and (E) may be used for cost.

The logical interval between the tags in the item (B) is defined as follows: For two tags [U1, L1, P1] and [U2, L2, P2], when U1 = U2: P2-P1-1 U1 ≠ U2 In the case of: L1-P1 + P2-1 is defined. That is, it corresponds to the number of characters (symbols) skipped at a certain point in the middle of the read result.

For example, in the example of FIG. 7, when the combination of the tags (2) is considered, one character is skipped between [Shinagawa-ku, 3, 3] and [Nishinakanobu, 3, 2]. (“Nishi” in “Nishishinagawa” has been skipped). Therefore, the logical interval between the two tags is one.
The logical interval of the other tags in (2) is zero.

The tag connection cost may be set so that the cost value becomes worse (to give a penalty) according to the logical interval. For example, if a logical interval × 50 points are additionally introduced as a cost, the cost value of the above (2) becomes −
450 points, which is worse than the -500 point of (1).

The physical interval between tags in the item (C) is an interval between segments corresponding to the tag. For example, in the example of FIG. 7, the tag [Nishinakanobu, 3, 1] of the segment (1, 1)
And the tag [Nishinakanobu, 3, 2] of the segment (4, 1) can be connected. The logical interval between the two tags is zero. On the other hand, the physical interval is a segment (2, 1) between
And (3, 1), which is equivalent to two segments. The method of counting the physical interval includes a method of counting the number of intervening segments, a method of counting the difference (distance) between two segments if coordinates are defined, and a method of averaging the distance. A value divided by the segment size is also conceivable.

In the case of the physical interval, similarly to the case of the logical interval, the cost of tag connection may be set so that the cost value becomes worse according to the physical interval (to give a penalty) ( (For example, physical interval × 50 points).

The difference between the logical interval and the physical interval of the tag in item (D) has the following meaning. For example, in the example of FIG. 7, regarding the combination of the above (2) and the connection between the tag [Shinagawa-ku, 3, 3] and the tag [Nishinakanobu, 3, 2], the logical interval is 1, The physical spacing is zero.
That is, a character (symbol) is expected at a place where there is no physical gap, and the reading is unnatural. On the other hand, the tag [Nishinakanobu, 3,1] of the segment (1,1) and the tag [Nishinakanobu,
[3,2], the logical interval is 0 and the physical interval is 2
(When counted by the number of segments). This means that noise is mixed between the tags, which is not a preferable interpretation. Here, it was described that when one of the logical interval and the physical interval is 0, it is unnatural that the other has a value other than 0, but more generally, the logical interval and the physical interval are It is good to make the cost value worse (giving a penalty) when the difference from the above is large.

Item (E), which has been conventionally used for cost calculation in reading a symbol string, takes into account the reliability or unreliability (distance) at the time of individual recognition.

As described above, the address reading apparatus has been described as the first embodiment. Further, the second embodiment and the third embodiment will be described with the same configuration (FIG. 1) as the first embodiment.

The second embodiment of the present invention is an apparatus for reading a sentence in a document. In this embodiment, the analog data indicates image data of a text area in a document, the symbol string indicates a character string, and the upper layer unit indicates a word. The data input means 1 and the individual recognition means 2 are the same as in the first embodiment. In general, as compared with the first embodiment, the types of words appearing in a character string are abundant, and the tag dictionary memory 4 stores those words (not only independent words such as nouns / verbs but also particles). And auxiliary words such as auxiliary verbs)
Item information will be registered. The upper layer constraint memory 7 describes word connection constraints (grammar). The format of the data stored in the symbol candidate string buffer 3, the tag information buffer 6, the read result buffer 9, and the like may be the same as in the first embodiment. This can be realized in the same manner as in the example.

The third embodiment of the present invention is a speech continuous speech recognition apparatus. In this embodiment, analog data indicates acoustic data of uttered continuous voice, symbol strings indicate phoneme strings, and upper layer units indicate words. The data input means 1 may use a microphone. The individual recognizing means 2 is a means for extracting segments corresponding to one phoneme from acoustic data and performing phoneme recognition for each segment, and is as described as a known means in Patent Documents 8 and 9. Also in the case of the third embodiment, the types of words to be handled are the same as those of the second embodiment, and the data input unit 1 and the individual recognition unit 2
The method of realizing each means except for the above may be considered in the same manner as in the second embodiment.

[0052]

According to the symbol string reading apparatus of the present invention, the result of the extraction and the individual recognition is not compared with the conventional upper layer unit dictionary in combination.
The tag assigning means 5 tags the symbol candidates to indicate the relationship with the upper layer unit, and the optimal tag chain searching means 8 finds the optimal combination of tags. Therefore, in the conventional symbol string reading device, in order to increase the accuracy, if the possibility is considered more widely, there is a problem that the processing amount increases in combination and the processing becomes complicated. According to the present invention, the problem is eliminated, and it is possible to efficiently obtain an optimum reading result.

Further, since the upper layer unit constraint and the connection constraint can be handled in the same framework, adjustment for obtaining an optimum result is easier than in the past.

[Brief description of the drawings]

FIG. 1 is a block diagram showing the configuration of an embodiment of the present invention.

FIG. 2 is a diagram showing an example of a conventional process of reading a destination address.

FIG. 3 is a diagram illustrating an example of a plurality of types of segments and character candidates in address / address reading.

FIG. 4 is an example of a list of address elements.

FIG. 5 is an example of the contents of a tag dictionary memory 4;

FIG. 6 is an example of the contents of a tag information buffer 6;

FIG. 7 is an example of tag concatenation by a first realization method of the optimal tag chain search means 8;

FIG. 8 is an example of tag concatenation by a second realization method of the optimal tag chain search means 8;

FIG. 9 is an example of tag concatenation by a third realization method of the optimal tag chain search means 8;

[Explanation of symbols]

 DESCRIPTION OF SYMBOLS 1 Data input means 2 Individual recognition means 3 Symbol candidate string buffer 4 Tag dictionary memory 5 Tag assigning means 6 Tag information buffer 7 Upper layer constraint memory 8 Optimal tag chain search means 9 Reading result buffer 10 Image data 20 Segment 30 Character candidate string 40 Key character 41 3 item information 90 Address reading result

Continuation of the front page (56) References JP-A-6-124366 (JP, A) JP-A-4-111186 (JP, A) JP-A-2-249599 (JP, A) Word Search Algorithm -Character Tag Method- ", Information Processing Society of Japan Research Report, 95-NL-107, (Vol. 95, No. 52), PP. 43-50 (58) Field surveyed (Int.Cl. ⁶ , DB name) G06K 9/72 G06K 9/62 PATOLIS (patent file) JOIS (JICST file)

Claims (8)

(57) [Claims] 1. Defining a higher hierarchical unit for a symbol
And the symbol string to be read is the upper floor
When there are two or more layers,
Symbol string to read one-dimensional symbol string corresponding to log data
In the reading device, from among the analog data,
Cut out a segment corresponding to one symbol, and
Individual recognition means for performing individual symbol recognition for each
A symbol candidate string buffer for storing the results of the different recognition means,
At least [U, U higher-order unit of the symbol
Information of the symbol string length L and the position P in the U of the symbol
Tag dictionary memory for storing (tags), and the symbol candidate string
From the tag dictionary memory for symbol candidates in the buffer
Tag for searching ternary information (tag) corresponding to the symbol candidate
Providing means for storing search results of the tag providing means.
Describes connection constraints between the logging information buffer and the upper layer unit
The upper layer constraint memory to be
Two ternary information [U1, L1, P1] and [U2, L2, P2]
And the positional relationship of the segments corresponding to the three-term information
U1 ・ L1 ・ P1 ・ U2 ・ L2 ・ P2 relationship and connection constraint
To connect to the analog data
Optimal tag chain search means for determining a one-dimensional symbol string
A symbol string reading device, wherein the optimal tag chain searching means includes two ternary information [U1, L1, P1] and [U2, L2, P2] in the tag information buffer.
2], condition 2a: the segment corresponding to [U1, L1, P1] is ahead of the segment corresponding to [U2, L2, P2] condition 2b: U1 = U2 and P1 <P2 condition 2c: U1 is U2 Can be present in front of the condition 2a and (condition 2b or condition 2c)
Holds when [U2, L2, P1] and [U2, L2,
P2] to form all possible combinations, calculate the cost of each combination, and select the best cost combination. 2. Defining a higher hierarchical unit for a symbol
And the symbol string to be read is the upper floor
When a sequence of two or more layers units, input Ana
Symbol string to read one-dimensional symbol string corresponding to log data
In the reading device, from among the analog data,
Cut out a segment corresponding to one symbol, and
Individual recognition means for performing individual symbol recognition for each
A symbol candidate string buffer for storing the results of the different recognition means,
At least [U, U higher-order unit of the symbol
Information of the symbol string length L and the position P in the U of the symbol
Tag dictionary memory for storing (tags), and the symbol candidate string
From the tag dictionary memory for symbol candidates in the buffer
Tag for searching ternary information (tag) corresponding to the symbol candidate
Providing means for storing search results of the tag providing means.
Describes connection constraints between the logging information buffer and the upper layer unit
The upper layer constraint memory to be
Two ternary information [U1, L1, P1] and [U2, L2, P2]
And the positional relationship of the segments corresponding to the three-term information
U1 ・ L1 ・ P1 ・ U2 ・ L2 ・ P2 relationship and connection constraint
To connect to the analog data
Optimal tag chain search means for determining a one-dimensional symbol string
A symbol string reading device, wherein the optimal tag chain searching means includes two ternary information [U1, L1, P1] and [U2, L2, P2] in the tag information buffer.
2], condition 3a: a segment corresponding to [U1, L1, P1] is immediately adjacent to a segment corresponding to [U2, L2, P2]. Condition 3b: condition 3a is not satisfied but [U1, L1, P1] ]
Condition 3c: U1 = U2 and P1 + 1 = P2 Condition 3d: U1 = U2 and P1 + 1 <P2 Condition 3e: U1 exists immediately before U2 P1 = L1 and P2 = 1 Condition 3f: Condition 3e is not satisfied but U1 can exist before U2. First, when condition 3a and (condition 3c or condition 3e) are satisfied, U1, L1, P1] followed by [U2,
L2, P2] are combined to form a combination, and the cost of each combination is calculated. If a combination having a cost value better than the threshold value cannot be obtained, the conditions 3b and (condition 3d or condition 3f) are satisfied. A symbol string reading device in which a combination of [U1, L1, P1] and [U2, L2, P2] is also formed, the cost is calculated again, and the best cost combination is selected. 3. Defining a higher hierarchical unit for a symbol
And the symbol string to be read is the upper floor
When there are two or more layers,
Symbol string to read one-dimensional symbol string corresponding to log data
In the reading device, from among the analog data,
Cut out a segment corresponding to one symbol, and
Individual recognition means for performing individual symbol recognition for each
A symbol candidate string buffer for storing the results of the different recognition means,
At least [U, U higher-order unit of the symbol
Information of the symbol string length L and the position P in the U of the symbol
Tag dictionary memory for storing (tags), and the symbol candidate string
From the tag dictionary memory for symbol candidates in the buffer
Tag for searching ternary information (tag) corresponding to the symbol candidate
Providing means for storing search results of the tag providing means.
Describes connection constraints between the logging information buffer and the upper layer unit
The upper layer constraint memory to be
Two ternary information [U1, L1, P1] and [U2, L2, P2]
And the positional relationship of the segments corresponding to the three-term information
U1 ・ L1 ・ P1 ・ U2 ・ L2 ・ P2 relationship and connection constraint
To connect to the analog data
Optimal tag chain search means for determining a one-dimensional symbol string
A symbol string reading device, wherein the optimal tag chain searching means includes a corresponding segment position in the three-item information [U, L, P] in the tag information buffer from a preceding one to a following one. In order, the corresponding segment position ahead of [U, L, P] is the three-term information [U ', L',
P ′], condition 4a: U ′ = U and P ′ <P Condition 4b: U ′ can exist in front of U, and condition 4a or condition 4b is satisfied [U ′, L ′, P '], A symbol string reading apparatus that determines the best cost combination by sequentially selecting the combination having the best cost value when [U, L, P] is connected. 4. Defining a higher hierarchical unit for a symbol
And the symbol string to be read is the upper floor
When a sequence of two or more layers units, input Ana
Symbol string to read one-dimensional symbol string corresponding to log data
In the reading device, from among the analog data,
Cut out a segment corresponding to one symbol, and
Individual recognition means for performing individual symbol recognition for each
A symbol candidate string buffer for storing the results of the different recognition means,
At least [U, U higher-order unit of the symbol
Information of the symbol string length L and the position P in the U of the symbol
Tag dictionary memory for storing (tags), and the symbol candidate string
From the tag dictionary memory for symbol candidates in the buffer
Tag for searching ternary information (tag) corresponding to the symbol candidate
Providing means for storing search results of the tag providing means.
Describes connection constraints between the logging information buffer and the upper layer unit
The upper layer constraint memory to be
Two ternary information [U1, L1, P1] and [U2, L2, P2]
And the positional relationship of the segments corresponding to the three-term information
U1 ・ L1 ・ P1 ・ U2 ・ L2 ・ P2 relationship and connection constraint
To connect to the analog data
Optimal tag chain search means for determining a one-dimensional symbol string
A symbol string reading device, wherein the optimal tag chain searching means includes two ternary information [U1, L1, P1] and [U2, L2, P2] in the tag information buffer.
2], the positional relation of the segment corresponding to the three-term information and the relation among U1, L1, P1, U2, L2, and P2 are connected using connection constraints, and finally the three-term information is connected. A symbol string reader that selects the combination that maximizes the number. 5. Defining a higher hierarchical unit for a symbol
And the symbol string to be read is the upper floor
When there are two or more layers,
Symbol string to read one-dimensional symbol string corresponding to log data
In the reading device, from among the analog data,
Cut out a segment corresponding to one symbol, and
Individual recognition means for performing individual symbol recognition for each
A symbol candidate string buffer for storing the results of the different recognition means,
At least [U, U higher-order unit of the symbol
Information of the symbol string length L and the position P in the U of the symbol
Tag dictionary memory for storing (tags), and the symbol candidate string
From the tag dictionary memory for symbol candidates in the buffer
Tag for searching ternary information (tag) corresponding to the symbol candidate
Providing means for storing search results of the tag providing means.
Describes connection constraints between the logging information buffer and the upper layer unit
The upper layer constraint memory to be
Two ternary information [U1, L1, P1] and [U2, L2, P2]
And the positional relationship of the segments corresponding to the three-term information
U1 ・ L1 ・ P1 ・ U2 ・ L2 ・ P2 relationship and connection constraint
To connect to the analog data
Optimal tag chain search means for determining a one-dimensional symbol string
A symbol string reading device, wherein the optimal tag chain searching means includes two ternary information [U1, L1, P1] and [U2, L2, P2] in the tag information buffer.
2], the positional relationship of the segment corresponding to the ternary information and the relationship among U1, L1, P1, U2, L2, and P2 are connected using connection constraints, and when U1 = U2: P2− When P1-1 U1 ≠ U2: a logical interval defined by L1-P1 + P2-1, a physical interval between segments corresponding to the ternary information, and a difference between the logical interval and the physical interval A symbol string reading device which calculates a cost value of a combination of ternary information using at least one of the above, and selects a combination having the best cost value. 6. Defining a higher hierarchical unit for a symbol
And the symbol string to be read is the upper floor
When there are two or more layers,
Symbol string to read one-dimensional symbol string corresponding to log data
In the reading device, from among the analog data,
Cut out a segment corresponding to one symbol, and
Individual recognition means for performing individual symbol recognition for each
A symbol candidate string buffer for storing the results of the different recognition means,
At least [U, U higher-order unit of the symbol
Information of the symbol string length L and the position P in the U of the symbol
Tag dictionary memory for storing (tags), and the symbol candidate string
From the tag dictionary memory for symbol candidates in the buffer
Tag for searching ternary information (tag) corresponding to the symbol candidate
Providing means for storing search results of the tag providing means.
Describes connection constraints between the logging information buffer and the upper layer unit
The upper layer constraint memory to be
Two ternary information [U1, L1, P1] and [U2, L2, P2]
And the positional relationship of the segments corresponding to the three-term information
U1 ・ L1 ・ P1 ・ U2 ・ L2 ・ P2 relationship and connection constraint
To connect to the analog data
Optimal tag chain search means for determining a one-dimensional symbol string
A symbol string reading device, wherein the analog data is image data of an address area of a post or a form, the symbol string is a character string, and the upper hierarchical unit is a prefecture name / city / county / town / village. A symbol string reading device that is an address element such as a name. 7. Defining a higher hierarchical unit for a symbol
And the symbol string to be read is the upper floor
When there are two or more layers,
Symbol string to read one-dimensional symbol string corresponding to log data
In the reading device, from among the analog data,
Cut out a segment corresponding to one symbol, and
Individual recognition means for performing individual symbol recognition for each
A symbol candidate string buffer for storing the results of the different recognition means,
At least [U, U higher-order unit of the symbol
Information of the symbol string length L and the position P in the U of the symbol
Tag dictionary memory for storing (tags), and the symbol candidate string
From the tag dictionary memory for symbol candidates in the buffer
Tag for searching ternary information (tag) corresponding to the symbol candidate
Providing means for storing search results of the tag providing means.
Describes connection constraints between the logging information buffer and the upper layer unit
The upper layer constraint memory to be
Two ternary information [U1, L1, P1] and [U2, L2, P2]
And the positional relationship of the segments corresponding to the three-term information
U1 ・ L1 ・ P1 ・ U2 ・ L2 ・ P2 relationship and connection constraint
To connect to the analog data
Optimal tag chain search means for determining a one-dimensional symbol string
A symbol string reading device, wherein the analog data is image data of a text area in a document, the symbol string is a character string, and the upper layer unit is a word. 8. Defining a higher hierarchical unit for a symbol
And the symbol string to be read is the upper floor
When there are two or more layers,
Symbol string to read one-dimensional symbol string corresponding to log data
In the reading device, from among the analog data,
Cut out a segment corresponding to one symbol, and
Individual recognition means for performing individual symbol recognition for each
A symbol candidate string buffer for storing the results of the different recognition means ,
At least [U, U higher-order unit of the symbol
Information of the symbol string length L and the position P in the U of the symbol
Tag dictionary memory for storing (tags), and the symbol candidate string
From the tag dictionary memory for symbol candidates in the buffer
Tag for searching ternary information (tag) corresponding to the symbol candidate
Providing means for storing search results of the tag providing means.
Describes connection constraints between the logging information buffer and the upper layer unit
The upper layer constraint memory to be
Two ternary information [U1, L1, P1] and [U2, L2, P2]
And the positional relationship of the segments corresponding to the three-term information
U1 ・ L1 ・ P1 ・ U2 ・ L2 ・ P2 relationship and connection constraint
To connect to the analog data
Optimal tag chain search means for determining a one-dimensional symbol string
A symbol string reading apparatus, wherein the analog data is acoustic data of continuous speech, the symbol string is a phoneme string, and the upper layer unit is a word.