PHP：使用Levenshtein距离匹配单词

Question

PHP：使用Levenshtein距离匹配单词

3

我一直在阅读和测试php levenshtein的一些示例。将 $input 与 $words 进行比较，输出结果为：comparing。

$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?

比较并从数组中删除“你好吗”这个字符串。

$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: 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

On second comparison, why does it output "orange" when "how are you" also has 6 similar characters like "hw are you"? Is there any way to improve or a better method for this? Also, I am saving all possible inputs in the database. Should I query and store them in an array, then use a "foreach" loop to get the Levenshtein distance? However, this would be slow if I have millions of inputs.

  <?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;
    }
    ?>

- Snippet

你测试了什么？其中一些输出应该会给你更好的提示去寻找... - codeling

刚刚更新了我的问题。 - Snippet

1

第一步：你应该找到一个最小的例子来展示你的问题。因此，我建议首先输出各个莱文斯坦距离，并从那里开始解决问题。第二步：将多个问题放在一个问题中也不是一个好主意（例如存储输出应该单独成为一个问题，而且我甚至不确定我理解你的意思）。 - codeling

感谢 @nyarlathotep 提供的提示，现在我知道原因了。 - Snippet

请分享问题是什么！这些信息可能对其他人也有用。 - codeling

好的，我还在测试中。非常欢迎提出改进意见。 - Snippet

2个回答

1

发现一些东西...但是使用了mysql http://www.artfulsoftware.com/infotree/queries.php#552 我认为这比在php上处理更好，因为我的数据存储在数据库中。

CREATE FUNCTION levenshtein( s1 VARCHAR(255), s2 VARCHAR(255) )
  RETURNS INT
  DETERMINISTIC
  BEGIN
    DECLARE s1_len, s2_len, i, j, c, c_temp, cost INT;
    DECLARE s1_char CHAR;
    -- max strlen=255
    DECLARE cv0, cv1 VARBINARY(256);
    SET s1_len = CHAR_LENGTH(s1), s2_len = CHAR_LENGTH(s2), cv1 = 0x00, j = 1, i = 1, c = 0;
    IF s1 = s2 THEN
      RETURN 0;
    ELSEIF s1_len = 0 THEN
      RETURN s2_len;
    ELSEIF s2_len = 0 THEN
      RETURN s1_len;
    ELSE
      WHILE j <= s2_len DO
        SET cv1 = CONCAT(cv1, UNHEX(HEX(j))), j = j + 1;
      END WHILE;
      WHILE i <= s1_len DO
        SET s1_char = SUBSTRING(s1, i, 1), c = i, cv0 = UNHEX(HEX(i)), j = 1;
        WHILE j <= s2_len DO
          SET c = c + 1;
          IF s1_char = SUBSTRING(s2, j, 1) THEN 
            SET cost = 0; ELSE SET cost = 1;
          END IF;
          SET c_temp = CONV(HEX(SUBSTRING(cv1, j, 1)), 16, 10) + cost;
          IF c > c_temp THEN SET c = c_temp; END IF;
            SET c_temp = CONV(HEX(SUBSTRING(cv1, j+1, 1)), 16, 10) + 1;
            IF c > c_temp THEN 
              SET c = c_temp; 
            END IF;
            SET cv0 = CONCAT(cv0, UNHEX(HEX(c))), j = j + 1;
        END WHILE;
        SET cv1 = cv0, i = i + 1;
      END WHILE;
    END IF;
    RETURN c;
  END;

还有一个帮助函数：

CREATE FUNCTION levenshtein_ratio( s1 VARCHAR(255), s2 VARCHAR(255) )
  RETURNS INT
  DETERMINISTIC
  BEGIN
    DECLARE s1_len, s2_len, max_len INT;
    SET s1_len = LENGTH(s1), s2_len = LENGTH(s2);
    IF s1_len > s2_len THEN 
      SET max_len = s1_len; 
    ELSE 
      SET max_len = s2_len; 
    END IF;
    RETURN ROUND((1 - LEVENSHTEIN(s1, s2) / max_len) * 100);
  END;

但我不知道为什么会导致错误 您的SQL语法有误；请检查与您的MySQL服务器版本相对应的手册以获取正确的语法，位于第5行

- Snippet

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Konstantin · Accepted Answer

首先，不管 similar_text() 输出什么，都无所谓，因为它使用另一种算法计算字符串之间的相似度。

让我们试着理解为什么 levenstein() 认为 hw r u my dear ange 更接近于 orange 而不是 'how are you。维基百科有一个很好的定义，说明了Levenstein距离是什么。

非正式地说，两个单词之间的Levenshtein距离是将一个单词变成另一个单词所需的最小单字符编辑次数（插入、删除、替换）。

现在让我们来计算一下，要将hw r u my dear angel更改为orange需要做多少次编辑。

你好我的亲爱天使，问候你一下 → 你好我的亲爱天使，问候你一下 (删除最后一个字符)
你好我的亲爱天使，问候你一下 → 你好我的亲爱天使，问候你一下(删除最后一个空格)
你好我的亲爱天使，问候你一下 → ange (删除前12个字符)
ange → orange (将a替换为o)

因此，需要进行1 + 1 + 12 + 1 = 15次编辑才能将你好我的亲爱天使，问候你一下变成橙色。

以下是将你好我的亲爱天使，问候你一下转化为你好吗的过程。

hw r u my dear angel → how r u my dear angel (插入一个 o 字符)
how r u my dear angel → how dear angel (删除 7 个字符)
how dear angel → how ar angel (删除 2 个字符)
how ar angel → how are angel (插入一个 e 字符)
how are angel → how are ang (删除最后 2 个字符)
how are ang → how are you (替换最后 3 个字符)

总共 1 + 7 + 2 + 1 + 5 = 16 次编辑。所以你可以看到，用 Levinstein 距离来衡量，orange 更接近于 hw r u my dear angel ;-)