JPH0944507A - Matching device - Google Patents

Abstract

PROBLEM TO BE SOLVED: To provide the matching device which matches words in a thesaurus at high speed and efficiently with small data size. SOLUTION: A hierarchical relation coding part 2 is previously stored with words and codes given according to the hierarchical positions of the words. When data to be compared is inputted from an input part 1, the hierarchical relation coding part 2 returns the code according to the inputted data. A matching part 3 performs bit logical operation for a plurality of data supplied from the input part 1 by using codes obtained from the hierarchical relation coding part 2. Through this bit logical operation, conceptual distances, hierarchical level differences, etc., of the hierarchical relation are calculated and on the basis of them, priority is calculated. Matching results are outputted from an output part 4.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a matching device for calculating a degree of data matching, and more particularly to a matching device based on a hierarchical relationship between data.

[0002]

2. Description of the Related Art Conventionally, researches on text retrieval and automatic classification have been actively conducted. In these fields, dictionaries that define synonyms and upper / lower relations between words called thesaurus are becoming more and more important.

In text search, the expression entered by the user often does not match the expression being searched. Therefore, in order to secure the hit rate of the searched contents, it is necessary to perform a search that includes synonyms and higher / lower words. Therefore, a method of expanding the word of the search request by using a thesaurus is often used.

Generally, when searching, the hierarchy of the thesaurus is traced based on the search request, and the obtained synonyms or higher /
A search is made using each of the subordinate terms. At this time,
If the thesaurus hierarchy is traced every time the search is performed, the search speed decreases, so that, for example, Japanese Patent Laid-Open No. 2-28027
As described in "Comprehensive Search Method of Database Search System" in Japanese Patent Publication No. 4, there is a technique for creating a comprehensive index including the upper and lower ranks of the thesaurus in advance to prevent the search speed from decreasing. Proposed.

However, even if such a comprehensive index is held, since it is necessary to perform a search based on a plurality of database keys included in the comprehensive index, the speed is still reduced as compared with the simple match search. Further, since it is necessary to create such comprehensive index information in advance, there is a problem that the amount of data and the cost for constructing a database increase.

For example, it is conceivable to perform matching in consideration of a thesaurus between a search key and a keyword and determine whether or not the search result is to be obtained based on the degree of matching. However, in the conventional matching method, it takes time to calculate the matching. This is a technology that cannot be used for searching.

On the other hand, in the field called automatic text classification, text is classified by using a semantic distance between texts using some standard.
At this time, the thesaurus is also used to obtain the distance between the texts.

For example, information processing, Vol. 36, no.
2, 1995.2, Iida, "Supercomputing in Artificial Intelligence," pp. In 164 to 168, as a part of the technique for obtaining the distance between phrases, a method for calculating a distance between words using a concept hierarchy is shown, and a semantic distance between an input and an example is given in advance. It is calculated by matching the base thesaurus code.

However, since this calculation method is a calculation based only on the distance to a common upper node, it is a leaf of a tree structure and only the distance between words arranged in the same hierarchy can be calculated. Since all words are not expressed as leaves at the same level, they cannot be applied when the concept in the middle of the hierarchy or the number of layers up to the leaf is different. Therefore, in comparing the distance between words, such a simple method is still insufficient. In addition, since a parallel computer is assumed, efficient distance calculation requires special processing such as associative memory, which is not common at present.

As described above, in the conventional technique, there is still insufficient technique for efficiently performing word matching in the thesaurus.

[0011]

SUMMARY OF THE INVENTION The present invention has been made in view of the above circumstances, and in particular, provides a matching device for efficiently matching words between words in a thesaurus at a high speed and with a small data size. That is the purpose.

[0012]

According to the present invention, in a matching apparatus for calculating a degree of similarity based on a hierarchical relation between data, each data of a data group having a hierarchical relation is held together with a code according to the hierarchical relation and input. Hierarchical data encoding means for converting into a corresponding code, and distance calculating means for calculating the distance in the hierarchical relationship by logical operation based on the code obtained by the hierarchical data encoding means for at least two given data. It is characterized by.

