Эта проблема возникла у меня около года назад, когда дело дошло до того, что пользователь ввел информацию о нефтяной платформе в базу данных различной информации. Цель состояла в том, чтобы выполнить нечеткий поиск строк, который мог бы идентифицировать запись в базе данных с наиболее распространенными элементами.
Часть исследования включала реализацию алгоритма Расстояние Левенштейна , который определяет, сколько изменений необходимо внести в строку или фразу, чтобы превратить ее в другую строку или фразу.
Реализация, которую я придумал, была относительно простой и включала взвешенное сравнение длины двух фраз, количества изменений между каждой фразой и того, можно ли найти каждое слово в целевой записи.
Статья находится на частном сайте, поэтому я приложу все усилия, чтобы добавить соответствующее содержание здесь:
Fuzzy String Matching - это процесс выполнения похожей на человека оценки сходства двух слов или фраз. Во многих случаях это включает в себя определение слов или фраз, которые наиболее похожи друг на друга. В этой статье описывается собственное решение проблемы нечеткого сопоставления строк и его полезность для решения множества проблем, которые могут позволить нам автоматизировать задачи, которые ранее требовали утомительного участия пользователя.
Введение
Необходимость нечеткого сопоставления строк изначально возникла при разработке средства проверки в Мексиканском заливе. Существовала база данных известных нефтяных платформ и платформ в Мексиканском заливе, и люди, покупающие страховку, давали нам некоторую плохо распечатанную информацию об их активах, и нам приходилось сопоставлять ее с базой данных известных платформ. Когда было предоставлено очень мало информации, лучшее, что мы могли сделать, - это полагаться на андеррайтера, чтобы «распознать» тот, на кого они ссылались, и вызвать нужную информацию. Вот где это автоматизированное решение пригодится.
Я провел целый день, исследуя методы нечеткого сопоставления строк, и в конце концов наткнулся на очень полезный алгоритм расстояния Левенштейна в Википедии.
Осуществление
После прочтения теории, лежащей в ее основе, я реализовал и нашел способы ее оптимизации. Вот как мой код выглядит в 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 для хорошего результата, но не к обоим. Этакий менталитет "возьми то, что мы можем получить".
Действительно удивительно, что оптимизированное значение этих пяти весов говорит о том, что происходит нечеткое сопоставление строк. Для совершенно разных практических случаев нечеткого сопоставления строк эти параметры очень разные. До сих пор я использовал его для 3 отдельных приложений.
Несмотря на то, что он не использовался в окончательной оптимизации, был создан лист сравнительного анализа, который сопоставляет столбцы с самими собой для всех идеальных результатов по диагонали и позволяет пользователю изменять параметры, чтобы контролировать скорость, с которой показатели расходятся от 0, и отмечать врожденное сходство между поисковые фразы (которые теоретически могут быть использованы для компенсации ложных срабатываний в результатах)
Другие применения
Это решение может быть использовано в любом месте, где пользователь желает, чтобы компьютерная система идентифицировала строку в наборе строк, где нет идеального соответствия. (Как примерное соответствие vlookup для строк).
Итак, что вы должны извлечь из этого, это то, что вы, вероятно, хотите использовать комбинацию эвристики высокого уровня (поиск слов из одной фразы в другой фразе, длину обеих фраз и т. Д.) Наряду с реализацией расстояния Левенштейна. алгоритм. Поскольку решение о том, какое совпадение является «наилучшим», является эвристическим (нечетким) определением - вам придется придумать набор весов для любой метрики, с которой вы столкнетесь, чтобы определить сходство.
С соответствующим набором эвристик и весов ваша программа сравнения быстро примет решения, которые вы бы приняли.