JPS5860800A - Similarity detector - Google Patents

Abstract

(57) [Summary] This bulletin contains application data before electronic filing, so abstract data is not recorded.

Description

DETAILED DESCRIPTION OF THE INVENTION The present invention relates to a similarity detection device that compares reference information and comparison information to evaluate their similarity.

In general, in glossy turn recognition such as voice recognition,
It is very unlikely that the input pattern to be compared and the original (reference) pattern will completely match. Therefore, in such cases, it is possible to detect not only whether the input cover pattern and the original pattern match, but also how much of a gap there is between the two patterns, that is, how similar the two patterns are. Is required.

The present invention has been made in view of the above circumstances, and its purpose is to:
An object of the present invention is to provide a similarity detection device that can efficiently detect the similarity of comparison information to reference information.

Hereinafter, one embodiment of the present invention will be described with reference to the drawings. FIG. 1 is a professional diagram showing the configuration of the similarity detection device, and 11.11! rri is, for example, a first and second holding section of a register configuration (or may be a memory' configuration). Reference information (data string) that is the basis of first holding unit KFi comparison
is held, and the comparison information (data string) to be compared is held in the second holding unit. 13 is a reading section.

The reading unit 13 reads the corresponding portions of the reference information and comparison information in units of constituent elements from the designated positions of the holding units 11 and 12 in response to a command from the determining unit 17, which will be described later. , the columns of the constituent elements are swapped as necessary, and the first. It is designed to be outputted to the comparator 14 as a second readout output. The comparator 14 compares these @1. It compares the second read outputs to detect coincidence/mismatch, and outputs a comparison detection signal COMP of logic 11' if they match, and logic 'o1 if they do not match. 15 is a counter for counting the number of times the comparator 14 detects a discrepancy; 16 is a storage section in which the count output of the counter 15 is stored; and 17 is a judgment section.

Judgment s77 is based on the comparison detection signal C output from the comparator 14.
According to OMP and the count output of the counter 15, the first . The next reading position in the second holding section 11, 12 and further replacement are designated.

With this designation, the reading unit 13 reads the constituent elements in advance,
In this embodiment, the similarity between the reference information and the comparison information is evaluated based on a comparison between the constituent elements, that is, a partial comparison. By the way, even if a match is not detected in this partial comparison, a match can be achieved by rearranging the arrangement of the constituent elements.・Configuration Ij of either the reference information or the comparison information! Instead of plain,
Sometimes a match can be made by looking ahead at the component several characters after the corresponding component. Therefore, in this embodiment, if no match is detected between the constituent elements that should originally be compared, the next #IItorl! The next operation (■) is performed without moving on to elementary comparison.

■-・First. The components at some positions (for example, the next position) following the corresponding position of the second holding unit 11.12 are read out, and the partial component string of either the reference information or the comparison information including the component at the corresponding position is read out. Perform the swap and compare.

If no match is detected in the operation (2), the operation (2) is performed without proceeding to the comparison of the next component in K11.

(2) Pre-read the components at some positions (for example, the next device) following ## in the first holding section 11 and compare them with the components at the 1* still position in the second holding section 12. If no match is detected in this operation (2), operation (2) is performed.

■...Several positions f following the insect position of the second holding part 12
Read ahead the S number elements of ft (for example, the next digit tjt),
Compare with the component at the corresponding position of the first holding part 1・The order of these operations ■ and ■ may be ■→■, and in this embodiment, the same is true even if a match is detected in either operation ■ or ■ It is designed to give an evaluation. If a match is not detected in the above operation (■), stop the operation of transforming the corresponding component to make it match as described in operations (■) to (6) above (operation ■), and then Similarly, we move on to the comparison of the next component.

When a match is detected by the comparator 14 (C
OMP='l'), the count output of the counter 15 at that time is stored in the storage section 16, and then the counter 15 is initialized, for example, cleared.

Further, if a match is not detected in the above operation (■), the judgment unit 11 increases the count output of the counter 15 by, for example, +1, stores it in the memory s16, and then clears the counter 15.Furthermore, the judgment unit I2 outputs the reference information. When the comparison between the information and the comparison information is completed, the sum of each count output stored in the storage unit 16 is calculated, and the degree of similarity is evaluated based on this value. In addition, in this embodiment, when calculating the sum of the above respective count outputs, the count output = "3" is equal to "2".
It is now processed as .

Next, the operation of the configuration shown in FIG. 1 will be explained by taking as an example the case of character string comparison in text sentence processing. For example, when the reference information is rTHI BU8I evil58J (referred to as a) and the comparison information is rHTK BU88INNESJ (referred to as b), rTHE BU8YJ (referred to as e), 1 and b are compared and a and C are compared, b,
Investigate which c has a higher degree of similarity to a.

First, a comparison between a and b will be explained. Now, a (rTHE BU8INESSJ) is placed in the first holding part 11, and f
jlIJ2 holding part 12 b (rHTE BU88IN
NE8J) are held respectively. When a comparison command is given to the determining unit 12 in this state, the determining unit 11 specifies the reading position of the first holding unit 11° and the second holding unit Z2 to the reading unit 13. As a result, the reading section 1B has the first holding section 11. The components T and H at the left end of the second holding section 12 are read out (in this embodiment, one character is one component), the first. It is output to the comparator 14 as a second readout output. Due to this, the first characters (T and H) are compared in the comparator 14. In this case, since they do not match, the comparator 14 outputs a comparison detection signal COMP of logic '01. The counter 15 counts up in response to the comparison detection signal COMP of logic 'O' and its count output becomes "1".
Based on the count output "1", the content of the next instruction to the reading unit 13 is determined, and the instruction for the above-mentioned operation (2) is given to the locking unit z3. Read unit 13# from this K
i first holding section 11. Each of the following 1 from the second holding part 12
Read the characters (2nd character) H, T, read the previous character T, H
Combined with HT and TH, replace one of the strings and read out the 1゜8g2 output from comparator 1.
Output to 4.

In this case, since they match, the comparator 14 outputs a logic '1''.
The comparison detection signal COMP of logic '11' is output.The judgment unit 17 knows that a match has been detected by the comparison detection signal COMPK of logic '11, and stores the count output '1' of the counter I5 at that time as shown in Figure 2. The counter 1s is then cleared. Next, in order to compare the 13th character of the judgment section 17F, an instruction to that effect is read out and given to the autopsy section 13. In this case, the comparator 14 compares the third characters, that is, E (a side) and E (b side), and a match is detected. Therefore, the counter 15 maintains a clear state, and as shown in FIG.
The count output "0" of 5 is stored. Hereinafter, as for the 4th character (blank) to the 7th character (S), the 4th to 7th characters match, respectively, as in the case described above, so the count output "0" of the counter 15 is the same as the whistle 2 figure. The data are sequentially stored in subsequent areas of the storage unit 16 as shown in FIG.

The next 8th character is I (a pull IJ), S (b side). In this case, they do not match, so the next 9th character is I (a side), 1 (b side).
ll) is also read out and the characters BN (a side), 5r (b side)
, replace one of the strings and compare (operation ■″). Since there is no match in the case of , the above-mentioned ■
An instruction for the operation is given from the judgment section 17 to the reading section 1M. As a result, one character is read ahead from the sgl holding unit 11 (9th character N) and compared with the 1208th character S of the second holding unit. A nine-voice piece will be performed. That is, one character is prefetched from the second holding section 12 (the ninth character I) and compared with the eighth character I of the first holding section 11 . As a result, the comparator 14 detects a match. In this example, the number of times a mismatch is detected after the 8th character is compared until a match is detected is three times, and as shown in FIG. The count output "3" of the counter 15 is stored. In this case, as mentioned above, a match between the 8th character of a and the 9th character of b is detected by the operation ■, so the next comparison is between the 9th character N of a and the 10th character N of b. It is done between. In this comparison, t
ill! As shown in FIG. 2, the count output "0" of the counter 15 is stored.

