JPH05334355A - Optional identity retrieval system - Google Patents

Abstract

PURPOSE:To shorten the retrieval time of optional identity retrieval. CONSTITUTION:An index word extracting process means 41 extracts an optional identity retrieval key (rear character string having respective characters of index words as initial characters) from the index words of respective records R1-Rn constituting a database and also makes the extracted optional identity retrieval key 21 correspond to a record key 22, a sorting process means 42 sorts the optional identity retrieval key 21 made to correspond to the record key 22 extracted by the index word extracting process means 41, and a merging process means 43 merges sorted optional identity retrieval keys 21 which have identity starting parts into one optional identity retrieval key 21 to generate an optional identity retrieval index 2. A searching means 1 makes a binary search of the optional identity retrieval index 2 by inputting an optional identity retrieval word to search for an optional identity retrieval key 21 whose start part identifies that of the inputted optional identity retrieval word, and outputs a record key 22 corresponding to the optional identity retrieval key 21 which is searched for.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a database search, and more particularly to an arbitrary match search system capable of performing an arbitrary match search at high speed.

[0002]

2. Description of the Related Art With the spread of computers, the use of databases is spreading in all fields. However, as the amount of data increases, the increase in data search time has become a problem. Particularly, in the arbitrary match search, since a whole character string search process is conventionally required, much search time is required.

FIGS. 6 and 7 are diagrams for explaining a conventional search method, and the conventional search method will be described below with reference to the drawings.

FIG. 6 is a diagram showing an example of the structure of a database to be searched, and this database is composed of five records R1 to R5.

Each of the records R1 to R5 is an index word 5
1, a set of attributes (a1, a2, ..., Am) 52, and a record key 53.

The record key 53 is a headline used when performing logical operation processing on the attribute value and updating the record, and has a one-to-one correspondence with the record. In the case of this example, DBK-1 to DBK-5 are given as record keys 53 to the respective records R1 to R5.

The index word 51 is a keyword provided for facilitating the interface with the database user. In the case of this example, the records R1, R2,
R3, R4, and R5 are provided with "aiueo", "iue", "kakiueo", "kiue", and "sis" as index words 51, respectively. Although there is only one index word in each record for simplification of description, one record generally has a plurality of index words. Also, in this example, each record R1
The R5 index words are all different, but different records may have the same index word.

FIG. 7 is a diagram showing an example of the structure of an index that has been conventionally used when searching the database shown in FIG. 6, and is composed of an index word 61 and a record key 62.

In the index word 61, the index words "aiueo", "iue", "kakiueo", "kiue", "sasis" of the records R1, R2, R3, R4 and R5 in the database shown in FIG. Stored in complete form. Also,
The record key 62 has each record R1, R2, R3, R
4, R5 record keys DBK-1, DBK-2, DB
K-3, DBK-4, and DBK-5 are stored in correspondence with the index words "aiueo", "iue", "kakiueo", "kiue", and "sis". Note that the index words 61 in the index are usually sorted in ascending order. If the index words are character strings other than numbers as shown in FIG. 7, they are sorted in the Japanese syllabary order, for example.

Next, a conventional search method will be described with reference to FIGS.

First, the operation when performing a prefix match search will be described.

In the prefix match search, an index word having a search word at the beginning is to be searched. If the search word "Kakiueo" is specified, the column of the search word 61 in the index of FIG. 7 is searched. Then, the search word "Kakiueo" is searched for, and the record key "DBK-3" stored in the column of the record key 62 is acquired correspondingly. afterwards,
From record R1 to R5 in the database shown in FIG. 6 to record R3 having the above record key "DBK-3"
Select. Here, since the index characters of the index of FIG. 7 are sorted in ascending order, it is possible to significantly reduce the search time by performing a binary search.

Next, the operation when performing an arbitrary match search will be described.

In the arbitrary match search, all index words including a search word in an arbitrary part are to be searched. For example, when performing an arbitrary match search with the search word "Gijutsu", "Koukyu" including "Gijutsu" All index terms such as “Gijutsukaihatsu” and “Dokubokujijutsukaihatsu” are searched.

