JPH1196170A - Database creation method, information search method, information search device, and recording medium - Google Patents

Abstract

(57) [Summary] [Problem] It is possible to suppress occurrence of a false drop when performing information retrieval using a signature in accordance with the frequency of appearance of a keyword in a text, suppress overhead of a storage area,
Provided are a database creation method, an information search method, and an information search device capable of performing a high-speed match search. A partial character string is cut out from a keyword in input information, and a bit string of a predetermined length assigned to the partial character string based on the frequency of appearance of the cut out partial character string in the keyword To generate a first signature for the input information, and store the input information in association with the generated first signature to create a database.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to an information search method using a signature (bit string) for performing an efficient search of a database and an information search apparatus using the same.

[0002]

2. Description of the Related Art For example, information retrieval systems for processing text information can be broadly classified into two types: a full-text retrieval system in which an arbitrary character string is to be searched, and a system in which retrieval is performed by using a keyword.

[0003] In a method of performing a search using a keyword, an auxiliary database relating to the keyword is created in advance to improve the search speed. As an auxiliary database to be created, a method of creating an inverted file that records the position in the text where each keyword appears in each keyword, and a signature that briefly expresses the information of the keyword that appears in each text record There is a method that uses a file.

[0004] The method using the transposed file enables high-speed retrieval, but has the problem that the size of the transposed file becomes enormous and the efficiency of the storage area is reduced. In the method using a signature file, information in one text record is compactly represented as a signature, which is advantageous in terms of a storage area, but causes a problem in search speed. However, the simple method has many possibilities such as parallel execution on a parallel computer, and much research and development has been continued.

Here, the signature file method will be described with reference to FIG. First, terms used in the following description will be described. A record is a collection of words (words). Of the words, the search target is particularly called a keyword. In the signature file method, a bit string called a signature is associated with each keyword. The correspondence to the bit string is called a bcw function (binary code
e word). In FIG. 1, three keywords “keyword1” and “keyword1” appearing in a record are shown.
Bit strings having a length of 10 correspond to "2" and "keyword3". Here, it should be noted that in each of the bit strings, three bits are "1" and the remaining bits are "0".

[0006] The length of the bit string is represented by the bit length (in this case, "1"
0 ”), and the number of bits that become“ 1 ”in this bit string (in this case,“ 3 ”) is called a weight. The signature for a record is obtained by taking the logical sum of all the signatures of the keyword appearing in the record for each bit.

A search method using this method will be described with reference to FIG. That is, the search term (in this case, “keyword
3)), a bit string is created using the same bcw function as before. Then, a record having a signature in which all bit positions of “1” in the bit string are “1” is output as a search result. That is,
The logical product of the search word bit string and the record bit string is
If it matches the bit string of the search word, the text is output as the search result. As described above, since the search can be performed by the logical operation of the bit string, the search by the signature file has a sufficiently high speed.

However, this method has a problem called false drop. That is, as shown in FIG.
Since the bitwise OR of “keyword1” and “keyword2” completely includes the bit string of “keyword3”, “keyword1” and “keyword2”
Although the record including “2” does not include “keyword3”, it becomes a search output for “keyword3”.

In order to eliminate false drops, it is necessary to apply a full-text search algorithm, which causes a reduction in the search speed of the signature file method. How to reduce false drops as described above is an important issue when implementing a search system using signature files. This corresponds to b
This is nothing but the problem of optimally designing the cw function. The design parameters at this time are (1) bit length,
There are three types: (2) weight, (3) a given bit length, and a specific method for associating a bit string with the weight. Next, a conventional technique will be described for these determination methods.

