JP3258063B2 - Database search system and method - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a database search system and method, and more particularly to a database search system and method for extracting necessary information from a database according to a plurality of conditions.

[0002]

2. Description of the Related Art When performing a condition search in a database search by a search for all properties, a predetermined search key is set, and the search key is applied to all properties to perform a search. For example, it is checked whether or not each property includes a search key, and properties including the search key are listed as search results.

In such a search, when a search is performed using a conditional expression (search expression) including a plurality of search keys, a conditional expression is formulated using a plurality of search keys, and the search is performed using the conditional expression. Is conventionally performed. For example, by keys A, B, C, and D, (A or B or C) and
A conditional expression such as D is created, and a search for all properties is performed using this expression.

[0004]

However, since such a search uses a conditional expression composed of a plurality of keys, the search time is extremely long, and the cost performance when the condition is not satisfied is low. Also, a similar conditional expression, for example, (A or B or C) and
When performing a search using a conditional expression such as E, there is a drawback that efficiency is low because partial logical conditions (A, B, or C) of the search already performed cannot be reused.

The present invention solves the above-mentioned drawbacks of the prior art, and enables a high-speed condition search regardless of the complexity of a conditional expression in a search based on a plurality of conditions, and enables the search results to be reused. It aims to provide a simple database search system.

[0006]

Means for Solving the Problems] database search system of the present invention, the j-th data C _i of the i-th property of the search _{target, j} and the i-th j-th data C _i in _property, near the _j A combination of a plurality of quantization amounts calculated based on the data C _{i, k} and a combination of a plurality of quantization amounts calculated based on the search key are compared, and all properties are searched based on the degree of matching. It is characterized in that it comprises a search means, a search result storage means for storing a search result by the search means, and a condition search means for performing a condition search using the search results stored in the search result storage means. In addition, the database search method of the present invention provides the j-th data C _{i, j} of the i-th property to be searched and the j-th data C in the i-th property.
A combination of a plurality of quantization amounts calculated based on the neighborhood data C _{i, k of i, j} and a combination of a plurality of quantization amounts calculated based on the search key are compared. It is characterized in that an ambiguous search corresponding to the search key is performed from all the properties, and a logical condition search is performed on the property list of the search result.

[0007]

According to the present invention, j of the i-th property to be searched is
Based on a search key and a combination of a plurality of quantization amounts calculated based on the _i- th data C _{i, j and} the neighborhood data C _{i, k} of the j-th data C _{i, j} in the i-th property. A comparison is made with the calculated combination of the plurality of quantization amounts, a search for all properties is performed based on the degree of matching, and the search result is stored. Next, a condition search is performed using the search result. Therefore, a search result based on a predetermined condition is stored, and a more complicated condition is searched using the search result. Therefore, a partial search result can be reused, and a high-speed condition search can be performed.

[0008]

FIG. 1 shows an embodiment of the system according to the present invention. As shown in FIG. 1, the present system includes a search unit 12, a search result list storage unit 14, and a property list condition search unit 16. The search unit 12 is a search key input unit 18
The search unit performs a search for all properties of the search target 10 as a database using a conditional expression including a predetermined search key input from the user.

For example, when the keys input from the search key input unit 18 are A and B as shown in FIG. 1, the search unit 12 performs a search using the conditional expressions A and B, and the result is a search result list. It is stored in the storage unit 14. In the example shown in the figure, the property number list searched by the conditional expression A is 3, 5, 10, and 20, and the property number list searched by the conditional expression B is 5, 10, 30. These property number lists are stored in the search result list storage unit 14 as search results.

The property list condition search unit 16 is a search unit that performs a search based on a more complicated conditional expression using the results stored in the search result list storage unit 14. For example, using the above search results based on the conditional expressions A and B, the conditional expression (A or
If you search by B) or (A and B)
The property list condition search unit 16 is a search result list storage unit 14
From the search results obtained by the conditional expressions A and B, and using these, the conditional expressions (A or B) or (A
and search by B).