Further, as in the invention described in claim 2,
Hierarchical difference calculating means for calculating a hierarchical level difference by logical operation based on a code obtained by the hierarchical data coding means for at least two data given can be provided.

Further, as in the invention according to claim 3,
Priority calculation means for calculating priority based on the results of the distance calculation means and the layer difference calculation means can be provided.

[0015]

According to the present invention, the code corresponding to the hierarchical relationship is held for each data of the data group having the hierarchical relationship. Then, for at least two pieces of given data, a corresponding code is obtained, and the distance in the hierarchical relationship is calculated by a logical operation based on the code. As a result, distance calculation can be performed without performing a time-consuming operation such as an arithmetic operation as in the related art, and matching based on a hierarchical relationship between data can be realized at high speed and easily. Further, as in the inventions according to claim 2 and claim 3, by adopting various configurations such as providing a layer difference calculating means and further a priority calculating means according to the use, the layer level difference and the priority can be obtained. It is possible to make a more detailed comparison.

[0016]

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS FIG. 1 is a schematic configuration diagram showing one embodiment of a matching apparatus of the present invention. In the figure, 1
Is an input unit, 2 is a hierarchical relation coding unit, 3 is a matching unit, and 4 is an output unit. The input unit 1 gives data to be compared. The hierarchical relation coding unit 2 returns a code given in advance according to a position between layers in response to an input. The matching unit 3 performs matching on a plurality of data supplied from the input unit 1 by bit logic operation using a code obtained from the hierarchical relation coding unit 2. The output unit 4 outputs the result obtained by the matching unit 3.

FIG. 2 is a block diagram showing an example in which one embodiment of the matching apparatus of the present invention is applied to a similar word search system. In the figure, 10 is a search request input unit, 11 is a terminal, 12 is OCR, 13 is a telephone and voice recognition unit, 14 is a storage device, 15 is an infrared / radio receiver, 20 is a thesaurus coding unit, 21 is a thesaurus,
30 is a matching unit, 31 is a distance calculation unit, 32 is a layer difference calculation unit, 33 is a priority calculation unit, 34 is an output instruction unit, 40
Is an output unit, 41 is a terminal, 42 is a facsimile or printer, 43 is a telephone or pager, 44 is an infrared / wireless transmission unit, 50 is a database unit, and 51 is a database. The search request input unit 10 corresponds to the input unit 1 shown in FIG. 1, and similarly, the thesaurus coding unit 20 is the hierarchical relation coding unit 2, the matching unit 30 is the matching unit 3, and the like.
The output unit 40 corresponds to the output unit 4, respectively. The database unit 50 is a unit that electronically stores various documents to be searched, and the documents are stored in the database 51.

The search request input unit 10 is, for example, the terminal 1
1, OCR 12, telephone and voice recognition unit 13 having a microphone for inputting voice, storage device 14 such as memory, disk, tape, infrared / radio receiving unit 15 for receiving infrared rays and radio waves from portable information equipment, etc. It consists of Of course, some of these may be used, or an input device other than this may be used.

The output unit 40 is a display of the terminal 41,
Facsimile / printer 42, telephone or pager 43 that outputs from a speaker by voice synthesis, infrared / wireless transmitter 4 that transmits information to portable information equipment by infrared or wireless
4 and the like. Of course, a part of them may be used, an output device other than this may be used, or the output device may be temporarily stored in a storage device connected to a network or the like.

The thesaurus coding unit 20 is a unit that converts the input word into a code held according to the hierarchical structure of the thesaurus 21.

The matching unit 30 is a unit that compares the input word with the keyword of the document in the database 51 and outputs the document having the keyword matching or similar to the search request. The distance calculation unit 31 is a unit that logically operates the codes of the search request and the document keyword converted by the thesaurus coding unit 20 to calculate the distance in the hierarchical relationship. The layer difference calculation unit 32 is a unit that performs a logical operation on the search request converted by the thesaurus encoding unit 20 and the code of the keyword of the document to calculate the difference between the layer levels. The priority calculation unit 33 is a unit that calculates the priority of the matching result based on the results of the distance calculation unit and the layer difference calculation unit. Based on the result obtained by the priority calculation unit 33, the output instruction unit 34 takes out a document having a keyword matching or similar to the search request from the database unit 50, and instructs the output unit 40 to output it.

