JPH0554148B2 - - Google Patents

Description

[Detailed Description of the Invention] (Industrial Application Field) The present invention relates to components of an information processing system,
More specifically, the present invention relates to a symbol string matching device that extracts a specific symbol string from a long symbol string and a control method thereof.

(Prior art and its problems) The symbol matching device described above extracts feature sequences in a pattern recognition system, extracts keywords from the original text file of sentences created with a word processor, supports language translation, and explains abbreviations in correspondence. It is used to construct unstructured databases using graphics, images, texts, etc., and is indispensable to the form of intelligent information processing systems.

Conventional symbol string matching requires sequential processing using software on a general-purpose computer, which requires an enormous amount of processing time and is limited to small scale operations. In addition, matching targets were limited to structured signal sequences separated by word. As an example, n
To find out where a pattern consisting of n child symbol strings is located in a text consisting of child symbol strings, use
This requires m(n-m+1) matching processes. m = 10 ⁹ stored on a magnetic disk, optical disk, etc.
Searching for sentences with n = 10 ³ character strings from text with 3 character strings requires 10 ¹² matching processes. Therefore, it is impractical to conduct tests using large amounts of original information such as text, images, figures, and sounds, so we recommend adding keywords to the original information in advance or using data structured in a tabular format. It was limited to inspection. Another disadvantage is that the processing time is too long for flexible symbol string matching that allows variations in the constituent elements of symbol strings.

More specifically, problems with the conventional symbol string matching device and its control system will be explained.

FIG. 6 shows the text that is the subject of symbol string matching. This text shows the beginning of the report as an example. A large number of such texts are stored in the file memory of the word processor. When searching for what you need from such text, it is required to be able to search directly using words that indicate the content of your request.

For example, the text in Figure 1 is memory,
In order to know whether a paper contains symbol strings such as bubbles, memory, etc.
It is necessary to search to see if there is a matching part in symbol strings such as memories and bubbles. Comparing such symbol strings with text would take a very long time if conventional computers and software were used.

A typical A4-sized piece of English text is approximately 3,000 characters long, including spaces between words. On the other hand, the length of the symbol string used for comparison and matching is also
Device also has 6 characters. Matching between 6-character and 3000-character strings generally requires character comparisons a number of times on the order of the product. Even if the character comparison time in the microprocessor is 1 μsec, it takes 18 msec to check each symbol string.

The actual number of characters in the text to be searched is
10 ⁹ characters, and the number of characters in the symbol string to be matched is 100.
It is possible to exceed. The number of symbol strings to be matched is not just one, but dozens. In that case, the verification time would be several hundred hours. Therefore, such matching is practically impossible, and in reality, keywords are extracted manually in advance and matching is limited to the extracted keywords.

Furthermore, it is difficult to match symbol strings in which some symbols are missing or incorrect, or symbol strings to which extra symbols are added. For example, regarding the character string "MEMORY", there may be a character string "MEMXRY" in which the character "O" is replaced with another character "X", "MEMRY" without the character "O", or an extra character "X". It is desirable for symbol string matching to be able to output that it is similar to the matching string "MEMORY" when "MEMXORY" with "MEMXORY" added is input. However, with conventional symbol string matching devices and control methods, if there are errors in some symbols, it is possible to check for similarity by superimposing them on the matching symbol string and comparing them, but if some symbols are missing or extra characters It was not possible to deal with the addition of

(Objective of the Invention) The object of the present invention is to easily solve the drawbacks of the conventional symbol string matching devices and methods described above, and to quickly convert arbitrary symbol strings from unstructured symbol strings such as text, images, figures, etc. The object of the present invention is to provide a symbol string matching device capable of flexible extraction and a control method thereof.

Another object of the present invention is to provide a low-cost symbol string matching device that is capable of matching symbol strings with missing or incorrect symbols, or with extra symbols added.

(Structure of the Invention) Therefore, according to the present invention, the following symbol string matching device and its control method can be obtained. That is, a symbol string storage means that takes a symbol code as an address input and stores a collation symbol string, a first calculation means connected to each of the output lines, and a first temporary storage means that interconnects the plurality of calculation means. and a second temporary storage means connected to the output of the specific first temporary storage means;
a second calculation means connected to a second temporary storage means.

