JPH0268663A - string search device - Google Patents

Abstract

PURPOSE:To efficiently use a register memory by inputting plural character strings to be retrieved and inserting a delimiter character between character strings and eliminating duplicate characters and registering them as a register character string. CONSTITUTION:When input character strings 1 to be detected are inputted in the register mode, a character collating part 10 outputs a character collation signal 2 at each time of registering one character, and the delimiter character is inserted among plural register character strings, and duplicate characters are not registered. When the input character string 1 of a document character string is inputted in the retrieval mode, it is collated with register character strings to output character collation signal 2 indicating coincidence or discord of each character. This signal 2 is inputted to a sequential encoding part 20, and this part 20 outputs a complete coincidence signal 3 when a register character string is detected in the document character strings, and the part 20 outputs a single character error detection signal 4 when a character string different from a register character string by one character is detected. Consequently, the delimiter character is used, and duplicate characters are not registered. Thus, the register memory is efficiently used.

Description

[Detailed Description of the Invention] (Field of Industrial Application) The present invention is a character string matching method, in particular, inputs a document file stored in secondary storage such as a magnetic disk or optical disk, and The present invention relates to a device that searches for a character string from character information (text) by comparing it with a keyword.

(Prior art) Conventional string matching methods include (1) sort search method, (2) associative memory method, (3) cellular array method, and (4)
Examples include the finite state automaton method and (5) DP method, but these methods have the following problems. In other words, (21, (3) cannot handle long character strings. (1
), (31, (4), and (5) cannot handle non-anchor matching of variable-length character strings. (5) has slow processing speed. (3), (4), and (5) have limited hardware size. It doesn't get smaller.

In order to solve some of these problems, (2) and (4)
) String search LSI (NEC-15
Developed by SP), T. Takahashi, et al., “String Matching Hardware Architecture,” Institute of Electronics and Communication Engineers Research Report (Computer Systems), CPSY 86-57.
It was announced in July 1986.

(Problem to be solved by the invention) String search L that combines (2) and (4) like this
Even with SI, if multiple identical characters or very similar character strings are registered in the associative memory, the entire memory cannot be used efficiently.Since fixed-length blocks are used to register character strings in the associative memory space, short If there are many character strings, there are disadvantages such as a lot of wasted registration memory space. It is an object of the present invention to provide a character string search device that solves this drawback.

(Means for Solving the Problems) In order to achieve the above object, a character string search device according to the present invention inserts a delimiter character between a plurality of input character strings at the time of registration, and searches for registered characters. Registration/Registration/Registration/Registration/Registration/Registration/Registration/Registration/Registration/Registration/Registration/Registration/Registration/Registration/Registration/Registration/Registration/Registration/Registration/Registration/Registration/Registration/Registration/Registration/Registration/Registration/Registration/Registration/Registration/Registration/Registration/registration/registration/registration/registration/registration/registration/registration/registration/registration/registration/registration/registration/registration/registration/registration/registration/registration/registration/registration/ that outputs a verification signal that registers each character as a string, and at the time of search, compares each character of the manually entered character string with the registered character string, indicates the registration of each character at the time of registration, and indicates whether or not there is a match at the time of search. It receives the registration/verification signal from the verification control unit, stores the character structure of the registered character string at the time of registration, compares it with the input character string at the time of search, and sends a character verification signal indicating the presence or absence of a match and the delimiter character for each character. Performs logical operation processing on the output character matching section and the character matching signal,
The apparatus includes a character string detection means that determines the presence or absence of a registered character string in the input character string for each delimiter at the time of searching based on the result.

(Function) The registration/verification control unit converts multiple character strings to be searched.
Insert a delimiter character between character strings, remove n1 and duplicate characters, and register as a registered character string. Match each character of the string entered during search with the registered string. At the time of registration/search, a registration/verification signal is output that indicates registration and indicates whether or not there is a match.

The character matching section stores the character structure of the registered character string at the time of registration from the registration/matching signal, compares it with the input string at the time of search, and outputs a character matching signal indicating whether or not there is a match and a delimiter for each character.

The character string detection means inputs a character matching signal and detects the presence or absence of a registered character string in the character string input at the time of search and a character string with a single character error. In this way, by using delimiters and not registering duplicate characters,
Registration memory can be used efficiently. Further, the registered character string and a single character error thereof are detected by the character detection means.

(Example) Next, embodiments of the present invention will be described with reference to the drawings.

FIG. 1 is a block diagram showing an embodiment of a character string search device of the present invention. In the registration mode, this device registers a character string to be searched as a registered character string, and in the search mode, detects the registered character string and a single character error therein from document character strings such as document files.

The clock generation unit 30 generates a clock signal 5f and a character matching unit 1.
0 and the sequential encoder 20. Input/output operations of each part are performed in synchronization with this clock signal 5. When the input character string l of a registered character string such as a keyword, an idiom, a short sentence, etc. to be detected is input in registration mode, the character matching unit IO outputs a character matching signal 2 for each character registration, and checks a plurality of registered characters. Separator EO8 (End) between columns
of String).

