Как рассчитать меру сходства расстояний для двух заданных строк?

Question

Мне нужно рассчитать сходство между 2 строками. Так что именно я имею в виду? Позвольте мне объяснить на примере:

• Настоящее слово: hospital
• Ошибочное слово: haspita

Теперь моя цель - определить, сколько символов мне нужно, чтобы изменить ошибочное слово, чтобы получить настоящее слово. В этом примере мне нужно изменить 2 буквы. Так какой будет процент? Я всегда беру длину настоящего слова. Таким образом, он становится 2 / 8 = 25%, поэтому эти 2 заданные строки DSM составляют 75%.

Как я могу достичь этого, когда производительность является ключевым фактором?

Answer 1

То, что вы ищете, называется редактировать расстояние или расстояние Левенштейна. В статье в Википедии объясняется, как она рассчитывается, и внизу есть хороший фрагмент псевдокода, который поможет вам очень легко кодировать этот алгоритм в C#.

Вот реализация с первого сайта, ссылка на которую приведена ниже:

private static int  CalcLevenshteinDistance(string a, string b)
    {
    if (String.IsNullOrEmpty(a) && String.IsNullOrEmpty(b)) {
        return 0;
    }
    if (String.IsNullOrEmpty(a)) {
        return b.Length;
    }
    if (String.IsNullOrEmpty(b)) {
        return a.Length;
    }
    int  lengthA   = a.Length;
    int  lengthB   = b.Length;
    var  distances = new int[lengthA + 1, lengthB + 1];
    for (int i = 0;  i <= lengthA;  distances[i, 0] = i++);
    for (int j = 0;  j <= lengthB;  distances[0, j] = j++);

    for (int i = 1;  i <= lengthA;  i++)
        for (int j = 1;  j <= lengthB;  j++)
            {
            int  cost = b[j - 1] == a[i - 1] ? 0 : 1;
            distances[i, j] = Math.Min
                (
                Math.Min(distances[i - 1, j] + 1, distances[i, j - 1] + 1),
                distances[i - 1, j - 1] + cost
                );
            }
    return distances[lengthA, lengthB];
    }

Answer 2

Я только что обратился к той же самой проблеме несколько недель назад. Так как кто-то спрашивает сейчас, я поделюсь кодом. В моих исчерпывающих тестах мой код примерно в 10 раз быстрее, чем пример C# в Википедии, даже если не указано максимальное расстояние. Когда предоставляется максимальное расстояние, это увеличение производительности увеличивается до 30x - 100x +. Обратите внимание на пару ключевых моментов для производительности:

• Если вам нужно сравнивать одни и те же слова снова и снова, сначала преобразуйте слова в массивы целых чисел. Алгоритм Дамерау-Левенштейна включает в себя множество сравнений>, <, == и ints сравнивать намного быстрее чем chars,
• Он включает в себя механизм короткого замыкания, чтобы выйти, если расстояние превышает установленный максимум
• Используйте вращающийся набор из трех массивов, а не массивную матрицу, как во всех реализациях, которые я видел в других местах
• Убедитесь, что ваши массивы срезаны по более короткой ширине слова.