a symbol string storage means that takes a symbol code as an address input and stores a collation symbol string; a first calculation means connected to each of the output lines; a first temporary storage means that interconnects the plurality of calculation means; a second temporary storage means connected to the output of a specific first temporary storage means, a second calculation means connected to the second temporary storage means, a register for storing an externally given allowable similarity, and this register. a symbol string matching device that includes a comparator that compares the contents of the symbol with the output of the second calculation means and outputs a matching result; A symbol is stored in each column of the symbol string storage means, and when collating the symbol string, the symbol is input to the decoder of the symbol string storage means, and the contents of multiple columns of the address indicated by the input symbol of the symbol string storage means are parallelized. control the increment of the contents of the counters in each stage connected to each column of the previous symbol string storage means based on the read information and the transfer to the next stage counter, and control the increment of the contents of the counters in each stage connected to each column of the previous symbol string storage means and the transfer to the counters in the next stage, and the two counters in the last stage differ by one time from each other. This is a control method for a symbol string matching device characterized in that the degree of similarity between the contents of the symbol string storage means and the sequentially input symbol strings is determined by adding the contents.

(Example) The present invention will be explained in more detail below using the drawings.

FIG. 1 is an explanatory diagram of an embodiment of the present invention. This symbol string matching device can process texts, images, images, etc. that become long symbol strings as shown in Figure 6.
It encodes speech, etc., inputs it sequentially from the symbol string input terminal 111, and transmits to the outside where a symbol string similar to a registered verification symbol string is included. A symbol string storage means 110 for storing symbol strings, a multi-stage multi-bit counter 120 whose contents are changed by its reading symbol 112, and a second temporary storage means connected to the output of the counter 120 at the lowest stage. an adder 140 which is a second calculation means that adds the contents N6 of the lowest counter 120 and the contents of the register 130;
It consists of The counter 120 includes a logic operation means 123 and a temporary storage means 124 for storing the result of the operation. Here, the logical operation means 123 and the temporary storage means 124 are used as the counter 1.
The explanation will be given using 20 as a representative.

Each symbol of the verification symbol string is stored in each bit of the symbol string storage means 110 in a bit pattern associated with the symbol. In the example shown in the figure, 6-bit symbol string storage means 1
10 stores a collation symbol string consisting of six symbols of "MEMORY". That is, the symbols "M", "N", "E", "M", "O", "R", and "Y" are respectively stored in the first to sixth bits of the symbol string storage means 110.
"1" is stored only in the address specified by ", and "0" is stored in the other addresses. The addresses of the symbol string storage means 110 correspond to the types of symbols, and the first to sixth
The bit-th read signal 112 has symbols “M” and “M”, respectively.
It becomes "1" only when "E", "M", "O", "R", and "Y" are input.

The counter 120 in each stage operates in synchronization with the clock signal 121, and the output of each stage is connected to the data input of the next stage. Zero is supplied to the data input of the first stage counter 120, and the output N6 of the last stage counter 120 is applied to the register 130. Transfer signal 1 at the rising edge of clock signal 121
22 is applied, the counter 120 of each stage
The contents of are transferred step by step from the top to the bottom in the figure. Further, when the transfer signal 122 is not applied and a read signal 112 of "1" is supplied from the symbol string storage means 110, the content of the counter 120 increases by 1 (hereinafter referred to as increment).
However, in the case of a read signal of "0", the contents are retained.A counter 120 operating in this manner may be implemented using a commercially available integrated circuit, such as a Texas-based integrated circuit.
SN74LS161N manufactured by Instrument Corporation can be used.