In the case of the present embodiment, the result stored in the search result list storage unit 14 is, as described above, a conditional expression A
The property number list searched by is 3, 5, 10,
20, and the number list of the property searched by the conditional expression B is 5, 10, 30. Therefore, the conditional expression (A or
In the case of the search in B), the OR of these property number lists is obtained to obtain property number lists 3, 5, 10, and 2.
0 and 30 are obtained. Similarly, conditional expression (A and B)
In the case of the search, the AND of these property number lists is obtained, whereby property number lists 5 and 10 can be obtained.
The obtained results of the property number list are sent again to the search result list storage unit 14 and stored therein.

Therefore, using these lists, the property list condition search unit 16 further calculates (A or B or
A search using a conditional expression such as (C), (A or B or C) and E can be similarly performed.

According to this embodiment, the result of the search by the conditional expression including the predetermined search key as described above is stored in the search result list storage unit 14 as a property number list, and the complex combination of these keys is stored. When performing a search using a simple conditional expression, a condition search is performed using the stored article number list.

Therefore, in the case of a search based on a complex conditional expression, it is not necessary to perform a search on all the properties based on a complex condition, and thus the search time can be reduced. Further, since the search is performed by reusing the result of the partial condition search, the search efficiency is high.

The search system according to the present invention can be applied to various database searches. For example, the present invention can be applied to search for a conditional expression in the following data search system.

FIG. 2 is a data flow diagram of a pattern search system based on neighboring features showing an embodiment to which the present invention is applied. In this search system, a neighborhood feature is created in advance by omitting all phase information of events (information) from all target properties, and a search for all properties is performed for the data group. The search algorithm includes a learning step and a search step. In the learning step, a neighborhood feature amount matrix is created for each property. In FIG. 2, this corresponds to a step of creating a neighborhood feature amount matrix 30 from the search target 10 and storing it in the structure file 40. Also, in the search step, the same processing as in the learning step is performed on the search key to determine the neighboring feature amount of the search key, a matching operation is performed with the nearby feature amount of the property, and the matching degree (similarity degree) is determined for each property. Every time)
Is obtained. In FIG. 2, this corresponds to a step of performing a matching operation with the property data of the structure file 40 in the search S4 based on the search key 50 and outputting the result as in the evaluation result list 70 or the sorted list 80. . Hereinafter, each step will be described.

(1) Learning Step In FIG. 2, the search target 10 is, for example, Japanese, English,
Document data in German, French, Hebrew, Russian, etc., or quantized waveform numerical data, chemical structural formulas, genetic information, etc. For such a search target, first, normalization processing is performed by the normalization means S1. Generally, a search target is represented by a sequence of the minimum unit of information (a character such as an alphabet in a document, a real number at a certain time in a numerical chart, and the like). It is converted into an integer sequence of n gradations by some method. This is called data normalization.

For example, in the case of English document data, ASCII
By using the code table as it is, the following 25
It is realized as a numerical representation of six gradations. …… This is a pen. …… 84 ｜ 104 ｜ 105 ｜ 115 ｜ 32 ｜ 105 ｜ 115 ｜ 32 ｜ 97 ｜ 32 ｜ 112 ｜ 101 ｜ 110 ｜ 46 ｜

In the above code, T is 84 and h is 10
It corresponds to 4 ....

Next, from the normalized data 20, a neighboring feature is calculated by the learning means S2, and is convolved in the form of a neighboring feature matrix 30 by the procedure described below. Here, various arithmetic expressions for extracting the neighborhood feature amount can be considered. This arithmetic expression also affects the sharpness of the search (less overdetection).

