JP2820183B2 - String comparison 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 character string comparing method for determining the degree of similarity between two character strings.

[0002]

2. Description of the Related Art Conventionally, as a method of judging the degree of approximation between a compared character string a having a length m and a comparison character string b having a length n, Levenste required for converting a character string b into a character string a is used.
There is known a method of calculating a cost (hereinafter, referred to as a distance) called an in-distance.

To explain the outline of this method, there are three types of character string conversions: addition, deletion, and modification of characters. Each of these conversion types is assigned a conversion cost. Then, the total required conversion cost is the distance between the character strings a and b.

When the value of the distance is 0, the two character strings are equal, and the larger the value, the more the two character strings are different.

Hereinafter, this method will be described with reference to the drawings, taking as an example the case where the degree of approximation between the compared character string "aXbYc" and the compared character string "abc" is obtained. For the sake of simplicity, the costs of addition, deletion, and change are 1, 2, and 3, respectively.

FIG. 6 is a flowchart showing a conventional method. In the cost array initialization step, the length of the line to be compared has the length of the character string to be compared "aXbYc" +1, that is, 6, and the comparison is made as the column size. Length of character string "abc" +
After the value of the array element M [0,0] of the array M having 1, ie, 4, is set to 0, the array element M [0, j] (0 <
j <6) is a value obtained by adding an additional cost 1 to the value of M [0, j-1].

Then, the array element M [i, 0] in the 0th column
For (0 <i <4), a value obtained by adding a deletion cost 2 to the value of M [i-1, 0] is used. The array M after the initialization step is initialized as shown in FIG.

Thereafter, in FIG. 6, a cost array operation step is executed. FIG. 7 shows a flowchart of the cost array calculation step. In this cost array calculation step, the array element M [i, j] in the repetition controlled by the row and column control variable initialization step S8, row control determination step S9, and column control determination step S10 in the flowchart of FIG. For each of (0 <i <4 <0 <j <6), values are obtained in ascending order of the array.