Reference 1 (Roberts, CS,
Partial-match retrieval v
ia the method of superimp
used codes, Proc. IEEE 6
7, Dec. , 1624-1642, 197
9. In (2), mathematical analysis of the bcw function was performed under the following preconditions, and design guidelines on bit length and weight were given.

(Precondition 1) The number of different keywords appearing in each record is constant. (Precondition 2) All keywords appear with equal probability. Under these two preconditions, the probability that a record having a bit length b, a weight w, and the number of keywords r false-drops is given by the following equation.

[0012]

(Equation 1) This equation can be approximated by the following equation when w is sufficiently smaller than m.

[0013]

(Equation 2)

When the value of this expression is minimum, that is, the false drop is minimum when w / b = 0.5, and exactly ち ょ う ど of the bits are “1” in the signature of the record. Is set so that
Since w / b indicates the ratio of bits that become "1" in the signature, it is referred to as the bit ratio hereinafter.

Note that the code length b of the signature is directly related to the storage area size. Therefore, it has been a conventional method to employ the optimum values of b and w while estimating the disk usage amount permitted for the system and the search speed reduction for removing the false drop from the above equation.

In the above analysis, two preconditions are assumed: the number of keywords appearing in each record is constant (precondition 1), and the appearance probabilities of keywords are equal (precondition 2). Was. However, in a general text database, the number of keywords appearing in records varies widely. If the number of records is fixed by forcibly defining the record format, practical operation becomes difficult. Furthermore, as is well known, in natural languages (Japanese, English, etc.), the analysis of the appearing words is extremely biased. After all, from the above simple analysis result, it is not possible to obtain the optimum design value for a practical text database.

Therefore, attempts have been made to relax the preconditions 1 and 2 to a practical level.
First, regarding precondition 1, a method of widely dividing a record into logical blocks in which the number of keywords is fixed has been widely adopted.

For the precondition 2, see Reference 2 (Ch
un-Wu Roger Leng, and Dik
Lun Lee: Optimal Weight As
signal for Signature Ge
neration, ACMTransactions
on Database Systems, Vol. 1
7, no. 2, 1992. ), Instead of simply dividing the record so that the number of keywords is constant, the signature for each divided record is “1”.
A method has been proposed in which record division is performed so that the number of bits set to the same is the same. This method is a therapeutic solution to the problem of keyword uneven distribution, and differs from the essential solution. For example, if the bit set to “1” by a high-frequency keyword is the same as the bit set to “1” by a medium-frequency keyword or less, a false drop when searching with such a medium-frequency keyword or less Becomes large. In a general text information database, a search using medium-frequency keywords is often more important than a search using high-frequency or low-frequency keywords, so this conventional technique is not sufficient.

Next, a description will be given of the prefix matching search.
The prefix search is performed by, for example, giving a search expression “comp” to “computer”,
The search is performed by a keyword such as “rs” or “computa- tion” where the front part of the keyword matches the search expression “comp”, which is an important function of the information search system. However, when performing a prefix match search by a simple signature method, it is necessary to generate a keyword using “comp” as a partial character string in front using a dictionary or the like, and perform a search for each of the generated keywords. And an increase in storage area overhead for storing dictionaries. Therefore, an improved system according to the prior art has been proposed.

Reference 3 (C. Fallouts: A
access Methods for Text, AC
M Computing Surveys, Vol. 1
7, no. 1, 1985. Has proposed a method of performing a forward match search without using a dictionary (that is, without a storage area overhead). However, simply applying the method of Reference 3 causes an increase in false drop, which is not practical. The scheme that enables the head-match search has no practical meaning unless it is used together with a method for reducing false drops.

In the index type creating apparatus described in Japanese Patent Application No. 7-121065, an invention is provided which extends the concept of a keyword in an information search system using signatures. In other words, a method is used in which a continuous character string frequently appearing in a text is identified based on statistical data, and is used as a search unit instead of a keyword. In this method, since a frequently appearing character string is used as a keyword, it has the meaning of improving the search ability for such frequently appearing character strings. However, the present invention focuses on a method of finding a frequently appearing character string, and uses a conventional invention as a method for reducing the number of false drops. Therefore, if the frequency of occurrence of frequently appearing character strings is biased, false drops may be increased and practical advantages may be lost.

In the information retrieval system described in Japanese Patent Application No. 3-190609, the structure of an index for a keyword is changed in accordance with the state of use of the system. This aims to gradually speed up the search time for keywords that are used more frequently, and collects usage frequency information using a neural network and relocates keywords inside the keyword storage device. It is composed of The present invention has a problem that high speed cannot be achieved unless the system is sufficiently used. Furthermore, when a plurality of users use the same database, there is a problem that correspondence to a case where different users have different keyword tendencies is not discussed.

In a document retrieval apparatus using signatures described in Japanese Patent Application No. 6-32441, a method for reducing the storage area size by devising a method for storing signatures is provided. The present invention is independent of the present invention because it does not relate to the reduction of the number of false drops or the adjustment of the signature creation method according to the data content.

In addition, a number of improved signature file methods according to the prior art have been proposed. For example, reference 4 (Dik Lun Lee, Young Man
Kim, and Gaurav Patel: Eff
client Signature File Met
hods for Text Retrieval, I
EEE Trans. on Knowledge an
d Data Eng. , Vol. 7, no. 3, 19
95. ) Describes several schemes using signatures and their mathematical analysis. For example, not only using signatures for records, but also considering signatures for a plurality of signatures, a method of performing a search at another stage has been proposed. It becomes possible. However, it is independent of the method for reducing the number of false drops and can be used with the device of the present invention.

[0025]

As described above,
In an information retrieval system using a conventional signature, sufficient measures have not been taken against false drops in accordance with the number of keywords appearing in a record and variations in the frequency of appearance of each keyword.

Therefore, the present invention can suppress the occurrence of a false drop when performing an information search using a signature in accordance with the frequency of occurrence of a keyword in a text.
It is an object of the present invention to provide a database creation method and an information search method capable of suppressing a storage area overhead and performing high-speed head-on search, and an information search apparatus using the same.

[0027]

According to a database creation method of the present invention, a partial character string is cut out from a keyword in input information, and the appearance frequency of the cut out partial character string in the keyword is extracted. Generating a first signature for the input information using a bit string of a predetermined length assigned to the partial character string based on the input information and the generated first signature with the generated first signature. By creating a database by storing in association with each other, it is possible to suppress the occurrence of false drops when performing information search using signatures, for example, according to the appearance frequency of keywords in text, and to reduce the overhead of the storage area , Fast match search can be performed.

An information retrieval method according to the present invention (claim 2) is a method for retrieving a database in which information and a first signature corresponding to the information are stored in association with each other. And a second character string corresponding to the search information is extracted from each of the extracted partial character strings by using a bit string assigned in advance based on the appearance frequency of the partial character string in the keyword.
By generating a signature of the second signature and comparing the generated second signature with the first signature in the database, by searching the database for information related to the search information, for example, According to the appearance frequency of the keyword, it is possible to suppress the occurrence of a false drop when performing the information search using the signature, to suppress the overhead of the storage area, and to perform the forward match search at high speed.

The information retrieval method according to the present invention (Claim 3) is to cut out a partial character string from a keyword in the input information, and based on the appearance frequency of the cut out partial character string in the keyword. Generating a first signature for the input information by using a bit string of a predetermined length assigned to, and storing the input information in association with the generated first signature. Create a database, and when searching for information, cut out partial character strings from the keywords in the input search information,
For each of the cut-out partial character strings, a second signature corresponding to the search information is generated using a bit string assigned in advance based on the appearance frequency of the partial character string in the keyword. 2 by comparing the signature of the second signature with the first signature in the database, and searching the database for information related to the search information. It is possible to suppress the occurrence of a false drop when performing a searched information search, suppress the overhead of a storage area, and perform a fast match search at a high speed.

[0030] The information retrieval apparatus of the present invention (claim 4) includes a cutout unit for cutting out a partial character string from a keyword in the input information, and the appearance frequency of the partial character string cut out by the cutout unit. Allocating means for allocating a bit string of a predetermined length to the partial character string; generating means for generating a first signature for the input information using the bit string allocated to the partial character string; Means for creating a database by storing the obtained information in association with the first signature generated by the generating means, extracting a partial character string from a keyword in the input search information, and extracting each partial character A second signature corresponding to the search information is generated using the bit string generated by the generation means for the column, and the generated second signature is generated. By collating the first signature of the a catcher database, and retrieving means for retrieving information related to the search information from the database,
By providing, for example, according to the frequency of appearance of the keyword in the text, it is possible to suppress the occurrence of false drop when performing information search using the signature,
The overhead of the storage area can be suppressed, and a forward match search can be performed at high speed.

[0031]

Embodiments of the present invention will be described below with reference to the drawings. FIG. 3 shows a configuration example of the information search device according to the present embodiment. In FIG. 3, a solid line indicates a data flow at the time of storing information, and a broken line mainly indicates a data flow at the time of retrieval.

First, each component of FIG. 3 will be described along the flow of data when storing information. The master database 5 is for storing the actual data of each record together with its identifier. Each record is
In addition to textual information, data of various formats such as graphic information and audio information that can be handled by a computer may be included.
The structure of the master database 5 is realized using a conventional technique. When storing information input via the input unit 1 as a record in the information search apparatus of the present invention, the record is first stored in the master database.

FIG. 4 shows a specific example of information input through the input unit 1 used in the description of the present embodiment, that is, a record. In parallel with the storage of the record in the master database 5, the keyword extracting unit 3 extracts a keyword from the text information of the record shown in FIG. 4, for example, as shown in FIG.

Further, the partial character string cutout unit 4 divides each of the keywords as shown in FIG. 5 into a partial character string of, for example, two characters as shown in FIG. FIG.
5 is a flowchart illustrating an example of a procedure of a partial character string cutout process in the partial character string cutout unit 4. In the partial character string cutout unit 4, for example, the code weight (the number of bits that become “1” in the bit string) w is “5” and the length k of the partial character string to be cut out is “2” (steps S1 to S1). S2). Two characters at a time starting from the first character of the keyword (i = 1), that is, the first and second characters,
The third and third characters,..., The fifth and sixth characters are cut out until the position of the first character of the two-letter character string to be cut out becomes i = 5 (steps S3 to S3). In step S7, a combination <XX, i> of the partial character string "XX" and the appearance position (the first character from the beginning) i of the first character of the partial character string in the keyword is output (step S4). .

For example, in the keyword "Objects", <Ob, 1> indicates that the partial character string "Ob" appears first, and <bj, 2> indicates the partial character string "bj".
Indicates that it appears second.

The partial character string cut out in this way is given to the signature creating section 9. The partial character cutout unit 4 further stores the frequency of occurrence of the combination of the partial character string and its appearance position in the record in the statistical information database 7 as statistical information of the partial character string. I have.

The statistical information data of the partial character string stored in the statistical information database 7 is used when a signature of the partial character string is created by the signature creating database updating unit 11 (described later).

The signature creation section 9 refers to the signature creation database 6 based on the partial character string cut out from the keyword, and creates a signature of the keyword and a signature of the record. Here, for example, the signature of the partial character string, the keyword, and the text is a 10-bit bit string.

The signature creation database 6 determines which bit position is "1" for each combination of the partial character string and its appearance position (that is, the signature for the combination of the partial character string and its appearance position). Is stored.

Referring now to FIG. 8, a procedure for creating a signature of a keyword in the signature creating section 9 will be described. The signature creation database 6 stores a set <xx, i> of the partial character string cut out by the partial character string cutout unit 4 and its appearance position and “1” of 10 bits corresponding to the set. Are stored as a pair (i.e., the signature for the substring). For example, as shown in FIG. 8, in the keyword “Objects”, of the 10-bit bit string, the 10th bit, <bj,
3> bit for <2>, 5 for <je, 3>
For the bit, <ec, 4>, the seventh bit, <c
A signature such that the second bit is “1” is assigned to t, 5>. In this manner, the signature for the keyword is created by taking the bitwise logical sum of the predetermined signature for the partial character string and its appearance position. For example, in this case, the signature of the keyword “object” is “011010100”.
1 ".

The signature of the record is created by taking the logical sum of the signatures for all the keywords in the record for each bit. The signature of the record created by the signature creation unit 9 is stored in the signature storage database 8.
Is accumulated in For example, the signature is stored in combination with the same identifier as the identifier attached to the record previously stored in the master database 5.

As a storage method at this time, it is possible to use a conventional technique (for example, Reference Document 4) and make it possible to speed up the retrieval. A method of assigning a signature to a partial character string stored in the signature creation database 6 and its appearance position will be described later.

Next, extraction of a partial character string and creation of a signature will be described in more detail. One of the objects of the present invention is to reduce the false drop of a search by a signature in a text database in which the frequency of appearance of keywords in text is uneven. In the prior art, a signature was created using a random number from a keyword, but the signature was greatly affected by uneven distribution of the keyword. To statistically control the signature creation by creating a database for the keywords themselves, it becomes necessary to store a huge number of keywords. Even in a medium-sized dictionary,
For example, the Kodansha English-Japanese dictionary has about 90,000 headwords and the Obunsha English-Japanese-Chinese dictionary has about 100,000 headwords. It is not practical because it involves overhead. In addition, since a database that stores a large number of keywords is accessed at the time of searching, a reduction in search speed is also a problem.

Therefore, in the present invention, a partial character is cut out from a keyword, and a signature for the partial character string is created. The number of possible combinations of substrings is based on the fact that the number can be adjusted freely by shortening the length of the substrings. For example, if the total number of character types is “50”, the length is “2”.
Is only "250". The problem of how long the partial character string should be may be determined by checking the size of the storage area. Further, a signature is created not only for the partial character string itself but also for a combination with information on the appearance position of the partial character string such as the number of the partial character string in the keyword as in the present embodiment. You may do so.

In the case of this embodiment, a partial character string having a length of "2" is used in consideration of its appearance position.
In this case, the character type to be handled is “50”, and as the appearance position, in the present embodiment, only the fifth partial character string from the beginning of the keyword is handled. Therefore, 50 ・ 50 ・
It is sufficient to prepare a table having 5 = 12,500 kinds of headings. Therefore, there is an effect that the overhead of the storage area can be reduced when performing the forward matching search.

Note that the longer the bit length of the signature for the partial character string is, the more the number of false drops can be suppressed, but the larger the storage area is. Therefore, when determining the bit length of the signature, it is necessary to determine the optimum value for the device in consideration of these.

Next, the signature creation database updating unit 11 will be described. In the signature creation database updating unit 11, the appearance frequency of the combination of the partial character string stored in the statistical information database 7 and its appearance position (that is, the appearance frequency of the partial character string in the keyword or the partial character string The signature (specifically, for example, which bit position in 10 bits is set to “1”) for the combination of the partial character string and the appearance position is determined with reference to the statistical information data of the appearance position. ), And the signature creation database 6 and the signature storage database 8 are updated based on the created one.

The method of determining the bit position for the combination of the partial character string and its appearance position follows the principle that the probability that each bit is set to "1" is equal. The method will be described below.

It is possible to easily collect statistical information of the appearance frequency of a partial character string and its appearance position in a record by using a conventional technique. For example, a table in which a partial character string and an appearance position are set as a heading is created, and each time an output from the partial character string cutout unit 4 is obtained, the number of appearances may be counted up by “1”. The number of appearances counted in this way is stored in the statistical information database 7 as statistical information data on the combination of the partial character string and its appearance position. By referring to the contents of the statistical information database 7, the appearance frequency of the partial character string in the keyword at any time can be calculated immediately.

The flowchart shown in FIG. 9 shows an example of the procedure of the signature creation processing of the partial character string in the signature creation database update unit 11. According to this flowchart, each bit in 10 bits is almost equally probable. Is "1"
The bit position in 10 bits for each partial character string can be determined as follows.

In the flowchart of FIG.
Each bit position of the 0-bit signature (i = 1 to 10)
Are initialized to "0" (steps S11 to S13). And
A partial character string having the highest appearance probability x is selected from the statistical information database 7 (step S14), and the bit position to be set to “1” in the 10-bit signature of the partial character string at that time is determined by the 10-bit signature. Probability p that will be "1" for each bit position (i = 1 to 10)
[I] is the lowest bit position (steps S15 to S15).
Step S16). When there are a plurality of bit positions having the lowest value of the probability p [i], an arbitrary bit position may be selected from them.

