Дамерау - Левенштейн Расстояние, добавление порога

У меня есть следующая реализация, но я хочу добавить порог, поэтому, если результат будет больше, чем просто, просто прекратите вычисление и вернитесь.

Как бы я пошел об этом?

РЕДАКТИРОВАТЬ: Вот мой текущий код,threshold еще не используется ... цель в том, что он используется

    public static int DamerauLevenshteinDistance(string string1, string string2, int threshold)
    {
        // Return trivial case - where they are equal
        if (string1.Equals(string2))
            return 0;

        // Return trivial case - where one is empty
        if (String.IsNullOrEmpty(string1) || String.IsNullOrEmpty(string2))
            return (string1 ?? "").Length + (string2 ?? "").Length;


        // Ensure string2 (inner cycle) is longer
        if (string1.Length > string2.Length)
        {
            var tmp = string1;
            string1 = string2;
            string2 = tmp;
        }

        // Return trivial case - where string1 is contained within string2
        if (string2.Contains(string1))
            return string2.Length - string1.Length;

        var length1 = string1.Length;
        var length2 = string2.Length;

        var d = new int[length1 + 1, length2 + 1];

        for (var i = 0; i <= d.GetUpperBound(0); i++)
            d[i, 0] = i;

        for (var i = 0; i <= d.GetUpperBound(1); i++)
            d[0, i] = i;

        for (var i = 1; i <= d.GetUpperBound(0); i++)
        {
            for (var j = 1; j <= d.GetUpperBound(1); j++)
            {
                var cost = string1[i - 1] == string2[j - 1] ? 0 : 1;

                var del = d[i - 1, j] + 1;
                var ins = d[i, j - 1] + 1;
                var sub = d[i - 1, j - 1] + cost;

                d[i, j] = Math.Min(del, Math.Min(ins, sub));

                if (i > 1 && j > 1 && string1[i - 1] == string2[j - 2] && string1[i - 2] == string2[j - 1])
                    d[i, j] = Math.Min(d[i, j], d[i - 2, j - 2] + cost);
            }
        }

        return d[d.GetUpperBound(0), d.GetUpperBound(1)];
    }
}
 AFract26 дек. 2014 г., 19:35
Этот ответ:stackoverflow.com/a/9454016/461444 дает реализацию, которая, кажется, действительно очень хорошо работает в соответствии с моими собственными тестами.

Ответы на вопрос(4)

поэтому я отвечу именно в этом конкретном контексте: вам лучше не оптимизировать расстояние Левенштейна, а уменьшить количество сравниваемых пар. Да, более быстрый алгоритм Левенштейна улучшит ситуацию, но не так сильно, как сокращение числа сравнений с N квадратов (с N в миллионах строк) до N * некоторого фактора. Мое предложение состоит в том, чтобы сравнивать только элементы, у которых есть разница в длине в допустимой дельте. На вашей большой таблице вы добавляете постоянный вычисляемый столбец вLEN(Data) и затем создайте индекс для него с помощью include Data:

ALTER TABLE Table ADD LenData AS LEN(Data) PERSISTED;
CREATE INDEX ndxTableLenData on Table(LenData) INCLUDE (Data);

Теперь вы можете ограничить чисто проблемное пространство, присоединившись к максимальной разнице по длине (например, 5),если ваши данныеLEN(Data) значительно варьируется:

SELECT a.Data, b.Data, dbo.Levenshtein(a.Data, b.Data)
FROM Table A
JOIN Table B ON B.DataLen BETWEEN A.DataLen - 5 AND A.DataLen+5
 CaffGeek04 окт. 2010 г., 23:28
Я смог значительно улучшить производительность, объединив свои таблицы сsoundex затем применяя расстояние Левенштейна
 user22058316 дек. 2010 г., 23:09
Я согласен, что сокращение количества сравнений лучше; однако я сократил свои сравнения с 1,2 сравнения exa до 127,8 гига сравнения. Теперь мне нужен лучший Левенстьен. На данный момент мне нужно сократить вычисления с 3,5 дней до 10 часов.
 Remus Rusanu04 окт. 2010 г., 23:42
Вам также следует попробовать добавить постоянный столбец как SOUNDEX, а затем добавить индекс (SOUNDEX) с помощью include (Data).

Дамерау - Левенштейн Расстояние, добавление порога (извините, я не могу комментировать, так как у меня еще нет 50 представителей)

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

var minDistance = threshold;

И ваше правило обновления:

if (d[i, j] < minDistance)
   minDistance = d[i, j];

Кроме того, ваши критерии раннего выхода:

if (minDistance > threshold)
   return int.MaxValue;

Теперь обратите внимание, что условие if выше никогда не будет выполнено! Вы должны скорее инициализироватьminDistance вint.MaxValue

который я могу придумать. После установки каждого индекса d, посмотрите, превышает ли он ваш порог. Оценка является постоянной во времени, так что это капля в море по сравнению с теоретической сложностью N ^ 2 общего алгоритма:

