JPH1139344A - Character string retrieval method using two-dimensional array code - Google Patents

Abstract

PROBLEM TO BE SOLVED: To reduce the number of comparisons even when there are plural specifications and to accelerate retrieval performance by comparing a code which encodes a conditional character string by using a two-dimensional array with a comparison object character including plural specification conditional characters. SOLUTION: A character string that meets a conditional character 1 which is given from character string data 4 is retrieved and stored in a coincidence data file 6. Comparison processing 5 compares the character 1 by using a conditional character code 3 that is acquired through code processing. Coding divides the conditional character string 1 into each conditional character and gives an one-dimensional storage number (primary subscript) of an array. Further, it divides the character into conditional classes, assigns a class number to the front of a two-dimensional storage number (secondary subscript), in the case of plural specifications, stores a corresponding data group as a flag in each class, corresponding to an element of a corresponding secondary subscript and makes it a conditional character code 3.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a character string search method, and more particularly to a character string search method using a computer.

[0002]

2. Description of the Related Art As a character search method for comparing a plurality of character string data stored in a file with a condition character string, a first character of a comparison target character string is compared with a first character of the condition character string, and a match is made. In this case, the following characters in the respective character strings are compared sequentially, and it is determined whether or not the character string matches the entire condition character string. The characters in the condition string are
In addition to ordinary characters, special characters that represent any one character, characters that represent any character (or character string),
Further, there is a method of designating a plurality of characters by designating a list or range of corresponding characters (this designation method is referred to as “plural designation”).

[0003] Among them, in order to perform a comparison by a plurality of designations, information of all characters (referred to as "corresponding character group") corresponding to a condition is retained by the designation and individually compared with characters to be compared. There is a need.

A conventional character search method will be described below with reference to FIG. In the conventional method, the condition string 10
1 is subjected to the encoding process 102, and as in the condition character code 103, the information of the corresponding character group is stored in one element of the array for each character. Then, the number of comparisons increases.

[0005]

As described above,
The above-described conventional character search method has the following problems.

The first problem is that the performance when a plurality of designations are made is significantly reduced.

[0007] The reason is that the number of comparisons in a plurality of designated portions is n for each character string data to be compared if the character to be compared is not in the corresponding character string, assuming that the number of designated characters is n. Even if it is in the string,
This is because the number of comparisons becomes ((1 + n) / 2), and the number of comparisons increases as the number of applicable characters, and in particular, the character string data increases.

The second problem is that there is no appropriate method for determining the size (number of elements) of an array holding individual characters necessary to store information on a corresponding character group when a plurality of characters are specified. ,That's what it means.

The reason is that, in the above-described concept, the size of an array for storing information of a corresponding character group in a plurality of designated portions is:
(Condition number of characters x number of allowed characters), but usually multiple designations are at most about 1 to 2 characters in the condition character string, and the number of applicable characters is, on average, smaller than the total number of usable characters. It can be a significant percentage, so most could be wasted arrays.

However, if an array smaller than this size is prepared, a size larger than the size of the prepared array is required depending on the specification, and so-called out-of-array reference may be caused.

Accordingly, an object of the present invention is to provide a character search method that reduces the number of comparisons and speeds up search performance even when a plurality of designations are made.

Further, according to the present invention, the size of an array necessary for storing information of a corresponding character by a plurality of designations is defined as follows.
An object of the present invention is to provide a character search method that does not waste much and is uniquely determined.

[0013]

In order to achieve the above-mentioned object, the present invention, in brief, is to code a conditional character string using a two-dimensional array. In a character search method according to the present invention, in a search for a character string by condition designation, a condition character is coded using a character type and a two-dimensional array representing a corresponding character flag in the character type, and the code and the plural designation condition character Is compared with the comparison target character including.

Further, the present invention includes a two-dimensional array having a condition type as a subscript in the row direction and a character type as a subscript in the column direction. A corresponding condition character type code is stored at the head of the column direction subscript. In the case of multiple specifications, the next element of the subscript in the column direction is
By sequentially coding with a corresponding flag of the character type, and comparing the code value of the character to be compared with the code stored in the subscript corresponding to the character type in the two-dimensional array by the corresponding flag of the character type to be compared, Character search is performed.

In the present invention, the condition code includes an array for storing information on the corresponding character flag for each character type for each condition character, and an array for managing these arrays for all the condition characters.