Figure 2 shows a clock signal 121 and a transfer signal 122.
The timing diagram is shown below. As for the symbol string to be compared, one symbol is input from the symbol string input terminal 111 every cycle T, and two pulse signals, one before and one after, are applied as a clock signal 121 during that period. Transfer signal 1
22 is applied as a pulse signal included at the rising edge of the preceding pulse signal of the clock signal 121. Therefore, each time one symbol is input, the counter 120 of each stage is transferred and incremented (however,
(when the read signal 112 is "1") are performed alternately. The register 130 takes in the contents of the final stage counter 120 in response to the transfer signal 122.

FIG. 3 is an explanatory diagram of the operation of the symbol string matching device shown in FIG. 1.

As shown in FIG. 1, when the verification symbol string "MEMORY" is stored in the symbol string storage means 110, the symbol string "MEMORY" which is the same as the verification symbol string is
The operation when is input from the symbol string input terminal 111 will be explained with reference to FIG. Further, cases in which some symbols "O" in the collation symbol string are erroneous, missing, and extra symbols "X" are added will be explained using FIGS. b, c, and d, respectively.

In the figure, the first row shows the symbol string input from the symbol string input terminal 111, the second row shows the times T ₀ to T ₇ tentatively determined for each symbol input, and the third and subsequent rows show the symbol string input from the symbol string input terminal 111. The contents of the counter 120 after the pulse signal is applied are N1, N from the top.
2, N3, N4, N5, and N6, and their values are shown. The last row shows the value of the output N of adder 140.

First, before the verification operation, the contents N1 to N6 of the counters 120 in each stage are set to zero. Although not shown, this can be easily done by applying a pulse signal to the clear terminal of the counter 120.

Referring to FIG. 3a, the operation when the same symbol string "MEMORY" as the collation symbol string is input from the symbol string input terminal 111 will be described. First, when the first symbol "M" is input, the transfer signal 122 is applied at the rising edge of the previous pulse signal of the clock signal 121, so the counter 1 of each stage is
The contents of 20 are transferred all at once from the upper stage to the lower stage. At this point, the contents N1 to N6 of the counters 120 in all stages are zero. Further, only the first and third bit read signals 112 of the symbol string storage means 110 become "1". Therefore, when the subsequent pulse signal of the clock signal 121 is applied, the first and third stage counters 12
Only the contents N1 and N3 of 0 are incremented from 0 to 1.

Now the first symbol “M” of the symbol string to be matched
Verification processing is performed on the

Similarly, when the next symbol "E" is input, only the content N2 of the second stage counter is incremented from 1 to 2. In this way, matching processing is performed for all symbol strings. The contents of the final stage counter 120 at each time (in this column, N
6) indicates the number of symbols that match each symbol in the symbol string input before that time. In FIG. 3a, the value of N6 of 6 at time T ₆ indicates that the symbol string is matched with the symbol string input before that time, that is, from T ₁ to _{T 6} .

Therefore, if the number of symbols in the verification symbol string is M (in the example shown in the figure, M = 6), the value of N6 will be M if the same symbol string is input, and M if only one symbol differs. -1. That is, the contents of the counter 120 at the final stage indicate the degree of similarity between the input symbol string and the verification symbol string. The adder 120 adds the contents of the final stage counter 120 and the contents of the register 130 that stores the contents one time before, and transmits the result to the outside as a similarity output 125.

In Figure 3b, some symbols “O” are replaced by other symbols “X”.
The contents of the counter 120 in each stage are shown when an incorrect symbol example is input. The counters 120 in each stage for inputting the first three symbols "M", "E", and "M" operate in the same manner as in FIG. 3a. However, when the next fourth symbol "X" is input, the content N4 of the fourth stage counter 120 is changed to the fourth bit read signal 112 of the symbol string storage means 110.
Since is "O", it is not incremented and maintains the same value of 3. Therefore, after the symbol string "MEMXRY" consisting of six symbols is input, the value of N6 is 5, which is smaller by 1 than in the case of FIG. 3a. That is, it can be recognized that a symbol string that differs from the verification symbol string in only one symbol has been input.

Figure 3c shows some symbols “O” in the collation symbol string.
shows the contents of the counters in each stage when the missing symbol string "MEMRYX" is input. 3 from the beginning
The same operation as in FIG. 3a is performed for inputting symbols. However, since the subsequent symbol string “RYX” is one symbol apart from the collation symbol, the times T ₄ , T ₅ , T ₆
The values of N4, N5, and N6 do not change and remain 3. Also, at time T4 when the symbol “R” is input,
N5 is incremented from 0 to 1. When the next symbol "Y" is input, N6 is incremented from 1 to 2. As a result, the maximum value of the content N6 of the final stage counter 120 is 3, and by simply monitoring N6, it is recognized that the input symbol string is a symbol string obtained by subtracting one symbol from the verification symbol string. Can not. However, adder 140
Since the output N is 5, it can be recognized that the symbol string input from time T ₁ to T ₆ contains five symbols that match the verification symbol string. Therefore, even for a symbol string in which some symbols are missing, the adder 140
Verification is possible by monitoring the output N of . The output N of the adder 140 is transmitted to the outside as a similarity output 125.

FIG. 3d shows the contents of the counter 120 in each stage when a symbol string "MEMXORY" including an extra symbol "X" is input. The same operation as in FIG. 3a is performed for inputting the first three symbols. However, since the fourth and subsequent symbol strings contain an extra symbol "X", they are offset by one symbol from the collation symbol string. Therefore, the values of N ₄ , N ₅ , and N ₆ at each of times T ₄ , T ₅ , and T ₆ are not incremented and remain at 3. However, the time T ₅ shifted by one time,
The values of N ₄ , N ₅ , and N ₆ in each of T ₆ and T ₇ are incremented from 0 to 3. Therefore, by simply monitoring _N6 , it is not possible to recognize that the input symbol string is a symbol string obtained by adding one extra symbol to the verification symbol string. However, since the value of the output N of the adder 140 becomes 6 at time _T7 , it can be recognized that the input symbol strings have a high degree of similarity.

Generally, if the symbol string length of the verification symbol string is n, the content Nn of the last stage counter 120 at time Ti
indicates the number of symbols in which the symbol string input from time Ti-n+1 to time Ti matches the verification symbol string. The output N of the adder 140 at time Ti, that is, the similarity output 125, is the output of the final stage counter 12.
It shows the sum of the contents at time Ti of 0 and one time before.
That is, the similarity output 125 indicates the sum of the number of symbols in which the input symbol string and the symbol string obtained by shifting the input symbol string by one symbol match the matching symbol string. Therefore, symbol strings with some symbols missing and symbol strings with extra symbols added can also be compared by monitoring the similarity output 125.

As mentioned above, the symbol string matching device shown in Figure 1 can extract not only symbol strings that completely match the verification symbol string, but also symbol strings in which any number of symbols are incorrect, making it flexible. It can be said that it is a high quality symbol string matching device.

Generally, when integrating symbol strings, it is easier to output the number of symbols that are different from the matching symbol string than the number of symbols that match the matching symbol string. When counting the number of matching symbols as shown in Figure 1, the counter 1
20 is from 0 to M, where M is the number of symbols in the matching symbol string.
The number of bits that can be counted up to log ₂ (M+1) is required. However, if we count the number of different symbols, assuming that the allowable discrepancy rate is 5%,
Since the counter 120 only needs to be able to count about 5% of M, the number of bits can be reduced.

A symbol string matching device that makes this possible can be realized by slightly modifying the symbol string matching device shown in FIG.

For example, read signal 1 of symbol string storage means 110
12 is "O", the counter 120 is incremented or decremented (the value is decreased by 1). Alternatively, the contents of the symbol string storage means 110 may be inverted and the counter 120 may be increased or decreased when the read signal 112 is "1". In this case, if the initial value of the counter 120 is to be incremented by zero, if it is to be decremented, it is necessary to prohibit the increment or decrement operation beyond the maximum countable value. This can be easily done by detecting that all bits of the counter 120 are 1 using a NAND gate circuit, or that all bits are 0 using a NOR gate circuit, and masking the read signal 212 of the symbol string storage means 110 with the detected output. realizable. However, if a counter having a built-in circuit for detecting the maximum value or minimum value is used as the counter 120, a NAND gate circuit or a NOR gate circuit is not necessary.

Further, it is also possible to replace the counter 120 with a shift register capable of parallel input. In this case, the transfer signal 122 controls the parallel transfer to the next stage shift register, and the read signal 112 controls the left shift or right shift of the contents. Data that differs only in the most significant bit or the least significant bit is supplied to the data input of the first stage shift register. Such a shift register has a Texas
74LS299 sold by Instrument Company
integrated circuits are available. If a shift register is used instead of the counter 120, when the number of symbols different from the collation symbol string is counted, the contents of the shift register will be automatically set to zero if the number of symbols different from the number of bits in the shift register is input. Because it is done,
Easier to control.

Furthermore, the counter 120 can be easily replaced not only with a shift register but also with other logical operation means.

Further, in the above description, a symbol string matching device that can tolerate the omission or addition of one symbol has been described, but it can be expanded to allow the omission or addition of a plurality of symbols. This is possible by using a plurality of stages of registers connected in series as the register 130, and by having the adder 140 add the contents of each register.

FIG. 4 is also an explanatory diagram of an embodiment according to the present invention.
This symbol string matching device extracts only the symbol strings that have a high degree of similarity to the matching symbol string from among the symbol strings to be matched, and is similar to the symbol string matching device 40 in FIG.
0 to comparator 410 and level setting register 4
20 have been added.

Before starting the matching operation, the allowable similarity of the symbol string to be extracted is set in the level setting register 420. This is a level signal 42 indicating the allowed similarity.
1 and a register set signal 422 to the level setting register 420.

The comparator 410 receives the similarity output 125 and the contents of the level setting register 420 as inputs A and B, respectively.
and compare the two. Then, the AZB output indicating whether the former is greater or equal is compared with the output signal 41
It is transmitted to the outside as 1. Symbol string symbol storage means 1
If (M-1) is set in the level setting register 420 for the number M of symbols in the verification symbol string stored in 10, the symbol string input from the symbol string input terminal 111 and the verification symbol string become (M-1). 1) Comparator 410 produces a match output 411 if more than one symbol matches. Therefore, the verification output 41
By monitoring 1, only symbol strings showing high similarity to the matching symbol string can be extracted.