Then, the occurrence probability x of the partial character string is added to the probability p [j] of "1" at the bit position j of the assigned signature (step S1).
7). Next, a partial character string having the second occurrence probability is selected, and the signature 1 for the partial character string is selected as described above.
The bit position to be set to “1” in the 0 bit is set to 1 at that time.
Each bit position of the 0-bit signature (i = 1 to 10)
Is assigned to the bit position having the lowest probability p [i] of "1", and the occurrence probability x of the partial character string is added to the probability p [j] of "1" at that bit position. Similarly, in the same manner, partial character strings are sequentially extracted from the partial character string statistical database 7, and p [i]
Is repeated for all partial character strings (step S18), and a new signature created as a result is stored in the signature creation database 6, and Update the signature assigned to a string.

In this way, the position where one of the 10 bits of the signature is set to "1" may be determined for each partial character string. This may be performed, for example, at the timing designated by the user. Thereby, the performance of the information search device can be automatically improved.

In a general-purpose information retrieval apparatus, it is difficult to predict in advance what kind of record data is given. Therefore, the signature creation unit 9 creates a signature using an existing signature creation database 6 in the initial state. At this time, since the appearance probability of the partial character string is different from the record data actually input via the input unit 1, the false drop rate may increase. However, as long as the data stored in the master database 5 is small, the search time overhead does not matter even if the false drop is large.