[0016]

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

FIG. 1 is a diagram for explaining an embodiment of the present invention. A character string satisfying a given condition character 1 is searched from character string data 4 and a matching data file 6 is searched.
System. In comparison processing 5 in this system, conditional character 1 is code-processed (2 in FIG. 1).
The comparison is performed using the conditional character code 3 obtained by the above.

Next, details of the conditional character code 3 in the embodiment of the present invention will be described with reference to FIG.

In coding, the given condition character string 1 is divided for each condition character, and the storage number of the first dimension of the array (referred to as "primary subscript") is given. Further, the character is divided into condition types, and a type number is assigned to the head of a storage number in the second dimension (referred to as a “secondary subscript”). The corresponding data group is stored as a flag in association with the element of the corresponding secondary subscript (7 in FIG. 2), and the condition character code code 3 is set.

FIG. 3 is a flowchart for explaining the operation of the embodiment of the present invention. The operation of the embodiment of the present invention will be described with reference to FIG.

With respect to a given condition character string, the character string is classified (step S11), and it is determined whether the entire character string is uniquely specified or matches the beginning (step S1).
2). In the case of unique designation or prefix matching, the number of processes increases, so comparison is made using a standard function or the like (step S1).
4).

In cases other than the above (N in step S12)
o), the condition type is divided for each constituent character, and if a plurality is specified, the data group is flagged for each character type and stored in an element of each array (step S1).
3).

Next, a character to be compared is obtained from the character string data file 4 (step S15), and it is determined whether or not the character string data is completed (step S16).

If the character string data is not completed, a comparison process is performed for each character (step S17), a final match determination process is performed (step S18), and it is determined whether or not the character strings match (step S19). , If they match,
The matching character string data is written (step S20), and the next character string data is read (step S15). The processing of steps S15 to S20 is performed for all character string data in the character data file.

FIG. 4 is a flowchart showing the processing flow of the comparison process for each character in step S17 in FIG.
With reference to FIG. 4, a description will be given of a comparison process with a comparison target character string.

In comparison with the character string to be compared, it is determined whether or not the secondary subscript of the corresponding condition character code is a plurality of designated characters based on the first element (step S4).
2) In the case of a character other than a plurality of designated characters, a comparison process is performed according to the conventional condition type because the process is increased (step S44).

On the other hand, when a plurality of characters are specified, the character type is determined for the (i + 1) th character of the comparison character data, and only the corresponding character type is encoded (step S4).
3).

Next, a comparison is made by taking a logical product of the elements (flags) of the character type of the condition character code corresponding to the character code to be compared (step S45).

It is determined whether or not the characters from the comparison result of the above processing match (step S46). In particular,
If the result in step S45 is other than 0, they match, and if they are 0, they do not match.

If they do not match, the next character string data is read (step S15 in FIG. 1).

If they match, the counter (i) is increased to move the comparison target to the next condition character or comparison target character (step S47). Here, if the comparison character string has been completed, the process proceeds to the final match determination process (step S in FIG. 1).
18).

If not completed, step S42
To S48 are repeated. The processing in each of the above steps can be realized by program control executed on a computer.

[0033]

Next, an embodiment of the present invention will be described.
The following characters are used, and the following character types are used.

. (Period) ... Character type 1.

0-9: Character type 2

AZ: Character type 3

In addition, the following 4
It is assumed that there are types, and they correspond to the following condition type numbers, respectively.

-Unique designation (condition type 0) ... designates one character from available characters.

Specifying an arbitrary one character (condition type 1): represents an arbitrary one of available characters.

-Arbitrary character designation (condition type 2): Indicates an available character or character string.

A plurality of designations (condition type 3)... Designation of a plurality of usable characters (such as a character string or range designation).

An example of a plurality of designations will be briefly described.

[ABC] → A, B, or C is represented.

[DF] represents one of D, E, and F.

[AC-E] represents one of A, C, D, and E.

It is also assumed that the range designation between the character types can be designated as being continuous in the order of 1 to 3 of the character types.

As an example of an actual condition character, a condition character string A
? * Consider [5-CX].

This means that the first character is A, and the last character is a character string of three or more characters of 5, 6, 7, 8, 9, A, B, C, and X.

In this case, since there are four types of condition and four condition characters, the character code is a 5 × 5 matrix.