public static int DamerauLevenshteinDistance(string string1, string string2, int threshold)
{
    ...

    for (var i = 1; i <= d.GetUpperBound(0); i++)
    {
        for (var j = 1; j <= d.GetUpperBound(1); j++)
        {
            ...

            var temp = d[i,j] = Math.Min(del, Math.Min(ins, sub));

            if (i > 1 && j > 1 && string1[i - 1] == string2[j - 2] && string1[i - 2] == string2[j - 1])
                temp = d[i,j] = Math.Min(temp, d[i - 2, j - 2] + cost);

            //Does this value exceed your threshold? if so, get out now
            if(temp > threshold) 
              return temp;
        }
    }

    return d[d.GetUpperBound(0), d.GetUpperBound(1)];
}
 CaffGeek01 окт. 2010 г., 23:00
Я ошибся, это не работает ... даже если результат должен был быть 1, если я передал порог 2, результат 3
 CaffGeek01 окт. 2010 г., 22:15
почти! Я настроил его, чтобы он заработал,d[i,j] должен был быть установлен по какой-то причине, так что я просто установил temp в то же время, затем проверил, и теперь он работает отлично! Спасибо!
Решение Вопроса

как я надеялся

    public static int DamerauLevenshteinDistance(string string1, string string2, int threshold)
    {
        // Return trivial case - where they are equal
        if (string1.Equals(string2))
            return 0;

        // Return trivial case - where one is empty
        if (String.IsNullOrEmpty(string1) || String.IsNullOrEmpty(string2))
            return (string1 ?? "").Length + (string2 ?? "").Length;


        // Ensure string2 (inner cycle) is longer
        if (string1.Length > string2.Length)
        {
            var tmp = string1;
            string1 = string2;
            string2 = tmp;
        }

        // Return trivial case - where string1 is contained within string2
        if (string2.Contains(string1))
            return string2.Length - string1.Length;

        var length1 = string1.Length;
        var length2 = string2.Length;

        var d = new int[length1 + 1, length2 + 1];

        for (var i = 0; i <= d.GetUpperBound(0); i++)
            d[i, 0] = i;

        for (var i = 0; i <= d.GetUpperBound(1); i++)
            d[0, i] = i;

        for (var i = 1; i <= d.GetUpperBound(0); i++)
        {
            var im1 = i - 1;
            var im2 = i - 2;
            var minDistance = threshold;

            for (var j = 1; j <= d.GetUpperBound(1); j++)
            {
                var jm1 = j - 1;
                var jm2 = j - 2;
                var cost = string1[im1] == string2[jm1] ? 0 : 1;

                var del = d[im1, j] + 1;
                var ins = d[i, jm1] + 1;
                var sub = d[im1, jm1] + cost;

                //Math.Min is slower than native code
                //d[i, j] = Math.Min(del, Math.Min(ins, sub));
                d[i, j] = del <= ins && del <= sub ? del : ins <= sub ? ins : sub;

                if (i > 1 && j > 1 && string1[im1] == string2[jm2] && string1[im2] == string2[jm1])
                    d[i, j] = Math.Min(d[i, j], d[im2, jm2] + cost);

                if (d[i, j] < minDistance)
                    minDistance = d[i, j];
            }

            if (minDistance > threshold)
                return int.MaxValue;
        }

        return d[d.GetUpperBound(0), d.GetUpperBound(1)] > threshold 
            ? int.MaxValue 
            : d[d.GetUpperBound(0), d.GetUpperBound(1)];
    }
 AFract26 дек. 2014 г., 19:23
Это работает хуже, чем моя текущая реализация, которая вычисляет точное значение, даже с очень низким порогом.
 AFract26 дек. 2014 г., 19:46
Я предлагаю вместо этого использовать stackoverflow.com/a/9454016/461444. Это очень быстро и, кажется, дает точные результаты.
 KeithS04 окт. 2010 г., 17:09
Легко понять, почему это не очень полезно. Вы устанавливаете minDistance в качестве порогового значения, затем заменяете его только меньшими значениями, затем проверяете, осталось ли значение minDistance тем же или увеличилось по сравнению с вычислением стоимости строки. Чтобы тест завершил досрочное завершение обработки, каждый индекс d [i] должен приводить к стоимости, превышающей пороговое значение, и, поскольку этот алгоритм никогда не уменьшит рассчитанную им стоимость, это крайне пессимистично.
 CaffGeek04 окт. 2010 г., 18:15
Из того, что я могу сказать, каждый внутренний /j цикл должен завершиться или результаты станут неправильными. Последний элемент в строке - это максимальное расстояние, которое может пройти преобразование. Наименьшее значение - это минимально возможное расстояние в настоящее время. Вот почему я отслеживаю самое низкое значение для каждой строки, и, если оно уже превышает пороговое значение, возвращаемся. Это должно предотвратить несколько внешних /i петли в строках, которые сильно отличаются

Ваш ответ на вопрос