JPS6128133A - Symbol string collating device - Google Patents

Abstract

PURPOSE:To extract flexibly an optional symbol string among non-structure symbol strings in a short time by inputting sequentially a long symbol string, checking the presence of the registered collation symbol string and transmitting it externaly. CONSTITUTION:The device is provided with a means 210 storing a collated symbol string in a bit pattern, an AND gate circuit being a transmission means 230 connected to each output, a register array 240 connected with the means 230 between registers 245, a register array 250 connected in series between registers 255, a means 260 outputting selectively an output of the array 240 selected by the content of the register 255 and a means 270 transmitting each output of the arrays 240, 250 selectively to the next array 240. Only when a symbol string ''ABABB'' is inputted to an address input 211, the content passes through a register of each stage of the array 240 and the content of a specific register is transmitted from a collated output terminal 280 via the means 270 and the arrays 240 are used to the collated symbol string comprising >7 by connecting them depending on the content of the array 250.

Description

Detailed Description of the Invention (Industrial Application Field) The present invention relates to a component of an information processing system, and more specifically, a symbol string matching device for extracting a specific symbol string from a long symbol string. and its matching method.

(Prior art and its problems) The above-mentioned symbol string matching device is used to extract keywords from the original text file of sentences created with a Google processor, to support language translation, and to provide abbreviations of correspondence. It is used for deciphering information, constructing unstructured databases using figures, images, texts, etc., and is indispensable for the formation of intelligent information processing systems.

Conventional symbol string matching requires sequential processing using general-purpose computer software, requires an enormous amount of processing time, and is limited to small-scale applications. 1, the matching target was limited to structured symbol strings separated by words. - For example, when checking where a button consisting of m symbol strings is located in a text consisting of n symbol strings, m (n m+1) matching processes are required. m = 10 stored on magnetic disks, optical disks, etc.
Extracting a sentence with n=103 character strings from a text with 9 character strings requires 1012 matching processes. Therefore, it is impractical to search using a large amount of source information such as text, image, figure, voice, etc., so the search is limited to searching by adding keywords to the source information in advance or searching for data structured in table format. It had been. However, it still has the disadvantage that the processing time is too long for flexible symbol string matching that allows variations in the constituent elements of symbol strings.

More specifically, the problems of the conventional symbol string matching device and its matching method will be explained.

FIG. 1 shows 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 is needed from among such texts, a word 1 is required that can be directly searched by a word indicating the desired content.

For example, if the text in Figure 1 is
-bble % symbol string (to know if the paper contains it)
It is necessary to search to see if there is a part that matches the symbol strings such as ries and bubble. Comparing such symbol strings with text would take a very long time if conventional computers and software were used.

A typical A-size English sentence is about 3,000 characters long, including the spaces between words. On the other hand, the length of the symbol string for comparison and matching is also bubble in the case of memory.
In the case of e, there are also 6 characters. Matching between 6-character and 3000-character strings generally requires a number of character comparisons on the order of the product. Even if the character comparison time in the microprocessor is 1 μm1eC, it takes 18 msec to search each symbol string.

In reality, the number of characters in the text to be searched is 10 degrees, and the number of characters in the symbol string to be matched may exceed 100. The number of symbol strings to be matched is not just one,
There are dozens of them. In that case, the verification time spans several hundreds of hours. Therefore, such a comparison is practically impossible,
Actual selection is limited to manually extracting keywords in advance and matching the extracted keywords.

[Purpose of the invention]

An object of the present invention is to easily solve the drawbacks of the conventional symbol string matching device and its method, and to convert text 2 images into a flexible system by quickly converting arbitrary symbol strings from unstructured symbol strings such as figures. An object of the present invention is to provide a symbol string matching device capable of extraction and a matching method thereof.

Another object of the present invention is to provide a low-cost symbol string matching device that can arbitrarily set the length of a matching symbol string.

Another object of the present invention is to provide an L S with a small number of output terminals.
The object of the present invention is to provide a symbol string matching device that can be easily converted into an I/O.

(Structure of the Invention) Therefore, according to the present invention, a symbol string storage means for storing a plurality of collation symbol strings in a bit pattern associated with each symbol, a first transmission means connected to each of the outputs, and each adjacent A plurality of first register arrays in which the registers are connected by a first transmission means, and I! The second register array in which adjacent registers are connected in series and the contents of the registers in each stage of the second register array selectively output the output of the first register array. and a second transmission means for selectively transmitting the output of the first register array and the output of the register in the second register array to the next first register array. A symbol string matching device fi is obtained in which an encoder or a shift register is added to the device and the output means of the device.

(Example) FIG. 2 is an explanatory diagram of the first embodiment of the present invention.