When the input character string l of the document character string is manually stored in the search mode, it is compared with the registered character string, and a character matching signal 2 indicating whether there is a match for each - character is output.

The sequential encoding unit 20 inputs this signal 2, and when it detects a registered character string in the document character string, it outputs a complete match signal 3, and when it detects a character string that differs by one character from the registered character string, it outputs a one-character error detection signal 4. Output.

The configuration of the character matching section 2 is shown in FIG. The registration/verification control unit 1.2 converts the input character string 1 into a character code 3 in the registration and search mode and outputs the character code 3.

The character registration/verification unit 14 inputs the character code 3 in the registration mode, and, for example, if the registered character string is "Fuzzy search information F:OS information search EO8J," the character registration/verification unit 14 removes duplicate characters from it and enters [Vague search information Like EO8J, it performs registration that saves memory space and registers/registers each character.
Activate verification signal 7. String conversion table 1
6 expands this signal 7 into the character structure of the original registered character string using the clock signal 5 and stores it in the storage element. In the search mode, each character of the document character string input with character code 3 is compared with the stored contents, and if there is a match, the registration/verification signal 7'! i-Output to active. When the character string conversion table 16 matches this signal 7 and the contents of the storage element,
In this example, "Character matching signal 2 for each character of fuzzy search EO8 information search EO8J is activated."

The character conversion table 16 is shown in FIG. 3(,), and the memory element is shown in FIG. 3(b). The dots in the grid representing the table 16 indicate the state in which the memory element has stored one character. Each storage element is 1
It consists of bit latches i6i1andr162 and ordart163. A registration/verification signal 7 synchronized with the clock signal 5 is applied to each column from the left of the column.
A clock signal 5 is applied to each row from top to bottom.

In the registration mode, when the clock signal 5 and the registration/verification signal 7 are simultaneously input to terminals C and D, the latch 161 stores one character and sets its output to a high level "H"'. As a result, the lattice points of the character conversion table 16 become stored in the dot state shown in the figure. In the search mode, the clock signal 5 and registration/verification signal 7 are applied to each row and column, and the latch 161 at that grid point is in the registration state.
For example, the AND gate 162 outputs Hn to the OR gate 163, and the OR gate 163 changes the character matching signal 2 to H''.

FIG. 4 shows a configuration example of the EOS latch portion of the character string conversion table 16. A launch 161 is connected to each grid point of the column to which the registration/verification signal 7 representing the character EO8 is applied from the registration/verification control unit 12, as in the other columns. latch 16
1 stores the character EO8 by applying the clock signal 5 and the signal 7 of EO8, and sets the EOS latch output 8 to H'.

FIG. 5 shows the configuration of the sequential encoder 20, which is a character string detection means. Each character of the registered string, for example, "
This circuit consists of AND gates a, b, c, or gates, d1, bit latches e, f. The input and output of each circuit are connected to each other in cascade, and when the detected character string and the registered character string match, the terminal "i" circuit outputs a perfect match signal 3, and if there is an error in the - character, the A single character error signal 4 is output from the character circuit.

In the circuit shown in the figure, when the input character string before "ambiguous..." ends, the EOS latch output 8 of that delimiter is output to the reset terminal SET of each latch e and f. Cent to memorizable state. "
In the circuit of ``A'', when the character matching signal 2 input to the gate a is ``H'' indicating a match of ``A'', the gate a outputs ``H'' to the latch e, and the latch e outputs ``H'' to the latch e. is memorized and the output to the circuit "I" is set to "H". On the other hand, andy-tb and C are respectively fi"l," and "H"
', the OR gate d outputs "L", and the latch f stores this n and outputs L# to the "i" circuit.

In the circuit "i", if the character matching signal 2 is "L" indicating a mismatch, the output of the OR gate (t)a becomes "L" and the latch e outputs "L". AND gate b outputs Hn, AND'y" -) c outputs L', and as a result, OR gate d outputs H", latch f stores the error, and one character error detection signal 9 & - character error Let it be H' indicating.

Now, when each character matching signal 2 of the character "ambiguous" indicates a match, the circuit for the final character "i" sets the exact match signal 3, which is the AND of the character matching signals 2 of each circuit, to "H". If there is an error in the - character, this signal 3 is set to "L".

As an example of operation in the registration mode, the case where the registered character string is "vague search", "information search", "..." is shown in Figures 6 to 8. As the input character string l, "vague search EO8 information search EO8..." in which the delimiter control character EO8 indicating the end of the registered character string is inserted is input.

When an input character string 1 is inputted in the registration mode in FIG. 1, the character collation section 10 registers the registered characters and character strings one by one in the registration/verification control section 12 of FIG. 2. At this time, the first character "A" of the first registered character string is registered in the first column of the registration/verification control unit 12, and at the same time, the position of the lattice point (1, 1) of the character string conversion table 16 is n. A dot is added to .

The grid points of the character string conversion table 16 are configured, for example, by a circuit as shown in FIG. 3, as described above. The vertical line corresponds to the registration/verification signal 7 in FIG. 2, and the horizontal line corresponds to the character verification signal 2 in the same figure. Here the first dot is latch 161
This means that the output is in the cent state (output is "H").

and n are sent by raising the registration clock signal of the row of the grid point while keeping active the line (vertical line) of the column of the grid point to which dots are to be added. Thereafter, when a registered character becomes a hint in the search mode and the registration/verification signal 7 becomes active, all the character verification signals 2 in the lines to which dots are added on the registration/verification signal 7 become active.

In Figure 7, the second character “i” is H on the registration/verification side! t
At the same time as n1 is registered in the second column of stz, a dot is added to the grid point (2, 2) of the character string conversion table 16. A dot is added to (3,3) for the third character "ma" in the same way, but since the fourth character "i" has already been registered in the second column, the registration/verification control unit 12 does not Only a dot is added to the grid point (2, 4) of the character string conversion table 16 without registration. Similarly in FIG. 8, the i button "Search" appears twice, so it is not registered in the registration/verification control unit 12 from the second time onwards.
First, only a dot is added to a predetermined position in the character string conversion table 16. In other words, when registering a registered character string, the character matching unit 1O checks whether the same character has been registered, and if it has already been registered, it does not register the same character twice and moves it to a predetermined position in the character string conversion table 16. Add processing to.

In the same way as above, information on the Nth character (EO8 is also counted as one character) of the registered character string is registered as a dot on the Nth line. When the delimiter control character EO8 is input to the registration/verification control unit 12 as the Nth character, the column of EO8 becomes active. In the EOS latch portion of the character string conversion table 16, as shown in FIG. 4, when the registration clock on the Nth line is raised in this state, the EOS latch 161 on the Nth line is set. Since the output of the latch 161 is input to the asynchronous reset terminal SET of the two latches a and f of the sequential encoder 20 in FIG.
” continues to be output.

As an example of operation in search mode, if a document string is
・” indicates when.

The input character string l is synchronously input to the character matching unit 10 as in the registration mode. The operation of the character matching unit 10 when a document character string is input is shown in FIGS. 9 to 14. The registration/verification control unit 12 compares each input character with all registered characters, and activates the registration/verification signal 7 of the matching character. In FIG. 9, when "recently," is input, no matching character exists yet, so none of the registration/verification signals 7 becomes active. 1st
In Figure 0, when "information" is input next, the registration/verification signal 7 in the 6th column of the registration/verification control unit 12 becomes active, and the character matching in the 8th row is activated by the dot at (6°8). signal 2
also becomes active. Note that in this figure, the broken edge portion represents an active signal line. In addition, ``report'', ``inspection'', ``
11~
It changes as shown in Fig. 13. Going further, the first one shows the point in time when "search" for "fuzzy search" was entered.
This is Figure 4. In FIGS. 10 to 14, a character surrounded by a circle 1 means that the complete match signal for that character in the sequential encoder 20 is in the "H" state.

The character collation signal 2, which is the output (signal line in the row direction) of the character string conversion table 16, is transferred in real time to the sequential encoder 2o as a result of character-by-character collation in this manner. Sequential encoder 1'W
zo (FIG. 5) is an AND circuit with a plurality of 1-bit branches that operate in synchronization with the registration/verification section 14, as described above.

The result of character matching input in real time from the OR logic circuit is sequentially compared with the registered character string. At this time, two signals, a complete match signal 3 and a single character error detection signal 4, are output for each registered character string. The exact match signal 3 for the last character of each registered character string indicates that the registered character string exists in the document character string, and the one-character error detection signal 4 for the same character differs from the registered character string by only one character. Indicates that the string exists.

Furthermore, the character matching signal 2 for the same character in a registered character string containing the same character always becomes actia' at the same time, but the sequential encoder 20 uses the exact match signal 3 and 1.
Since the character error and error detection signals 4 are successively propagated and synthesized,
The exact match signal 3 and single character error detection signal 4 of the registered character string that is not applicable do not become active in the end. for example,
In FIG. 13, two character matching signals 2, "search" for "vague search" and "search" for "information search", are active, but the former "search" is not circled. This
means that the perfect match signal 3 of the former "search" is "L". That is, this is because the exact match signal 3 of the character "search" before "search" is "L". (Example 13
(FIG. 14) The single character error detection signal 4 becomes active for the registered character string "Information Search" as well for one document character string as shown below.

"*Information Search""Information*Search""Information*Search""InformationCheck" (* is any single character) Input the document string as above and match it with the pre-registered keywords. By doing this, it is possible to construct a character string search device that can search for a necessary character string and can also detect character strings that differ by only one character.

(Effect of the invention) As explained above, the present invention has the following effects.

(1) Even if the same character is included in multiple registered character strings, those characters will not be registered twice, and the registered character string will not be divided into fixed-length blocks. Column registration space can be used efficiently.

(2) Character strings containing a single character error can be detected.

(3) Since the device configuration is a repeating structure of the same structure, design is easy and implementation efficiency is high, and VLS can be performed only once.

[Brief explanation of the drawing]

FIG. 1 is a block diagram showing an embodiment of the character string search device of the present invention, FIG. 2 is a block diagram showing an example of the configuration of the character matching section of the same embodiment, and FIG. An explanatory diagram showing an example of a conceptual configuration of a string conversion table, FIG. 4(b) is a circuit diagram showing an example of its internal configuration, and FIG. FIG. 5 is a circuit diagram showing an example of the configuration of the sequential encoding section of the same embodiment, and FIGS. 6 to 8 are explanations showing examples of operations in registration mode in the same embodiment in chronological order. Figures 9 to 14
The figure is an explanatory diagram chronologically showing an example of the operation in the search mode in the same embodiment. 10...Character matching section 12...Registration/verification control section l4...Character registration/verification section 16...Character string conversion table 20...Sequential encoding section 30...Clock generation section 161, e, f...1 bit latch 162, a to C... amplifier 9-toe 163, d... orake 9-toe

Claims (1)

[Claims] 1. At the time of registration, a plurality of input character strings are registered as a registered character string by inserting delimiters between the character strings, and at the time of search, each character of the input character string is a registration/verification control unit that outputs a registration/verification signal that compares the registered character string, indicates the registration of each character at the time of registration, and indicates the presence or absence of a verification match at the time of search; and a registration/verification control unit that receives the registration/verification signal and registers the character at the time of registration. a character matching unit that stores the character structure of a character string, compares it with an input string during a search, and outputs a character matching signal indicating the presence or absence of a match for each character and the delimiter; and a logical operation process on the character matching signal. and character string detection means for determining the presence or absence of the registered character string in an input character string for each delimiter character at the time of searching based on the result. 2. In the apparatus according to claim 1, the registration/verification control unit does not perform duplicate registration when the same character exists in the registered character string, and selects the registered character from the character configuration of the character verification unit during a search. A character string search device characterized by identifying columns. 3. In the apparatus according to claim 1, the character string detection means outputs a complete match signal when the registered character string is included in the document character string, and detects a character string that differs by only one character from the registered character string. A character string search device characterized by outputting a single character error detection signal when a character string error is detected.