As the addition of data to the master database 5 is continued and the size of the database is increased, the number of false drops is increased, and the problem of a decrease in search speed starts to be a problem. At this time, the signature creation database updating unit 11 uses the statistical information data of the partial character string collected in the statistical information database 7 in the data addition up to that time and uses the signature for the partial character string in accordance with the flowchart shown in FIG. Is created again, and the signature creation database 6 is updated.

The signature creation database update unit 11
Updates the signature creation database 6 and uses the updated signature creation database 6 to update the signatures of all records stored in the signature storage database 8 so far in the same manner as the description of the signature creation unit 9. And recreate. In the signature storage database 8, the re-created signature is replaced with the old signature, so that the procedure does not increase the size of the signature storage database 8.

Next, each component in FIG. 3 will be described along the flow of data at the time of information retrieval. From the search information included in the search instruction request input via the input unit 1, text information that can be a search condition is extracted by the question formula processing unit 2.

The question formula processing unit 2 prompts the user to input search information including text information that can be a search condition via the input unit 1 in an interactive manner with the user.

The text information extracted as a search condition by the question formula processing unit 2 is input to the keyword extracting unit 3 and subsequently to the partial character string extracting unit 4, and the keyword extracting and partial extracting are performed as in the case of storing information. The character string is cut out.

