Является ли мое решение Левенштейна редактировать расстояние неверно? - PullRequest
Новая
       26

Является ли мое решение Левенштейна редактировать расстояние неверно?

0 голосов
/ 28 апреля 2019

Я работаю над этой Levenshtein Edit Distance проблемой на AlgoDaily, и мое решение кардинально отличается от их решения. Раньше я не слышал о расстоянии редактирования Левенштейна, поэтому я основывал свой подход на описании проблемы и на том, как мне ее решить.

Описание проблемы

Расстояние редактирования - это способ количественно определить, насколько разные две строки. Это рассчитывается с использованием минимального количества преобразований для поворота одна строка в другую.

Преобразования включают вставку, удаление и замену. Вот расстояние редактирования рукавицы до сидения:

  1. варежка -> ситтен (замена "s" на "m")
  2. sitten -> sittin (замена «i» на «e»)
  3. сижу -> сидя (вставка "g" в конце).

Расстояние редактирования 3

Подход AlgoDaily с использованием концепции Левенштейна (javascript) 

function getEditDistance(a, b) {
    if (a.length == 0) return b.length;
    if (b.length == 0) return a.length;

    var matrix = [];

    // increment along the first column of each row
    var i;
    for (i = 0; i <= b.length; i++) {
        matrix[i] = [ i ];
    }

    // increment each column in the first row
    var j;
    for (j = 0; j <= a.length; j++) {
        matrix[0][j] = j;
    }

    // Fill in the rest of the matrix
    for (i = 1; i <= b.length; i++) {
        for (j = 1; j <= a.length; j++) {
            if (b.charAt(i - 1) == a.charAt(j - 1)) {
                matrix[i][j] = matrix[i - 1][j - 1];
            } else {
                matrix[i][j] = Math.min(
                    matrix[i - 1][j - 1] + 1, // substitution
                    Math.min(
                        matrix[i][j - 1] + 1, // insertion
                        matrix[i - 1][j] + 1
                    )
                ); // deletion
            }
        }
    }

    return matrix[b.length][a.length];
}

Мой подход (C #)

Выводит правильное расстояние для вышеупомянутого теста «варежка» -> «сидя». Я запустил его для нескольких других, и он продолжает выводить правильно. Я что-то упускаю (кроме того, что я фактически не применяю концепцию Левенштейна)? 

    public static int CalculateEditDistance(string source, string destination) {
        if (string.IsNullOrWhiteSpace(source)) {
            return destination?.Length ?? 0;
        }

        if (string.IsNullOrWhiteSpace(destination)) {
            return source?.Length ?? 0;
        }

        source = source.ToLowerInvariant();
        destination = destination.ToLowerInvariant();

        var matches = 0;
        var minLength = Math.Min(source.Length, destination.Length);
        var index = 0;
        while (index < minLength) {
            if (source[index] == destination[index]) {
                matches++;
            }

            index++;
        }

        var substitutions = minLength - matches;
        var additions = (destination.Length - source.Length) >= 0 ? destination.Length - source.Length : 0;
        var deletions = (source.Length - destination.Length) >= 0 ? source.Length - destination.Length : 0;

        return substitutions + additions + deletions;
    }
...