Нечеткое соответствие текста (предложений / заголовков) на C#

Question

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

также у меня есть метод, который возвращает значение от 0 до 1:

/// <summary>
/// Gets the similarity between two strings.
/// All relation scores are in the [0, 1] range, 
/// which means that if the score gets a maximum value (equal to 1) 
/// then the two string are absolutely similar
/// </summary>
/// <param name="string1">The string1.</param>
/// <param name="string2">The string2.</param>
/// <returns></returns>
public static float CalculateSimilarity(String s1, String s2)
{
    if ((s1 == null) || (s2 == null)) return 0.0f;

    float dis = LevenshteinDistance.Compute(s1, s2);
    float maxLen = s1.Length;
    if (maxLen < s2.Length)
        maxLen = s2.Length;
    if (maxLen == 0.0F)
        return 1.0F;
    else return 1.0F - dis / maxLen;
}

но этого для меня недостаточно.Потому что мне нужен более сложный способ сопоставления двух предложений.

Например, я хочу автоматически пометить какую-нибудь музыку, у меня есть оригинальные названия песен, и у меня есть песни с мусором, например супер, качественный, годы , подобные 2007, 2008, и т.д.ит.п..кроме того, некоторые файлы содержат только http://trash..thash..song_name_mp3.mp3, другие - нормальные.Я хочу создать алгоритм, который будет работать более совершенным, чем мой сейчас..Может быть, кто-нибудь может мне помочь?

вот мой текущий алгоритм:

/// <summary>
/// if we need to ignore this target.
/// </summary>
/// <param name="targetString">The target string.</param>
/// <returns></returns>
private bool doIgnore(String targetString)
{
    if ((targetString != null) && (targetString != String.Empty))
    {
        for (int i = 0; i < ignoreWordsList.Length; ++i)
        {
            //* if we found ignore word or target string matching some some special cases like years (Regex).
            if (targetString == ignoreWordsList[i] || (isMatchInSpecialCases(targetString))) return true;
        }
    }

   return false;
}

/// <summary>
/// Removes the duplicates.
/// </summary>
/// <param name="list">The list.</param>
private void removeDuplicates(List<String> list)
{
    if ((list != null) && (list.Count > 0))
    {
        for (int i = 0; i < list.Count - 1; ++i)
        {
            if (list[i] == list[i + 1])
            {
                list.RemoveAt(i);
                --i;
            }
        }
    }
}

/// <summary>
/// Does the fuzzy match.
/// </summary>
/// <param name="targetTitle">The target title.</param>
/// <returns></returns>
private TitleMatchResult doFuzzyMatch(String targetTitle)
{
    TitleMatchResult matchResult = null;

   if (targetTitle != null && targetTitle != String.Empty)
   {
       try
       {
           //* change target title (string) to lower case.
           targetTitle = targetTitle.ToLower();

           //* scores, we will select higher score at the end.
           Dictionary<Title, float> scores = new Dictionary<Title, float>();

           //* do split special chars: '-', ' ', '.', ',', '?', '/', ':', ';', '%', '(', ')', '#', '\"', '\'', '!', '|', '^', '*', '[', ']', '{', '}', '=', '!', '+', '_'
           List<String> targetKeywords = new List<string>(targetTitle.Split(ignoreCharsList, StringSplitOptions.RemoveEmptyEntries));

          //* remove all trash from keywords, like super, quality, etc..
           targetKeywords.RemoveAll(delegate(String x) { return doIgnore(x); });
          //* sort keywords.
          targetKeywords.Sort();
        //* remove some duplicates.
        removeDuplicates(targetKeywords);

        //* go through all original titles.
        foreach (Title sourceTitle in titles)
        {
            float tempScore = 0f;
            //* split orig. title to keywords list.
            List<String> sourceKeywords = new List<string>(sourceTitle.Name.Split(ignoreCharsList, StringSplitOptions.RemoveEmptyEntries));
            sourceKeywords.Sort();
            removeDuplicates(sourceKeywords);

            //* go through all source ttl keywords.
            foreach (String keyw1 in sourceKeywords)
            {
                float max = float.MinValue;
                foreach (String keyw2 in targetKeywords)
                {
                    float currentScore = StringMatching.StringMatching.CalculateSimilarity(keyw1.ToLower(), keyw2);
                    if (currentScore > max)
                    {
                        max = currentScore;
                    }
                }
                tempScore += max;
            }

            //* calculate average score.
            float averageScore = (tempScore / Math.Max(targetKeywords.Count, sourceKeywords.Count)); 

            //* if average score is bigger than minimal score and target title is not in this source title ignore list.
            if (averageScore >= minimalScore && !sourceTitle.doIgnore(targetTitle))
            {
                //* add score.
                scores.Add(sourceTitle, averageScore);
            }
        }

        //* choose biggest score.
        float maxi = float.MinValue;
        foreach (KeyValuePair<Title, float> kvp in scores)
        {
            if (kvp.Value > maxi)
            {
                maxi = kvp.Value;
                matchResult = new TitleMatchResult(maxi, kvp.Key, MatchTechnique.FuzzyLogic);
            }
        }
    }
    catch { }
}
//* return result.
return matchResult;
}