Now, for example, if "ueo" is specified as the search word for performing the arbitrary match search, the column of the index word 61 of the index of FIG. 5 is searched, and the search word "ueo" specified at an arbitrary position is searched. Find all the search terms that include ". Here, since the index word 61 is sorted with respect to the complete character string, the binary search cannot be applied to search for the search word included in any part of the index word. Therefore, when performing an arbitrary match search, conventionally, the entire search is performed from the end of the index, and the record key "DBK-1" with the index word "aiueo" and the record key "DBK-3" with the index word "kakiueo" are used. It was necessary to find out.

[0016]

As described above, the conventional index is created with the prefix search in mind, and since the binary search cannot be performed when performing the arbitrary match search, the number of index words is small. When performing an arbitrary match search in 100,000 to several million practical databases, there is a problem that the search time becomes very long.

An object of the present invention is to provide an arbitrary match search method capable of significantly shortening the search time in the arbitrary match search.

[0018]

In order to achieve the above object, the present invention provides (A) a database composed of a plurality of records each having an index word, and each character in the index word is the first character from the index word. And an index word extraction processing means for associating the extracted arbitrary match search key with the record key of the record containing the extracted index word. By sorting the arbitrary match search keys extracted by the index word extraction processing means and associated with the record keys, the arbitrary match search keys associated with the record keys are arranged in a predetermined order. By inputting a sort processing means for creating an arbitrary match search index and an arbitrary match search word, the arbitrary match search index is binary-searched and Find any match search key that matches the search term and the prefix match, but provided a search means for outputting a record key corresponding to any matching search key searched.

Further, according to the present invention, in order to further shorten the search time, (B) a database composed of a plurality of records each having an index word, and each character in the index word from each of the index words is set as the first character. Index word extraction processing means for extracting a rearward character string as an arbitrary match search key, and associating the extracted arbitrary match search key with a record key of a record including the extracted index word, and the index word A set in which the arbitrary match search keys extracted by the extraction processing means and associated with the record key are sorted to sort the arbitrary match search keys associated with the record key in a predetermined order. Of the arbitrary matching search keys included in the set created by the sorting processing means and the forward matching arbitrary matching search keys are merged. And a merge processing means for creating an arbitrary match search index in which a merged arbitrary match search key that is associated with the record key and an unmerged arbitrary match search key are arranged in a predetermined order, and an arbitrary match A search for inputting a search word to perform a binary search on the arbitrary match search index, find an arbitrary match search key that prefix-matches the arbitrary match search word, and output a record key corresponding to the found arbitrary match search key. And means are provided.

[0020]

In the configuration of (A), the index word extraction processing means extracts and extracts a backward character string from each index word with each character in the index word as a leading character as an arbitrary match search key. The arbitrary match search key and the record key are associated with each other.

Further, in the sort processing means, the arbitrary match search key extracted by the index word extraction processing means and associated with the record key is sorted, and associated with the record key. An arbitrary match search index in which arbitrary match search keys are arranged in a predetermined order is created.

When the arbitrary matching search word is input, the searching means performs a binary search on the arbitrary matching search index created by the sort processing means, finds an arbitrary matching search key that prefix-matches the arbitrary matching search word, and finds the arbitrary matching search key. Outputs the record key associated with the match search key.

In the configuration of (B), the merge processing means is provided for the set in which the arbitrary match search keys associated with the record keys created by the sort processing means are arranged in a predetermined order. An arbitrary match search index is created by merging arbitrary matching search keys that are prefixed and matching the record key with the merged arbitrary match search key and the unmerged arbitrary match search key in a predetermined order. create.

[0024]

Embodiments of the present invention will now be described in detail with reference to the drawings.

FIG. 1 is a block diagram of an embodiment of the present invention, in which a search means 1, an arbitrary match search index 2 and
It comprises a database management system 3 and an arbitrary match search index creating means 4.

The arbitrary match search index 2 has an arbitrary match search key 21 and a record key 22, as shown in FIG.

Each column of the arbitrary match search key 21 has an arbitrary match search key WK-i (i = 1, 2, ..., P), and each column of the record key 22 has an arbitrary match search key WK-i. Record key DBK-j (j = 1, 2, ..., Of record)
q) is stored.

In the example of FIG. 2, there are three records having the arbitrary match search key WK-1, and the record key is DBK.
-1, DBK-2, and DBK-3 are shown. The other lines show the same.