This symbol string verification device sequentially inputs text that is a long symbol string, checks whether the text contains a registered verification symbol string, and transmits the verification symbol string to the outside. A symbol string storage means 210 that stores the symbol string with a button, an AND gate circuit serving as a first transmission means 230 connected to each output, and a plurality of first register array 240 and an adjacent second register 255
a second register array 250 connected in series;
an output means 260 for selectively outputting the output of the first register array 240 selected according to the contents of each register 255 of the second register array 250; and a second transmission means 270 for selectively transmitting the output of the register 255 in the array 250 to the next first register array 240.

In the example shown in the figure, the first register array 240 in the upper stage includes six registers 245, and the first register array 240 in the lower stage includes five first registers 245.
Contains 5. 6. The first register arrays 240 are connected by an OR gate circuit 270 and an AND gate circuit 230. When using a collation symbol string with six or fewer symbols, "" is written in the first second register 255 of the second register.
In this case, fP, the second transmission means 270 connected to the first second register 255 stores the contents of the second register 255, ie @1'', without passing the output of the first register array 240. is supplied to the AND gate circuit. Therefore, the input and output of the six first register arrays 240 located in the upper and lower stages are separated. Also, the first
The register array 240 is outputted to the outside as a verification output via the output means 260.

On the other hand, for collation symbol strings with seven or more symbols,
f of the first and second stages of the second register array 250
"0" and "1" are respectively stored in the 4fJ2 register 255. In this case, the second transmission means 270 passes the output of the first register array 240 in the upper stage and supplies it to the AND gate circuit 230. Therefore, the upper and lower first register arrays 240 are connected. In addition, the output means 26
0 passes the output of the first register array 240 in the lower stage as a verification output. For a collation symbol string consisting of seven or more symbols, such as jin, the first register array 2
40 are connected and used. This concatenation can be controlled by the contents of second register array 250.

Each symbol of the collation symbol string is stored in each bit of the symbol storage means 210 in a bit pattern associated with the symbol. In this bit pattern, only the address selected by the symbol is "1". In the example shown in FIG. 2, the 11-bit symbol storage means 210 stores an example of collation symbols consisting of five symbols "A, BABB". That is, 1'' is stored only in the 1f3th bit of the address designated by the symbol "A" and the 2j4+5th bit of the address designated by the symbol "B", and 0" is stored in the other bits. However, the symbol string storage means 2] 6th of 0
The bit stores 1" in all addresses.

Therefore, the AND gate circuit 230 connected thereto is the fifth
The content Q5 of the sixth register 245 is supplied as is to the sixth register 245.

Further, 1'' is stored in the first second register of the second register array 250, and outputted to the outside via the output Q 5 lx output means 270 of the first register array 240 in the upper stage.

As explained earlier, the address of the symbol storage means 210 corresponds to the type of symbol, and the 1.3rd bit is read or output as 1 only when the symbol "A" is input. 2nd ν4
, 5 bits read output becomes "1" only when "B" is input. Also, the read output of the 6th bit is always “
1” is generated.

The symbols constituting the text to be compared are sequentially applied to the address input 211 of the symbol storage means 210, and the contents of the address corresponding to the symbol are read out. The read output of the first bit of the symbol storage means 210 is output as the first internal signal.
The signal is supplied to the first stage register 245 of the register array 240. The other read output is supplied to an internal signal transmission means 230 composed of an AND gate circuit, and determines whether or not to transmit the internal signal accumulated in the register 245 at each stage in the register array 240 to the register 245 at the next stage. control. Registers 245 at each stage in this register array 240
is the same clock signal 24 applied for each symbol input.
1 to capture internal signals. The internal signal is a symbol string "ABABB" in the address 211 of the symbol storage means 210.
It passes through the registers at each stage of the register array 240 only when the amount is input, and the contents of the specific register are outputted from the verification output terminal 280 via the output means 270.

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

This is stored in the symbol storage means 210 as shown in FIG.
ABB" verification symbol string is stored, and its address
The first register array 240 when the symbol string of the text "ABABAAABBABABBAB" is input to 11
The outputs Q1 to Q6 of each stage are shown. The output Q1 of the first stage of the first register array 240 becomes 1 only when the symbol "A" is input, and the output Q2 of the second stage becomes 1 only when Ql is 1 and the symbol "B" is input. In this way, Q6 output to the collation output terminal 280 becomes 1'' when a symbol string equal to the collation symbol ABABB'' appears in the text.

In this example, since Q6 becomes "1" at time T14, it can be seen that the underlined symbol string input one time before that is equal to the matching string.

In this example, only the collation symbol string "ABABB" stored in the symbol storage means 210 is detected, but even if part of the symbol string in the text is duplicated or missing, it can be detected if there is no confusion. is also possible.

For example, if the head of the collation symbol string can be the symbol "Z", by storing 1" at the address specified by the symbol 2 at the 0th pit of the symbol storage means 210, the ABA
Both symbol strings “B B” and “ZBABB” can be extracted.