Next, the 10th character E of 1 is compared with the 11th character N of b. In this case, there is a mismatch, so the 11th character of a is 8. The 12th character E of b is also read and the character string E8 (1
side), NE (b@), and replace one of the character strings and compare (operation ■). In this case as well, there is no match, so in comparing the 11th character S of a and the 1st character N of bol, Shift (operation ■), and since they do not match even with the operation ■, the 10th character E of Sara Ka and the 12th character E of b
Move on to comparison with (operation ■).

As a result, a match is detected in the comparator 14. In this example, the number of times the mismatch has been detected from the previous clearing of the KAKUN-RI 15 until the above match is detected is 3, as shown in FIG. The count output "3" of the counter I5 is stored in a further area of the storage unit 16 so that In this case, as mentioned above, a match between the 10th character of a and the 12th character of b was detected by the operation ■, so the next comparison is between the 11th character B of a and the 13th character S of b. It will be held in

As is clear from this comparison, a match is detected, and storage unit 1
In the area further following 6, the count output "0" of the counter 15 is stored as shown in Figure 2.

Next, the 12th character (S) of 1 is compared with the 14th character (blank) of b. In this case, there will be a mismatch, and the subsequent comparison based on operation (2) will also be a mismatch. Then, by the operation ■ following the operation ■, the 13th character (blank) is pre-read by one character from the first holding unit 11, and the 14th character b (
f rank) and a match is detected. Therefore, in the subsequent area of the storage unit 16, the count output “2” of the counter 16 is stored as shown in FIG. When the comparison between a) and the contents of the second holding unit 120 (comparison information b) is completed, the sum of each count output sequentially stored in the storage unit 16 is calculated. At this time, since the determination unit 17 processes the count output "3" as the count output "2", the total sum becomes "7" in the above example. If this sum is small, the degree of similarity is high, and it becomes K.