FIG. 3 is a flow chart showing an example of the overall operation in an example of a similar word search system, and FIG. 4 is a flow chart showing an outline of an example of a matching algorithm. First, in S61, the search request input unit 10
When the user's search request RQ is input from, the conversion to thesaurus code is performed by the thesaurus coding unit 20 in S62, and the thesaurus code C1 of the search request is obtained.

Then, in S63, one document DQ is retrieved from the database 51 to be searched.
Further, in S64, the keywords KW of this document are sequentially extracted. Keywords may be extracted from the document on the spot at the time of search, or if high-speed search is required,
A document that is manually or automatically added to the document in advance may be used. In S65, the keyword KW is code-converted by the thesaurus coding unit 20 as in the search request RQ, and the keyword thesaurus code C2 is obtained.

When both the thesaurus code C1 of the search request and the thesaurus code C2 of the keyword are obtained, S6 is executed.
At 6, code matching is performed. First,
In S81, the layer difference calculation unit 32 obtains the layer level of the search request thesaurus code C1 by a logical operation and sets it as the layer level L1 of the search request. Similarly, S82
In step 1, the hierarchical level of the thesaurus code C2 of the keyword is obtained by a logical operation and set as the hierarchical level L2 of the keyword. In S83, the hierarchical level L of the search request
The difference between 1 and the hierarchical level L2 of the keyword is calculated and used as the hierarchical level difference LD. Subsequently, the distance calculation unit 31 calculates the bit-exclusive OR of the thesaurus code C1 of the search request and the thesaurus code C2 of the keyword in S84,
The conceptual distance CD. Furthermore, the priority calculation unit 33 uses the S
At 85, the priority PL is calculated according to the extracted layer level difference LD and the conceptual distance CD.

When the codes are matched in this way, the obtained hierarchy level difference LD, concept distance CD,
Whether or not the priority PL and the like satisfy the criteria is determined in S67.
To check. When it is determined in S68 that the criterion is satisfied, the output instruction unit 34 determines in S69 the result buffer BF.
The document DQ is output to. Of course, the output unit 40 may be directly instructed to output.

In step S70, it is determined whether or not all the keywords attached to the document currently being processed have been processed, and the processing in steps S64 to S64 is performed until the processing of the last keyword is completed.
The process of S70 is repeated. For one document,
When all the keywords have been processed, it is determined in S71 whether or not all the documents have been processed, and steps S63 to S70 are executed until the processing of the last document is completed.
Is repeated.

By carrying out such processing, a document having a keyword matching or similar to the search request is searched and output. As described above, in the matching process, the layer difference and the conceptual distance are calculated by using the logical operation, so that the matching process can be performed at high speed. Therefore, it is possible to realize a high-speed similar word search with a small data size without tracing the thesaurus hierarchy or using a comprehensive index as in the related art.

An example of the above operation will be described below by using a specific example. FIG. 5 is an explanatory diagram showing a specific example of the structure of the thesaurus. For example, the word "private car"
It is a subordinate concept of “automobile” and represents a superordinate concept such as “sports car”, “sedan”, and “RV car”. For each word, as shown in square brackets "[]" in the figure,
A code starting from level 1 is sequentially assigned to each word having the same parent in each hierarchy. Here, binary 4 bits are used for one layer and are shown in hexadecimal.

Some examples of codes actually assigned to the respective words are also shown in parentheses "()" in the drawing. For example, in the word “private car”, concrete object [2] → machine [3] → vehicle [A] → vehicle [2] →
Following the hierarchy of car [4] → private car [4], and having one level of lower-order data, this is represented as [0] and "23A2440H"
Is assigned a 4-byte hexadecimal code. here,
The trailing'H 'indicates hexadecimal numbers, 1
The hexadecimal value "23A2440" is shown. Similarly, the code "23A2442H" is assigned to the word "sedan", which is located at the lower level of "private vehicle" and is the end data. Here, since each node has eight hierarchies of 15 or less, a 4-bit 7-level code is used, but of course, this allocation is free and may be designed according to the structure of the thesaurus. Since this assignment can be easily automated by traversing the hierarchical structure of the thesaurus, it is possible to eliminate the labor such as manual code assignment.