The signature creation unit 9 creates a signature for a partial character string of a keyword in text information as a given search condition, using the same signature creation database 6 used in the case of storing information. Do.

Next, the signature comparison device 10 compares the signature of the search condition created by the signature creation section 9 with the signature stored in the signature storage database 8, and if there is a record that matches both of them. , The identifier of the record is read, and the secondary search unit 1
Transfer to 2.

The secondary search unit 12 retrieves the actual data of the record from the master database 5 using the record identifier as a key, removes the false drop, and outputs it via the output unit 13.

The output unit 13 includes, for example, a printer device, a display device, a speaker device, and the like.
As described above, according to the above-described embodiment, the keyword in the information (record) input by the partial character string cutout unit 4 is divided into partial character strings. The appearance frequency is counted and stored in the statistical information database 7. When the signature generation unit 7 generates a bit string (signature) for the input information based on the bit string (signature of the partial character string) allocated to the partial character string stored in the signature generation database, the bit string is generated. The information is stored in the signature storage database 8 and the master database 5 in association with the input information. At the time of information search, the signature creation unit 9 generates a bit string for the search information input via the input unit 1,
The information is searched for by collating it with the bit string stored in the signature storage database 8. The signature creation database update unit 11 assigns a bit string of a predetermined length to the partial character string based on the frequency of occurrence of the partial character string stored in the statistical information database 7 in the keyword, and accordingly, the signature By updating the signature stored in the storage database 8,
Even for a text database having a special keyword appearance frequency different from a general keyword appearance frequency, the occurrence of a false drop can be suppressed in accordance with the number of keywords appearing in the text and variations in the appearance frequency of each keyword. In addition, since a signature is assigned to a combination of a partial character string (for example, two characters) in a keyword and an appearance position in the keyword, overhead of a storage area can be suppressed when performing a forward match search,
High-speed information retrieval can be performed.