This symbol string matching device also makes it possible to match symbol strings that do not have delimiters such as spaces for each symbol string that has a meaning such as a word. It is also possible to match different symbol strings that have similar meanings. English words, especially nouns V1: The final letter often differs between singular and numeral forms. For example, ' rlemory
``me-mories'' becomes plural. In this case, the collation symbol string is “memory” and “mem”.
By storing a symbol string with both the symbols "y" and "i" added to the end of "ori", that is, S"memory,
Both symbol strings "memory" and "mem-ories" can be matched.

This symbol string matching device can be easily integrated into an LSI, resulting in a reduction in cost, and since it can match one symbol in approximately the cycle time of a symbol string storage means, such as an IC memory, it can produce high-speed symbol strings. Enables matching. Furthermore, it is possible to handle collation symbol strings of various symbol string lengths.

Still, the number of output terminals that generate verification outputs is reduced, making it easier to implement into an LSI.

FIG. 4 is an explanatory diagram of another embodiment of the symbol string matching device according to the present invention. This symbol string matching device can match multiple matching symbol strings of arbitrary symbol string lengths in parallel. To make this possible, an OR gate circuit 470 and a first AND gate are provided, which correspond to the second transmission means 270, first transmission means 230, and output means 260 used in the symbol string storage device of FIG. The circuit 430, the second AND gate circuit 460, and further the symbol string storage means 210 and the first register array 44.
0, a second register array 450, and an encoder 490 added to an AND gate circuit 460 as an output means.

The first register array 440 includes M registers, each including N registers 445 . Register array 4 for each section
Each register 445 in 40 is connected to the first AND gate circuit 4
30 and register array 440 of each node 1
are the OR gate circuit 470 and the first AND gate circuit 43
Connected via 0. Second register array 450 includes M registers corresponding to the number of first register array 440, which are connected in series.

The collation symbol string is stored in the symbol string storage means 210 with a bit button associated with the symbol as in FIG. 2. That is,
By writing 1'' only in the address of the symbol string storage means 210 indicated by the symbol of the collation symbol string, that symbol is stored.The number of symbols of the collation symbol string is the number N of the registers 445 of the first register array 440. If the size is very small, M collation symbol strings can be stored in the symbol string storage means 210 corresponding to the first register array 440. At this time, each register 455 of the second register array 450 can store M collation symbol strings. "1" is stored as a marker that separates the verification symbol strings. This marker can be written in series by applying the marker input signal 451 and the marker write clock signal 452 to the second register array 450. It is necessary to store "1" at all addresses in the symbol string storage means 2100 pits corresponding to the difference between the number of symbols in the symbol string and N.

For example, register 445 of first register array 440
Let the number N of zeros be 8, and add a 6-character collation symbol string "me"
When storing “Mory”, the first
Store "1" in all addresses of the 2nd and 2nd bits, and store m"9"'e in the 3rd to 8th bits respectively.
"1"wO"tsu6r"? 1” is stored only in the address corresponding to the symbol “y”. When stored in this way, the first and second stage registers 445 in the first register array 440 have symbol string input terminals. “1” is always held regardless of the symbol input from 221.
・Ru. As a result, the internal signal "■" is sent to the first register array 44 only when the 6-digit string equal to the collation symbol ``memory'' is input from the symbol string input terminal 221.
0 is transmitted to the final stage register 445, and a verification output 480 is generated via the second AND gate circuit 460. In other words, it is possible to match a verification symbol string having a length shorter than the number of stages N of the register 445.

On the other hand: For collation symbol strings whose symbol string length is greater than N,
A collation symbol string is stored across two or more first register arrays 44.0. For this purpose, the register 455 of the second register array 450 corresponding to the link 9 of the first register array 440 stores O'', which means continuous. As a result, "0" is output. A circuit 470 connected to the register 455 of the second register array 450 is connected to the register 455 of the second register array 450.
The contents of the register 445 at the final stage of 40 are converted to the AND gate circuit 4 which leads to the register array 4400 Å of the next plan 1.
30. That is, the two first register arrays 440 are connected in series 1'. register 455 in second register array 450, such as
Depending on the contents of , the register array 440 of each node 1 can be connected in series or separated. That is, the number of stages N of registers 445 in the first register array 440
The register 445 can be deleted in units of .

Thus, depending on the contents of the second register array 450,
The internal signal in the final stage register 445 in any first register array 440 can be guided to the collation output 480, and the plurality of first register arrays 440 can be arbitrarily divided.
Connection is possible. Therefore, a plurality of collation symbol strings having an arbitrary symbol string length can be stored in the symbol string storage means 210, and parallel verification of the collation symbol strings can be performed.

