如何优化 PHP 应用程序和 MySQL 数据库之间的 Levenshtein 距离计算？

MySQL 和 PHP 中的 Levenshtein：一种优化方法

在原始代码片段中，计算给定单词与每个单词之间的 Levenshtein 距离使用 PHP 中的 levenshtein 函数从数据库中提取术语。然而，这种方法涉及多个数据库查询，这对于大型数据集可能效率低下。更有效的解决方案是利用 Levenshtein 距离作为数据库查询本身的过滤器。

要实现此目的，您需要在 MySQL 中实现 Levenshtein 函数。例如，您可以考虑以下自定义函数：

DELIMITER $$
CREATE FUNCTION levenshtein(s1 VARCHAR(255), s2 VARCHAR(255)) RETURNS INT
BEGIN
DECLARE len1 INT DEFAULT LENGTH(s1);
DECLARE len2 INT DEFAULT LENGTH(s2);
DECLARE i, j, cost, d INT DEFAULT 0;

DECLARE sp VARCHAR(255);

IF len1 = 0 THEN
    RETURN len2;
ELSEIF len2 = 0 THEN
    RETURN len1;
ELSE
    SET sp = REPEAT(' ', len1);
    FOR i = 1 TO len1 DO
        SET sp = CONCAT(sp, i);
    END FOR;
    SET sp = CONCAT(sp, CHAR(10));
    FOR j = 1 TO len2 DO
        SET sp = CONCAT(sp, j, CHAR(10));
        SET cost = j;
        FOR i = 1 TO len1 DO
            IF s1 SUBSTRING(i, 1) = s2 SUBSTRING(j, 1) THEN
                SET d = 0;
            ELSE
                SET d = 1;
            END IF;
            SET cost = LEAST(
                cost + 1,
                i + 1 + 1,
                j + d + 1
            );
            SET sp = CONCAT(sp, cost);
        END FOR;
    END FOR;
    SET sp = CONCAT(sp, CHAR(10));
    RETURN SUBSTRING_INDEX(sp, CHAR(10), -1) - len1 - 1;
END IF;
END$$
DELIMITER ;

在 MySQL 中定义 Levenshtein 函数后，您可以按如下方式修改查询：

$word = mysql_real_escape_string($word);
mysql_qery("SELECT `term` FROM `words` WHERE levenshtein('$word', `term`) BETWEEN 0 AND 4");

此查询将返回单词表中与指定单词的编辑距离在 0 到 4 之间的所有术语。通过避免多个 PHP 循环并依赖数据库的内置函数，您可以实现显着的性能提升，尤其是对于大型数据集。

以上是如何优化 PHP 应用程序和 MySQL 数据库之间的 Levenshtein 距离计算？的详细内容。更多信息请关注PHP中文网其他相关文章！