PHP:使用levenshtein距离来匹配单词

Question

我一直在阅读和测试php levenshtein中的一些例子.将$ input与$ words输出进行比较比较

$input = 'hw r u my dear angel';

    // array of words to check against
    $words  = array('apple','pineapple','banana','orange','how are you',
                    'radish','carrot','pea','bean','potato','hw are you');

输出

Input word: hw r u my dear angel
Did you mean: hw are you?

比较,删除hw你在阵列中.

$input = 'hw r u my dear angel';

    // array of words to check against
    $words  = array('apple','pineapple','banana','orange','how are you',
                    'radish','carrot','pea','bean','potato');

在第二个删除hw你是在数组输出

Input word: hw r u my dear angel
Did you mean: orange? 

在哪里 similar_text()

 echo '<br/>how are you:'.similar_text($input,'how are you');
    echo '<br/>orange:'.similar_text($input,'orange');
    echo '<br/>hw are you:'.similar_text($input,'hw are you');

how are you:6
orange:5
hw are you:6

在第二次比较为什么它输出橙色时,你怎么还6类似的文字像汉王是你？有没有办法改进或更好的方法呢？同时我保存数据库上所有可能的输入.我应该查询并存储array然后foreach用来获取levenshtein distance？但如果有数百万人,这将是缓慢的.

码

  <?php
    // input misspelled word
    $input = 'hw r u my dear angel';

    // array of words to check against
    $words  = array('apple','pineapple','banana','orange','how are you',
                    'radish','carrot','pea','bean','potato','hw are you');


    // no shortest distance found, yet
    $shortest = -1;

    $closest = closest($input,$words,$shortest);


    echo "Input word: $input<br/>";
    if ($shortest == 0) {
        echo "Exact match found: $closest\n";
    } else {
        echo "Did you mean: $closest?\n";
    }
    echo '<br/><br/>';

    $shortest = -1;
    $words  = array('apple','pineapple','banana','orange','how are you',
                    'radish','carrot','pea','bean','potato');
    $closest = closest($input,$words,$shortest);
    echo "Input word: $input<br/>";
    if ($shortest == 0) {
        echo "Exact match found: $closest\n";
    } else {
        echo "Did you mean: $closest?\n";
    }

    echo '<br/><br/>';
    echo 'Similar text';
    echo '<br/>how are you:'.similar_text($input,'how are you');
    echo '<br/>orange:'.similar_text($input,'orange');
    echo '<br/>hw are you:'.similar_text($input,'hw are you');



    function closest($input,$words,&$shortest){
        // loop through words to find the closest
    foreach ($words as $word) {

        // calculate the distance between the input word,
        // and the current word
        $lev = levenshtein($input, $word);

        // check for an exact match
        if ($lev == 0) {

            // closest word is this one (exact match)
            $closest = $word;
            $shortest = 0;

            // break out of the loop; we've found an exact match
            break;
        }

        // if this distance is less than the next found shortest
        // distance, OR if a next shortest word has not yet been found
        if ($lev <= $shortest || $shortest < 0) {
            // set the closest match, and shortest distance
            $closest  = $word;
            $shortest = $lev;
        }


    }
    return $closest;
    }
    ?>

Answer 1

首先,输出similar_text()是什么并不重要,因为它使用另一种算法来计算字符串之间的相似性.

让我们试着理解为什么levenstein()这么想,我亲爱的肛门更接近橙色,而不是"你好吗？维基百科对Levenstein距离的定义很好.

非正式地,两个单词之间的Levenshtein距离是将一个单词更改为另一个单词所需的单字符编辑(插入,删除,替换)的最小数量.

现在让我们计算一下我们需要做多少次编辑才能将我亲爱的天使变成橙色.

1. 我亲爱的天使→我亲爱的天使(删除最后一个角色)
2. hw ru亲爱的ange→hw ru我的dearange(删除最后一个空格)
3. hw ru my dearange→arange(删除前12个字符)
4. arange→orange(用o代替a)

所以需要1 + 1 + 12 + 1 = 15编辑总计来改变我亲爱的天使变成橙色.

这是我亲爱的天使变成了你怎么样.

1. 我亲爱的天使→我亲爱的天使怎么样(插入o字符)
2. 如何我亲爱的天使→多么亲爱的天使(删除7个字符)
3. 怎么亲爱的天使→如何天使(删除2个字符)
4. 如何天使→天使怎么样(插入e字符)
5. 怎么天使→怎么是ang(删除最后2个字符)
6. ang怎么样→你好吗(最后3个字符的替代)

总1 + 7 + 2 + 1 + 5 = 16编辑.所以你可以看到莱文斯坦的距离橙色更接近我的亲爱的天使 ;-)