It should be noted that the question formula processing unit 2, the keyword extraction unit 3, the partial character string extraction unit 4, the signature creation unit 9, the signature comparison unit 10, the signature creation database update unit 11, and the secondary search described in the above embodiment. Part 12
The processing operation of the magnetic disk (floppy disk,
Hard disk, etc.), optical disk (CD-ROM, DV)
D, etc.), and can be stored in a recording medium such as a semiconductor memory and distributed.

[0065]

As described above, according to the present invention,
According to the frequency of appearance of the keyword in the text, it is possible to suppress the occurrence of a false drop when performing the information search using the signature, to suppress the overhead of the storage area, and to perform the forward match search at high speed.

[Brief description of the drawings]

FIG. 1 is an exemplary view for explaining a signature in an information search;

FIG. 2 is a diagram for explaining an information search method using a signature.

FIG. 3 is a diagram showing a configuration example of an information search device according to an embodiment of the present invention.

FIG. 4 is a diagram showing a specific example of record data.

FIG. 5 is a view showing an example of a keyword cut out from the record of FIG. 4;

FIG. 6 is a view showing an example of a partial character string cut out from the keyword in FIG. 5;

FIG. 7 is a flowchart for explaining a processing operation of a partial character cutout unit in FIG. 3;

FIG. 8 is an exemplary view for explaining a procedure for creating a signature of a keyword by the signature creating unit in FIG. 3;

