CN104008119B - A kind of one-to-many mixed characters string fusion comparison method - Google Patents

Abstract

The invention discloses a one-to-many mixed character string fusion comparison method, which uses a source character string to find the most similar or matching target character string from a group of character strings to be compared. First use the improved GST* algorithm, and then use a partially ordered string comparison algorithm POC. Combining the characteristics of the above two algorithms in terms of string disorder and partially ordered matching, the matching degree values calculated by the two algorithms are weighted and fused to obtain the final matching degree. In addition, considering that synonymous strings have different expressions in different occasions, a string equivalent replacement strategy is adopted to equivalently replace synonymous character substrings in the source string and the string to be compared with the same string, Greatly improve the matching of two strings. By matching the source string with a group of strings to be matched respectively, and then sorting the matching degrees, and taking the string with the highest matching degree as the target string, the better matching of one-to-many mixed strings is realized.

Description

A One-to-Many Mixed String Fusion Comparison Method

technical field

The invention belongs to the technical field of character string intelligent comparison, and in particular relates to a novel one-to-many mixed character string fusion comparison method.

Background technique

String comparison is a basic problem in computer science, and its research content has important application value in many fields such as information retrieval and pattern recognition ^[1]-[4] .

Document 1 studies the fuzzy matching algorithm of Chinese character strings respectively, and Document 2 studies a Chinese character string similarity calculation method based on Chinese character clustering features. Document 3 compares the LCS and GST algorithms. The GST algorithm is a greedy string comparison algorithm and an unordered matching algorithm. It is widely used at present, but the algorithm uses the method of character-by-character comparison of two strings. , so the time complexity of the algorithm is large. Document 4 studies the RKR-GST algorithm after the improvement of the GST algorithm, which improves the operating efficiency of the GST algorithm, but the choice of the hash function in the RKR-GST algorithm has a great impact on the operation of the algorithm.

Existing character string comparison methods often only use one algorithm, which fails to make full use of the respective characteristics of unordered character substrings and partially ordered character substrings in the calculation of matching degrees, and their comparison results are often not ideal. In some practical applications of some mixed character strings, not only high accuracy of comparison is required, but also high speed of comparison is required. At present, it is often difficult to accurately express the similarity of character strings through a single matching calculation method.

In addition, the existing string comparison methods do not consider the situation that synonymous strings may have different expressions, which makes it difficult for the existing string comparison methods to meet the requirements of more accurate and high matching rates in such cases.

references:

[1] Chen Kaiqu, Zhao Jie, Peng Zhiwei. Fast Chinese String Fuzzy Matching Algorithm [J]. Chinese Journal of Information, 2003, 18(2): 58-65

[2] Wang Jingting. Research on Similarity Calculation of Chinese Strings Based on Chinese Character Clustering Features [J]. Modern Library and Information Technology, 2011, 20(2): 48-53

[3] Yu Haiying. Comparison of LCS and GST Algorithms in String Similarity Measurement [J]. Electronic Science and Technology, 2011, 24(3): 101-103

[4] Niu Yongjie. Analysis and Implementation of RKR_GST Algorithm in _NET [J]. Information Technology, 2012, 3: 171-174

Contents of the invention

In view of the above deficiencies in the prior art, the purpose of the present invention is to provide a more accurate method for fusion and comparison of mixed character strings. It solves the problems that it is difficult to accurately express the similarity between strings with a single matching degree calculation method in practical applications, and the existing string comparison methods are almost invalid when synonymous strings have different expressions.

The purpose of the present invention is achieved by the following means:

A one-to-many mixed string fusion comparison method, which performs fusion comparison on the similarity of mixed strings composed of Chinese characters, numbers, and English letters based on the clustering characteristics of Chinese characters, so as to improve the accuracy of expressing the similarity of strings degree, including the following main steps:

1) Take out the source string and a set of strings to be matched;

2) Read out the string equivalent replacement dictionary built in memory in advance, and perform equivalent replacement of some characters (substrings) in the group of strings to be matched; Unify the two substrings with different descriptions but the same meaning in the string to be matched;

3) Take out the source string, and then take out a string to be matched in the array of strings to be matched after equivalent replacement;

4) Use the GST* algorithm to calculate the matching degree a between the source string and the string to be matched:

The traditional GST algorithm is used to obtain the common substrings in the two strings, and store them in the public substring linked list. If the ratio of the character length of a certain common substring to the character length of a longer character string is greater than or equal to 0.33, then when calculating the matching degree, the number of characters of the common substring is multiplied by a weight, and the weight is a constant greater than 1; If the ratio of the character length of a certain common substring to the character length of the longer string is less than 0.33, and the number of characters in the common substring is greater than the minimum matching length, then the number of characters in the common substring is directly taken into account when calculating the matching degree. into the calculation;

5) Use the partial order string matching algorithm POC (Partial Order Comparison, POC) to calculate the matching degree b between the source string and the string to be matched:

The two mixed strings containing Chinese characters, numbers and English letters to be matched are respectively called the source string and the string to be matched,

First, search for the same characters or Chinese characters in the source string and the string to be matched, and record their numbers;