As an example of the learning means S2, a procedure for obtaining a quantization amount from the normalized data 20 and obtaining a neighboring feature amount matrix 30 using the quantization amount will be described. For example, FIG.
Suppose that there are a plurality of target properties (documents) to be searched, and the quantization of the i-th property is considered. Here, j-th data of the i-th property (document) (character) and C _{i, j,} C _i, the data for the k-neighborhood of _{j C i, j + 1,} C i, j + 2, · .., C _{i, j + k} . In the i-th property, a normalized numeric string 135,6 as shown in FIG.
4,37,71,101 and ... is that alongside, C _i, the quantization amount x and C _i relates _j, quantization amount y is about k vicinity of _j, x = f (C _{i, j)} y = G (C _{i, j} , C _{i, j + 1} , C _{i, j + 2} , .., C _{i, j + k} ) ... It is obtained by the following equation (1).

Here, f (C _{i, j} ) is an n-stage quantization function for C _{i, j} . That is, it is a value obtained by performing a predetermined operation on the j-th data C _{i, j} of the i-th property, and is represented by any integer from 1 to n. Accordingly, in the matrix (coordinates) shown in FIG. 4, x is obtained by the value of the quantization amount x obtained by the calculation of the n-stage quantization function f.
The position in the axial direction is determined in the range of 1 to n.

Further, g (C _{i, j} , C _{i, j + 1} , C _{i, j + 2} ,..., C
_{i, j + k} ) is an m-step quantization function for the neighborhood of k in front of C _{i, j} . That is, the j-th data C of the i-th property
_{i, j} and a predetermined number of data C near the data C _{i, j
i, j + 1} , C _{i, j + 2} ,..., C _{i, j + k} are values obtained by performing a predetermined operation, and are represented by any integer from ₁ to _m . For example, as shown in FIG.
_{When i, j} is 135 and k is 3, C _{i, j + 1} , C
data 64 following data 135 as _{i, j + 2} , C _{i, j + 3} ,
37 and 71 are extracted, and a predetermined calculation is performed on the correlation between these data and the data 135. j-th data C
_{When i, j} is the next 64, data 37, 71, 101 following data 64 are extracted as Ci _{, j + 1} , Ci _{, j + 2} , Ci _{, j + 3} , and these data are extracted. A predetermined calculation is performed for the correlation between the data 64 and the data 64. The position of the matrix (coordinates) shown in FIG. 4 in the y-axis direction in the range of 1 to m is determined by the value of the quantization amount y obtained by the calculation of the m-stage quantization function g.

Therefore, by obtaining the quantization amounts x and y from the data 20 normalized as described above, FIG.
The position in the matrix (coordinates) shown in FIG. Although there are various other arithmetic expressions f () and g () for obtaining the quantization amount, for example, f: x → x g: (x, y) → xy (or | xy) |) Expression (2): The expression f () uses the input value as it is as the quantization amount, and the expression g () denotes the difference between the two input values or the absolute value of the difference. Can be considered as a quantization amount. In this case, the normalized data 20 corresponds to the previous example 84 | 104 | 105 | 11.
In 5 _..., C i, when the _j a 84, C _{i, j} and C _i, the front of the _j k
The coordinate positions of the quantization amounts x and y related to the neighborhood are (84, 2)
0), (84, 21), (84, 31),. Also,
In addition to the above equation (2), a neighborhood feature may be extracted by performing four arithmetic operations on individual character integer values of some character strings. The coordinate positions of the quantization amounts x and y shown in FIG.
(51, 71), (32, 103),... Are obtained by a method different from the above equation (2).

In this system, each piece of property information is a property serial number i and a weight w with respect to x and y obtained as described above.
It is stored as a set of (x, y, i). The weight w (x, y, i) is
The value of the weight w (x, y, i) may be fixed to 1 although it is obtained by a predetermined calculation from the data x, y, i.

Data C for each property as described above
4 based on the values of the quantization amounts x and y obtained for each of _{i and j} .
Store the data as indicated by the bar at That is, the serial number i of the property and the weight w thereof are placed at the position of the coordinates determined by the values of the quantization amounts x and y of the data C _{i, j.}
Data containing (x, y, i) is stored. In the figure, the length of the bar is shown to be extended each time such data is stored. Normally, the weight w (x, y, i) is set to 1, so that only the data of the serial number i of the property is stored at the position of the coordinates determined by the values of x and y.