FIG. 5 is also an explanatory diagram of an embodiment according to the present invention.

This symbol string matching device collates multiple matching symbol strings in parallel and outputs matching codes indicating matching matching symbol strings.The symbol string matching unit corresponding to the symbol string matching device shown in Fig. 4 500, an encoder 520 that inputs each verification output 411 output from each symbol string verification unit 500, and a decoder 530 that supplies a register set signal 422 to each symbol string verification unit 500. It consists of

The symbol code input from the symbol string input terminal 111, the clock signal 121, the transfer signal 122, and the level signal 421 indicating the allowable similarity are commonly supplied to each symbol string matching unit 500.

To set the allowable similarity to the symbol string matching unit 500, supply the basic register set signal 532 together with the unit selection signal 531 to the decoder 530,
This is done by supplying the level signal 421 to the symbol string matching section 510. At this time, decoder 5
30 is a register set signal 422 that is sent only to the symbol string matching unit 500 for which the allowable similarity is to be set.
Apply.

When the symbol codes constituting the symbol string to be matched are inputted sequentially from the symbol string input terminal 111, they are compared in parallel with each symbol string to be verified registered in each symbol string matching unit 500, and the code is compared in parallel with each symbol string to be matched registered in each symbol string matching unit 500. A matching output 411 is generated from a matching string matching unit 500 that stores matching symbol strings indicating similarity. The encoder 520 receives and encodes the verification output 411, and generates a valid signal 522 of "0" indicating that it matches the classification code 521 of the input symbol string. Which verification output 411
If both indicate a mismatch, the encoder generates a valid signal 522 of "1" indicating a mismatch.