Secondly, use the longer string in the source string and the string to be matched as the standard to find the matching degree 1 (match_degree1):

Using the shorter string as the standard, find the matching degree 2 (match_degree2):

[ ] in formulas (1) and (2) means rounding;

Again, compare the first or second number and letter in the source string and the string to be matched, and the last or second-to-last number and letter, and if one of them is equal, adjust the match_degree2 value of matching degree 2 For match_degree2+1:

Assign different weights 0.41 and 0.59 to matching degree 1 and matching degree 2, and find the final matching value b of the source string and the string to be matched:

b=match_degree1×0.41+match_degree2×0.59 (3)

6) Perform weighted fusion of the matching degree a obtained by step 4) GST* calculation and the matching degree b obtained by step 5) POC calculation. The fusion method is that if the matching degree a is greater than the matching degree b, the final matching degree is a; if Matching degree a is less than matching degree b, then the final matching degree is equal to (a+b)/2;

7) Sort the matching degree calculated by the source string and each to-be-matched string in the to-be-matched string array, and use the to-be-matched string corresponding to the maximum matching degree as the target string that best matches the source string.

In step 4), the common substrings that are the same as the source string and the string to be matched are first searched out, and then different weights are assigned to the common substrings of different lengths, which increases the weight of longer common character substrings.

The GST* algorithm of the present invention is aimed at the phenomenon that the matching degree of the shorter common substring that exists in the traditional GST algorithm may be larger than the matching degree of the long common substring, and it is improved: if the character length of the common substring is the same as the longer If the ratio of the character length of the string is greater than or equal to 0.33, multiply the number of characters of the common substring by the weight (a constant greater than 1) when calculating the matching degree; if the character length of the common substring is greater than the character length of the longer string The ratio of is less than 0.33, and the number of characters in the common substring is greater than the minimum matching length, then the number of characters in the common substring is directly brought into the calculation when calculating the matching degree.

In step 5), two mixed strings containing numbers, letters, and Chinese characters are used as the source string and the string to be matched respectively; the longer string and the shorter string are used as the standard to find the matching degree 1 and matching degree 2; then compare whether the first or more numbers and letters, and the last one or more numbers and letters are equal, and modify the matching degree 2. Finally, different weights are assigned to the two matching degrees to obtain the matching degree value between the two strings.

The partial ordered character string comparison algorithm POC of the present invention considers that the matching degree 2 can better reflect the actual matching situation, so the matching degree 2 is given a slightly larger weight.

The invention provides a character string equivalent replacement strategy. For example, "high voltage side" and "220KV side", "kilovolt" and "kV" are equivalent in meaning. The existing comparison algorithms cannot accurately reflect the equivalence relationship between them, so a string equivalent replacement strategy is proposed. Build a character substring equivalent replacement dictionary in advance, using the form of: substring to be matched = equivalent source side substring, such as kilovolts = kV, which means that the character substrings on both sides of the equal sign are the same in meaning , the substring on the left side of the equal sign represents a substring in the string to be matched, and the substring on the right side of the equal sign represents a substring in the source string equivalent to the left side.

Before doing the matching degree calculation, first check whether the string to be matched contains a character substring equivalent to the character substring on the left side of each line in the replacement dictionary, and if so, replace it with the source side character substring on the right side of the equal sign . On this basis, the fusion comparison algorithm is used to compare and calculate the corresponding matching degree, which greatly improves the matching accuracy and can reflect the real matching situation between the two character strings involved in the comparison.

The invention is suitable for comparison of one-to-many mixed character strings. Calculate the matching degree of the source string and a group of strings to be matched respectively, and sort the obtained matching degrees, find out the string to be matched with the highest matching degree with the source string, and determine it as the target string, This enables better matching of one-to-many strings.

Description of drawings:

FIG. 1 is a flow chart of a novel one-to-many character string fusion comparison method.

Fig. 2 is an application example of the fusion comparison method of one-to-many mixed character strings.

detailed description

Below in conjunction with accompanying drawing, method of the present invention is described in further detail

The present invention will be described in further detail below in conjunction with the accompanying drawings. The invention specifically relates to a fusion comparison method of mixed character strings. Firstly, the character string to be matched is referred to as the source character string and the character string to be matched respectively. The present invention is more suitable for finding the target matching character string that best matches the source character string from a group of character strings to be matched.

The specific implementation method is as follows.

1. Take out the source string and a set of strings to be matched;

2. Read out the string equivalent replacement dictionary built in advance, and perform equivalent replacement for some characters in the group of strings to be matched. For example, "high voltage side" is equivalent to "220KV side", and "kV" is equivalent to "kV". Before calculating the string matching degree, the above different descriptions can be unified by using the equivalent replacement dictionary;

3. Take out the source string, and accordingly take out a string to be matched in the array of strings to be matched after equivalent replacement;

4. Use the GST* algorithm to calculate the matching degree between the source string and the string to be matched.

The improvement effect of the GST* algorithm and the traditional GST algorithm is illustrated by the following examples.

