JPH0738196B2 - Structure search 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 structure search method for performing information search for data having a structure.

[0002]

2. Description of the Related Art In computer processing using knowledge such as artificial intelligence, structured data is often used as a basic element for expressing the knowledge and data. Considering the application of more advanced and large-scale knowledge processing that requires a large amount of knowledge and data, a high-speed search method for structured data is important.

In a system such as a deductive database or a knowledge database, a term including a variable is usually used as a basic element of a knowledge expression, and a unification operation is indispensable as the basic operation. As the scale of knowledge grows, a fast operation (search mechanism) of unifiable terms for a large number of terms is essential. Therefore, some kind of speed-up method is required, but since the term has a structure different from a constant and the structure is variable, it is possible to apply a conventional high-speed method such as B-tree or hash method. Can not.

Therefore, a method has been proposed in which a code word is assigned to each term and a simple operation is performed on the code word to select a candidate that can be unified in advance. As one of them, for example, Wise, MJ & Poerts, DMW
“Indexing Prolog via Superimposed Code Word and F
ield Encoded Words ”.International Conference on L
ogic Programming, IEEE Computer Society Press, pp2
03-210, Feb, 1984 FEW (field
Field Encorded Word) method is known.

The above-mentioned FEW method will be described below.
First, terms are defined. The terms are defined recursively as follows. (1) Variables and 0-argument function elements are terms (0-argument function elements are constants). (2) The n-argument function (term 1, term 2, ..., Term n) is a term. Then, when an appropriate term is assigned to a variable for this term, a term that becomes the same term (can be unified) is searched.
For example, in the following, f (X, b, g
(X)) and f (a, Y, g (a)) are both f (a, b, g) by substituting a for X and b for Y.
(A)), it is possible to unify. Conversely, f
(X, b, g (X)) and f (a, Y, g (b)) cannot be unified. In addition, unification is used in Prolog and the like, and is often used in knowledge representation centered on a logic language.

However, since a variable assignment operation is included,
For example, with respect to an envisaged question (term), even if there is no property such as continuity in which all corresponding data (unification possible terms) are arranged in advance so as to be continuous, it is possible to It is difficult to apply the indexing method of i.e., that of non-structure.

The processing method of the FEW method is performed as follows. Codewords are generated for all terms in the term set to be searched and for terms that are queries. That is, for an n-bit codeword, when the term is (1) 0-argument function (constant), an n-bit code is generated using a hash function. (2) If it is an m-argument functor, the codeword is divided into m + 1 parts, the hash value of the m-argument functor is divided into the first subword, and the remaining m are divided into terms of each argument. Generate a code for the codeword. (3) In the case of a variable, a code with all bits set to 1 is generated for the stored term, and a code with all bits set to 0 is generated for the query term.

Then, by comparing the codewords of all the terms in the term set to be searched with the codewords of the term that is the inquiry, unification candidate items are extracted. That is, if the codeword of the term to be searched is S and the codeword of the query term is Q, the term satisfying Q∧S = Q is a candidate term. However, ∧ represents the logical product of each bit. Then, it is examined whether the candidate term can be unified with the term of the query.

FIG. 2 shows an example of the term set, and FIG. 3 shows an example of encoding. For example, the terms to be searched are (1) to (5) in FIG.
The search process when the inquiry term is given as (a) in FIG. 2 is as follows. First, a codeword is assigned to each term in the term set to be searched, as in the example of FIG. In the case of a constant or a variable, the code word is obtained by the hash function ψ according to the above rule. In the case of the m-argument function, the codeword is divided into m + 1 codewords using an appropriate function, the hash value of the functor is assigned to the first codeword, and the code of each argument is assigned to the remaining m. Give to. If the argument is also the m-argument, further division is performed. When it cannot be further divided (the assigned codeword is too short), the division is not performed and, for example, the hash value of the functor is used as the code. However, all the bits 1 are given to the variables existing in the term to be searched. In addition, a code word is similarly created for an item that is an inquiry. However, all the bits 0 are given to the variables existing in the term of the inquiry.

