JPH0752451B2 - Information retrieval device - Google Patents

Description

Description: TECHNICAL FIELD The present invention relates to an information search device for searching information by hardware, and particularly, information search capable of downsizing hardware and improving search speed. Regarding the device.

[Prior art]

Conventionally, in an optical disk file device or the like, when searching a registered image or searching character string data such as a sentence or the like that includes a partial character string as a key, a search is conventionally performed by software. However, this technique has a problem that when the number of images to be registered or the character string data increases, the search time increases and the waiting time of the user also increases.

As a countermeasure against this problem, a hardware search technique is drawing attention, and a finite automaton search technique is generally known. For example, when performing a character search by a finite state automaton, the character string search device uses a random access memory (hereinafter abbreviated as RAM) storing a state transition table.
A partial character string that is the key of the search item is input in advance to this RAM, the character string data sent from the storage device is collated with the partial character string that is the key, and a match signal is output when both match. Is output.

The state transition of this finite automaton is, as shown in FIG.
For example, when searching for a three-character key called HIT, if the input character from the storage device is H, the state of the automaton transits from the initial state “0” to the state “1”. Note that the status is "0"
If the input character at is other than H, the state continues to be "0".

In the state "1", if the next input character is T, the state transitions to the state "2", if it is H, the transition does not occur, and if it is another input character, the state transitions to the state "0".

In the state "2", if the next input character is T, the state transitions to the state "3", if it is H, the state transitions to the state "1", and if it is another input character, the state transitions to the state "0". In this way, when the state transition destination differs depending on the input character and the state transitions to state "3", HIT
It means that the key is detected. However, in this technique, most of the data stored in the state transition table of the RAM is in the state "0", so there is a problem that the memory utilization efficiency is low. Therefore, a proposal has been made to reduce the size of the state transition table.

For example, in the technique disclosed in Japanese Patent Laid-Open No. 60-105040, a pattern in which a character code is divided into powers of 2 is used as an entry in the state transition table, and the size of the state transition table is reduced. A finite state automaton searches for a certain search item (attribute) while performing a state transition.

However, with this technology, the key character string is
In a small system of about several tens of bytes, the information to be searched is divided into multiple items, and when the search key is specified for each item, that is, when there are multiple attributes, attribute processing is continued. There is no mention of the technique to be carried out.

[Problems to be solved by the invention]

As described above, in the technology having a finite automaton for each attribute, when there are a plurality of attributes, it is necessary to have as many finite automatons as the number of the attributes in parallel, which increases the amount of hardware and configures a search device. It was difficult and there was a problem with the search speed.

An object of the present invention is to improve such problems, and in a small-scale system in which a key character string is a few bytes to a few tens of bytes, it is possible to miniaturize hardware and improve search speed. To provide a device.

[Means for solving problems]

In order to achieve the above object, the information search device of the present invention is
(1) In an information search device that performs a search by a finite state automaton using a state transition table, a memory for storing a plurality of state transition tables for each set and input search item at different addresses and a state transition table are used. Address point means for detecting the end of the search for each search item by counting the number of input characters, and setting the start address of the state transition table corresponding to the next search item after the end of the search for one search item And is provided.

(2) In the information search device according to (1), the address point means includes an attribute length memory that stores a byte length of each search item and an initial value memory that stores a start address of each state transition table. , A byte length counter that counts the byte length of the search item stored in the attribute length memory for each input of each character of the search item, and the start address of the first state transition table from the initial value memory when the search starts And read
An attribute number counter that sequentially counts the start address of each state transition table corresponding to each search item in the initial value memory by counting the byte length count end of each inspection item by the byte length counter, and this attribute It is characterized by comprising a data selector for setting the start address of the state transition table designated by the number counter in the state transition memory.

[Action]

In the present invention, the state transition in one finite automan
The RAM area is divided for each attribute and used.

When the search for the attribute is started, the initial address of the state transition RAM corresponding to the attribute is read from the initial value RAM by the data selector and stored in the address latch.

Next, when the character input for each byte is started, the finite state automaton repeats the state transition from the initial address for each input character until the characters for the number of bytes indicating the attribute length being searched are input.

Thus, when the character input for the attribute length is completed, the determination result for this attribute is output to the data latch.

By repeating these operations, continuous attribute processing can be performed.

〔Example〕

 An embodiment of the present invention will be described below with reference to the drawings.

FIG. 1 is a block diagram of an information retrieval device in one embodiment of the present invention, FIG. 2 is a timing chart of various signals in one embodiment of the present invention, and FIG. 3 is an information retrieval device in one embodiment of the present invention. 3 is an operation flowchart of FIG.

The information retrieval apparatus of this embodiment, as shown in FIG.
A RAM 3, a data latch 4, a determination circuit 5, a selector 6, an attribute number counter (CNT1) 7, an initial value RAM 8, an attribute length RAM 9, an attribute length counter (CNT2) 10, an address latch 13, and an inverter 14 are provided. Further, the address latch 13 and the data latch 4 are flip-flops (FFs), and these FFs and the state transition RAM 3 form one finite automaton.

