JPS6244829A - Method for extracting pattern - Google Patents

Abstract

PURPOSE:To extract rapidly a pattern by comparing an element of an extracted pattern stored in a register with an element of a data base stored in a memory to store the compared result, cascade-connecting the successively compared and stored results of respective elements and detecting the coincidence of all the elements. CONSTITUTION:In each comparator/register array 10 in plural pattern detecting means mutually cascade-connected in accordance with the length of an extracted pattern, cells 101-10m having n bit width each of which is obtained by combining a comparator with a register are cascade-connected, a read/write signal or the like is decoded by a decoder 111 and supplied to respective cells 101-10n and these cells 101-10n are used as an interface with a CPU. The initial element of the data base is read out from a direct memory and inputted in the array 10, and when the coincidence of the element with the element of the extracted pattern is detected by one of cells 101-10m, the detected result is outputted from the selector 113 and stored. Coincidence of the succeeding element is similarly detected.

Description

DETAILED DESCRIPTION OF THE INVENTION 2. Field of Industrial Application The present invention relates to a pattern extraction method in a data processing device, and particularly to a pattern extraction method that allows a pattern to be extracted to be quickly retrieved from a database.

BACKGROUND OF THE INVENTION Conventionally, data processing for extracting specific patterns from a database has been performed by software. According to this method, to extract one pattern,
The nesting level increases as the pattern length increases, and processing takes a relatively long time. Furthermore, in order to extract a plurality of patterns, processing must also be performed in parallel.

Problems to be Solved by the Invention However, in such conventional pattern extraction methods, it takes a very long time to extract patterns because the extraction is performed by CPU operations that depend on software. Further, in order to extract a plurality of patterns, the only way is to access the database 3, - source multiple times or to access the pattern each time, and it is not possible to perform the extraction operation of the plurality of patterns at the same time. Moreover, in the conventional pattern extraction method as described above, nesting must be performed for the number of patterns in accordance with the number of patterns at the time of pattern extraction. The problem is that the longer the process, the longer it takes to process.

The present invention has been made with attention to such problems, and its purpose is to store extraction patterns in advance in hardware, access the database by direct memory access, and combine this accessed data with the above-mentioned data. It is an object of the present invention to provide a pattern extraction method capable of performing pattern extraction at high speed by comparing preset extraction patterns.

Means for Solving the Problems In order to achieve the above object, the present invention includes a memory holding a database for pattern extraction, and a plurality of pattern detection units each having a register and a comparator for holding extracted patterns, Each element of the extraction pattern is held in a register by the processing device, and each element in the database is read out by direct memory access.
The gist of this method is to sequentially compare an element with one element in a database, connect the matching results in a cascade, and extract patterns from time to time based on all element matches.

To compare the first element of the effect extraction pattern, the first element of the database is read by direct memory access (DMA). The read elements of the database are input in parallel to a plurality of pattern detection means, and each pattern detection means compares one element of the extracted pattern with one element from the database. If the patterns match between both elements, a match signal +t I I+ is written to the corresponding bit position of the register, and if they do not match, it is not written and is re-written by the next DMA.
\-.

The first element of the frequency extraction pattern is compared.

This operation is performed sequentially on database elements to extract patterns. The pattern detection means can be cascaded with each other and can freely correspond to the length of the extraction pattern.

Embodiment FIG. 1 is a diagram showing an example of a system for implementing the pattern extraction method according to the present invention. In this figure, numerals 1 to 3 indicate the basic configuration of the pattern detection means of the pattern extraction device, 4 is a processing device that performs data processing for pattern extraction, that is, a microprocessor, 5 is a DMA control device, and 6 is a memory. Each is shown below. Each basic configuration 1, 2,
3. Microprocessor4. DMA control device5. The memory 6 is connected to a data bus 8 and an address bus 9, respectively, to accept and send out various data, and each of the operating sections is connected to an interconnected signal line 41. The operation is controlled by a signal sent via a control line 42.