FIG. 4 shows an explanatory diagram of the search candidate selection processing. Here, FIG. 4A shows a question term and its codeword, and FIG. 4B shows a search process. As shown in FIG. 4A, the code word Q is also given to the term (question term) that is an inquiry. Then, in the code word to be searched, S, and in the query code word Q, terms satisfying Q∧S = Q are search candidates. In this case, the search candidates include the terms (1) and (4) ( Figure 4 (b)), of which item (4)
Is a term that can be unified. However, even if Q∧S = Q is satisfied, unification may not be possible. Fail this
This is called s drop (fails drop), and (1) in FIG. 4B corresponds to this. In this case, Q ∧ S
Since it is known that a term that does not satisfy = Q cannot be unified, it is not necessary to try to unify, and the search time can be shortened accordingly.

On the other hand, in the CCW (Concatinated Code Word) method, which is known as a method similar to the FEW method described above, a coded version of each function and variable inside the term (element code word) is used in accordance with a predetermined structure. ) Is used as a code word. In this case, for comparison of hash values, it is checked whether or not each (element) codeword is a variable, and if either is the case, a method of selecting a candidate is adopted.

[0012]

However, in the above-mentioned FEW method, since the so-called superposition code (SCW) method is followed as the comparison operation, at most Com (n, n / 2) Only the type of functor can be identified, and the resolution (the type of data that can be identified by the code word) is reduced. Here, Com (n, n / 2) indicates the number of combinations for extracting n / 2 out of n. On the other hand, although the above CCW method can identify 2n-1 types of element codewords of n bits each, it is necessary to determine the structure in advance, and if the structure does not match, the codeword becomes useless. I had a problem. The present invention has been made to solve the above conventional problems, and an object of the present invention is to provide a structure search method capable of improving the encoding resolution (accuracy).

[0013]

According to a method of searching a structure of the present invention, in a computer system that performs data representation using terms, at least one question term from a set of search terms and the question term are simply combined with each other. In a structure search method for searching a search term to be unified, for the search term and the query term, a codeword generating unit that generates a codeword of the term for each function and variable in the term, The codeword includes a codeword of the query term generated by the codeword generation means and a determination means for determining a term having a possibility of unification based on a logical operation result of the codeword of the search term. The generating means sets a minimum element consisting of 2 bits or more in the codeword, recursively divides the codeword according to the structure of the term when generating the codeword, and at this time, does not divide into the minimum element or less, and Determine the code of each divided codeword, and determine Stage, is characterized in that selects candidates for unification based on the logical operation of the code word of the smallest element between the search term and the question section.

[0014]

In the structure search method of the present invention, when a search term that unifies with at least one question term is searched from a set of search terms, first, the search term and the question term are generated. The minimum element consisting of 2 bits or more is set in the generated codeword, and when the codeword is generated, the division is recursively performed according to the structure of the term, and at this time, the division is not performed below the minimum element,
Further, the code of each divided code word is determined. Next, a candidate for unification is selected by a logical operation of codes between the minimum elements of the search term and the query term. As described above, in the present invention, since the minimum element having 2 bits or more is set, it is possible to determine the specific code representing the variable within the minimum element. As a result, if either the query term or the search term is the specific code of the variable for each minimum element, it is considered as a candidate for unification, and otherwise, when the codewords are exactly the same, it is considered as a candidate. , When it becomes a candidate for unification, it is possible to make the whole as a candidate for unification. In this case, the codes other than the variables do not have to overlap with the specific codes of the variables, and assuming that the minimum element bit width is m bits and the width of the assigned codeword is n bits, the formula of FIG. (1)
It is possible to give the codes of the number ((2 ^m −1) ^{(n / m)} ) shown in. In general, since this is larger than the number of combinations to take n / 2 out of the above n, Com (n, n / 2), the number of types of functors that can be identified is larger than in the conventional method, and the resolution is improved. Can be made. Therefore,
The above problems can be solved.

[0015]