Это работает нормально, но только в некоторых случаях многие названия, которые должны совпадать, не совпадают...Я думаю, мне нужна какая-то формула для игры с весами и т.д., но я не могу ее придумать..

Идеи?Предложения?Алгос?

кстати, я уже знаком с этой темой (мой коллега уже опубликовал ее, но мы не можем предложить правильное решение этой проблемы.):Приближенные алгоритмы сопоставления строк

Answer 1

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

• Rolling_Stones.Best_of_2003.Дикие лошади.mp3
• Супер. Качество.Дикие лошади.mp3
• Tori_Amos.Дикие лошади.mp3

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

Answer 2

Немного устарел, но это может быть полезно будущим посетителям.Если вы уже используете алгоритм Левенштейна и вам нужно немного усовершенствовать его, я опишу некоторые очень эффективные эвристики в этом решении:

Получение ближайшего совпадения строк

Ключ в том, что вы получаете 3 или 4 (или Еще) методы оценки сходства между вашими фразами (расстояние Левенштейна - это всего лишь один метод) - и затем, используя реальные примеры строк, которые вы хотите сопоставить как похожие, вы корректируете веса и комбинации этих эвристик, пока не получите что-то, что максимизирует количество положительных совпадений.Затем вы будете использовать эту формулу для всех будущих матчей, и вы должны увидеть отличные результаты.

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

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

---

Простой, быстрый и очень полезный показатель.Используя это, я создал две отдельные метрики для оценки сходства двух строк.Один я называю "valuePhrase", а другой - "valueWords".valuePhrase - это просто расстояние Левенштейна между двумя фразами, а valueWords разбивает строку на отдельные слова на основе разделителей, таких как пробелы, тире и все остальное, что вам угодно, и сравнивает каждое слово с каждым другим словом, суммируя кратчайшее расстояние Левенштейна, соединяющее любые два слова.По сути, он измеряет, действительно ли информация в одной "фразе" содержится в другой, точно так же, как перестановка слов.Я потратил несколько дней в качестве побочного проекта на то, чтобы придумать наиболее эффективный из возможных способов разделения строки на основе разделителей.

valueWords, фраза значения и функция разделения:

Public Function valuePhrase#(ByRef S1$, ByRef S2$)
    valuePhrase = LevenshteinDistance(S1, S2)
End Function

Public Function valueWords#(ByRef S1$, ByRef S2$)
    Dim wordsS1$(), wordsS2$()
    wordsS1 = SplitMultiDelims(S1, " _-")
    wordsS2 = SplitMultiDelims(S2, " _-")
    Dim word1%, word2%, thisD#, wordbest#
    Dim wordsTotal#
    For word1 = LBound(wordsS1) To UBound(wordsS1)
        wordbest = Len(S2)
        For word2 = LBound(wordsS2) To UBound(wordsS2)
            thisD = LevenshteinDistance(wordsS1(word1), wordsS2(word2))
            If thisD < wordbest Then wordbest = thisD
            If thisD = 0 Then GoTo foundbest
        Next word2
foundbest:
        wordsTotal = wordsTotal + wordbest
    Next word1
    valueWords = wordsTotal
End Function