An identification number of a property is added to the neighborhood feature amount matrix created in this way, and the matrix is stored as a structure file 40.

(2) Search Step First, a search key 50 is input. For example, "This is ap
en. "is used as a search key. The key information is normalized to the following integer sequence by the normalization means S3 based on the same normalization method as the normalization means S1 in the learning step for the search key 50. ｜ 104 ｜ 105 ｜ 115 ｜ 32 ｜ 105 ｜ 115 ｜ 32 ｜ 97 ｜ 32 ｜ 112 ｜ 101 ｜ 110 ｜ 46 ｜

Next, in the search means S4, the same neighborhood feature extraction formulas f () and g as those of the learning means S2 in the learning step are used.
Using (), a series of pairs of quantization amounts x and y is created from the head of the normalized numerical sequence of the search key 50. Next, based on a series of pairs of quantization amounts x and y of the search key 50,
As the content frequency ω _i of the search key 50 for the property i extracted from the structure file 40, V (x _j , y _j , i) is j = 1
Ｍm are calculated by summing.

However, V (x _j , y _j , k) is equal to the weight of the property i stored in the structure file 40, and is set to 0 when there is no weight.

Therefore, when there is data (when there is a bar) at the position of the quantization amount x, y in FIG. 4 corresponding to the combination of the quantization amount x, y obtained from the numerical sequence of the key 50 to be searched. Stores the value of the weight in the storage location of the serial number i of the property indicated by the data in the separately provided storage means,
It is stored as e (degree of match).

Next, in the evaluation result output means S5, the structure evaluation value scor obtained for each property in the structure file 40 is obtained.
By dividing e (degree of match) by the evaluation value in the case of perfect match, the content probability of the search key 50 is obtained, and a list 70 of evaluation results is obtained. Further, the sorting unit S6 sorts the list 70 in descending order of the content probability to obtain a sorted list 80.

The sorted list 80 is a search result, and by referring to a higher order property, it is possible to know a property name having a high probability that the search key is included in the property. Since the content probabilities are obtained for all of the perfect match and the incomplete match, a fuzzy match search can be performed.

Further, since all properties are searched for all information of a search key, the probability of occurrence of a search leak is essentially zero.

The evaluation time of the search key for one property depends only on the number of characters of the key, and does not depend on the size of the property. Therefore, the search can be performed at a very high speed.

As a result of the data search as described above, properties whose score (key content probability) is higher than a predetermined threshold value are extracted from the sorted list 80, and are extracted as search results by the above-described conditional expression A or B. And The property number list of these properties is stored in the search result list storage unit 14 of FIG. 1, and based on this, the property list condition search unit 16 uses, for example, (A and B) or (A or B) as described above.
or C) A condition search such as and E is performed.

In the data search as described above, the search result is obtained as a sorted list 80, which is stored in the search result list storage unit 14, and a condition search is performed based on the stored data. A high-speed search can be performed even for a complicated conditional expression.

The neighboring feature amounts need not be extracted for all data of each property. For example, one or more specific integer values in property data, a specific range of integer values,
Alternatively, the neighborhood feature may be created (extracted) by excluding one or more specific bits in each byte constituting the data string. Further, in the case of a two-byte character as in a Japanese document, for example, the upper-order byte may be excluded and the neighboring feature amount may be extracted from the lower-order byte.

In the above example, the neighborhood feature matrix is 256
The next bit matrix, which corresponds to 8K bytes.
Therefore, a database in which the data of one property is about 1 KB is not an efficient system.
Therefore, it is preferable to provide the data compression means S7 to perform data compression to reduce the capacity of the structure file 40.

FIG. 5 shows an example of the data compression method. In this example, the property name 40a (identification code) having an element value of 1 for each element of the 256-order neighborhood feature amount matrix is stored as a data string of 1 byte / item. Therefore, a property name whose element value is 0 is excluded as unnecessary data.