Embodiments of the present invention will now be described in detail with reference to the drawings. First, in the present invention, a codeword in which the features of each term are extracted is prepared in advance from a set (database) of terms to be searched. In addition, for search inquiries, codewords are similarly created for the question term or a set of question terms, and the search target is narrowed down by comparing the codewords. Only perform unification processing with the question item. Compared to the unifying process, the comparison operation of the codewords can be performed at an extremely high speed, so that a high-speed process can be expected as compared with the case where the unifying process is performed on all the search targets.

That is, the processing outline of the unified search according to the present invention is as follows.
It is configured as follows. (1) A codeword is created for each term in the set of terms to be searched (this codeword is usually stored in a file called an index file). (2) When a search instruction for a search target is given, a codeword for each term is created for a question term that is a term expressing the search condition or a term set thereof. (3) Extract combinations that have the possibility of unification by using the codeword to be searched and the codeword of the query term. (4) Perform unification processing on the combinations narrowed down in (3) above. Furthermore, if there is an inquiry for the search target, (2)
Repeat (4) to. As a result, (1)
Overhead can be reduced.

The feature of the present invention resides in the indexing method in the above (1) and (2). In such an indexing method, how to express the information of the word to be searched using a short code word becomes a problem, and the result becomes the rate of narrowing down in (3), which affects the entire processing time. FEW, which is an indexing method for unifying search, uses coding by a superposition code as a coding method for codewords. It is known that the selection efficiency is highest when the code word is encoded so that the number of bits in which 1 appears and the number of bits in which 0 appears when the code word is expressed in binary to perform the OR operation are equal. ing.

In the present invention, the codeword is considered to have a division unit of 2 bits or more. The code word is divided into units, and the unit cannot be further divided. In the present invention, the following method is used to give the codeword. (1) When the given term is a constant, the hash value for that codeword is calculated and used as the code of that codeword. (2) When the given term is a variable, the value for that codeword shall be 0. (3) When the given term is expressed by the m-argument function, the codeword is divided into m + 1 pieces, and for each divided codeword, the first divided codeword is , The hash value of the function name is used as a code, and the remaining codewords are calculated by recursively applying this codeword for each argument term. At this time, if it cannot be divided, the hash value of the function name is used as the codeword of the entire codeword.

FIG. 1 shows the construction of code words for terms similar to the example of the FEW method described in the section of the prior art. In this embodiment, the minimum division unit is 4 bits, and one codeword consists of 8 division elements. The term to be encoded is f (a, h (X, c)).

Here, since the top level of this term has two arguments f, this codeword is divided into three. In this case, the first two elements are assigned to the function symbol f, and the remaining three elements are assigned to the two arguments. That is, the first two elements are "01" using the hash function value of f into 8 bits.
010101 ". The subsequent three elements are determined by the first argument a, but since this is a constant, the hash value to 12 bits is calculated,
It becomes "100110100101". For the last three elements, the codeword of the second argument h (X, c) is calculated. Since this is a two-argument function h, it is further divided, and the first element is a hash of h to 4 bits. The value is "0010",
The second variable is "000", and the last is "100".
It becomes "0". In this case, the division that is finer than the minimum element is not performed. For example, when the second argument of f is a three-argument function, whether the hash value of the function symbol is used without division, or the hash value using the first two arguments and the function symbol is used. Take the way. These can be determined from the set of target terms and the characteristics of the question.

On the other hand, the search for the above codeword is as follows. It is a candidate if all the minimum elements satisfy the condition "the codeword is the same for the minimum element or one of them is 0". That is, if the value of each minimum element of each codeword is 0, it is treated as a variable. No matter what value comes to the place where the variable appears, it becomes a candidate. FIG. 5 shows a comparison of code words. For example, in the case shown in FIG. 5A, since the second elements of the codewords to be compared are neither 0 nor equal, they are not candidates. On the other hand, in the case shown in FIG. 5B, all the elements are equal or one of them is 0, so that they remain as candidates.

At this time, as in the conventional FEW method, S∧Q
Since the comparison is not a judgment such as = Q but a normal comparison, assuming that the bit width of the minimum element is m bits, the code of the variable is removed from the code word of n bits in FIG. formula
You can identify symbols of type (1). For example, when the minimum element is 4 bits, for an 8-bit codeword,
In the conventional FEW method, Com (8,4) = 70 different codes are used, but in the present embodiment, as shown in equation (2),
225 different codes can be used.