Therefore, by monitoring the valid signal 522 and the classification code 521, the input symbol string can be classified. Furthermore, the encoder 520 and decoder 530 reduce the number of input/output terminals, making it easy to implement the symbol string matching device into an LSI.

(Effects of the Invention) As described above, since the symbol string matching device of the present invention enables matching based on similarity, it also makes it possible to match symbol strings in which some symbols are incorrect. English words, especially nouns, often have different final letters depending on whether they are singular or plural. For example, “memory” becomes “memories” in plural. In this case, if you use the basic “memory” as a collation symbol string and set the allowable similarity to allow a single character error,
“Memories” can also be extracted. It also enables matching of symbol strings with some symbols missing or symbol strings with extra symbols added. In general, it is not possible to determine in advance where in the symbol string the missing part of a symbol or the addition of an extra symbol will occur or how the symbol will be missing or added. Therefore, conventional symbol string matching must be programmed to accommodate all possible symbol string changes. However, in the symbol string matching method and symbol string matching device of the present invention, this problem can be easily dealt with by setting an allowable degree of similarity. That is, the symbol string matching device and its method of the present invention enable flexible symbol string matching.

It also reduces the number of input/output terminals, making it easier to integrate into LSI, leading to lower prices.

Furthermore, if current semiconductor technology of 256 kilobit RAM is used, 128 verification symbol strings consisting of 8 symbols of 8-bit code can be stored on one chip, and they can be verified in parallel.

The ability to classify a symbol string consisting of 256 kinds of symbols into 128 classes in one step means that up to 128 keywords (symbol string ) can be extracted all at once. In the past, it was difficult to test multiple keywords at the same time, so the above chip has a great impact.