In this finite state automaton, the state transition RAM 3 stores a state transition table and is divided into a plurality of attributes. Further, when the input character 11 indicating one character of 8-bit data and the clock signal CLK22 which gives the input timing of the input character 11 are input to the address latch 13, the address latch 13 outputs the address on the state transition RAM 3. Then, the state transition RAM 3 transits the state for each input character according to this address, and sets the data corresponding to the address in the data latch 4. Further, when the character input for the attribute length of the attribute to be searched is completed, the data selector 6 reads the initial address on the state transition RAM 3 corresponding to the next attribute from the initial value RAM 8 and sets it in the address latch 13.

The attribute number counter 7 indicates the number of the attribute currently being processed on the state transition RAM 3, and the attribute length counter 10 sets the byte length of the attribute to be processed at the start of the search. The count of the remaining bytes of the attribute is sequentially counted down, and the break of the attribute is detected.

Further, the initial value RAM8 stores the start address of each attribute divided and stored in the state transition RAM3, and the attribute length RAM9 stores the lengths of those attributes. In this embodiment, the initial value and the attribute length are stored in the same RAM.

In this embodiment, before the information retrieval, as shown in FIGS. 2 and 3, the reset signal RST21 externally applied to the attribute number counter 7 is “0” (30).
0). At this time, the counts of the attribute number counter 7 and the attribute length counter 10 are cleared, that is, "0". Therefore, the CNT1 output 24 has the content "0", and the output of the zero output terminal of the attribute length counter 10, that is, the Z output 23 is "1".

When the operator sets the attribute to search (30
1), the reset signal RST21 externally applied to the attribute number counter 7 is released and becomes "1" (302).
At this time, the initial value RAM8 and the attribute length RAM9 are
The data corresponding to the attribute to be searched first, that is, the initial address and the attribute length are sent to the data selector 6.

Next, the CLK22 is synchronized with the input character 11 and the address latch 13
Data selector 6, the data selector 6 selects the selection control signal,
That is, the Z output 23 of the attribute length counter 10 is "1".
Therefore, the input data of the A terminal of the data selector 6,
That is, the initial value data is output to the address latch 13, and this initial value data is latched in the address latch 13 (30
Four). At the same time, since the input to the initial value load terminal LD of the attribute length counter 10, that is, the Z output 23 of the attribute length counter 10, is “1”, the first attribute length is latched in the attribute length counter 10 (304 ).

In this way, when the initial setting is performed, every time a character is input (305), the finite state automaton transits the state for each character (306). According to this character input, for example, when the attribute length is 4, the attribute length counter
10 counts down from 3 to 0 (307), CNT2
When the output 25 becomes "0" (308), the Z output 23 of the attribute length counter 10 becomes "1". At this time, the output of the data latch 4 is sent to the determination circuit 5 by using the Z output 23 as a synchronization signal (309), and the determination circuit 5 outputs the determination result (310).
Finish the search.

When the search is continued (311), the attribute number counter 7 (CMT1) is incremented from 1 to 2 and points to the data of the next attribute (312). According to this point, the initial value and the attribute length corresponding to the next attribute are read (303), set in the address latch 13 and the attribute length counter 10 (304), respectively, and the state transition RAM 3 is newly updated. The search for the next attribute is started from the latched address (305, 306).

By repeating these sequences, each attribute is searched.

In this way, by dividing the address of the state transition RAM 3 for each attribute, in an information retrieval device whose key character string is several bytes to several tens of bytes, one finite automaton is used to retrieve a plurality of attributes. Processing can be performed.

〔The invention's effect〕

According to the present invention, in an information retrieval device using a finite automaton in which a character string serving as a key is several bytes to several tens of bytes, the hardware can be downsized and the retrieval speed can be improved.

[Brief description of drawings]

FIG. 1 is a block diagram of an information retrieval apparatus in one embodiment of the present invention, FIG. 2 is a timing chart of various signals in one embodiment of the present invention, and FIG. 3 is a diagram of an information retrieval apparatus in one embodiment of the present invention. An operation flowchart, FIG. 4 is an explanatory diagram of state transition of a finite state automaton. 3: State transition RAM, 4: Data latch, 5: Judgment circuit, 6: Data selector, 7: Attribute number counter (CNT1), 8: Initial value RAM, 9: Attribute length RAM, 10: Attribute length counter (CNT2) , 11: Input character, 13: Address latch, 14: Inverter, 21: Reset signal (RST), 22: Clock signal (C
LK), 23: Output from the Z terminal of the attribute length counter (Z
Output), 24: Attribute number counter output (CNT1 output), 25: Attribute length counter output (CNT2 output).

Claims (2)

[Claims] 1. An information search apparatus for performing a search by a finite state automaton using a state transition table, a memory for storing a plurality of the state transition tables for each set and input search item at different addresses, and each of the states. The end of the search for each search item using the transition table is detected by counting the number of input characters, and after the search for one search item is completed, the start address of the state transition table corresponding to the next search item is set. An information retrieving apparatus, characterized in that it is provided with address point means for performing. 2. The information search device according to claim 1, wherein the address point means stores an attribute length memory for storing a byte length of each search item and a start address of each state transition table. An initial value memory, a byte length counter for counting the byte length of the search item stored in the attribute length memory for each input of each character of the search item, and the initial value memory at the start of the search, The start address of the first state transition table is read, the count end of the byte length of each search item by the byte length counter is counted, and the start address of each state transition table corresponding to each search item is set to the initial value. The attribute number counter that is sequentially specified for the memory, and the attribute number counter that is specified The starting address of the state transition table, the information retrieval apparatus characterized by comprising a data selector to be set to the state transition memory.