JPS63187334A - Character-string pattern matching device - Google Patents

Abstract

PURPOSE:To efficiently prepare a finite state automaton by a memory of a small quantity, by allowing the titled device to contain an uncertain character of fixed length or variable length, which limits a range of characters as a part of a pattern. CONSTITUTION:In a state of matching an uncertain character to which a range of characters is limited as a part of a pattern, only when characters of a limited range are inputted, a condition for detecting the pattern is maintained. An input characters are set to lower 8 bits of an address register 7 from a data transfer path 3, and to upper 8 bits, X'00' are set in advance as an initial value, and data of 8 bits stored in an address shown by the address register 7 are read out to memory registers 9, 10 from a RAM 5 and a RAM 6, respectively. The contents of the memory register 9 are set to the upper 8 bits of the address register 7 by the next cycle, and also as for the contents of the memory register 10, a detecting pattern is decided by a discriminating circuit 11 and is outputted to a signal line 4. In such a way, this device can contain the uncertain character of fixed length or variable length which are limited by a range of a character as a part of the pattern.

Description

[Detailed description of the invention] (Technical field to which the invention pertains) The present invention is characterized in that each character is represented by a fixed length code,
This relates to a ``character string pattern matching process'' that determines whether a relatively short character string, called a separately given pattern, exists as a partial string in a relatively long character string called text.

(Prior Art) In the field of data processing systems, searches are made to search for only those containing a specific substring called a pattern from a collection of character string data (called text) such as sentences.
It is often necessary to extract all patterns contained within text.

Usually, one character is expressed by an n-bit (fixed length) code, so text and patterns are a series of n-bit codes.

The LIKE predicate of SQL is known as a command that specifies such character string pattern matching processing. (
IBM Program Product SQ
L/DS Application Business Programming Manual) LIK
In the E predicate, the characters in the pattern are fixed-length characters that match any single character other than regular characters.
-1ength don't care character (FDC)
;H31), and a variable-length indeterminate character (Variable-1engt) that matches any character string of any digit.
h don'tcare character (VDC; represented by "%"") can be used.

FIG. 6 is an explanatory diagram of such a conventional character string pattern matching mechanism.

In FIG. 6, 1 is a storage device in which text is stored;
2 is a character string pattern matching device, 3 is a data transfer path, and 4 is a signal line for outputting search results.

In the character string pattern matching device 2, a method using a finite automaton is conventionally known as a method for performing character string pattern matching. (L,A,)lo
llaar, “Hardware Systems
for TextInformation Retri
eval,”ACM 5IGIR6th Conference
ence 1983) Figure 7 is an explanatory diagram showing the state transition of a finite automaton, where 50 represents the state of the finite automaton, 60 represents the direction of the state transition, and the three-letter pattern "BIC" in the text is can be detected.

This operation will be explained below.

The initial state of the finite automaton is state (0), and if the input character is II B II, it transitions to state (1).

It #II in the same figure represents other characters, and the state (0
) continues to remain in state (0) if the input character is other than II B Tl.

The same applies to state (1); if the input character is 1'', the state transitions to state (2), if the input character is B'', the state transitions to state (1), and otherwise to state (0).

In state (2), if the input character is "110", "B"
This means that a pattern called "IC" has been detected.

FIG. 8 is an explanatory diagram of a finite automaton that detects the pattern "IgB%C" in text.

FIG. 9 is an explanatory diagram of a finite automaton that detects the pattern "B C" in text.

Explanations of symbols in these figures are the same as those in FIG. 7.

The previously known character string pattern matching device described above can handle FDC ("-") and VDC ("%"), but it cannot handle uncertain characters with a limited range of characters. As a result of this failure, there were the following drawbacks.

For example, the patterns are “BIC”, “82G”, “8
3C", "84C", "85C", "B2O", "87"
If you want to handle “G”, “88C”, “B9O”, 11
8C", "BAC" etc. will also be erroneously detected, so "BIC" to "B9O" must be explicitly written as a pattern. In this case, the finite automaton will be as shown in Figure 10, and the number of states will be As the number of tables increases, the memory capacity for storing the tables representing them increases, and the table operation time also increases.