Next, the operation of one embodiment of the present invention will be described.
This will be described in detail with reference to FIG.

The value of the array of condition codes when the condition character string 51 is coded is, as in the case of the condition code 52, the head of the secondary subscript is filled with the corresponding condition character type code.
In the case of multiple designations (D [n] [0] = 3), the next element (D [n] [1], D [n] [2],
..) Are sequentially stored with corresponding flags of the character types. The data of the other elements of the condition code 52 are not used for the condition character string 51, but D [0] [0] = 0 is the condition type 0, and D [1] [0] = 1 is the condition type. Type 1, D [2]
[0] = 2 indicates the condition type 2.

Next, encoding of a plurality of conditional characters [5-CX] in the conditional character string 52 will be described with reference to FIG.

In the coding of a plurality of condition characters, a number is assigned to each corresponding character by the condition character type, and whether or not there is a character in an element corresponding to the number is represented by 0 or 1. The following describes each character type.

In condition character [5-CX], character type 1
Is not included. Therefore, D [3]
0 is stored in [1] (61 in FIG. 6).

In addition, since the characters 5 to 9 correspond to the character type 2, the flag of the portion corresponding to them is set to 1, and those arranged in order from 0 to 9 (62 in FIG. 6) are expressed as a binary number. Considered and stored in D [3] [2]. In the following, this binary number will be described after being deciphered into ten.

Similarly, the same processing is performed for the character type 3 (63 in FIG. 6), and the data is stored in D [3] [3].

Next, the actual comparison will be described in detail with reference to FIG. Since comparison processing other than the multiple condition characters is performed by the conventional processing, the description will be limited to the comparison with the multiple condition characters (steps S43 and S45 in FIG. 4).

As one specific example, the condition character [5-C
X], and consider "6" as an example of a character to be compared. First, the character type of "6" is 2, and "6" is coded in the same manner as the conditional character to obtain 64 (71 in FIG. 7).

Next, the logical product of this code and the corresponding code (D [3] [2]) in the conditional character code 72 is calculated. As a result, the result is 64, and the result that the logical product matches because the logical product is not 0 is obtained.

When the same plural condition characters are compared with "E", the character type and the order of "E" are determined (see 7 in FIG. 7).
As shown in 3), 0 which is the result of the logical product with the corresponding code (D [3] [3]) in the conditional character code 72, that is, the result of mismatch is obtained.

Next, the difference from the conventional code is shown in FIG.
This will be described in detail with reference to FIG.

When the conditional character string 51 of FIG. 11A is expressed using a conventional code, it becomes as shown by 111 in FIG. 11B. Here, the parentheses ([,]) of the primary suffixes 3 and 13 indicate the start and end of the character data corresponding to a plurality of conditions.

For the size of the array, the conventional code is 1
4. In the code according to the present embodiment, 25 is smaller in the conventional code than in the conventional code. However, the number of comparisons in a plurality of condition parts per character string data is smaller than that in the conventional 9 (= the number of applicable characters) according to the present embodiment. In code, it is only once.

Further, as shown in FIG. 12, A? Considering − * [5-X], the condition code is 36 in the conventional condition code, which is more than 25 in the code according to the present embodiment. Also, the number of comparisons of a plurality of designated portions per character string data is one, which is considerably smaller than that of 31 in the conventional code. As described above, in the code according to the present embodiment, the number of elements of the array does not change regardless of the designation as long as the number of conditional characters is the same, and the comparison of a plurality of designated portions is always one.
Turns.

Although the number of elements used in the conventional code varies depending on the condition character string, the number of elements of the array required to prevent out-of-array reference is reduced when the condition character is four characters. , 4 × {(number of characters of character type 1) + (number of characters of character type 2) + (number of characters of character type 3)} = 4 × (1 + 10 + 26) = 148.

Another embodiment of the present invention will be described with reference to FIG. When storing the input file 81 in the storage device 83, the data type is classified from the upper index file 87 based on the keywords in the data in advance, and the data relating to the keyword and the pointer to the data file 87 are stored for each data type. There is a search method in a system constituted by an index file 89 to be executed.