Search request RQ input in S61 of FIG.
Is converted to the thesaurus code C1 in S62. FIG. 6 is a conceptual diagram showing an example of conversion into a thesaurus code. Here, as a data structure, Japanese Patent Laid-Open No. 5-2
An example using hashing as described in "Data Access Method" of Japanese Patent No. 8194 will be shown. The input data refers to the hash table based on the hash value obtained by the hash function. Here, a pointer to a chain index is stored in the hash table, the chain index is referred to based on this pointer, and after checking the chain index for collision, the converted data is referred to. A code corresponding to a word is stored in the converted data, and a code corresponding to the input data is obtained.

For example, when the data "sedan" is input, the hash value is obtained by the hash function, the hash table is referred to based on this, and the chain index is checked for collision, and then the thesaurus code C1. As a result, "23A2442H" is obtained. Also, as shown in FIG. 6, "motorcycle" and "motorcycle"
Although synonyms such as are different as input data, they are codes that are made uniform by conversion. In this way, the code can be obtained directly from the data without having to follow the hierarchical relationships in the thesaurus.

Although an example using the hash method has been described here, it goes without saying that another data structure such as BTree may be used.

The search request RQ input in this way
Is converted by a hash function and converted into a thesaurus code C1 by tracing a hash table and a chain index. Then, one document is retrieved from the database 51 to be searched in S63, and the keyword of this document is retrieved in S64. Here, it is assumed that “personal computer” is retrieved as the keyword KW. The keyword KW is code-converted by the thesaurus coding unit 20 in S65 by the same method as described above. For example, when the keyword is "personal computer", it is converted into a thesaurus code "23EC220H" as shown in FIG.

When both the thesaurus code C1 of the retrieval request and the thesaurus code C2 of the keyword are obtained, S
At 66, code matching is performed. Matching is roughly divided into level difference calculation in the layer difference calculation unit 32 and concept distance calculation in the distance calculation unit 31.

First, the layer difference calculation unit 32 uses S81 and S8.
In step 2, the hierarchical levels of the search request thesaurus code C1 and the keyword thesaurus code C2 are calculated.
Specifically, a mask code in units of 4 bits as shown below is prepared, the AND is sequentially performed with the thesaurus code C1 of the search request and the thesaurus code C2 of the keyword, and the level is determined by repeating until AND becomes non-zero. To be done. When all the ANDs up to level 1 are 0, that is, when the code of C1 or C2 is 0, it is the root of the thesaurus, and in this case, it is the "concept", so the level is 0. Level 7: 000000FH Level 6: 00000F0H Level 5: 0000F00H Level 4: 000F000H Level 3: 00F0000H Level 2: 0F00000H Level 1: F000000H

As the code for the "sedan" was "23A2442H" as described above, first 00000
When it is ANDed with 0FH, it becomes 000000FH AND 23A2442H = 2H, and since it is non-zero, it is found to be a level 7 word, and the processing ends.

Since the code for the "personal computer" was "23EC220H" as described above, first 0000
When ANDed with 00FH, the result is 000000FH AND 23EC220H = 0H, which is zero, and is further ANDed with 00000F0H. Then, 00000F0H AND 23EC220H = 20H, which is a nonzero value, is known to be a level 6 word, and the processing ends.

Although the method using the mask by AND has been described here, the number of bits according to the level, for example, in the case of level 7, right shifting by 4 bits and checking the lower overflow flag are also possible. Of course they are logically the same. In any case, since these bit-wise logical operations can be generally executed at very high speed, it is possible to realize high-speed processing.

The absolute value of the difference between the hierarchy levels obtained in this way is calculated in S83 to be the hierarchy level difference LD. In this case, | 7-6 | = 1.

