About PHP's similarity calculation function: introduction to the use of levenshtein

About PHP's similarity calculation function: introduction to the use of levenshtein_PHP tutorial

WBOY

Release： 2016-07-21 15:11:45

Original

1145 people have browsed it

Instructions for use
First read the description of the levenshtein() function in the manual:

The levenshtein() function returns the Levenshtein distance between two strings.

Levenshtein distance, also known as edit distance, refers to the minimum number of edit operations required between two strings to convert one into the other. Permitted editing operations include replacing one character with another, inserting a character, and deleting a character.

For example, convert kitten to sitting:

sitten (k→s)
sittin (e→i)
sitting (→g) levenshtein() function gives equal weight to each operation (replacement, insertion and deletion). However, you can define the cost of each operation by setting the optional insert, replace, and delete parameters.

Grammar:

levenshtein(string1,string2,insert,replace,delete)

Parameter Description

string1 required. The first string to compare.
string2 required. The second string to compare.
insert is optional. The cost of inserting a character. The default is 1.
replace optional. The cost of replacing a character. The default is 1.
delete optional. The cost of deleting a character. The default is 1.
Tips and Notes

If one of the strings exceeds 255 characters, the levenshtein() function returns -1.
The levenshtein() function is not case sensitive.
levenshtein() function is faster than similar_text() function. However, the similar_text() function provides more accurate results that require fewer modifications.
Example

Copy code The code is as follows:

echo levenshtein("Hello World","ello World");
echo "
";
echo levenshtein("Hello World","ello World",10,20,30);
?>

Output: 1 30

Source code analysis
levenshtein() is a standard function, and there is a file specifically implemented for this function in the /ext/standard/ directory: levenshtein.c.

levenshtein() will select the implementation method based on the number of parameters. For the cases where the parameter is 2 and the parameter is 5, the reference_levdist() function will be called to calculate the distance. The difference is that for the last three parameters, when the parameter is 2, the default value 1 is used.

And in the implementation source code, we found a situation that was not explained in the documentation: the levenshtein() function can also pass three parameters, which will eventually call the custom_levdist() function. It takes the third parameter as the implementation of a custom function. The calling example is as follows:

Copy the code The code is as follows:

echo levenshtein("Hello World","ello World", 'strsub');

The executive will report Warning: The general Levenshtein support is not there yet. This is because this method has not been implemented yet, it is just a pitfall.

The implementation algorithm of the reference_levdist() function is a classic DP problem.

Given two strings x and y, find the minimum number of modifications to change x into y. The modified rules can only be one of the following three types: deletion, insertion, or change.
Use a[i][j] to represent the minimum number of operations required to change the first i characters of x into the first j characters of y. Then the state transition equation is:

Copy code The code is as follows:

When x[i]==y[j]: a[i][j] = min(a[i-1 ][j-1], a[i-1][j]+1, a[i][j-1]+1);
When x[i]!=y[j]: a[ i][j] = min(a[i-1][j-1], a[i-1][j], a[i][j-1])+1;

Before using the state transition equation, we need to initialize the matrix d of (n+1)(m+1) and let the values of the first row and column grow from 0. Scan two strings (nm level), compare the characters, use the state transition equation, and finally $a[$l1][$l2] is the result.

The simple implementation process is as follows:

Copy the code The code is as follows:

    $s1 = "abcdd";
    $l1 = strlen($s1);
    $s2 = "aabbd";
    $l2 = strlen($s2);

    for ($i = 0; $i < $l1; $i++) {
        $a[0][$i + 1] = $i + 1;
    }
    for ($i = 0; $i < $l2; $i++) {
        $a[$i + 1][0] = $i + 1;
    }

    for ($i = 0; $i < $l2; $i++) {
        for ($j = 0; $j < $l1; $j++) {
            if ($s2[$i] == $s1[$j]) {
                $a[$i + 1][$j + 1] = min($a[$i][$j], $a[$i][$j + 1] + 1, $a[$i + 1][$j] + 1);
            }else{
                $a[$i + 1][$j + 1] = min($a[$i][$j], $a[$i][$j + 1], $a[$i + 1][$j]) + 1;
            }
        }
    }

    echo $a[$l1][$l2];
    echo "n";
    echo levenshtein($s1, $s2);

在PHP的实现中，实现者在注释中很清楚的标明：此函数仅优化了内存使用，而没有考虑速度，从其实现算法看，时间复杂度为O(m×n)。其优化点在于将上面的状态转移方程中的二维数组变成了两个一组数组。简单实现如下：

复制代码代码如下:

    $s1 = "abcjfdkslfdd";
    $l1 = strlen($s1);
    $s2 = "aab84093840932bd";
    $l2 = strlen($s2);

    $dis = 0;
    for ($i = 0; $i <= $l2; $i++){
        $p1[$i] = $i;
    }

    for ($i = 0; $i < $l1; $i++){
        $p2[0] = $p1[0] + 1;

        for ($j = 0; $j < $l2; $j++){
            if ($s1[$i] == $s2[$j]){
                $dis = min($p1[$j], $p1[$j + 1] + 1, $p2[$j] + 1);
            }else{
                $dis = min($p1[$j] + 1, $p1[$j + 1] + 1, $p2[$j] + 1);  // 注意这里最后一个参数为$p2  
            }
            $p2[$j + 1] = $dis;
        }
        $tmp = $p1;
        $p1 = $p2;
        $p2 = $tmp;  
    }

    echo "n";
    echo $p1[$l2];
    echo "n";
    echo levenshtein($s1, $s2);

The above is the optimization of the previous classic DP by PHP kernel developers. The optimization point is to continuously reuse two one-dimensional arrays, one to record the last result and the other to record the result this time. If you assign different values to the three operations according to the parameters of PHP, just change the corresponding 1 to the value corresponding to the operation in the above algorithm. The first parameter of the min function corresponds to modification, the second parameter corresponds to deletion of the source code sky, and the third parameter corresponds to addition.

Levenshtein distance description
Levenshtein distance was first invented by Russian scientist Vladimir Levenshtein in 1965 and named after him. If you don’t know how to pronounce it, you can call it edit distance. Levenshtein distance can be used for:
Spell checking (spelling check)
Speech recognition (sentence recognition)
DNA analysis (DNA analysis)
Plagiarism detection (plagiarism detection) LD uses a mn matrix to store distance values .