Further, each basic configuration 1.2.3 is connected in parallel to the DMA control device 5 through the signal line 6 (base 1.62) so that each of the basic configurations (e.g. 1 and 2) may be configured so that they can operate in relation to each other by cascade connection. In the figure, 71 is a DMA request signal line issued from basic configuration 3, 72 is a DMA request signal line issued from basic configuration 2, and 7 is a DMA request signal line issued from basic configurations 2 and 3 (or including basic configuration 1). This is an AND gate that performs a logical product between the signals and finally outputs the result to the MA request signal line 61.

The pattern extraction basic configuration 1 (the same applies to the basic configuration 2.3) has a configuration as shown in FIG. 2, for example. As is clear from this figure, the basic configuration 1 includes a comparator and register array 1o, a comparator and register array 1o, and a comparator and register array 1o.
control/status register 11.
! :, flip-flop 12 in J-, and gate 1
3,16°18, an inverter 14,15, and an OR gate 17. Comparator and register array 10 includes:
A plurality of cells 101, 102, .
A selector 112 selects a decoder 111 for controlling reading and writing from the U bus to the register and a signal from basic configuration 1 that informs the CPU of the pattern extraction timing.
and a selector 113 for selecting a signal for arbitrary cascade connection between the basic configurations 1, 2 and 3.

FIG. 4 shows the comparator and register cell 101 in FIG.
...10m shows an example of the internal structure. In the figure, 1001 is a register with a bit width of n, 1002 is a bus driver with a bit width of n, 10o3 is a data comparator with a bit width of n, and 1o04 is a data comparator with a bit width of n. A flip-flop 1006 that holds the comparison result in this cell is a gate that combines the comparison result in this cell with the comparison result of the previous cell.

The operation when extracting a pattern in a system having such a configuration will be explained.

First, in the comparator and register cell of FIG.
Write by W. Also, the contents of this register can be
When reading data, data is output to Don through signal REGR. Then, the contents of register 1o01 and D
A comparator 1oO3 constantly compares the contents of oNn and outputs a signal indicating a match or a mismatch. This signal and C
MPo (match signal from the previous stage comparator and register cell)
The gate 1006 performs an AND operation with the D-flip-flop, and holds this result in the D-flip-flop at the timing of CT.

The timing of this (ljT) is to indicate that the compared data in the data array is valid.

Further, the D-flip-flop has a signal R1! :SE
Initialized by T. In this way, this comparator and register cell receives the comparison result signal CMPO from the previous stage comparator and register cell, determines and holds the match or mismatch of the extraction pattern elements up to this stage, and stores the comparison result signal CMPO from the previous stage comparator and register cell. A comparison result signal CMP1 is output to the cell.

The comparator and register array 10 has the comparator and register cells 101 to 10m connected in cascade 9.

Each register is provided with a bus enable signal KN by a decoder 111 for passing address data.
, basic configuration block chip select signals CS, I
It decodes the J-write control signal R/W and generates register read and register write signals. Using this signal, the contents of the D-bus are written to and read from the corresponding register, thereby interfacing with the CPU. Control the RKST signal to initialize the comparator and register array. The CMPK signal provides timing for comparing the contents written in advance to the register group and the contents of the D-bus,
The mWONT signal is binary data that controls how many of the m comparators and register groups are to be enabled. The Fix signal is an input signal (FixO signal of the block in the previous stage) for cascading the blocks and comparing m or more pieces of data. This is a signal for cascading with the block. The IEQN signal is a signal indicating that there is a match in that block, and the CMPK signal 10
,,-;; It is strobed at the timing of the issue.

In order to use the comparator and register array in the periphery of the CPU, a control/status register is built into the basic configuration 1゜2.3 to control DMA timing, interleaved requests, etc. .

This basic configuration 1, 2, and 3 is based on the Mu bus and D bus data sent from the CPU, the R/W signal, the O8 signal, and the E bus.
N signal.

