JPH0573618A - Retrieval method for structural body - Google Patents

Abstract

PURPOSE:To reduce the probability of fail drop by expanding the kings of functional elements capable of identification and to reduce a rate that an item which cannot be simplified is included in a candidate with can be simplified. CONSTITUTION:In the case of retrieving a simplified retrieval item to at least one inquiry item from the set of the retrieval items, a minimum element consisting of two or more bits is set for a code word generated in the algorithm to the retrieval item and the inquiry item. At the time of generating the code word, it is not divided into less than the minimum element and the code words of the divided elements are decided. Then, a simplified candidate is selected in the logic operation of the code words of the minimum elements in the retrieval items and the inquiry items.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a method for searching a structure for searching information having structured data.

[0002]

2. Description of the Related Art In computer processing using knowledge such as artificial intelligence, data having a structure 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 fast retrieval method for structured data is important.

In a system such as a deductive database or a knowledge database, terms including variables are often used as basic elements of knowledge representation, and unification operations are essential as basic operations. 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 technique 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 technique 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 (unification possible) 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. Further, unification is used in Prolog and the like, and is often used in knowledge representation centered on a logic language.

However, since the variable substitution operation is included,
For example, with respect to an envisaged question (term), there is not even a property such as continuity in which all corresponding data (unification-possible terms) are arranged in advance so as to be continuous. It is difficult to apply the indexing method, that is, the method for 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, if the term is (1) 0-argument functor (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 selected codeword. (3) In the case of a variable, generate a code in which all bits are 1 for the stored term and a code in which all bits are 0 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 possible candidate terms 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 checked 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, if the terms to be searched are (1) to (5) in FIG.
The search process when the inquiry item is given as (a) in FIG. 2 is as follows. First, a codeword is assigned to each term of 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-mentioned rules. 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. If further division is not possible (the assigned codeword is too short), 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 inquiry term.

FIG. 4 shows an explanatory diagram of the search candidate selection process. 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 a term (question term) that is an inquiry. Then, in the codeword to be searched, S, and in the codeword Q of the query, terms satisfying Q∧S = Q are search candidates. In this case, the search candidates include 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 the term that does not satisfy = Q cannot be unified, it is not necessary to attempt the unification, 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 above-mentioned FEW method, each function element and variable inside the term are encoded according to a predetermined structure (element code word). ) Is used as a code word. In this case, for comparison of hash values, it is checked whether or not each (element) codeword is equal or either is a variable, and if all are the same, a method of selecting a candidate is adopted.

[0012]

However, in the FEW method described above, a so-called superposition code (SCW) method is followed as a comparison operation, and therefore, at most Com (n, n / 2) Only the types of functors 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, the above CCW method can identify 2n-1 types of element codewords of n bits each, but 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 method for searching a structure capable of improving the resolution (accuracy) of encoding.

[0013]

According to the 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 retrieval terms is simply combined with the question term. In a structure search method for searching for a search term to be unified, a codeword for generating a codeword of the term by the algorithm for each of the function and variable in the search term and the query term And a determination unit that determines a term that has a possibility of unification based on a logical operation result of the codeword of the query term generated by the codeword generation section and the codeword of the search term. , The code word generating means sets a minimum element of 2 bits or more in the code word,
When the codeword is generated, it is not divided into the minimum element or less,
Further, the code of each divided code word is determined, and the determination means selects a candidate for unification based on a logical operation of the code words of the minimum elements of the search term and the query term. is there.

[0014]

In the structure search method of the present invention, when searching a search term that unifies at least one question term from a set of search terms, first, for the search term and the question term, When the minimum element consisting of 2 bits or more is set in the codeword generated by the algorithm and the codeword is generated,
No division is made below the minimum element, and the code of each divided codeword 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 question term. Therefore, the types of functors that can be identified are expanded,
The drop probability can be reduced. As a result, it is possible to reduce the ratio of non-unification terms into the unification candidates.

[0015]

Embodiments of the present invention will be described in detail below with reference to the drawings. First, in the present invention, a codeword in which the characteristics 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 the unification process with the question item is performed. Compared to the unification process, the comparison operation of the codewords can be performed at extremely high speed, and therefore high-speed processing can be expected as compared with the case where the unification process is performed on all 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 for the combinations narrowed down in (3) above. Furthermore, if there is an inquiry for the search target, (2)
Repeat steps (4) to (4). 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, the problem is whether to express the information of the search target word by using a short code word, and the result becomes the narrowing rate 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 are the same when the code word is expressed by a binary word to perform the OR operation. 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 is 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 structure 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 is composed 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 to 8 bits.
010101 ". The subsequent three elements are determined by the first argument a, but since this is a constant, calculate the hash value to that 12 bits,
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 is a variable, so "000", and the last is "100".
It becomes "0". In this case, division that does not become finer than the minimum element is not performed. For example, when the second argument of f is a three-argument function, whether to use the hash value of the function symbol without dividing it or use the hash value using the first two arguments and the function symbol. 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 that "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 smallest 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 the 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 Expression (2),
225 different codes can be used.

In the above embodiment, the selection of the candidate by the code word is constituted by the program, but it can be constituted by the hardware. FIG. 6 shows an example of the determination means configured by 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 an 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 each bit of each codeword, and each exclusive-NOR circuit 1, 2, 3,
It is composed of an AND circuit 7 for inputting the output of 4 and an OR circuit 8 for inputting the output of the AND circuit 7 and the outputs of the NOR circuits 5 and 6.

Further, in the above-mentioned embodiment, the case of the term as the structure has been described as an example, but a structure used in a general programming language or the like usually has its structure definition and data separated, It is 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 above, according to the structure search method of the present invention, the selection of the candidate term by the search is performed by the logical operation of the minimum elements of 2 bits or more of the search term and the question term. Thus, for example, the types of functors that can be identified with respect to the n-bit codeword having the m-bit minimum element are from Com (n, n / 2) to FIG.
It is possible to reduce the probability of the Fails drop by expanding to the expression (1) and selecting the unification candidate. Therefore, it is possible to reduce the rate of entry of non-unification terms into unification candidates, and as a result, increase the number of terms,
High-speed search is possible by unifying terms.

[Brief description of drawings]

FIG. 1 is an explanatory diagram of a structure search method of 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 the 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.

Claims (1)

[Claims] 1. A method for retrieving a structure for retrieving a search term that unifies with at least one question term from a set of search terms in a computer system that performs data representation using terms , For the search term and the question term, for each functor and variable in the term, a codeword generation means for generating a codeword of the term by the algorithm, and a question generated by the codeword generation means A code word of the term, and a determination means for determining a term having a possibility of unification based on a logical operation result of the code word of the search term, wherein the code word generation means has two or more bits in the code word. Is set, and when the codeword is generated, the codeword is not divided below the minimum element, and the code of each of the divided codewords is determined. For logical operation of codewords between minimum elements Search method of a structure and selects the Hazuki unification candidate.