''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
' SplitMultiDelims
' This function splits Text into an array of substrings, each substring
' delimited by any character in DelimChars. Only a single character
' may be a delimiter between two substrings, but DelimChars may
' contain any number of delimiter characters. It returns a single element
' array containing all of text if DelimChars is empty, or a 1 or greater
' element array if the Text is successfully split into substrings.
' If IgnoreConsecutiveDelimiters is true, empty array elements will not occur.
' If Limit greater than 0, the function will only split Text into 'Limit'
' array elements or less. The last element will contain the rest of Text.
''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
Function SplitMultiDelims(ByRef Text As String, ByRef DelimChars As String, _
        Optional ByVal IgnoreConsecutiveDelimiters As Boolean = False, _
        Optional ByVal Limit As Long = -1) As String()
    Dim ElemStart As Long, N As Long, M As Long, Elements As Long
    Dim lDelims As Long, lText As Long
    Dim Arr() As String

    lText = Len(Text)
    lDelims = Len(DelimChars)
    If lDelims = 0 Or lText = 0 Or Limit = 1 Then
        ReDim Arr(0 To 0)
        Arr(0) = Text
        SplitMultiDelims = Arr
        Exit Function
    End If
    ReDim Arr(0 To IIf(Limit = -1, lText - 1, Limit))

    Elements = 0: ElemStart = 1
    For N = 1 To lText
        If InStr(DelimChars, Mid(Text, N, 1)) Then
            Arr(Elements) = Mid(Text, ElemStart, N - ElemStart)
            If IgnoreConsecutiveDelimiters Then
                If Len(Arr(Elements)) > 0 Then Elements = Elements + 1
            Else
                Elements = Elements + 1
            End If
            ElemStart = N + 1
            If Elements + 1 = Limit Then Exit For
        End If
    Next N
    'Get the last token terminated by the end of the string into the array
    If ElemStart <= lText Then Arr(Elements) = Mid(Text, ElemStart)
    'Since the end of string counts as the terminating delimiter, if the last character
    'was also a delimiter, we treat the two as consecutive, and so ignore the last elemnent
    If IgnoreConsecutiveDelimiters Then If Len(Arr(Elements)) = 0 Then Elements = Elements - 1

    ReDim Preserve Arr(0 To Elements) 'Chop off unused array elements
    SplitMultiDelims = Arr
End Function

Меры сходства

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

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

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

Применение Чтобы обеспечить оптимизацию нечеткого сопоставления, я взвешиваю каждую метрику.Таким образом, каждое приложение fuzzy string match может взвешивать параметры по-разному.Формула, определяющая итоговый балл, представляет собой простую комбинацию показателей и их весов:

value = Min(phraseWeight*phraseValue, wordsWeight*wordsValue)*minWeight + 
        Max(phraseWeight*phraseValue, wordsWeight*wordsValue)*maxWeight + lengthWeight*lengthValue

Используя алгоритм оптимизации (здесь лучше всего подходит нейронная сеть, потому что это дискретная, многомерная задача), цель теперь состоит в том, чтобы максимизировать количество совпадений.Я создал функцию, которая определяет количество правильных совпадений каждого набора друг с другом, как можно видеть на этом последнем скриншоте.Столбец или строка получает очко, если строке, которая должна была быть сопоставлена, присвоен наименьший балл, и неполные баллы начисляются, если для наименьшего балла существует ничья, и правильное совпадение находится среди связанных совпадающих строк.Затем я оптимизировал его.Вы можете видеть, что зеленая ячейка - это столбец, который наилучшим образом соответствует текущей строке, а синий квадрат вокруг ячейки - это строка, которая наилучшим образом соответствует текущему столбцу.Оценка в нижнем углу - это примерно количество успешных совпадений, и это то, что мы хотим максимизировать в нашей задаче оптимизации.

Answer 3

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

мусор ..thash..song_name_mp3.mp3 и мусор..spotch..song_name_mp3.mp3

в конечном итоге все выглядело бы так же.

Конечно, вам понадобилась бы некоторая эвристика.Одна вещь, которую вы могли бы попробовать, - это пропустить строку через конвертер soundex.Soundex - это "кодек", используемый для проверки того, "звучит" ли что-то одинаково (как вы могли бы сказать телефонному оператору).Это более или менее грубая фонетическая транслитерация, частично защищенная от неправильного произношения.Это определенно беднее, чем edit distance, но намного, намного дешевле.(Официальное использование предназначено для имен и использует только три символа.Однако нет причин останавливаться на достигнутом, просто используйте сопоставление для каждого символа в строке.Видишь википедия для получения подробной информации)

Итак, мое предложение состояло бы в том, чтобы озвучить ваши струны, разбить каждую из них на несколько отрезков длины (скажем, 5, 10, 20), а затем просто посмотреть на кластеры.Внутри кластеров вы можете использовать что-то более дорогое, например редактировать расстояние или максимальную подстроку.

Answer 4

Проделана большая работа над несколько связанной проблемой выравнивания последовательностей ДНК (поиск "локального выравнивания последовательностей") - классическим алгоритмом является "Нидлман-Вунш", и более сложные современные алгоритмы также легко найти.Идея заключается в том, что - аналогично ответу Грега - вместо определения и сравнения ключевых слов попробуйте найти самые длинные слабо совпадающие подстроки в длинных строках.

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

Answer 5

Существует Репозиторий на GitHub реализуем несколько методов.