The search means 1 searches the field of the arbitrary match search key 21 of the arbitrary match search index 2 to find an arbitrary match search key having a character string that prefix-matches the input search word, and finds the arbitrary match search key found. Corresponding to, the record key stored in the arbitrary match search index 2 is output to the database management system 3.

The database management system 3 includes a database composed of the records R1 to Rn and a database management function. The database management system 3 receives the record key output from the search means 1 and displays the attribute of the record having this record key. Output.

Each record R1 constituting the database
Rn is an index word 31, an attribute set 32, and a record key 3
3 and 3.

The arbitrary match search index creating means 4 is for creating the optional match search index 2, and comprises an index word extraction processing means 41, a sort processing means 42, and a merge processing means 43.

Next, the operation of this embodiment will be described. In the following description, the number of records R1 to Rn in the database management system 3 is 5 (n
= 5), and the contents of the records R1 to R5 are the same as those of the records R1 to R5 shown in FIG. 6, respectively.

First, the operation of the arbitrary match search index creating means 4 will be described.

When a start instruction is added from the database management system 3 to the index word extraction processing means 41 in the arbitrary match search index creation means 4, a record R1 is issued.
~ For each of the index words 31 of R5, a process of extracting a backward character string having each character in the index word as a first character as an arbitrary match search key, and further extracting it to the extracted arbitrary match search key The process of adding the record key of the record including the index word is performed. The database management system 3 outputs the start instruction when the database is updated.

For example, by performing the above-mentioned processing on the index word "aiueo" of the record R1, the arbitrary matching search keys "aiueo", "iueo", "ueo", "eo", and "o" are extracted and extracted. The record key DBK-1 of the record R1 is added to each of the generated arbitrary match search keys.
Is added.

By performing the above processing on the index words of all the records R1 to R5, a set of arbitrary matching search keys to which the record keys shown in FIG. 3 are added can be obtained.

The sort processing means 42 sorts in ascending order (in the order of Japanese syllabary) with respect to the arbitrary match search keys to which the record keys in the set of FIG. 3 created by the index word extraction processing means 41 are added.
Do.

As a result, the set shown in FIG. 4 is obtained.

The merge processing means 43 is a sort processing means 42.
The following processing is performed on the set of FIG.

The merge processing means 43 first selects an arbitrary matching search key at the head of the set, and searches for an arbitrary matching search key that prefix-matches it.

If the forward matching arbitrary matching search key cannot be found, the selected arbitrary matching search key is stored in the head area of the arbitrary matching search key 21 of the arbitrary matching search index 2 and the selected arbitrary matching search is performed. The record key added to the key is stored in the head area of the record key 22 of the arbitrary match search index 2.

If an arbitrary match search key that matches the prefix can be found, the one having the largest number of characters among the searched arbitrary match search keys is stored in the head area of the arbitrary match search key 21 of the arbitrary match search index 2. At the same time, all the record keys added to the above-mentioned forward matching arbitrary matching search key are stored in the head area of the record key 22 of the arbitrary matching search index 2.

In the case of the set shown in FIG. 4, since the arbitrary matching search key at the head is "aiueo" and there is no arbitrary matching search key prefixed with it, the arbitrary matching search index 2 as shown in FIG. Arbitrary match search key 2
Arbitrary match search key "aiueo" in the first area
In the head area of the record key 22, the record key "DBK
"-1" is stored.

After that, the merging means 43 selects the unprocessed arbitrary match search key in the set which is closest to the head, and performs the same process as described above.

In the case of the set of FIG. 4, since the closest arbitrary match search key among the unprocessed arbitrary match search keys is "Iue", the arbitrary match search key "Iue" is prefixed to it. Iueo "is sought out.
Moreover, since the arbitrary match search key having the largest number of characters among the prefix-matching arbitrary match search keys is “Iueo”, the arbitrary match search key is searched in the second area of the arbitrary match search key 21 as shown in FIG. The key "Iueo" is stored, and the record key "D" added to the arbitrary match search keys "Iueo" and "Iue" is stored in the second area of the record key 22.
BK-1, DBK-2 "is stored.

Thereafter, the above-described processing is performed until the unprocessed arbitrary match search key is exhausted, and the arbitrary match search index 2 shown in FIG. 5 is created.

Next, the operation when performing an arbitrary match search will be described.