Whether or not the i-th character of the comparison character string "aXbYc" is equal to the j-th character of the comparison character string "abc" is determined in a character comparison step S11. (Step S12) Array element M
[I, j], the value of the array element M [i-1, j-1], the value obtained by adding an additional cost 1 to the value of the array element M [i, j-1], the array element M [i- [J] cost 2
Is stored as the minimum value among the three values obtained by adding.

If they are different, cost calculation 2 (step S
13), the array element M [i, j] is added to the array element M [i−
[1, j-1]], the value obtained by adding the change cost 3 to the value of the array element M [i, j-1], and the value obtained by adding the additional cost 1 to the value of the array element M [i-1, j]. Is stored as the minimum value among the three values obtained by adding the deletion cost 2 to the value. FIG. 9 shows an array cost array M after the values of the array elements have been obtained in this manner.

The distance L2 in FIG. 9 is the character string to be compared "aXbY
c "and the degree of approximation of the comparison character string" abc ". In this case, it is 4.

[0012]

In the conventional character string comparison method, the continuity of characters in the character string is ignored.
For example, the compared character string “aXbYc” and the comparison character string “a
bc "and the compared character string" abcXY "and the compared character string" abc "become equal, and the continuity of the characters a, b, and c is not reflected in the determination of the similarity. there were.

Accordingly, it is an object of the present invention to provide a character string comparison method capable of more accurately determining the degree of approximation of a character string.

[0014]

According to the invention, the length m
The similarity between the compared character string a and the comparison character string b having the length n is set as a cost for each of addition, deletion, and change of characters, and the row size is m + 1 and the column size is n + 1. Is prepared, the array element M in the 0th column is prepared.
The value of [i, 0] (0 ≦ i ≦ m) is the cost of i × deletion, and the value of the array element M [0, j] (0 ≦ j ≦ n) is j × addition. And an array element M [i, j] (0 <i ≦ m, 0 <
j ≦ n) to the value of array element M [i−1, j−1],
The i-th character of the compared character string a and the j-th character of the compared character string b
If the second character is equal, 0; otherwise, the value obtained by adding the cost of the change, the value obtained by adding the additional cost to the value of the array element M [i, j-1], the array element M [i-1, j] And a value obtained by adding the cost of the deletion to the value of the cost calculation step. In the character string comparison method in which the character string a and the character string b are approximated by the cost of conversion into the string a, the partial matching array M ′ having the same size as the cost array M is further provided.
And a partial matching sequence initialization step of initializing all the array elements of the partial matching sequence M ′ to 0, and an array element M ′
If the value of [i, j] (0 <i ≦ m, 0 <j ≦ n) is equal to the j-th character of the compared character string b and the j-th character of the compared character string b, the array element M ′ A partial match operation step of adding 1 to the value of [i-1, j-1].
The character string comparison method is characterized in that the maximum length of the partial match obtained in the partial match calculation step is used as the degree of approximation of the character string, together with the cost of converting the character string b into the character string a.

[0015]

As described above, according to the character string comparison method of the present invention, in order to measure the continuity of characters, the partial matching array initializing step of initializing the partial matching array M 'storing the intermediate result and the array element M If the value of [i, j] is the same as the i-th character of the compared character string a and the j-th character of the comparison character string b, the value of the array element M '[i-1, j-1] A partial matching operation step of adding 1 to the comparison string, and the largest value among the array elements of the partial matching array M ′ obtained by the partial matching operation step is the compared character string a and the comparison character string b. Is the maximum length of the substring that matches

[0016]

DESCRIPTION OF THE PREFERRED EMBODIMENTS The present invention will be described with reference to the drawings.
FIG. 1 is a flowchart of the present invention, and FIG. 2 is a flowchart of the calculation steps of FIG.

A case will be described as an example where the character string to be compared "abcXY" is compared with the character string to be compared "abc". For simplicity of description, the costs of addition, deletion, and change are 1, 2, and 3, respectively.

In the initialization step shown in FIG. 1, the length of the line to be compared "aXbYc" is +1 as the line size, that is,
6, the cost array M and the cost array M having the length of the comparison character string “abc” +1 as the column size, ie, 4.
In the cost array initializing step 1 and the partially identical array initializing step 2, the partial coincidence array M ′ having the same size as is initialized as follows.

After setting the value of array element M [0,0] to 0,
For the array element M [0, j] (0 <j <6) on the 0th row, a value obtained by adding an additional cost 1 to the value of M [0, j-1] is used.

Then, the array element M [i, 0] in the 0th column
For (0 <i <4), a value obtained by adding a deletion cost 2 to the value of M [i-1, 0] is used. All array elements of array M 'are initialized to zero. The cost array M after the execution of the initialization step is initialized as shown in FIG.

Thereafter, the calculation step shown in FIG. 1 is executed. This calculation step includes a cost calculation step 3 and a partial match calculation step 4. Each step of the row and column control variable initialization step S1, the row control determination step S2, and the column control determination step S3 in the flowchart shown in FIG. Array element M [i,
j] (0 <i <4, 0 <j <6) and array element M ′
For each of [i, j] (0 <i <4, 0 <j <6), values are obtained in ascending order of the array subscript.

Next, the i-th character string of the compared character string "abcXY"
It is determined in a character comparison step S4 whether or not the jth character of the comparison character string "abc" is equal to the jth character. If the jth character is equal, the cost operation 1 (step S5) sets the array element M [i, j] The value of the array element M [i-1, j-1], the value obtained by adding an additional cost 1 to the value of the array element M [i, j-1], and the value of the array element M [i-1, j] Removal cost 2
Is stored, and the minimum value among the three values of the array element M ′ is stored in the partial match operation (step S4).
A value obtained by adding 1 to the array element M '[i-1, j-1] is stored in [i, j].

If different, cost calculation 2 (step S
6), the array element M [i, j] is added to the array element M [i−
[1, j-1]], the value obtained by adding the change cost 3 to the value of the array element M [i, j-1], and the value obtained by adding the additional cost 1 to the value of the array element M [i-1, j]. Is stored as the minimum value among the three values obtained by adding the deletion cost 2 to the value.

FIG. 4 shows the cost array M after the values of the array element 0 have been obtained in this manner.
Is shown in FIG.

The distance D1 shown in FIG.
cYX ”and the conversion cost of the comparison character string“ abc ”.
The maximum matching length L1 shown in FIG. 5 is the maximum length of the matching partial character string between the compared character string and the compared character string.

The distance D1 and the maximum matching length L1 obtained here are used as the degree of approximation of the character string.

[0027]

As described above, the present invention considers the continuity of characters when determining the degree of approximation of a character string.
The maximum length of the partial character string that matches the compared character string and the comparison character string can be obtained in the same manner, and the degree of approximation of the character string can be determined more accurately.

[Brief description of the drawings]

FIG. 1 is a flowchart of a character string comparison method according to the present invention.

FIG. 2 is a flowchart of a calculation step of FIG. 1;

FIG. 3 is a diagram showing a cost array M after execution of an initialization step in FIG. 1;

FIG. 4 is a diagram showing a cost array M after execution of the calculation step of FIG. 1;

FIG. 5 is a partial coincidence array M ′ after execution of the calculation step of FIG. 1;
FIG.

FIG. 6 is a flowchart of a conventional character string comparison method.

FIG. 7 is a flowchart of a cost array calculation step in FIG. 6;

FIG. 8 is a diagram showing a cost array M after execution of an initialization step in FIG. 6;

FIG. 9 is a diagram showing a cost array M after execution of the calculation step of FIG. 6;

[Explanation of symbols]

 1 Cost array initialization step 2 Partial match array initialization step 3 Cost calculation step 4 Partial match calculation step

Continuation of the front page (56) References JP-A-62-89134 (JP, A) JP-A-1-181124 (JP, A) JP-A-60-27938 (JP, A) JP-A-2-108157 (JP) JP-A-63-233427 (JP, A) JP-A-2-232768 (JP, A) JP-A-3-100865 (JP, A) L. Kashiap and B.K. J. Ommen, "A UNIF IED THEORY FOR ORDER PRESERVING PROPERTIES INVOLVING TWO STRINGS", Proceedings of the 1980 Conference on Information Services. Du and SC Chang, "A model and a fast algorithm for multiple errors spelling corrections", Acta Informatica 29, 281-28, Acta Informatic, 29, 281-28 (Int.Cl. ⁶ , DB name) G06F 17/30

Claims (1)

(57) [Claims] 1. A degree of approximation between a compared character string a having a length m and a comparison character string b having a length n is set to a cost for each of addition, deletion, and change of a character. After preparing a cost array M with m + 1 and a column size of n + 1,
The value of the array element M [i, 0] (0 ≦ i ≦ m) in the column is the cost of i × deletion, and the array element M [0, j]
A cost array initialization step in which the value of (0 ≦ j ≦ n) is added by j ×, and the value of an array element M [i, j] (0 <i ≦ m, 0 <j ≦ n) The value of the array element M [i-1, j-1] is added to the i-th character of the compared character string a and the j-th character of the compared character string b.
0 if the 2nd character is equal, otherwise the sum of the costs of change, array element M
It is the minimum value of three values: a value obtained by adding an additional cost to the value of [i, j-1], and a value obtained by adding a deletion cost to the value of the array element M [i-1, j]. And a cost calculation step of sequentially calculating the character string b obtained by the cost calculation step and converting the character string b into the character string a by using the character string a and the character string b as an approximation degree. In the column comparison method, further, a partial matching array M ′ having the same size as the cost array M is prepared, and all array elements of the partial matching array M ′ are initialized to 0. The value of element M ′ [i, j] (0 <i ≦ m, 0 <j ≦ n) is calculated by comparing the i-th character of the compared character string a with the j-th character of the compared character string b.
If the second character is equal, the array element M '[i-1, j
-1], which is a value obtained by adding 1 to the value of [-1]. The maximum length of the partial match obtained in the partial match calculation step is combined with the cost of converting the character string b into the character string a. A character string comparison method, wherein the degree of approximation of the character string is used.