This symbol string identification device is also useful for classifying feature sequences in systems that perform pattern recognition, such as OCR devices and speech recognition devices. Converting this symbol string identification device into a single-chip LSI will also be useful as a dictionary necessary for language translation. Normally, RAM is connected to this chip,
By storing word translations corresponding to the classification codes of each symbol string, translations of up to 128 words per chip can be immediately obtained upon completion of symbol string input. A normal RAM connected to a symbol string identification chip can store various types of information in accordance with the classification code of each symbol, and thereby various symbol string information processing functions can be achieved. Ru. For example, if the part-of-speech code of a word, the number of occurrences of a symbol string, and processing instructions for a symbol string sentence are stored in correspondence with the classification code of the symbol string, it becomes easier to collect and organize knowledge information.

The processing speed of this symbol string extraction device is such that the cycle time Tc of the semiconductor RAM used in the symbol storage means 210, 410 approximately corresponds to the processing time of one symbol. If Tc is 100ms, the text of 10 ⁹ symbol strings can be matched with 10 ³ symbol strings.
It can be done in 10 seconds. Since matching using current software requires about 10 hours, the symbol string matching device of the present invention significantly shortens the matching time.

In summary, according to the present invention, the drawbacks of long processing time and lack of flexibility due to conventional symbol string classification using a combination of a microcomputer and software can be easily solved. Furthermore, considering that the symbol string identification device of the present invention can be easily integrated into a single LSI chip, such an LSI can be used for extracting keywords from original text files and for language translation, so it can be used to extract feature sequences for electronic words and pattern recognition systems. It becomes an indispensable functional element in classification.

[Brief explanation of the drawing]

FIG. 1 is an explanatory diagram of an embodiment of the symbol string matching device according to the present invention, FIG. 2 is a timing diagram of clock signals and transfer signals, FIG. 3 is an explanatory diagram of the operation of the symbol string matching device, FIGS. FIG. 5 is an explanatory diagram of another embodiment of the present invention, and FIG. 6 is an explanatory diagram of symbol string matching. 110... Symbol string storage means, 120... Counter, 123... First calculation means, 124... Temporary storage means, 130... Register, 140... Adder, 410... Comparator, 420... Level setting Register, 500...Symbol string matching unit,
510...Symbol string matching unit, 520...Encoder, 530...Decoder.

Claims (1)

[Scope of Claims] 1. Symbol string storage means that takes a symbol code as an address input and stores a collation symbol string, a first arithmetic means connected to each of the output lines, and a first arithmetic means that interconnects the plurality of arithmetic means. 1 temporary storage means and a specific 1st temporary storage means;
A symbol string collation device comprising: second temporary storage means connected to the output of the temporary storage means; and second calculation means connected to the second temporary storage means. 2. The symbol string matching device according to claim 1, wherein the first calculation means and the first temporary storage means are each a counter or a shift register. 3. Symbol string storage means that uses symbol codes as address inputs and stores collation symbol strings, first calculation means connected to each of the output lines, and first temporary storage means that interconnects the plurality of calculation means. , specific first
a second temporary storage means connected to the output of the temporary storage means; a second calculation means connected to the second temporary storage means; a register for storing an externally given allowable similarity; 1. A signal string matching device comprising: a comparator that compares the output of the second calculation means and outputs a matching result. 4. The symbol string matching device according to claim 3, wherein the first calculation means and the first temporary storage means are each a counter or a shift register. 5. Symbol string storage means that uses symbol codes as address inputs and stores collation symbol strings, first calculation means connected to each of the output lines, and first temporary storage means that interconnects the plurality of calculation means. , specific first
a second temporary storage means connected to the output of the temporary storage means; a second calculation means connected to the second temporary storage means; a register for storing an externally given allowable similarity; 1. A symbol string matching device comprising: a comparator that compares the outputs of the two arithmetic means and outputs a matching result; an encoder connected to the comparator; and a decoder connected to the register. 6. The symbol string matching device according to claim 5, wherein the first calculation means and the first temporary storage means are each a counter or a shift register. 7. Store each symbol in the symbol string in each column of the symbol string storage means so that only the address designated by the symbol has a different value, input the symbol to the decoder of the symbol string storage means when collating the symbol string, and The contents of multiple columns of the address indicated by the input symbol of the symbol string storage means are read in parallel, and the contents of the counters of each connected stage are increased and the contents of the next stage are increased based on the read information of each column of the previous symbol string storage means. The similarity between the contents of the symbol string storage means and the sequentially input symbol string is determined by controlling the transfer to the counter of the symbol string and adding the two contents of the final stage counter that are different by one time. A control method for a symbol string matching device.