FIG. 9 is a flowchart for explaining the processing operation of the signature creation database update unit in FIG. 3;

[Explanation of symbols]

 DESCRIPTION OF SYMBOLS 1 ... Input part 2 ... Question formula processing part 3 ... Keyword extraction part 4 ... Partial character string extraction part 5 ... Master database 6 ... Database for signature creation 7 ... Statistical information database 8 ... Signature storage database 9 ... Signature creation part 10 ... Signature Comparison unit 11: Signature update database update unit 12: Secondary search unit 13: Output unit

Claims (6)

[Claims] 1. A partial character string is cut out from a keyword in input information, and a predetermined length of a predetermined length assigned to the partial character string is determined based on the frequency of appearance of the cut out partial character string in the keyword. Generating a first signature for the input information using a bit string and storing the input information in association with the generated first signature to create a database; Method. 2. A method for searching a database in which information and a first signature corresponding to the information are stored in association with each other, wherein a partial character string is cut out from a keyword in the input search information. For each partial character string, a second signature corresponding to the search information is generated using a bit string assigned in advance based on the frequency of occurrence of the partial character string in the keyword, and the generated second signature and An information search method, wherein information related to the search information is searched from the database by matching the signature with a first signature in the database. 3. A partial character string is cut out from a keyword in input information, and a predetermined length of a predetermined length assigned to the partial character string is determined based on an appearance frequency of the cut out partial character string in the keyword. A first signature for the input information is generated using a bit string, the input information is stored in association with the generated first signature, and a database is created. A partial character string is cut out from the keyword in the input search information, and the search information is extracted by using a bit string assigned in advance based on the frequency of appearance of the cut out partial character string in the keyword. And generate a second signature corresponding to the generated second signature.
An information search method, wherein information related to the search information is searched from the database by matching the signature of (1) with a first signature in the database. 4. A extracting means for extracting a partial character string from a keyword in input information, and a predetermined length of the partial character string based on an appearance frequency of the partial character string extracted by the extracting means. Allocating means for allocating a bit string; generating means for generating a first signature for the input information by using the bit string allocated to the partial character string; and a generating means for generating the input information by the generating means. Means for creating a database by associating them with the signature of No. 1 and extracting a partial character string from a keyword in the input search information, and extracting a bit string generated by the generating means for each of the extracted partial character strings. And generating a second signature corresponding to the search information using the generated second signature.
A search unit that searches the database for information related to the search information by comparing the signature of the search with a first signature in the database. 5. A extracting means for extracting a partial character string from a keyword in input information, and a predetermined length of said partial character string based on an appearance frequency of the partial character string extracted by said extracting means. Allocating means for allocating a bit string; generating means for generating a first signature for the input information by using the bit string allocated to the partial character string; and a generating means for generating the input information by the generating means. Means for creating a database by storing the program in association with one signature, and a machine-readable recording medium recording a program for executing the program. 6. A extracting means for extracting a partial character string from a keyword in input information, and a predetermined length of the partial character string based on an appearance frequency of the partial character string extracted by the extracting means. Allocating means for allocating a bit string; generating means for generating a first signature for the input information by using the bit string allocated to the partial character string; and a generating means for generating the input information by the generating means. Means for creating a database by associating them with the signature of No. 1 and extracting a partial character string from a keyword in the input search information, and extracting a bit string generated by the generating means for each of the extracted partial character strings. And generating a second signature corresponding to the search information using the generated second signature.
A search unit for searching the database for information related to the search information by matching the signature of the first signature with the first signature in the database; and a machine-readable recording medium recording a program for executing the following.