Нечеткий текст (предложения/заголовки), соответствующий в С#

Ответ 1

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

• Rolling_Stones.Best_of_2003.Wild_Horses.mp3
• Super.Quality.Wild_Horses.mp3
• Tori_Amos.Wild_Horses.mp3

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

Ответ 2

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

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

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

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

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

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

valueWords, функция valuePhrase и Split:

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

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

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

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

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

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

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

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

Ответ 3

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

trash..thash..song_name_mp3.mp3 а также garbage..spotch..song_name_mp3.mp3

будет выглядеть одинаково.

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

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

Ответ 4

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

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

Ответ 5

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