(Object of the Invention) An object of the present invention is to provide a character string pattern matching device that can include fixed-length or variable-length uncertain characters with a limited range of characters as part of a pattern. It is in.

(Structure of the Invention) (Characteristics of the Invention and Differences between the Prior Art) The present invention provides a method for matching uncertain characters with a limited range of characters as part of a pattern. The feature is that the pattern detection conditions are maintained only when the pattern is detected.

A conventional character string pattern matching device that targets only indefinite characters differs in that the pattern detection conditions are unconditionally maintained while matching the characters.

(Embodiment) FIG. 1 is a block diagram showing an embodiment of the present invention, in which 5 is a random access memory (RAM) that stores state transition information (next state number) of a finite automaton, and 6 is a detection 7 is an address register that holds the address of data to be read from RAM 5 and RAM 6; 8 is an address decoder common to RAM 5 and RAM 6; 9 and 10 are RAM 5. R
A memory register 11 stores data read from AM6, and a determination circuit 11 outputs a search result.

Here, we define a fixed-length indeterminate character (RFDC) that matches any single character in a limited range with ILE]TT, and a variable-length indeterminate character (RFDC) that matches any character in a limited range of any digit with ILE]TT. RVDC) will be expressed in %[coba. [The characters in square brackets indicate a limited range of characters.

Next, the operation shown in FIG. 1 will be explained.

The input character is set in the lower 8 bits of the address register 7 via the data transfer path 3.

The upper 8 bits of address register 7 have x as the initial value.
'oo' is set, and the 8-bit data stored at the address indicated by address register 7 is stored in the RAM.
5. Read out from RAM 6 to memory register 9 and memory register 10, respectively.

The contents of memory register 9 are set to the upper 8 bits of address register 7 in the next cycle.

Further, the contents of the memory register 10 are outputted to the signal line 4 after a detection pattern is determined by the determination circuit 11 .

The following operations are repeated every time one character in the text is input.

Figure 2 shows that one character is expressed as an 8-bit code, and a maximum of 2
In a system realizing a 56-state finite automaton, when a given pattern is 11B% [1 to 91C'', an example of data stored in RAM5 and RAM6 as a search preparation operation is shown.

In Figure 2, 12.13 are RAM5, R
8-bit data stored in one word of AM6, 1
4 is the upper 8 bits of the RAM address, and 15 is the lower 8 bits of the RAM address.

Note that logically, the upper 8 bits 14 of the RAM address are the state number of the finite automaton, and the lower 8 bits of the RAM address are
Bit 15 corresponds to the code of the character input from the text. Further, 16 is a character corresponding to each character code.

In the data 12.13 of FIG. 2, it is assumed that x'oo' is stored where the value is not specified. Data 12 is the state number to which the next transition should be made.

Data 13 is a bitmap indicating whether or not a pattern has been detected; for example, if the least significant bit is 1, it indicates that the first pattern has been detected.

FIG. 3 shows an example of data stored in RAM5 and RAM6 as a search preparation operation when the pattern given under the same conditions as in FIG. 2 is "B-[l~91C". It is expressed.

FIG. 4 is a state transition diagram representing the state transition information and detection pattern information of the finite automaton stored in the RAM 5 and RAM 6 in FIG. 2. The state transition diagram can be viewed in the same way as in FIG.

=8- In Fig. 4, state (1) is a state in which uncertain characters are matched, and characters in a limited range LL I II
~II As long as 9 TT is input, the pattern detection conditions are maintained, and then when the last character 11 C++ is input, the given pattern “B%[1~9]C” is detected. That means you did it.

If the contents shown in FIG. 2 are stored in the RAM 5 and RAM 6, the finite automaton will operate according to the state transition diagram shown in FIG.

FIG. 5 is a state transition diagram representing the state transition information and detected pattern information of the finite automaton stored in RAM5 and RAM6 in FIG. In Figure 5,
States (1) and (2) are states in which uncertain characters are matched, and characters in a limited range "1" to LL 9 ++ are matched.
Only when the pattern detection condition is maintained and state (3) is entered, then when the last character # CIT is input, the given pattern "B-[1 to 9 CI
This means that I has been detected.

Similarly, if the contents of FIG. 3 are stored in the RAM 5 and RAM 6 of FIG. 1, the finite automaton will operate according to the state transition diagram shown in FIG.

(Effect of the invention) When the control information of the finite automaton shown in FIG. 10 is developed into RAM5 and RAM6 under the same conditions as shown in FIG.
It will look like Figure 1.

The memory capacity required in this case is 11 words.

On the other hand, the required memory capacity in the case of FIG. 3 is 4 words.

In this way, conventional string pattern matching devices
Since it was not possible to include indeterminate characters with a limited range of characters as a pattern, a large amount of memory is used and the efficiency of creating an automaton is poor when you want to perform processing with a limited range of indeterminate characters.

On the other hand, in the character string pattern matching device of the present invention, when processing indeterminate characters with a limited range of characters as part of a pattern, a finite automaton can be efficiently created using a small amount of memory.

[Brief explanation of the drawing]

Figure 1 is a block diagram showing an embodiment of the present invention, and Figure 2 is a system that expresses one character with an 8-bit code and represents a finite automaton with a maximum of 256 states. %[1~91G” RAM5, RAM6
Figure 3 is an explanatory diagram of an example of the data stored in each of the ``B[1~91C''] patterns in a system that expresses one character with an 8-bit code and realizes an automaton with a maximum of 256 states. RAM5 in certain cases
, an explanatory diagram of an example of data stored in RAM 6, respectively, FIG. 4 is a state transition diagram expressing the state transition information and detected pattern information of the finite automaton stored in RAM 5 and RAM 6 in FIG. 2, and FIG. RAM in Figure 3
5. A state transition diagram expressing the state transition information and detected pattern information of the finite automaton stored in the RAM 6. Figure 6 is an explanatory diagram of the conventional string pattern matching mechanism. Figure 7 is the state of the conventional finite automaton. An explanatory diagram showing the transition =11−. Figure 8 is an explanatory diagram of a finite automaton that detects the pattern ttB%CIt in text. Figure 9 is an explanatory diagram of a finite automaton that detects the pattern It B C11 in text. Figure 10 is an explanatory diagram of a finite automaton that detects any of the patterns (i'l"B I C", "82 G", ..., "89C") in the text. , Fig. 11 shows R when the given pattern is "BIC", "B2O", ..., "B10" in a conventional character string pattern matching device.
It is an explanatory view of an example of data stored in AM5 and RAM6, respectively. 1...Storage device storing text, 2...Character string pattern matching device, 3...Data transfer path, 4...Signal line for outputting search results, 5...Finite automaton RAM for storing state transition information, 6...RAM for storing detected pattern information, = 12
- 7...Address register of RAM5 and RAM6, 8...Address decoder common to RAM5 and RAM6, 9.10...RAM5. Memory register of RAM6, 11... Discrimination circuit that outputs search results, 12, 13.
・RAM5. 8-bit data stored in one word of RAM6, 14... Upper 8 bits of RAM address, 15...
・Lower 8 bits of the RAM address, 16...Character corresponding to the character code. 50...state of finite automaton, 60...direction of state transition. Patent applicant: Nippon Telegraph and Telephone Corporation No. 2 'l'#2"3""4" Photo '6'"7
'``8'' ``Gu ``B''C' Nrei 6th 3rd ``l''``2''3'``4''``5''``6''
7° ``8''``9''``B'' σn 6 Figure 10 Figure 8 Figure 9 Figure 11

Claims (2)

[Claims] (1) Each character is expressed as a fixed-length code, and it is determined whether a relatively short character string called a separately given pattern exists as a substring in a relatively long character string called text. 1. A character string pattern matching device that performs character string pattern matching processing that includes fixed-length or variable-length indeterminate characters with a limited character range as part of the pattern. (2) Equipped with a memory for storing the next state number and detection pattern number corresponding to the set of state number and code number, and a mechanism for writing and reading data into the memory, and Store the next state number and detection pattern number in the memory in advance,
After text is entered, the string pattern matching process is performed by indexing the memory for each character of the text, and the entered characters are matched by matching uncertain characters within a limited range of characters. The character string pattern matching device according to claim 1, wherein the character string pattern matching device remains in that state only when the target character is in a limited range.