Further, the number of collation output terminals 480 is 1/N of the number M of the first register arrays 440, which is 111 the number of registers 445 in the plurality of first register arrays 440. Since the number of output terminals is small, it is easy to convert into I and S, which lowers the price.

Each matching output 480 is directed to an encoder 490, which generates a classification code 49 for the matched symbol string.

If none of the matching outputs 480 has reached the encoder 490, the encoder 490 sends an indiscernible signal 492
Output. Such an encoder 490 is commercially available under the trade name Priority Encoder. The number of bits of the classification code 491 is N bits when the number of collation outputs 480 is 2N, which reduces the number of output terminals of the symbol string collation device and easily realizes LS'I.

It is also possible to input the signal of the comparison output 480 in parallel to the encoder 490 and use a shift register that outputs the signal in series. In the case of a wire, the number of output terminals is one, which further facilitates LSI implementation.

If the twelfth second AND gate circuit 430, 460 and the OR gate circuit 470 have the functions of a first internal signal transmission means, an internal signal output means, and a second internal signal transmission means, respectively. , it is also possible to replace the gate circuit with another gate circuit.

(Effects of the Invention) As described above, according to the present invention, it is possible to realize a symbol string matching device that easily solves the problem of the conventional symbol string matching requiring too much matching time. It is possible to perform verification that can flexibly deal with errors and changes in some symbols. Furthermore, multiple collation symbol strings with different symbol string lengths can be stored and collated in parallel. Therefore, hardware is used efficiently, resulting in lower costs and shorter collation times.

The symbol string matching device of the present invention is currently 256 kilopits) R
If AM semiconductor technology is used, and the code length of a symbol is 8 bits, the verification symbol string with an average length of 8 symbols will be 128.
can be stored on one chip and compared in parallel.

The ability to classify a symbol string consisting of 256 types of symbols into 128 classes with one chip means that it can classify 128 keywords ( It means that the extraction of the symbol string) can be done all at once. In the past, it was difficult to search multiple keywords at the same time, so the impact of the above chip is significant.

This symbol string identification device is also useful for identifying feature sequences in systems that perform button recognition, such as OCR devices and speech recognition devices. 1-chip LSI of this symbol string identification device
It also serves as a dictionary necessary for language translation. If a normal RAM is connected to this chip and translations of words are stored in correspondence with the classification code of each symbol string, translations of up to 128 words per chip can be obtained immediately upon completion of inputting symbol strings.

The normal RAM connected to the symbol string identification chip can store various types of information corresponding to the top codes of the symbol strings, thereby achieving various symbol string information processing functions. Ru. For example, if the part-of-speech code of a word, the number of occurrences of a symbol string, and a processing command for a symbol string sentence are stored in correspondence with the '4'a4 code of a 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 as the symbol storage means approximately corresponds to the processing time of one symbol. If Tc is 100 ns, matching of 103 symbol strings against Tegis) K of 109 symbol strings can be performed 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, the drawbacks of long processing time and lack of flexibility caused by 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 LS'I can be used for extracting keywords from original text files, electronic dictionaries for language translation, and slam recognition systems. It becomes an indispensable functional element in the classification of feature series.

[Brief explanation of drawings]

FIG. 1 is an explanatory diagram of the symbol string matching problem, FIG. 2 is an explanatory diagram of an embodiment of the symbol string matching device according to the present invention, FIG. 7, and FIG.

Claims (4)

[Claims] (1) Symbol string storage means for storing a plurality of collation symbol strings with bit patterns associated with each symbol, a first transmission means connected to each of the outputs, and a first transmission means that connects mutually adjacent registers. A plurality of connected first register arrays and a second register array in which adjacent registers are connected in series.
a register array, an output means for selectively outputting the output of each first register array according to the contents of the registers in each stage of the second register array, and output means for selectively outputting the output of each first register array and the second register array. a second transmitting means for selectively transmitting the outputs of the registers in the first register array to the next first register array. (2) The symbol string matching device according to claim 1, wherein the first transmission means and the output means are AND gate circuits, and the second transmission means is an OR gate circuit. (3) A symbol string storage means for storing a plurality of collation symbol strings with bit patterns associated with each symbol, a first transmission means connected to each of the outputs, and a first transmission means that communicates between each adjacent register. A plurality of connected first register arrays and a second register array in which adjacent registers are connected in series.
a register array, an output means for selectively outputting the output of each first register array according to the contents of the registers in each stage of the second register array, and output means for selectively outputting the output of each first register array and the second register array. 1. A symbol string collation device comprising: a second transmission means for selectively transmitting the output of a register in the first register array to the next first register array; and an encoder or a shift register added to the output means. (4) The symbol string matching device according to claim 3, wherein the first transmission means and the output means are AND gate circuits, and the second transmission means is an OR gate circuit.