Ответ 1
Мне была представлена эта проблема около года назад, когда дело дошло до поиска введенной пользователем информации о нефтяной вышке в базе данных различной информации. Цель состояла в том, чтобы выполнить какой-то поиск нечетких строк, который мог бы идентифицировать запись базы данных с наиболее распространенными элементами.
Часть исследования включала в себя реализацию алгоритма Levenshtein distance, который определяет, сколько изменений необходимо внести в строку или фразу, чтобы превратить ее в другая строка или фраза.
Реализация, с которой я столкнулся, была относительно простой и включала взвешенное сравнение длины двух фраз, количества изменений между каждой фразой и того, можно ли найти каждое слово в целевой записи.
Статья находится на частном сайте, поэтому я сделаю все возможное, чтобы добавить соответствующее содержимое здесь:
Согласование нечеткой строки - это процесс выполнения человекоподобной оценки сходства двух слов или фраз. Во многих случаях это связано с определением слов или фраз, которые наиболее похожи друг на друга. В этой статье описывается внутреннее решение проблемы соответствия нечетких строк и ее полезность при решении множества проблем, которые могут позволить нам автоматизировать задачи, которые ранее требовали утомительного участия пользователя.
Введение
Необходимость выполнения сопоставления нечеткой строки первоначально возникла при разработке средства проверки Мексиканского залива Мексики. Существовала база данных известных нефтяных вышек и платформ Мексиканского залива, а люди, покупающие страховку, давали нам немного плохо напечатанную информацию об их активах, и нам приходилось сопоставлять ее с базой данных известных платформ. Когда было предоставлено очень мало информации, самое лучшее, что мы могли бы сделать, это полагаться на андеррайтера, чтобы "распознать" тот, на который они ссылались, и вызвать соответствующую информацию. Именно здесь это автоматическое решение пригодится.
Я провел день, исследуя методы сопоставления нечетких строк и в конце концов наткнулся на очень полезный алгоритм расстояния Левенштейна в Википедии.
Реализация
После прочтения теории, основанной на ней, я реализовал и нашел способы ее оптимизации. Вот как выглядит мой код в VBA:
'Calculate the Levenshtein Distance between two strings (the number of insertions,
'deletions, and substitutions needed to transform the first string into the second)
Public Function LevenshteinDistance(ByRef S1 As String, ByVal S2 As String) As Long
Dim L1 As Long, L2 As Long, D() As Long 'Length of input strings and distance matrix
Dim i As Long, j As Long, cost As Long 'loop counters and cost of substitution for current letter
Dim cI As Long, cD As Long, cS As Long 'cost of next Insertion, Deletion and Substitution
L1 = Len(S1): L2 = Len(S2)
ReDim D(0 To L1, 0 To L2)
For i = 0 To L1: D(i, 0) = i: Next i
For j = 0 To L2: D(0, j) = j: Next j
For j = 1 To L2
For i = 1 To L1
cost = Abs(StrComp(Mid$(S1, i, 1), Mid$(S2, j, 1), vbTextCompare))
cI = D(i - 1, j) + 1
cD = D(i, j - 1) + 1
cS = D(i - 1, j - 1) + cost
If cI <= cD Then 'Insertion or Substitution
If cI <= cS Then D(i, j) = cI Else D(i, j) = cS
Else 'Deletion or Substitution
If cD <= cS Then D(i, j) = cD Else D(i, j) = cS
End If
Next i
Next j
LevenshteinDistance = D(L1, L2)
End Function
Простая, быстрая и очень полезная метрика. Используя это, я создал две отдельные метрики для оценки сходства двух строк. Один из них я называю "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 Phrase в приведенной выше таблице, была =valuePhrase(A2,B2)-0.8*ABS(LEN(B2)-LEN(A2)). Я эффективно уменьшал штраф на расстояние Левенштейна на 80% от разницы в длине двух "фраз". Таким образом, "фразы", которые имеют одинаковую длину, страдают от полного штрафа, но "фразы", содержащие "дополнительную информацию" (дольше), но помимо того, что они по большей части разделяют одни и те же персонажи, подвергаются уменьшенному штрафу. Я использовал функцию Value Words как есть, и тогда моя окончательная эвристика SearchVal была определена как =MIN(D2,E2)*0.8+MAX(D2,E2)*0.2 - средневзвешенное значение. Какой из двух оценок был ниже, он получил 80% и 20% от более высокого балла. Это была всего лишь эвристика, которая соответствовала моему варианту использования, чтобы получить хорошую скорость матча. Эти веса - это то, что можно было бы затем настроить, чтобы получить наилучший коэффициент соответствия с их тестовыми данными.
Как вы можете видеть, последние две метрики, которые являются метриками с нечеткой строкой, уже имеют естественную тенденцию давать низкие баллы для строк, которые должны соответствовать (вниз по диагонали). Это очень хорошо.
Применение Чтобы обеспечить оптимизацию нечеткого соответствия, я взвешиваю каждую метрику. Таким образом, каждое приложение нечеткой строки может весить параметры по-разному. Формула, определяющая окончательный счет, представляет собой просто комбинацию показателей и их весов:
value = Min(phraseWeight*phraseValue, wordsWeight*wordsValue)*minWeight
+ Max(phraseWeight*phraseValue, wordsWeight*wordsValue)*maxWeight
+ lengthWeight*lengthValue
Использование алгоритма оптимизации (нейронная сеть лучше всего здесь, потому что это дискретная, многомерная проблема), цель состоит в том, чтобы максимизировать количество совпадений. Я создал функцию, которая определяет количество правильных совпадений каждого набора друг с другом, как это видно на этом последнем снимке экрана. Столбец или строка получает точку, если младшему счету присваивается строка, которая должна была быть сопоставлена, а частичные точки указываются, если есть связь для самого низкого балла, и правильное совпадение относится к связанным последовательностям. Затем я оптимизировал его. Вы можете видеть, что зеленая ячейка - это столбец, который лучше всего соответствует текущей строке, а синий квадрат вокруг ячейки - это строка, которая лучше всего соответствует текущему столбцу. Счет в нижнем углу - это примерно количество успешных матчей, и это то, что мы говорим о нашей проблеме оптимизации, чтобы максимизировать.
Алгоритм был замечательным успехом, и параметры решения говорят об этом типе проблемы. Вы заметите, что оптимизированный балл составлял 44, а наилучший результат - 48. 5 столбцов в конце являются приманками и не имеют никакого значения для значений строк. Чем больше приманки, тем труднее будет найти наилучшее совпадение.
В этом конкретном случае сопоставления длина строк не имеет значения, потому что мы ожидаем сокращения, которые представляют более длинные слова, поэтому оптимальный вес для длины равен -0,3, что означает, что мы не наказываем строки, которые различаются по длине. Мы уменьшаем оценку в ожидании этих сокращений, предоставляя больше места для неполных совпадений слов для замены несловных совпадений, которые просто требуют меньших замен, потому что строка короче.
Вес слова равен 1.0, тогда как вес фразы равен 0,5, что означает, что мы наказываем целые слова, отсутствующие в одной строке, и больше ценим целую фразу. Это полезно, потому что многие из этих строк имеют одно общее слово (опасность), где действительно важно, поддерживается ли комбинация (область и опасность).
Наконец, минимальный вес оптимизирован на уровне 10 и максимальный вес в 1. Что это означает, что если лучший из двух оценок (фразу значения и слова значения) не очень хорош, матч сильно наказывается, но мы не очень наказываем худшее из двух баллов. По сути, это ставит акцент на том, чтобы либо valueWord, либо valuePhrase имели хороший балл, но не оба. Какой-то "взять то, что мы можем получить".
Это действительно захватывает то, что оптимизированное значение этих 5 весов говорит о том, что происходит нечеткое соответствие строк. Для совершенно разных практических случаев совпадения нечетких строк эти параметры очень разные. Я использовал его для 3 отдельных приложений.
В процессе окончательной оптимизации не использовался, был установлен лист контрольных показателей, который соответствует столбцам для всех идеальных результатов по диагонали и позволяет пользователю изменять параметры для контроля скорости, с которой баллы отклоняются от 0, и отмечают врожденные сходства между поисковые фразы (которые теоретически могут использоваться для смещения ложных срабатываний в результатах)
Другие приложения
Это решение может использоваться везде, где пользователь хочет, чтобы компьютерная система идентифицировала строку в наборе строк, где нет идеального соответствия. (Как примерное совпадение vlookup для строк).
Итак, что вы должны извлечь из этого, заключается в том, что вы, вероятно, захотите использовать комбинацию эвристики высокого уровня (поиск слов одной фразы в другой фразе, длина обеих фраз и т.д.) вместе с реализацией расстояния Левенштейна алгоритм. Поскольку решение о том, что является "лучшим" совпадением, является эвристическим (нечетким) определением - вам придется придумать набор весов для любых показателей, которые вы придумали для определения сходства.
С помощью соответствующего набора эвристик и весов вы сможете быстро сравнить свои программы сравнения с принятыми вами решениями.