Next, a comparison between a and C will be explained. In this case, the first
1 (rT part BUSI Po5SJ) will be held in the holding section 11, and e ("Tnh BUSYJ) will be held in the second holding section 12.As is clear, operation ■ is required for the first to seventh characters. A match is detected without going through ~ ■ Therefore, t;II3 is stored in seven consecutive areas of the storage unit 16
As shown in the figure, count output "0" is stored.

On the other hand, for the 8th to 11th characters, operate ■~
Since no match is detected even after step (■), the operation for matching the corresponding character is stopped (operation -).

In this case, the count output of the counter 15 is "3", and the judgment unit 17 adds 1 to this count output "3",
It is stored in the storage unit I6 as a count output "4".

Therefore, the count output "4" is stored in four consecutive areas of the storage unit 16 as shown in Figure 3. In addition, for the second character (S) of lot, by reading ahead the 13th character (blank), a match is detected between the 13th character (blank) of and the 12th character (blank) of b, so the memory 160 A count output "2" is stored in the subsequent area as shown in Figure 3. As a result of the partial comparison between a and C, the sum of the count outputs sequentially stored in the storage unit 16 is "18". Therefore, it is easy to see that C and Kurape b are more similar to Hatake. As is clear from the above description, according to this embodiment, the degree of similarity of comparison information to reference information can be expressed as a numerical value (the smaller the degree, the higher the degree of similarity). Therefore, information can be recognized by setting a reference value for each reference information and comparing the reference value with the sum of the count outputs (single similarity). This is not limited to the processing of text sentences in the above embodiment, but is also applicable to voice I&! i! It is also suitable for recognition of turns and turns.

In the above embodiment, the count output of Kakunta 15 was used as it is for similarity evaluation (the count output "3" was used as it is for similarity evaluation).
Exception) 1 weight specification section is provided for operation details (■
~ ■) You may make a further difference by K, -
! In addition, operations (1) to (2) do not necessarily have to be performed in the order of the above embodiments, and some of operations (1) to (2) may be omitted.

Further, in the above embodiment, the case where the comparison is performed using one character (1 element) as the minimum unit has been explained, but it is also possible to provide a specific section (two or more constituent elements) and compare each section.

As detailed above, according to the similarity detection device of the present invention,
The degree of similarity between comparison information and reference information can be detected efficiently.

[Brief explanation of the drawing]

FIG. 1 is a block diagram showing an embodiment of the similarity detection device of the present invention, and FIGS. 2 and 3 are diagrams showing an example of the storage contents of a storage unit for showing comparison results for two types of comparison information. It is. 11...[1 holding part, I! ... Joy 2 holding department, IJ・
...Reading unit, 14...Comparator, 15...Kakunta. 16... Storage section, 17... Judgment section. Applicant's agent Patent attorney Takehiko Suzue Figure 1

Claims (3)

[Claims] (1) A first holding section where reference information is held, a second holding section where comparison information is held, and the above reference information and comparison information are collected from designated areas of these first and second holding sections, respectively. a comparator that reads out the first and second read outputs from the first and second readout sections by reading out the first and second readout outputs from the first readout section and the second readout outputs by interchanging the columns of the constituent elements as necessary; a counter for counting the number of times the comparator detects a mismatch; a storage section for storing the count output of the counter; Every time a match is detected by the comparator, the count output of the counter at that time is stored in the storage section K11, and when the comparison of the reference information and comparison information is completed, the similarity is stored based on the contents stored in the storage section. 1. A similarity detection device, comprising: a determination unit that evaluates the degree of similarity. (2) When a match is detected by the comparator, the judgment section initializes the counter after storing the count output of the counter in the storage section, and also initializes the subsequent component with respect to the reading section. In addition to giving an instruction to read a predetermined number of components, if the comparator detects a mismatch, read/read the component string containing the corresponding component.
Claim 1, characterized in that an instruction for a replacement operation or an operation for pre-reading a predetermined number of components following the corresponding component is given to the reading unit in accordance with the count output of the counter. similarity detection device. (3) When the comparator detects a discrepancy and the count output of the counter reaches a predetermined value, the judgment section adds a constant value to the count output of the counter and stores it in the storage section; 3. The similarity detection device according to claim 2, wherein an instruction is given to the reading unit to read out a predetermined number of subsequent components.