In the above embodiment, the selection of the candidate by the code word is configured by the program, but this can also be configured by hardware. FIG. 6 shows an example of the determination means composed of hardware. Here, FIG.
6A is an overall circuit diagram of the determination means, and FIG. 6B is an internal circuit diagram of the determination circuits A and B. In this way, the determination circuit A
And the decision circuit B are configured so that each 1 bit of the code word is inputted, and each decision circuit A,
The outputs of B, ... Are input to the AND circuit, and the logical product of them is calculated. In addition, each determination circuit A, B
Is an exclusive-NOR (EX-NOR) circuit 1, 2, 3, 4 for inputting each bit of codewords.
And NOR circuits 5 and 6 for inputting the respective bits of the respective codewords, and the exclusive-NOR circuits 1, 2, 3 and
The AND circuit 7 inputs the output of No. 4 and the OR circuit 8 inputs the output of the AND circuit 7 and the outputs of the NOR circuits 5 and 6.

Further, in the above embodiment, the case of the term as the structure has been described as an example, but a structure generally used in a programming language or the like has its structure definition and data separated, It is also possible to represent such a structure in the form of a term, and therefore, the present invention can be applied by converting such a structure into a term expression. Further, in the above-mentioned embodiment, the minimum division unit is composed of 4 bits, but the present invention is not limited to this, and if it is 2 bits or more, the same effect as that of the above-mentioned embodiment is obtained.

[0025]

As described in detail above, according to the method for searching a structure of the present invention, the selection of candidate items by searching is
Since it is performed by the logical operation of the minimum elements of 2 bits or more of the search term and the query term, for example, the type of the functor that can be identified with respect to the n-bit codeword having the m-bit minimum element is Com ( n, n / 2) to FIG.
The number can be expanded to the number represented by the equation (1) in (c), and the encoding resolution can be improved. Due to this improvement in resolution, different functional elements have been erroneously determined to be candidates for unification by being encoded into the same code, but according to the method of the present invention, they can be encoded into different codes. Therefore, the probability of wrong candidate selection, that is, the failure drop can be reduced. As a result, unnecessary processing is reduced in the unification processing for a large number of terms, and high-speed search is possible.

[Brief description of drawings]

FIG. 1 is an explanatory diagram of a method for searching a structure according to the present invention.

FIG. 2 is an explanatory diagram of a term set.

FIG. 3 is an explanatory diagram showing an example of encoding in a conventional structure search method.

FIG. 4 is an explanatory diagram of search candidate selection processing in a conventional structure search method.

FIG. 5 is an explanatory diagram of codeword comparison processing in the structure search method of the present invention.

FIG. 6 is a configuration diagram showing another embodiment of the determination means in the structure search method of the present invention.

Continuation of the front page (56) Reference JP-A-1-276237 (JP, A) JP-A-1-232436 (JP, A) JP-A-1-232426 (JP, A) WISE, M. J. & POERTS, D.E. M. W. "INDEXING PRO LOG VIA SUPERIMPOSE D CODE WORD AND FIE LD ENCODED WARDS". INTERNATIONAL CONFER ENCE ON LOGIC PROGR AMMING, IEEE COMPUTER SOCIETY PRESS, PP 203-210, FEB, 1984

Claims (1)

[Claims] 1. A method for retrieving a structure for retrieving a search term unifying with at least one question term from a set of search terms in a computer system for performing data representation using terms , For the search term and the query term, for each functor and variable in the term, the codeword of the term
A code word generating means for generating a query word, a code word of the query term generated by the code word generating means, and a logical operation result of the code word of the search term to determine a term having a possibility of unification. Determination means, and the code word generation means includes 2 for the code word.
Set the minimum element consisting of more than bits, and recursively divide according to the structure of the term when generating the codeword.
The code is not divided below the minimum element, and the code of each divided code word is determined, and the determination means is a candidate for unification based on the logical operation of the code words of the minimum elements of the search term and the question term. A method for searching a structure, characterized by selecting.