Вид старого, но может быть полезным для будущих посетителей. Если вы уже используете алгоритм Левенштейна и вам нужно пойти немного лучше, я опишу некоторые очень эффективные эвристики в этом решении:
Получение наиболее близкого совпадения строк
Суть в том, что вы придумали 3 или 4 (или больше ) метода измерения сходства между вашими фразами (расстояние Левенштейна - это всего лишь один метод) - и затем использовали реальные примеры строк, которые вы хотите чтобы совпадения были похожими, вы корректируете веса и комбинации этих эвристик, пока не получите что-то, что максимизирует количество положительных совпадений. Затем вы используете эту формулу для всех будущих матчей, и вы должны увидеть отличные результаты.
Если в процессе участвует пользователь, также лучше, если вы предоставите интерфейс, позволяющий пользователю видеть дополнительные совпадения, которые имеют высокий уровень сходства, если они не согласны с первым выбором.
Вот выдержка из связанного ответа. Если вы в конечном итоге захотите использовать любой из этих кодов как есть, заранее прошу прощения за необходимость конвертировать VBA в C #.
Простой, быстрый и очень полезный показатель. Используя это, я создал две отдельные метрики для оценки сходства двух строк. Один я называю «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
Используя алгоритм оптимизации (нейронная сеть лучше всего подходит здесь, потому что это дискретная многомерная задача), теперь цель состоит в том, чтобы максимизировать количество совпадений. Я создал функцию, которая определяет количество правильных совпадений каждого набора друг к другу, как видно на этом окончательном снимке экрана. Столбец или строка получают балл, если наименьший балл присваивается той строке, которая должна была быть сопоставлена, и частичные баллы присваиваются, если есть галстук для наименьшего балла, и правильное совпадение находится среди связанных сопоставленных строк. Я тогда оптимизировал это. Вы можете видеть, что зеленая ячейка - это столбец, который лучше всего соответствует текущей строке, а синий квадрат вокруг ячейки - это строка, которая лучше всего соответствует текущему столбцу. Счет в нижнем углу - это примерно количество успешных совпадений, и это то, что мы говорим нашей задаче оптимизации, чтобы максимизировать.