RIC8ET (for example, POWICRON R1!:8
Control data is set in the control/status register by the KT) signal, and the basic configuration is controlled while reading the status. Further, the comparator and register array 1o are also read/written using the above signals to set a desired extraction pattern. In this way, when extracting the set pattern, 0DRI is activated by the Fixi signal! :The Q signal is a DM person request signal, and when this signal is active, the DACK signal (
DMA response signal) becomes active and DMA processing is performed. A signal 29 obtained by stropping the timing of this DMA processing by 117, -7 with the HAi signal is used as a comparison timing signal for the comparator and register array. Match signal 2 is sent from the comparator and register array 10 at this timing.
7 is output, and this coincidence signal is set to J- in the flip-flop 12 in accordance with the timing of the ICN signal. Then, the coincidence flag signal 26 is output from the flip-flop 12 at J- of , and if the interwoven enable signal 21 is 1 when this signal 25 is 1, the iNT signal is set to 0 by the AND gate 16, and the interwoven request is Output. Further, the coincidence flag signal 26 is also input to the control/status register 11, and the CPU
From this point on, polling of interacted factors can be performed. The match flag signal is also used to abort DMA requests. When the basic configuration block is the final stage of a cascade connection or used alone, the DMA is used so that the CPU can perform processing when a data match is detected.
Processing must be interrupted. The signal 23 is 0 in the case of the previous stage of the cascade, and is used to always output the DREQ signal.
is a signal for performing DMA processing.

An example of an algorithm for extracting a specific character string from a database using this system is shown in FIG.

In this example, RAMe contains “ABCABICDEABOABCABCDABCDK
``There is a database of character strings, from which ``A
BCABCABCDAB” character string (this is the first
) and the character string °'BCDE'' (this is the second character string).The basic configuration of the register array consists of 8 bits x 8 registers. Therefore, in order to extract the first character string mentioned above, 12 registers are required, so two basic configurations are connected in cascade (see Figure 1, 1 and 2).
). In addition, in order to simultaneously extract °'BCDE', the basic configuration is connected in parallel and used (Figures 1 and 2).
and 3). In such a system configuration, first, the 113th
In the 6-zo diagram, the comparator and register array 10 in the basic configuration 1 is filled with one of the first character strings. Write “CDAB” and set each data length to 8,
4 to each control/status register 11. In addition, the comparator and register array 1 in the basic configuration 3
Write the second character string “BODE” to 0, set the data length to 4, and write the control/status register 11.
write to.

Further, initialization is performed by setting the start address and length of the database in the RAM 6 in DMACs.

After the initial settings, the basic configurations 1 to 3 and the DMAC 5 are activated to perform pattern extraction processing. At this time, in FIG. 1, the DM request signals 72 and 71 become active and are output from the basic configurations 2 and 3, and the AND gate 7 performs a logical product to send the DM request signal 61 to the DMAC 5. Output. Note that in this example, basic configuration 1 and basic configuration 214, .

are connected in cascade and operate in conjunction, so basic configuration 1 does not output its own DMA request signal. DM
When the AC5 receives the DMA request signal 61, it sends the address of RAMe to the Mubus and sends the address of each basic configuration 1, 2, and 3.
A DMA permission signal is issued to the terminal to cause the processing to be performed.

In the algorithm shown in FIG. 6, since the database in the first stage of processing is 9 people, it matches the first pattern of basic configuration 1. As a result, the FixO signal and EQN A signal is issued and the first bit position is set to 9°1'' as shown in FIG.

In the second stage of processing, since the database is "JIB", the 102nd pattern of basic configuration matches, and basic configuration 3
The first pattern also matches. The register enters the set state because the character strings in the previous stage match and the characters at the current stage match, and is reset otherwise.Therefore, in this second stage of processing, the register in basic configuration 1 will be in the set state. T+1'' is set in the second bit position 157.

On the other hand, in the register with basic configuration 3, 1 is placed in the first bit position.
" is set. The same procedure is followed, but in the fourth stage, the first pattern of basic configuration 1 matches the fourth pattern, but the third pattern of basic configuration 3 matches. There will be a mismatch.

Therefore, in basic configuration 3, the registers are reset.