If the number of properties is 255 or more, the property name 40a cannot be represented by one byte, so only the lower one byte is stored. For example, when the number of properties is 10,000, the property name is represented by 2 bytes, and the lower 1 byte is used. Then, every time the property name code exceeds 255, the marker 40b is inserted into the data string.

At the time of retrieval, a data string of the structure file corresponding to each of the neighboring feature amounts of the retrieval key is extracted, and an appearance frequency table for each property name is created. At this time, the marker 40
Each time the value exceeds b, 255 is added to the article name code. The evaluation result list 70 of FIG. 2 is obtained based on the appearance frequency table created in this manner.

When the data string of the property name code is, for example, half or more of all the properties, the neighboring feature amount matrix element may be regarded as common to each property, and the element may be deleted.

In the above embodiment, the normalizing means S1,
Learning means S2, normalization means S3, search means S4, evaluation result output means S5, sort means S6, data compression means S7
Can be configured by a computer program, but dedicated hardware may be configured using logic circuit elements.

[0045]

According to the present invention, the j-th data C _i of the i-th property of the search _{target, j} and the i-th j-th data C _i in _property, near the _j data C _i, and _k Is compared with a combination of a plurality of quantization amounts calculated based on the search key and a combination of a plurality of quantization amounts calculated based on the search key, and the entire property is searched based on the degree of matching. The search can be performed, and the omission of the search can be substantially eliminated, and the search can be performed at a high speed. Then, by storing the search results and performing a conditional search based on the stored search results, a search with complicated conditions can be performed at high speed, and a partial search result can be reproduced. Since it can be used, there is no waste and it is possible to increase the search efficiency.

[Brief description of the drawings]

FIG. 1 is a data flow diagram of an embodiment of a database search system according to the present invention.

FIG. 2 is a data flow diagram of a database search system to which the search system according to the present invention is applied.

FIG. 3 is a diagram illustrating quantization of neighborhood information.

FIG. 4 is a diagram showing a stored information structure.

FIG. 5 is a data configuration diagram of a compressed neighboring feature amount.

[Explanation of symbols]

 10 Search Target 12 Search Unit 14 Search Result List Storage Unit 16 Property List Condition Search Unit 18 Search Key Input Unit 20 Normalized Data 30 Nearby Feature Matrix 40 Structure File 50 Search Key 60 Normalized Key 70 Evaluation Result List 80 Sorted List S1 normalization means S2 learning means S3 normalization means S4 search means S5 evaluation result output means S6 sorting means S7 data compression means

──────────────────────────────────────────────────続 き Continuation of the front page (56) References JP-A-2-130673 (JP, A) JP-A-60-65335 (JP, A) Patent 2993539 (JP, B2) Patent 2993540 (JP, B2) Patent 3151730 (JP, B2) Roy E. Kimbell, "Searching for Text? Send an N-Gram!", BYTE 1988 MAY, pp. 1-35. 297-312 (58) Field surveyed (Int. Cl. ⁷ , DB name) G06F 17/30 JICST file (JOIS)

Claims (3)

(57) [Claims] 1. Calculation based on j-th data C _{i, j} of an i-th property to be searched _{and j} i-th data C _{i, j} neighboring data C _{i, k} in an i-th property A search unit that compares a combination of a plurality of quantization amounts and a combination of a plurality of quantization amounts calculated based on a search key, and performs a search for all properties based on the degree of matching, and stores a search result obtained by the search unit. A database search system comprising: a search result storage unit for performing a condition search using a search result stored in the search result storage unit. 2. The search result storage means stores a search result for each search key detected by the search means as a property number list, and the condition search means stores a logical condition search based on the property number list. The database search system according to claim 1, wherein the search is performed. 3. A calculated based on the search target of the i-th property of the j-th data C _i, j-th data C _i in _j and the i-th _property, neighboring data C _i of _j, to a _k A combination of a plurality of quantization amounts and a combination of a plurality of quantization amounts calculated based on the search key are compared, and a fuzzy search corresponding to the search key is performed from among all the articles based on the degree of matching, and the search is performed. A database search method characterized by performing a logical condition search on the resulting property list.