Conventionally, list data has been searched for the number of specified keywords. In the embodiment of the present invention, keywords belonging to each data type are numbered in the upper index file 83 and managed. By doing so (91 in FIG. 9), at the time of search, the search data 84 is flagged for each data type based on the information of the upper index file 83. In FIG. 9, the correspondence between the upper search file 91 and the data type 1 is indicated by 92. In comparison with the index file for each data type, each data in the file is similarly flagged, and the logical product of the input condition code and the corresponding data type is obtained, and it can be determined whether or not the values match.

[0068]

As described above, according to the present invention, the following effects can be obtained.

A first effect of the present invention is to solve the problem of the conventional method, that is, to reduce the search performance when using a plurality of designations, and to speed up the search performance.

The reason is that, in the present invention, since the coding is performed at the beginning of the search processing by converting the data of a plurality of conditional character portions into data, the number of comparisons becomes one for each character string data.

A second effect of the present invention is that it is possible to avoid waste of the array storing the information of the corresponding character group and the possibility of occurrence of out-of-array reference.

The reason is that, in the present invention, by changing the size of the array necessary for storing the information of the corresponding character group from the number of usable characters to the number of character types, all the information for each conditional character code is obtained. Even if you do, it will not be so large.

[Brief description of the drawings]

FIG. 1 is a diagram for describing an embodiment of the present invention.

FIG. 2 is a diagram for explaining a two-dimensional code according to the embodiment of the present invention.

FIG. 3 is a flowchart showing a processing flow according to the embodiment of the present invention.

FIG. 4 is a flowchart illustrating a comparison processing flow for each character according to the embodiment of the present invention.

FIG. 5 is a diagram for explaining one embodiment of the present invention;
It is a figure showing the example of the code of the whole condition character.

FIG. 6 is a diagram for explaining one embodiment of the present invention;
It is a figure showing an example of a code about a plurality of designated character parts.

FIG. 7 is a diagram for explaining one embodiment of the present invention;
FIG. 6 is a diagram illustrating an example of a method of comparing a plurality of designated characters with a comparison target character;

FIG. 8 is a diagram showing a configuration of another embodiment of the present invention.

FIG. 9 is a diagram showing an application example of coding according to another embodiment of the present invention.

FIG. 10 is a diagram for explaining a conventional character search method.

FIG. 11 is a code of a condition character string 51 according to a conventional code.

FIG. 12 shows codes of another example of a condition character string according to the related art and the present embodiment.

[Explanation of symbols]

DESCRIPTION OF SYMBOLS 1 Condition character string 2 Encoding processing 3 Condition character code 4 Character string data 5 Comparison processing with a condition character string 6 Matching character string data 7 Information for each condition character 51 Example of a condition character string 52 Conditions corresponding to the condition character string 51 Code 61 Code table for character type 1 of condition character string 51 62 Code table for character type 2 of condition character string 51 63 Code table for character type 3 of condition character string 51 71 Code for character type 2 of comparison target character “6” Table 72 Multiple designation data part in condition code of condition character string 51 Code table for character type 3 of comparison target character "E" 81 Input file 82 Input device 83 Storage device 84 Search data 85 Search device 86 Matching data storage file 87 Data file 88 Top search file 89 Search file for each data type 91 Top search Example of search file 88 92 Example of code table relating to data type 101 101 Code of condition character string 51 by conventional code 111 Example of condition character string 112 Code of condition character string 111 by conventional code 113 Condition character by code of the present invention Code for column 111

Claims (3)

[Claims] In a character string search by condition specification, a condition character is coded using a character type and a two-dimensional array representing a corresponding character flag in the character type, and a comparison including the code and a plurality of specified condition characters is performed. A character string search method characterized by comparing with a target character. 2. A two-dimensional array having a condition type subscript in the row direction and a character type subscript in the column direction. A corresponding condition character type code is stored at the head of the column direction subscript. , The next element in the column index,
By encoding with a corresponding flag of the character type, and comparing the code value of the character to be compared with the code stored in the subscript corresponding to the character type in the two-dimensional array by the corresponding flag of the character type to be compared, A character string search method characterized by performing a search. 3. A corresponding condition character type code is stored at the head of a column direction subscript of a two-dimensional array in which a condition type is a subscript in the row direction and a character type is a subscript in the column direction. With reference to the two-dimensional array, which is sequentially coded by the corresponding flag of the character type,
A character search is performed by comparing a code value of a character to be compared with a code stored in a subscript corresponding to the character type of the two-dimensional array by a corresponding flag of the character type to be compared. A recording medium on which a program to be executed is recorded.