Subsequently, the distance calculation unit 31 calculates the conceptual distance between words. The conceptual distance is obtained based on the bit exclusive OR (XOR) between codes. Here, 23A2442H XOR 23EC220H = 4E662H. The value thus obtained indicates the so-called closeness between words (concepts). The conceptual distance is given according to the range of values obtained here. Similar to the above-mentioned hierarchy level check, this assignment can be easily obtained as the minimum value which becomes non-zero by AND with the following mask code. Note that X
When all bits of the OR result are 0, the concept code is 0 because the codes are the same. Concept Distance 7: F000000H Concept Distance 6: 0F00000H Concept Distance 5: 00F0000H Concept Distance 4: 000F000H Concept Distance 3: 0000F00H Concept Distance 2: 00000F0H Concept Distance 1: 000000FH

Here, the value of the bit exclusive OR is "4E".
662H ”, F000000H AND 4E662H = 0H 0F00000H AND 4E662H = 0H 00F0000H AND 4E662H = 40000H, and it is understood that the conceptual distance = 5.

FIG. 7 is an explanatory diagram of a specific example of the matching result. In FIG. 7, each keyword and the thesaurus code C2 of the keyword are used as a search request for "sedan".
"Sedan" thesaurus code C1 "23A2442
Value of bit exclusive OR with “H”, concept distance, level difference,
It shows about the priority. The priority will be described later with reference to this figure again.

As shown in FIG. 7, the concept distance is not directly related to the level difference. For example, regarding "sedans", the value of the bit exclusive OR with "private car" which is one level higher (parent-child relationship) is 2H, and "sports car" having the same higher word one level below is 3H, These are very close relationships, and the concept distance is 1.

On the other hand, in the "car" which is two levels higher (grandparent relationship), the value of the bit exclusive OR is 42H, but the "bus" which is one level lower (uncle / aunt).
And 52H, and one level lower (a cousin), that is, 50H for a "bonnet bus" of the same level, and the conceptual distance from them is 2. In addition, the "PC" mentioned above
, The bit exclusive OR value is 4E662H, and the concept distance is 5.

FIG. 8 is a conceptual diagram in which a part of the conceptual distance in the specific example is two-dimensionally mapped. In FIG.
A circle indicates a node, a solid line indicates a thesaurus hierarchy, and a height indicates a hierarchy level. The thesaurus hierarchy shown here is part of what is shown in FIG. Now
If the concept distance is made to correspond to a two-dimensional distance based on the “sedan”, nodes having the same concept distance can be arranged and shown on arcs of equal distance as shown in FIG.

In the above example, the AND of the mask code is used in the calculation of the conceptual distance, but it can be realized by various methods as long as they are logically the same. FIG. 9 is an explanatory diagram of a method of calculating the conceptual distance using an OR gate. For example, as shown in FIG. 9, O of bits corresponding to the same layer
It is conceivable to take R and set the most significant bit that turns ON as the concept distance. In the example shown in FIG. 9, the value "4E662H" of the bit exclusive OR of thesaurus codes of "sedan" and "personal computer" is input to the OR circuit every 4 bits, and "0011111" is obtained as an output. Since the position of the most significant bit of this result is the fifth, the concept distance is 5
Becomes In this calculation method, the circuit can be easily configured by the wired logic, so it can be said to be a method suitable for hardware implementation. Of course, the calculation may be performed using another method.

Further, in this example, the concept distance limited to 0 to 7 is introduced in order to calculate the priority thereafter. When the XOR operation between expressions having a certain concept distance is actually performed as described above, the result takes only a specific range (10H to FFH in the case of the concept distance 2).
For example, to find a rough distance between words,
Of course, the result of calculating XOR may be used directly.

Further, in this embodiment, a fixed length of 4 bits is assigned to all layers of the thesaurus, but the thesaurus structure is various, such that the number of nodes increases as the leaves get closer. In such a case, a different number of bits may be assigned to each layer, and this can be effectively used even when the storage capacity is limited. In addition, in the thesaurus, not all leaf data are at the same hierarchical level, but the present invention can compare data across different hierarchical levels, so that it is very effective even in such a case.