For example, "abcde" and "qbcio", "abcde" and "qbico" are two groups of character strings to be compared, and the GST algorithm is used to calculate the matching degree of both groups of character strings to be 40%.

The GST* algorithm is used to calculate the matching degree of the two groups of strings, and the results are 43.2% and 40% respectively. It can be seen that the comparison result of the GST* algorithm is more accurate.

The GST* algorithm makes the matching degree of two strings with longer common substrings higher.

5. Use the partial ordered string matching algorithm POC to calculate the matching degree between the source string and the string to be matched.

The two mixed character strings containing Chinese characters, numbers and letters to be matched are respectively called the source string and the character string to be matched.

First, search for the same characters in the source string and the string to be matched, and record their numbers.

Secondly, use the longer string in the source string and the string to be matched as the standard to find the matching degree 1 (match_degree1):

Using the shorter string as the standard, find the matching degree 2 (match_degree2):

[□] in formulas (1) and (2) means rounding.

Again, compare the first (or second) number and letter in the source string and the string to be matched, and the last (or second last) number and letter, and if one of them is equal, adjust the matching degree The match_degree2 value of 2 is match_degree2+1.

Finally, because in practical applications, matching degree 2 can better reflect the actual matching situation, so matching degree 2 is given greater weight.

Assign different weights 0.41 and 0.59 to matching degree 1 and matching degree 2, and find the final matching value b of the source string and the string to be matched:

b=match_degree1×0.41+match_degree2×0.59 (3)

6) Perform weighted fusion of the matching degree a obtained by step 4) GST* calculation and the matching degree b obtained by step 5) POC calculation. The fusion method is that if the matching degree a is greater than the matching degree b, the final matching degree is a. If the matching degree a is smaller than the matching degree b, the final matching degree is equal to (a+b)/2.

Get the final comparison result, making full use of the characteristics of the two algorithms;

7. Check whether the loop is executed;

8. Sort each matching degree, find out the character string corresponding to the highest matching degree, and use it as the most matching target character string.

Fig. 2 is an application example of the mixed character string one-to-many comparison method of the present invention. Matches are computed for a set of mixed strings. Figure 2 lists the matching degree of GST*_POC after using the GST* algorithm, the partial ordered string matching algorithm (POC algorithm), and the weighted fusion method of the two algorithms.

It can be seen that in the first comparison and the second comparison in Fig. 2, the string to be matched in the first item is closer to the source string in the first column than the string to be matched in the second item.

From the results in Figure 2, it can be concluded that a relatively ideal comparison result has been obtained by using the algorithm of the present invention.

Claims (1)

1. a kind of one-to-many mixed characters string fusion comparison method, to based on Chinese characters clustering feature by Chinese character, numeral, English The similarity of the mixed characters string of letter composition carries out fusion ratio pair, to improve the similar accuracy of expression character string, including Following key step：

1) source string and one group of matching string are taken out；

2) the character string equivalencing dictionary built in memory in advance is read, to partial character in this group of matching string I.e. substring carries out equivalencing；Using equivalencing dictionary, will have not in source string occasion and matching string occasion Describe together but two kinds of substrings of implication identical are unified；

3) source string is taken out, a character to be matched in the matching string array after equivalencing is taken out successively String；

4) source string and the matching degree a of the matching string are calculated using GST* algorithms：

Using traditional GST algorithms, each public substring in two character strings is obtained, they are stored in public substring chained list, if The ratio of the character length of some public substring and longer character string character length is more than or equal to 0.33, then is calculating matching degree When the character number of the public substring is multiplied by weight, the weight is constant more than 1；If the character of some public substring is long Degree and the ratio of longer character string character length are less than 0.33 and the character number of public substring is more than smallest match length, then The character number of the public substring is brought directly to calculating when calculating matching degree；

5) source string and the matching degree b of matching string are calculated using partially orderly string matching algorithm POC：

Two mixed characters strings containing Chinese character, numeral and English alphabet to be matched are referred to as source string and to be matched Character string,

First, source string and identical character in matching string are searched out, their number is recorded, secondly, with source Longer character string is standard in character string and matching string, seeks matching degree 1：

, as standard, to seek matching degree 2 wherein compared with short character strings：

[] represents to round in formula (1), (2)；

Again, the 1st or the 2nd numeral and letter, last 1 or reciprocal in source string and matching string are respectively compared 2nd numeral and letter, if wherein 1 equal, the numerical value of adjustment matching degree 2 is match_degree2+1:

Different weights 0.41,0.59 are assigned to matching degree 1 and matching degree 2, the matching of source string and matching string is asked Spend b：

B=match_degree1 × 0.41+match_degree2 × 0.59 (3)

6) by step 4) GST* calculate obtained by matching degree a and step 5) POC calculate obtained by matching degree b be weighted fusion, Fusion method is, if matching degree a is more than matching degree b, final matching degree is a；If matching degree a is less than matching degree b, most Whole matching degree is equal to (a+b)/2；

7) each matching string calculating in source string and matching string array is obtained into matching degree to be ranked up, The corresponding matching string of maximum matching degree, the target string most matched with source string is used as.