Расстояние Левенштейна — это мера разницы между двумя строками, представляющая собой минимальное количество односимвольных изменений (вставок, удалений или замен), необходимых для преобразования одной строки в другую. В этой статье блога мы рассмотрим несколько методов расчета расстояния Левенштейна в PHP, а также приведем примеры кода.

Метод 1: встроенная функция levenshtein()
PHP предоставляет встроенную функцию levenshtein(), которая вычисляет расстояние Левенштейна между двумя строками. Вот пример того, как его использовать:

$distance = levenshtein("kitten", "sitting");
echo "Levenshtein distance: " . $distance; // Output: Levenshtein distance: 3

Метод 2: подход динамического программирования
Мы также можем реализовать алгоритм расстояния Левенштейна, используя подход динамического программирования. Этот метод более эффективен, чем рекурсивный подход. Вот пример:

function levenshteinDistance($str1, $str2) {
    $m = strlen($str1);
    $n = strlen($str2);
    $dp = [];
    for ($i = 0; $i <= $m; $i++) {
        $dp[$i][0] = $i;
    }
    for ($j = 0; $j <= $n; $j++) {
        $dp[0][$j] = $j;
    }
    for ($i = 1; $i <= $m; $i++) {
        for ($j = 1; $j <= $n; $j++) {
            $dp[$i][$j] = min(
                $dp[$i - 1][$j] + 1,
                $dp[$i][$j - 1] + 1,
                $dp[$i - 1][$j - 1] + ($str1[$i - 1] !== $str2[$j - 1] ? 1 : 0)
            );
        }
    }
    return $dp[$m][$n];
}
$distance = levenshteinDistance("kitten", "sitting");
echo "Levenshtein distance: " . $distance; // Output: Levenshtein distance: 3

Метод 3: сложность оптимизированного пространства
Подход динамического программирования использует матрицу для хранения промежуточных результатов, что может потребовать большого количества памяти для больших строк. Мы можем оптимизировать сложность пространства, используя одновременно только две строки матрицы. Вот пример:

function levenshteinDistanceOptimized($str1, $str2) {
    $m = strlen($str1);
    $n = strlen($str2);
    $prev = range(0, $n);
    $curr = array_fill(0, $n + 1, 0);
    for ($i = 1; $i <= $m; $i++) {
        $curr[0] = $i;
        for ($j = 1; $j <= $n; $j++) {
            $curr[$j] = min(
                $prev[$j] + 1,
                $curr[$j - 1] + 1,
                $prev[$j - 1] + ($str1[$i - 1] !== $str2[$j - 1] ? 1 : 0)
            );
        }
        $prev = $curr;
    }
    return $curr[$n];
}
$distance = levenshteinDistanceOptimized("kitten", "sitting");
echo "Levenshtein distance: " . $distance; // Output: Levenshtein distance: 3

В этой статье мы рассмотрели несколько методов расчета расстояния Левенштейна в PHP. Мы обсудили использование встроенной функции levenshtein()и реализацию алгоритма с использованием как подхода динамического программирования, так и подхода оптимизированной пространственной сложности. В зависимости от вашего конкретного варианта использования и размера используемых строк вы можете выбрать метод, который лучше всего соответствует вашим потребностям. Расстояние Левенштейна — мощный инструмент для измерения сходства строк и определения минимального количества изменений, необходимых для преобразования одной строки в другую.

Поняв и внедрив эти методы, вы сможете эффективно вычислять расстояние Левенштейна и расширять возможности сравнения строк и анализа сходства ваших PHP-приложений.