Then, in S85, the priority calculation unit 33 calculates the priority according to the conceptual distance calculated by the distance calculation unit 31 and the layer level difference calculated by the layer difference calculation unit 32. As described above, the concept distance and the hierarchy level difference are not directly related. Even if the concept distances are the same, the similarities between them often differ. As shown in FIG. 8 described above, both “car” and “bonnet bus” have a conceptual distance of 2 with respect to “sedan”, but the similarity is “car”.
Is a direct grandchild, so the similarity is considered to be high. On the other hand, depending on the structure of the thesaurus, synonyms may be arranged as lower nodes with respect to upper nodes. In such a case, the same hierarchical level has a higher degree of similarity. Thus, by using the concept distance and the layer level difference, these can be evaluated as different axes.

In this example, the following formula is used as the priority. Priority = total number of levels × 2− (conceptual distance × 2−level difference) Here, the total number of levels is 7 in this example. For each of the keywords shown in FIG. 7, the following values are returned for "sedan". 14: Sedan (7 × 2- (0 × 2-0) = 14) 13: Private car 12: Sports car, automobile 11: Bus, vehicle, ... 10: Bonnet bus, motorcycle, ... 5: PC, ... Of course, the priority may be calculated by various calculation methods other than the above-described calculation formula.

Then, in S67 of FIG. 3, the extraction criterion is checked using the matching result obtained as described above. Here, if the priority value is 12 or more, it is regarded as the matching result. In the example of each keyword shown in FIG. 7 above, if the document has any of the keywords “sedan”, “private car”, “sports car”, and “automobile”, the document is output to the result buffer BF. It

Of course, this reference value may be set appropriately. Further, other extraction criteria may be used as the extraction criteria. For example, the entire document is scanned as needed, and then the extraction criterion is weighted by statistical processing.

In this way, the matching process between the search request and one keyword and the document extraction are completed.
The processing is advanced by repeating the processing up to this point for all the keywords attached to one document, and further sequentially performing them for each document in the database 51.

Through the above processing, the result buffer BF stores a document containing keywords similar to the user's search request "sedan", specifically "sedan", "sports car", "RV car", "private use". Documents including “car”, “car”, etc. are accumulated. In response to this result, the output instruction unit 34
Instructs the output unit 40 to output a document based on the priority. The output unit 40 outputs the search result, and the search process ends.

In the above-mentioned similar word retrieval system, the matching unit 30 calculates the concept distance, the hierarchy level difference, and the priority from these, but, for example, only the concept distance is used, or the concept distance and the hierarchy level difference are calculated. To use,
You may use the calculation result of some of these.

Needless to say, the present invention can be applied to general comparison processing between data having a hierarchical relationship and is not limited to application to the above-mentioned similar word retrieval system. Hereinafter, a case where one embodiment of the matching device of the present invention is applied to an automatic document classification system will be described.

Currently, in automatic classification, automatic classification using sample data is one of the general techniques. However, it has been difficult to include thesaurus expansion in the past due to cost issues. By applying the matching device of the present invention to matching with standard data, automatic classification can be performed at low cost.

For example, consider automatically classifying a document with respect to a sample data group (part) having the following keywords. [Sample 1] Keywords: Cellular, Telephone, Automotive, PHS Category: Mobile Phone [Sample 2] Keywords: Terminal, Reflection, Resistance, Delay Category: Terminator [Sample 3] Keywords: Cellular, Terminal, PDA, Network Category: Cellular Terminal

It is assumed that the input document also has keywords. This may be given in advance or extracted on the spot. [Input document] Keywords: mobile, terminal, communication

Here, the similarity between the input document including the thesaurus expansion and the keyword of each sample is obtained. The method similar to the case of the above-mentioned similar word search system can be used for the calculation of the similarity. Furthermore, the sum of those having the lowest similarity to each keyword of the input document is obtained. The example calculated in the samples 1-3 is shown. (Sample 1) Mobile: Cellular = 1, Terminal: PHS = 4, Communication: Telephone = 2 Total 7 (Sample 2) Mobile: Delay = 6, Terminal: Terminal = 0, Communication: Delay =
3 Total 9 (Sample 3) Mobile: Mobile = 1, Terminal: Terminal = 0, Communication: Network = 2 Total 3