From the sixth stage to the eighth stage, pattern matching is performed in basic configuration 3, and IJ11 is sequentially set in the register from the first bit to the last bit. When the last bit is set to "1", it indicates that the required character string has been extracted, and in the basic configuration 3 above, "BO" is set.
A pattern of DE'' is extracted.

At this time, in FIG. 1, the DMA request signal 71 becomes inactive and DMA is interrupted, while the interwoven request signal 41 in FIG. 1 becomes active and the MP[T
Request processing to 4. MPH processing is completed and basic configuration 3
When restarted, the DMA request signal becomes active again and processing resumes.

In the 16th stage of processing, a match result was obtained for all bits of the register of basic configuration 1, and up to 1 block BCABCAB could be extracted, but this is because basic configuration 1 and basic configuration 2 are cascade-connected. The DMA request signal 71 does not become inactive, and the process continues to the next 17th stage.

Then, in the 17th stage of processing, the matching result of basic configuration 1 and the first pattern of basic configuration 2 are matched, and "ABCAB"
This means that up to CABC'l was extracted.

Such processing is continued, and in the 20th stage processing, the final pattern of basic configuration 2 is matched, and the initially targeted pattern "BCABCABCDAB" is extracted.

At this time, the DMA request signal 72 becomes inactive and the D
MA is interrupted, the interwoven request signal becomes active, and processing is requested from MPUa. MPU4
performs the processing, and when you restart basic configuration 2, the DMA
The request signal becomes active again and processing resumes. As described above, a plurality of character string patterns are simultaneously extracted in parallel by activating a plurality of basic configurations at the same time in step 174.

FIG. 6 shows three types of character strings “ABO” and “ABO” that are different from those in the above embodiment.
This is an example of an algorithm for extracting "ABCMB", 'tCDAB' and "BCDE" from the database. In this case, since character string patterns are extracted using each of basic configurations 1 to 3, there is no need to cascade connect a plurality of basic configurations.

Therefore, in the system configuration example shown in FIG.
A signal line is connected to send a DMA request signal 73 from the basic configuration 1 to the AND gate 7 .

As described in detail, according to the present invention, it is possible to extract a plurality of patterns by accessing the database only once, thereby improving the processing speed for pattern extraction. can do. Further, by creating one basic configuration and using n pieces of it in parallel, it is possible to process 1 to n patterns 184-ji at the same time. Furthermore, by creating one basic configuration and connecting it in cascade, it is possible to process pattern lengths that exceed the basic configuration. Furthermore, since various phenomena (long character strings, short character strings, etc.) can be dealt with using the method described above, the basic configuration can be fixed and it is easy to implement into an LSI.

[Brief explanation of the drawing]

FIG. 1 is a block diagram of a device to which the pattern extraction method of the present invention is applied, FIG. 2 is a block diagram of its basic configuration, and FIG. 3 is a block diagram of the comparator and register array in FIG.
FIG. 4 is a block diagram of the comparator and register cell in FIG. 3, FIG. 6 is a diagram showing an operating algorithm in the system shown in FIG. 1, and FIG. FIG. 1.2.3 Basic configuration (pattern detection means)
, 4...MPtT (processing device), 5...
・DMA0, 6...RAM (memory), 7...
...AND gate, 10...Comparator and register array, 11...K196-Tuntrol life status register, 1o1...
Comparator and register cells. Name of agent: Patent attorney Toshio Nakao and 1 other person No. 1
Figure 42 - FJI indentation line Figure 4 Figure 5

Claims (2)

[Claims] (1) Each element of the extraction pattern is held in a register in the detection means by the processing device, and each element in the database held in memory is read out by direct memory access, one element of the extraction pattern and one element in the database. The next element held in the register and the next element in the database are successively compared and the results are held, and these comparison results are connected in cascade and extracted. A pattern extraction method characterized by detecting matches between all elements of a pattern and all elements of a specific pattern in a database. (2) The pattern extraction method according to claim 1, wherein the plurality of pattern detection means can be connected in cascade to each other.