Код (работает точно так же, если вы замените int[] с String в объявлениях параметров:

/// <summary>
/// Computes the Damerau-Levenshtein Distance between two strings, represented as arrays of
/// integers, where each integer represents the code point of a character in the source string.
/// Includes an optional threshhold which can be used to indicate the maximum allowable distance.
/// </summary>
/// <param name="source">An array of the code points of the first string</param>
/// <param name="target">An array of the code points of the second string</param>
/// <param name="threshold">Maximum allowable distance</param>
/// <returns>Int.MaxValue if threshhold exceeded; otherwise the Damerau-Leveshteim distance between the strings</returns>
public static int DamerauLevenshteinDistance(int[] source, int[] target, int threshold) {

    int length1 = source.Length;
    int length2 = target.Length;

    // Return trivial case - difference in string lengths exceeds threshhold
    if (Math.Abs(length1 - length2) > threshold) { return int.MaxValue; }

    // Ensure arrays [i] / length1 use shorter length 
    if (length1 > length2) {
        Swap(ref target, ref source);
        Swap(ref length1, ref length2);
    }

    int maxi = length1;
    int maxj = length2;

    int[] dCurrent = new int[maxi + 1];
    int[] dMinus1 = new int[maxi + 1];
    int[] dMinus2 = new int[maxi + 1];
    int[] dSwap;

    for (int i = 0; i <= maxi; i++) { dCurrent[i] = i; }

    int jm1 = 0, im1 = 0, im2 = -1;

    for (int j = 1; j <= maxj; j++) {

        // Rotate
        dSwap = dMinus2;
        dMinus2 = dMinus1;
        dMinus1 = dCurrent;
        dCurrent = dSwap;

        // Initialize
        int minDistance = int.MaxValue;
        dCurrent[0] = j;
        im1 = 0;
        im2 = -1;

        for (int i = 1; i <= maxi; i++) {

            int cost = source[im1] == target[jm1] ? 0 : 1;

            int del = dCurrent[im1] + 1;
            int ins = dMinus1[i] + 1;
            int sub = dMinus1[im1] + cost;

            //Fastest execution for min value of 3 integers
            int min = (del > ins) ? (ins > sub ? sub : ins) : (del > sub ? sub : del);

            if (i > 1 && j > 1 && source[im2] == target[jm1] && source[im1] == target[j - 2])
                min = Math.Min(min, dMinus2[im2] + cost);

            dCurrent[i] = min;
            if (min < minDistance) { minDistance = min; }
            im1++;
            im2++;
        }
        jm1++;
        if (minDistance > threshold) { return int.MaxValue; }
    }

    int result = dCurrent[maxi];
    return (result > threshold) ? int.MaxValue : result;
}

куда Swap является:

static void Swap<T>(ref T arg1,ref T arg2) {
    T temp = arg1;
    arg1 = arg2;
    arg2 = temp;
}

Answer 3

Существует большое количество алгоритмов расстояния сходства строк, которые можно использовать. Некоторые из перечисленных здесь (но не исчерпывающе перечислены):

• Левенштейн
• Рукодельница Wunch
• Смит Уотерман
• Смит Водный Гото
• Яро, Яро Винклер
• Жаккар Сходство
• Евклидово расстояние
• Кости сходство
• Косинус сходство
• Монж Элкан

Библиотека, которая содержит реализацию всего этого, называется SimMetrics, которая имеет реализации java и C#.

Answer 4

Я обнаружил, что Левенштейн и Яро Винклер отлично подходят для небольших различий между строками, таких как:

• Орфографические ошибки; или же
• ö вместо o в имени человека.

Однако, сравнивая что-то вроде заголовков статей, в которых значимые куски текста были бы одинаковыми, но с "шумом" по краям, Смит-Уотерман-Гото был фантастическим:

Сравните эти 2 заголовка (которые одинаковы, но отличаются от разных источников):

Эндонуклеаза из Escherichia coli, которая вводит отдельные полинуклеотидные цепные расщепления в ультрафиолетовой облученной ДНК

Эндонуклеаза III: эндонуклеаза из Escherichia coli, которая вводит деления одной полинуклеотидной цепи в ультрафиолетовой облученной ДНК

Этот сайт, который предоставляет алгоритм сравнения строк показывает:

• Левенштейн: 81
• Смит-Водяной Гото 94
• Яро Винклер 78

Яро Винклер и Левенштейн не так компетентны, как Смит Уотерман Гото, в обнаружении сходства. Если мы сравним два заголовка, которые не относятся к одной статье, но имеют соответствующий текст:

Жировой обмен у высших растений. Функция ацилтиоэстераз в метаболизме ацил-коферментов А и ацилацил-белка-носителя

Жировой обмен у высших растений. Определение ацилацил-белка-носителя и ацил-кофермента А в сложной липидной смеси

Джаро Винклер дает ложный положительный результат, но Смит Уотерман Гото не делает:

• Левенштейн: 54
• Смит-Водяной Гото 49
• Яро Винклер 89

Как указала Anastasiosyal, SimMetrics имеет код Java для этих алгоритмов. Я успешно использовал Java-код SmithWatermanGotoh от SimMetrics.

Answer 5

Вот моя реализация Damerau Levenshtein Distance, которая возвращает не только коэффициент подобия, но также возвращает места ошибок в исправленном слове (эту функцию можно использовать в текстовых редакторах). Также моя реализация поддерживает различные веса ошибок (подстановка, удаление, вставка, транспонирование).

public static List<Mistake> OptimalStringAlignmentDistance(
  string word, string correctedWord,
  bool transposition = true,
  int substitutionCost = 1,
  int insertionCost = 1,
  int deletionCost = 1,
  int transpositionCost = 1)
{
    int w_length = word.Length;
    int cw_length = correctedWord.Length;
    var d = new KeyValuePair<int, CharMistakeType>[w_length + 1, cw_length + 1];
    var result = new List<Mistake>(Math.Max(w_length, cw_length));

    if (w_length == 0)
    {
        for (int i = 0; i < cw_length; i++)
            result.Add(new Mistake(i, CharMistakeType.Insertion));
        return result;
    }

    for (int i = 0; i <= w_length; i++)
        d[i, 0] = new KeyValuePair<int, CharMistakeType>(i, CharMistakeType.None);

    for (int j = 0; j <= cw_length; j++)
        d[0, j] = new KeyValuePair<int, CharMistakeType>(j, CharMistakeType.None);

    for (int i = 1; i <= w_length; i++)
    {
        for (int j = 1; j <= cw_length; j++)
        {
            bool equal = correctedWord[j - 1] == word[i - 1];
            int delCost = d[i - 1, j].Key + deletionCost;
            int insCost = d[i, j - 1].Key + insertionCost;
            int subCost = d[i - 1, j - 1].Key;
            if (!equal)
                subCost += substitutionCost;
            int transCost = int.MaxValue;
            if (transposition && i > 1 && j > 1 && word[i - 1] == correctedWord[j - 2] && word[i - 2] == correctedWord[j - 1])
            {
                transCost = d[i - 2, j - 2].Key;
                if (!equal)
                    transCost += transpositionCost;
            }

            int min = delCost;
            CharMistakeType mistakeType = CharMistakeType.Deletion;
            if (insCost < min)
            {
                min = insCost;
                mistakeType = CharMistakeType.Insertion;
            }
            if (subCost < min)
            {
                min = subCost;
                mistakeType = equal ? CharMistakeType.None : CharMistakeType.Substitution;
            }
            if (transCost < min)
            {
                min = transCost;
                mistakeType = CharMistakeType.Transposition;
            }

            d[i, j] = new KeyValuePair<int, CharMistakeType>(min, mistakeType);
        }
    }

    int w_ind = w_length;
    int cw_ind = cw_length;
    while (w_ind >= 0 && cw_ind >= 0)
    {
        switch (d[w_ind, cw_ind].Value)
        {
            case CharMistakeType.None:
                w_ind--;
                cw_ind--;
                break;
            case CharMistakeType.Substitution:
                result.Add(new Mistake(cw_ind - 1, CharMistakeType.Substitution));
                w_ind--;
                cw_ind--;
                break;
            case CharMistakeType.Deletion:
                result.Add(new Mistake(cw_ind, CharMistakeType.Deletion));
                w_ind--;
                break;
            case CharMistakeType.Insertion:
                result.Add(new Mistake(cw_ind - 1, CharMistakeType.Insertion));
                cw_ind--;
                break;
            case CharMistakeType.Transposition:
                result.Add(new Mistake(cw_ind - 2, CharMistakeType.Transposition));
                w_ind -= 2;
                cw_ind -= 2;
                break;
        }
    }
    if (d[w_length, cw_length].Key > result.Count)
    {
        int delMistakesCount = d[w_length, cw_length].Key - result.Count;
        for (int i = 0; i < delMistakesCount; i++)
            result.Add(new Mistake(0, CharMistakeType.Deletion));
    }

    result.Reverse();

    return result;
}

public struct Mistake
{
    public int Position;
    public CharMistakeType Type;

    public Mistake(int position, CharMistakeType type)
    {
        Position = position;
        Type = type;
    }

    public override string ToString()
    {
        return Position + ", " + Type;
    }
}

public enum CharMistakeType
{
    None,
    Substitution,
    Insertion,
    Deletion,
    Transposition
}

Этот код является частью моего проекта: Яндекс.Лингвистика.NET.

Я написал несколько тестов, и мне кажется, что метод работает.

Но комментарии и замечания приветствуются.

Answer 6

Вот альтернативный подход:

Это слишком долго для комментария.

Типичным методом нахождения сходства является расстояние Левенштейна, и нет никаких сомнений в том, что есть библиотека с доступным кодом.

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

Другая идея заключается в использовании некоторого варианта триграмм или н-граммов. Это последовательности из n символов (или n слов, или n геномных последовательностей, или n чего угодно). Сохраняйте сопоставление триграмм со строками и выбирайте те, которые имеют наибольшее перекрытие. Типичным выбором n является "3", отсюда и название.

Например, английский будет иметь следующие триграммы:

• Eng
• NGL
• циклооксигеназы
• лис
• иш

И Англия будет иметь:

• Eng
• NGL
• GLA
• ЛВС
• а также

Ну, 2 из 7 (или 4 из 10) совпадают. Если это работает для вас, и вы можете проиндексировать таблицу триграмм / строк и получить более быстрый поиск.

Вы также можете объединить это с Левенштейном, чтобы уменьшить набор сравнений с теми, которые имеют некоторое минимальное общее число n-грамм.

Answer 7

Вот реализация VB.net:

Public Shared Function LevenshteinDistance(ByVal v1 As String, ByVal v2 As String) As Integer
    Dim cost(v1.Length, v2.Length) As Integer
    If v1.Length = 0 Then
        Return v2.Length                'if string 1 is empty, the number of edits will be the insertion of all characters in string 2
    ElseIf v2.Length = 0 Then
        Return v1.Length                'if string 2 is empty, the number of edits will be the insertion of all characters in string 1
    Else
        'setup the base costs for inserting the correct characters
        For v1Count As Integer = 0 To v1.Length
            cost(v1Count, 0) = v1Count
        Next v1Count
        For v2Count As Integer = 0 To v2.Length
            cost(0, v2Count) = v2Count
        Next v2Count
        'now work out the cheapest route to having the correct characters
        For v1Count As Integer = 1 To v1.Length
            For v2Count As Integer = 1 To v2.Length
                'the first min term is the cost of editing the character in place (which will be the cost-to-date or the cost-to-date + 1 (depending on whether a change is required)
                'the second min term is the cost of inserting the correct character into string 1 (cost-to-date + 1), 
                'the third min term is the cost of inserting the correct character into string 2 (cost-to-date + 1) and 
                cost(v1Count, v2Count) = Math.Min(
                    cost(v1Count - 1, v2Count - 1) + If(v1.Chars(v1Count - 1) = v2.Chars(v2Count - 1), 0, 1),
                    Math.Min(
                        cost(v1Count - 1, v2Count) + 1,
                        cost(v1Count, v2Count - 1) + 1
                    )
                )
            Next v2Count
        Next v1Count

        'the final result is the cheapest cost to get the two strings to match, which is the bottom right cell in the matrix
        'in the event of strings being equal, this will be the result of zipping diagonally down the matrix (which will be square as the strings are the same length)
        Return cost(v1.Length, v2.Length)
    End If
End Function