The sample having the smallest sum obtained in this way is considered to have the highest degree of similarity to the input document, so the input document is classified into the relevant category. In this example, the sum calculated in sample 3 is the smallest, so
The input document is classified into the category “mobile terminal” of the sample 3. Automatic classification is performed by sequentially performing the above-mentioned processing for all input documents.

In the above application examples to each system, an example using a thesaurus has been described. However, since data having a hierarchical structure is generally widely used, the present invention applies to other than the thesaurus such as a file directory. It can also be applied to matching between data.

[0063]

As is apparent from the above description, according to the present invention, comparison between data having a hierarchical structure such as a thesaurus is simple based on simple bit logical operations such as AND and XOR. It becomes possible to execute at high speed only by processing. In addition, by using bit logic operation processing as a base, not to mention realization by software,
It is easy to implement as hardware.

According to the present invention, it is possible to make a comparison even in the case of data extending in the middle of a hierarchy, which was difficult with the conventional simple processing such as the number of layers up to the common upper node. In addition, by using the layer level difference, it is possible to set a detailed comparison standard according to the type of data and to set the priority.

As described above, since the matching processing including thesaurus expansion, which has been difficult in the past, can be executed easily and at high speed, for example, similar text search and automatic text classification to which the matching processing of the present invention is applied can be performed at high speed. There is an effect that it can be realized at low cost.

[Brief description of drawings]

FIG. 1 is a schematic configuration diagram showing an embodiment of a matching device of the present invention.

FIG. 2 is a block diagram showing an example in which one embodiment of the matching device of the present invention is applied to a similar word search system.

FIG. 3 is a flowchart showing an example of overall operation in an example of a similar word search system.

FIG. 4 is a flowchart showing an outline of an example of a matching algorithm.

FIG. 5 is an explanatory diagram showing a specific example of the structure of a thesaurus.

FIG. 6 is a conceptual diagram showing an example of conversion into a thesaurus code.

FIG. 7 is an explanatory diagram of a specific example of a matching result.

FIG. 8 is a conceptual diagram in which a part of the conceptual distance in a specific example is two-dimensionally mapped.

FIG. 9 is an explanatory diagram of a method of calculating a conceptual distance using an OR gate.

[Explanation of symbols]

1 ... Input unit, 2 ... Hierarchical relationship coding unit, 3 ... Matching unit, 4 ... Output unit, 10 ... Search request input unit, 11 ... Terminal,
12 ... OCR, 13 ... Telephone and voice recognition unit, 14 ... Storage device, 15 ... Infrared / wireless receiving unit, 20 ... Thesaurus coding unit, 21 ... Thesaurus, 30 ... Matching unit,
31 ... Distance calculation unit, 32 ... Hierarchical difference calculation unit, 33 ... Priority calculation unit, 34 ... Output instruction unit, 40 ... Output unit, 41 ... Terminal, 42 ... Facsimile / printer, 43 ... Telephone / pager, 44 ... Infrared ray -Wireless transmission unit, 50 ... Database unit, 51 ... Database.

Claims (3)

[Claims] 1. Hierarchical data in which each data of a data group having a hierarchical relationship is held together with a code according to the hierarchical relationship and converted into a code according to an input in a matching device for calculating a similarity based on a hierarchical relationship between data. A matching device comprising: a coding means and a distance calculation means for calculating a distance in a hierarchical relationship by a logical operation based on a code obtained by the hierarchical data coding means for at least two given data. 2. A hierarchical difference calculating means for calculating a hierarchical level difference by a logical operation based on a code obtained by the hierarchical data coding means for at least two given data. Item 1. The matching device according to item 1. 3. The matching apparatus according to claim 2, further comprising priority calculation means for calculating priority based on the results of the distance calculation means and the layer difference calculation means.