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

Ответ 1

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

Здесь реализация с первого сайта, связанного ниже:

private static int  CalcLevenshteinDistance(string a, string b)
    {
    if (String.IsNullOrEmpty(a) || String.IsNullOrEmpty(b))  return 0;

    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];
    }

Ответ 2

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

• Если вам нужно сравнивать одни и те же слова снова и снова, сначала конвертируйте слова в массивы целых чисел. Алгоритм Damerau-Levenshtein включает в себя много > , <, == сравнения и 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;
}

Ответ 3

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

• Levenstein
• Запуск Needleman
• Смит Уотерман
• Смит Уотерман Готох
• Jaro, Jaro Winkler
• сходство с Jaccard
• Евклидово расстояние
• Dice сходство
• Косинус сходства
• Monge Elkan

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

Ответ 4

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

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

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

сравните эти 2 заголовка (которые одинаковы, но сформулированы по-разному из разных источников):

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

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

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

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

Jaro Winkler и Levenshtein не так компетентны, как Smith Waterman Gotoh, обнаруживая сходство. Если мы сравниваем два заголовка, которые не являются одной и той же статьей, но имеют некоторый соответствующий текст:

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

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

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

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

Как отметил Anastasiosyal, SimMetrics имеет java код для этих алгоритмов. У меня был успех с помощью кода Java SmithWatermanGotoh из SimMetrics.

Ответ 5

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

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

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

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

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

Например, английский имел бы эти триграммы:

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

И Англия имела бы:

• Eng
• NGL
• GLA
• LAN
• и

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

Вы также можете комбинировать это с Levenshtein, чтобы уменьшить совокупность сравнений с теми, у которых есть минимальное количество n-граммов.

Ответ 6

Вот моя реализация 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
}

Этот код является частью моего проекта: Yandex-Linguistics.NET.

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

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

Ответ 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