When an arbitrary matching search word is input, the searching means 1 performs a binary search on the column of the arbitrary matching search key 21 of the arbitrary matching search index 2 to find an arbitrary prefix that matches the input arbitrary matching search word. The matching search key is searched for, and the record key stored in the column of the record key 22 corresponding to the searched arbitrary matching search key is output to the database management system 3.

When the record key is added from the search means 1, the database management system 3 outputs the record having the record key.

Now, for example, if "u" is input to the search means 1 as an arbitrary match search word, the search means 1 will use the arbitrary match search key 2 of the arbitrary match search index 2.
Performs a binary search on the column 1 and searches for an arbitrary match search key "Ueo" that prefix-matches the arbitrary match search word "Wa"
And the record keys "DBK-1", "DBK-2", and "DBK-" stored in the column of the record key 22 in association with the found arbitrary match search key "WEO".
3 ”and“ DBK-4 ”are output to the database management system 3.

In the above-described embodiment, the processing result of the merge processing means 43 is the arbitrary match search index 2, but the processing result of the sort processing means 42 (the set shown in FIG. 4) is the arbitrary match search index. It can also be 2. In this case, since the merge has not been performed, the number of items in the arbitrary match search index 2 is large, and the merge processing means 43 is used.
Although the search speed is slower than when the processing result of (1) is set to the arbitrary match search index 2, the binary search can be performed in the arbitrary match search, so the search time is very short compared to the conventional example. Become.

[0053]

As described above, the present invention is an arbitrary match search in which the arbitrary match search keys obtained by extracting a backward character string starting from each character in the index word from each index word are sorted. Since the arbitrary match search is performed using the index, and the binary search can be performed also in the arbitrary match search, there is an effect that the search time in the arbitrary match search can be shortened.

Further, according to the present invention, since the merge processing means merges the prefix matching arbitrary matching search keys into one, it is possible to reduce the number of items of the optional matching search index, and thus further shorten the searching time. There is an effect that can be.

[Brief description of drawings]

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

FIG. 2 is a logical configuration diagram of an arbitrary match search index 2.

FIG. 3 is a diagram showing an example of a processing result of an index word extraction processing means 41.

FIG. 4 is a diagram illustrating an example of a processing result of a sort processing unit 42.

FIG. 5 is a diagram showing an example of a processing result of a merge processing unit 43.

FIG. 6 is a diagram showing a configuration example of a database.

FIG. 7 is a diagram showing a configuration example of an index that has been conventionally used.

[Explanation of symbols]

 1 ... Search means 2 ... Arbitrary match search index 21 ... Arbitrary match search key 22 ... Record key 3 ... Database management system 31 ... Index word 32 ... Attribute set 33 ... Record key 4 ... Arbitrary match search index creation means 41 ... Index word Extraction processing means 42 ... Sort processing means 43 ... Merge processing means

Claims (2)

[Claims] 1. A database composed of a plurality of records having index words, and a character string at the back of each index word having each character in the index word as a leading character is extracted as an arbitrary match search key and extracted. Index word extraction processing means for associating the arbitrary match search key with the record key of the record containing the extracted index word, and the association with the record key extracted by the index word extraction processing means Sort processing means for creating an arbitrary match search index in which the arbitrary match search keys associated with the record key are arranged in a predetermined order by sorting the arbitrary match search keys. Is input, a binary search is performed on the arbitrary match search index to find an arbitrary match search key that prefix-matches the arbitrary match search word. An arbitrary match search method, comprising: a search unit that outputs a record key corresponding to the found arbitrary match search key. 2. A database composed of a plurality of records having index words, and a character string behind each index word having each character in the index word as a leading character is extracted as an arbitrary match search key and extracted. Index word extraction processing means for associating the arbitrary match search key with the record key of the record containing the extracted index word, and the association with the record key extracted by the index word extraction processing means Sort processing means for creating a set in which the arbitrary match search keys associated with the record keys are arranged in a predetermined order by sorting the selected arbitrary match search keys, and the sort processing means Of the arbitrary match search keys included in the set, the forward matching arbitrary match search keys are merged to be associated with the record key. Merge processing means for creating an arbitrary match search index in which a paged arbitrary match search key and a non-merged arbitrary match search key are arranged in a predetermined order; Arbitrary match search characterized by including a search means for performing a binary search on the search index to find an arbitrary match search key that prefix-matches the arbitrary match search word and output a record key corresponding to the found arbitrary match search key. method.