Получение наиболее близкого совпадения строк
Мне нужен способ сравнить несколько строк с тестовой строкой и вернуть строку, которая очень похожа на нее:
TEST STRING: THE BROWN FOX JUMPED OVER THE RED COW
CHOICE A : THE RED COW JUMPED OVER THE GREEN CHICKEN
CHOICE B : THE RED COW JUMPED OVER THE RED COW
CHOICE C : THE RED FOX JUMPED OVER THE BROWN COW
(Если я сделал это правильно) Самая близкая строка к "ТЕСТОВОЙ СТРОКЕ" должна быть "ВЫБОР С". Какой самый простой способ сделать это?
Я планирую реализовать это на нескольких языках, включая VB.net, Lua и JavaScript. На этом этапе псевдокод является приемлемым. Если вы можете привести пример для конкретного языка, это также приветствуется!
14 ответов
Эта проблема возникла у меня около года назад, когда дело дошло до того, что пользователь ввел информацию о нефтяной платформе в базу данных различной информации. Цель состояла в том, чтобы сделать какой-то нечеткий поиск строки, который мог бы идентифицировать запись базы данных с наиболее распространенными элементами.
Часть исследований включала реализацию алгоритма расстояния Левенштейна, который определяет, сколько изменений необходимо внести в строку или фразу, чтобы превратить ее в другую строку или фразу.
Реализация, которую я придумал, была относительно простой и включала взвешенное сравнение длины двух фраз, количества изменений между каждой фразой и того, можно ли найти каждое слово в целевой записи.
Статья находится на частном сайте, поэтому я приложу все усилия, чтобы добавить соответствующее содержание здесь:
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 для строк).
Итак, что вы должны извлечь из этого, это то, что вы, вероятно, хотите использовать комбинацию эвристики высокого уровня (поиск слов из одной фразы в другой фразе, длину обеих фраз и т. Д.) Наряду с реализацией алгоритма расстояния Левенштейна. Поскольку решение о том, какое совпадение является "наилучшим", является эвристическим (нечетким) определением - вам придется придумать набор весов для любой метрики, с которой вы столкнетесь, чтобы определить сходство.
С соответствующим набором эвристик и весов ваша программа сравнения быстро примет решения, которые вы бы приняли.
Эта проблема постоянно возникает в биоинформатике. Принятый выше ответ (который был кстати кстати) известен в биоинформатике как алгоритмы Нидлмана-Вунша (сравните две строки) и Смита-Уотермана (найдите приблизительную подстроку в более длинной строке). Они прекрасно работают и десятилетиями были рабочими лошадками.
Но что, если у вас есть миллион строк для сравнения? Это триллион парных сравнений, каждое из которых равно O(n*m)! Современные секвенаторы ДНК легко генерируют миллиард коротких последовательностей ДНК, каждая длиной около 200 "букв" ДНК. Как правило, мы хотим найти для каждой такой строки лучшее совпадение с геномом человека (3 миллиарда букв). Понятно, что алгоритм Нидлмана-Вунша и его родственники не подойдут.
Эта так называемая "проблема выравнивания" является областью активных исследований. Самые популярные алгоритмы в настоящее время способны находить неточные совпадения между 1 миллиардом коротких строк и геномом человека в считанные часы на разумном оборудовании (скажем, восемь ядер и 32 ГБ ОЗУ).
Большинство из этих алгоритмов работают, быстро находя короткие точные совпадения (начальные числа), а затем расширяя их до полной строки, используя более медленный алгоритм (например, Смит-Уотерман). Причина, по которой это работает, в том, что нас действительно интересуют только несколько близких матчей, поэтому стоит избавиться от 99,9...% пар, которые не имеют ничего общего.
Как поиск точных совпадений помогает найти неточные совпадения? Ну, допустим, мы допускаем только одно различие между запросом и целью. Легко видеть, что эта разница должна возникать либо в правой, либо в левой половине запроса, и поэтому другая половина должна точно совпадать. Эта идея может быть распространена на множественные несоответствия и является основой для алгоритма ELAND, обычно используемого с секвенаторами ДНК Illumina.
Есть много очень хороших алгоритмов для точного сопоставления строк. Учитывая строку запроса длиной 200 и целевую строку длиной 3 миллиарда (человеческий геном), мы хотим найти любое место в цели, где есть подстрока длины k, которая точно соответствует подстроке запроса. Простой подход состоит в том, чтобы начать с индексации цели: взять все подстроки длиной k, поместить их в массив и отсортировать их. Затем возьмите каждую подстроку длиной k и выполните поиск в отсортированном индексе. Сортировка и поиск могут быть выполнены за O(log n).
Но хранение может быть проблемой. Индекс цели из 3 миллиардов букв должен содержать 3 миллиарда указателей и 3 миллиарда слов длиной k. Казалось бы, это уместно менее чем в несколько десятков гигабайт оперативной памяти. Но удивительно, что мы можем значительно сжать индекс, используя преобразование Берроуза-Уилера, и он по-прежнему будет эффективно запрашиваться. Индекс человеческого генома может умещаться менее чем в 4 ГБ ОЗУ. Эта идея лежит в основе популярных средств выравнивания последовательностей, таких как Bowtie и BWA.
В качестве альтернативы мы можем использовать массив суффиксов, который хранит только указатели, но представляет одновременный индекс всех суффиксов в целевой строке (по существу, одновременный индекс для всех возможных значений k; то же самое верно для преобразования Берроуза-Уилера)). Индекс массива суффиксов генома человека займет 12 ГБ ОЗУ, если мы используем 32-битные указатели.
Ссылки выше содержат множество информации и ссылок на первичные исследовательские работы. Ссылка ELAND ведет в PDF с полезными рисунками, иллюстрирующими вовлеченные концепции, и показывает, как обращаться со вставками и удалениями.
Наконец, хотя эти алгоритмы в основном решили проблему (повторного) секвенирования отдельных человеческих геномов (миллиарда коротких строк), технология секвенирования ДНК улучшается даже быстрее, чем закон Мура, и мы быстро приближаемся к триллионным наборам данных. Например, в настоящее время ведутся проекты по секвенированию геномов 10000 видов позвоночных, каждый длиной около миллиарда букв. Естественно, мы захотим выполнить попарно неточное сопоставление строк с данными...
Я оспариваю тот вариант B, который ближе к тестовой строке, так как это всего 4 символа (и 2 удаления) из исходной строки. Принимая во внимание, что Вы видите C как более близкий, потому что это включает и коричневый и красный. Это, однако, будет иметь большее расстояние редактирования.
Существует алгоритм Levenshtein Distance, который измеряет расстояние редактирования между двумя входами.
Вот инструмент для этого алгоритма.
- Тарифы выбора А на расстоянии 15.
- Ставки выбора Б на расстояние 6.
- Оцените выбор C как расстояние 9.
РЕДАКТИРОВАТЬ: Извините, я продолжаю смешивать строки в инструменте Левенштейна. Обновлено для правильных ответов.
Реализация Lua, для потомков:
function levenshtein_distance(str1, str2)
local len1, len2 = #str1, #str2
local char1, char2, distance = {}, {}, {}
str1:gsub('.', function (c) table.insert(char1, c) end)
str2:gsub('.', function (c) table.insert(char2, c) end)
for i = 0, len1 do distance[i] = {} end
for i = 0, len1 do distance[i][0] = i end
for i = 0, len2 do distance[0][i] = i end
for i = 1, len1 do
for j = 1, len2 do
distance[i][j] = math.min(
distance[i-1][j ] + 1,
distance[i ][j-1] + 1,
distance[i-1][j-1] + (char1[i] == char2[j] and 0 or 1)
)
end
end
return distance[len1][len2]
end
Вы можете найти эту библиотеку полезной! http://code.google.com/p/google-diff-match-patch/
В настоящее время он доступен на Java, JavaScript, Dart, C++, C#, Objective C, Lua и Python.
Это тоже работает довольно хорошо. Я использую это в нескольких моих проектах Lua.
И я не думаю, что было бы слишком сложно перенести его на другие языки!
Вы можете быть заинтересованы в этом блоге.
http://seatgeek.com/blog/dev/fuzzywuzzy-fuzzy-string-matching-in-python
Fuzzywuzzy - это библиотека Python, которая предоставляет простые меры расстояния, такие как расстояние Левенштейна для сопоставления строк. Он построен поверх difflib в стандартной библиотеке и будет использовать реализацию C Python-levenshtein, если она доступна.
Если вы делаете это в контексте поисковой системы или внешнего интерфейса базы данных, вы можете рассмотреть возможность использования такого инструмента, как Apache Solr, с плагином ComplexPhraseQueryParser. Эта комбинация позволяет выполнять поиск по индексу строк с результатами, отсортированными по релевантности, определенной по расстоянию Левенштейна.
Мы использовали его против большой коллекции исполнителей и названий песен, когда входящий запрос может содержать одну или несколько опечаток, и он работал довольно хорошо (и удивительно быстро, учитывая, что коллекции состоят из миллионов строк).
Кроме того, с помощью Solr вы можете выполнять поиск по индексу по запросу через JSON, поэтому вам не придется заново изобретать решение между разными языками, на которые вы смотрите.
Эту проблему трудно реализовать, если входные данные слишком велики (скажем, миллионы строк). Я использовал упругий поиск, чтобы решить это. Просто вставьте все входные данные в БД, и вы сможете быстро найти любую строку на основе любого расстояния редактирования. Вот фрагмент кода C#, который даст вам список результатов, отсортированных по расстоянию редактирования (от меньшего к большему)
var res = client.Search<ClassName>(s => s
.Query(q => q
.Match(m => m
.Field(f => f.VariableName)
.Query("SAMPLE QUERY")
.Fuzziness(Fuzziness.EditDistance(5))
)
));
Для эффективного запроса большого набора текста вы можете использовать концепцию Edit Distance/ Prefix Edit Distance.
Изменить расстояние ED(x,y): минимальное количество преобразований, которые нужно получить от термина x до термина y
Но вычисление ЭД между каждым термином и текстом запроса требует значительных ресурсов и времени. Поэтому вместо того, чтобы сначала вычислять ED для каждого термина, мы можем извлечь возможные совпадающие термины, используя технику, называемую индексом Qgram. а затем применить расчет ED на этих выбранных условиях.
Преимущество методики индекса Qgram - поддержка нечеткого поиска.
Одним из возможных подходов к адаптации индекса QGram является построение инвертированного индекса с использованием Qgrams. Там мы храним все слова, которые состоят из определенной Qgram, под этой Qgram (вместо хранения полной строки вы можете использовать уникальный идентификатор для каждой строки). Для этого вы можете использовать структуру данных Tree Map в Java. Ниже приведен небольшой пример хранения терминов.
col: col mbia, col ombo, gancol a, tacol ama
Затем при запросе мы вычисляем количество общих Qgrams между текстом запроса и доступными терминами.
Example: x = HILLARY, y = HILARI(query term)
Qgrams
$$HILLARY$$ -> $$H, $HI, HIL, ILL, LLA, LAR, ARY, RY$, Y$$
$$HILARI$$ -> $$H, $HI, HIL, ILA, LAR, ARI, RI$, I$$
number of q-grams in common = 4
общее количество q-грамм = 4.
Для терминов с большим количеством общих Qgrams мы вычисляем ED/PED по термину запроса, а затем предлагаем термин конечному пользователю.
Вы можете найти реализацию этой теории в следующем проекте (см. "QGramIndex.java"). Не стесняйтесь задавать любые вопросы. https://github.com/Bhashitha-Gamage/City_Search
Чтобы узнать больше о редактировании расстояния, индексе префикса редактирования расстояния Qgram, пожалуйста, посмотрите следующее видео профессора доктора Ханны Баст https://www.youtube.com/embed/6pUg2wmGJRo (урок начинается с 20:06)
Очень, очень хорошим ресурсом для таких алгоритмов является Simmetrics: http://sourceforge.net/projects/simmetrics/
К сожалению, удивительный веб-сайт, содержащий много документации, пропал:(В случае повторного запуска, его предыдущий адрес был следующим: http://www.dcs.shef.ac.uk/~sam/simmetrics.html
Вуаля (любезно предоставлено "Wayback Machine"): http://web.archive.org/web/20081230184321/http://www.dcs.shef.ac.uk/~sam/simmetrics.html
Вы можете изучить исходный код, для таких сравнений существуют десятки алгоритмов, каждый из которых имеет свой компромисс. Реализации в Java.
Здесь вы можете иметь Golang POC для вычисления расстояний между заданными словами. Вы можете настроитьminDistance а также difference для других областей применения.
Игровая площадка: https://play.golang.org/p/NtrBzLdC3rE
package main
import (
"errors"
"fmt"
"log"
"math"
"strings"
)
var data string = `THE RED COW JUMPED OVER THE GREEN CHICKEN-THE RED COW JUMPED OVER THE RED COW-THE RED FOX JUMPED OVER THE BROWN COW`
const minDistance float64 = 2
const difference float64 = 1
type word struct {
data string
letters map[rune]int
}
type words struct {
words []word
}
// Print prettify the data present in word
func (w word) Print() {
var (
lenght int
c int
i int
key rune
)
fmt.Printf("Data: %s\n", w.data)
lenght = len(w.letters) - 1
c = 0
for key, i = range w.letters {
fmt.Printf("%s:%d", string(key), i)
if c != lenght {
fmt.Printf(" | ")
}
c++
}
fmt.Printf("\n")
}
func (ws words) fuzzySearch(data string) ([]word, error) {
var (
w word
err error
founds []word
)
w, err = initWord(data)
if err != nil {
log.Printf("Errors: %s\n", err.Error())
return nil, err
}
// Iterating all the words
for i := range ws.words {
letters := ws.words[i].letters
//
var similar float64 = 0
// Iterating the letters of the input data
for key := range w.letters {
if val, ok := letters[key]; ok {
if math.Abs(float64(val-w.letters[key])) <= minDistance {
similar += float64(val)
}
}
}
lenSimilarity := math.Abs(similar - float64(len(data)-strings.Count(data, " ")))
log.Printf("Comparing %s with %s i've found %f similar letter, with weight %f", data, ws.words[i].data, similar, lenSimilarity)
if lenSimilarity <= difference {
founds = append(founds, ws.words[i])
}
}
if len(founds) == 0 {
return nil, errors.New("no similar found for data: " + data)
}
return founds, nil
}
func initWords(data []string) []word {
var (
err error
words []word
word word
)
for i := range data {
word, err = initWord(data[i])
if err != nil {
log.Printf("Error in index [%d] for data: %s", i, data[i])
} else {
words = append(words, word)
}
}
return words
}
func initWord(data string) (word, error) {
var word word
word.data = data
word.letters = make(map[rune]int)
for _, r := range data {
if r != 32 { // avoid to save the whitespace
word.letters[r]++
}
}
return word, nil
}
func main() {
var ws words
words := initWords(strings.Split(data, "-"))
for i := range words {
words[i].Print()
}
ws.words = words
solution, _ := ws.fuzzySearch("THE BROWN FOX JUMPED OVER THE RED COW")
fmt.Println("Possible solutions: ", solution)
}
Вот быстрое решение, которое не зависит от каких-либо библиотек и достаточно хорошо работает для таких вещей, как автозаполнение форм:
function compare_strings(str1, str2) {
arr1 = str1.split("");
arr2 = str2.split("");
res = arr1.reduce((a, c) => a + arr2.includes(c), 0);
return(res)
}
Можно использовать в автозаполнении ввода следующим образом:
HTML:
<div id="wrapper">
<input id="tag_input" placeholder="add tags..."></input>
<div id="hold_tags"></div>
</div>
CSS:
body {
background: #2c2c54;
display: flex;
justify-content: center;
align-items: center;
}
input {
height: 40px;
width: 400px;
border-radius: 4px;
outline: 0;
border: none;
padding-left: 5px;
font-size: 18px;
}
#wrapper {
height: auto;
background: #40407a;
}
.tag {
background: #ffda79;
margin: 4px;
padding: 5px;
border-radius: 4px;
box-shadow: 2px 2px 2px black;
font-size: 18px;
font-family: arial;
cursor: pointer;
}
JS:
const input = document.getElementById("tag_input");
const wrapper = document.getElementById("wrapper");
const hold_tags = document.getElementById("hold_tags");
const words = [
"machine",
"data",
"platform",
"garbage",
"twitter",
"knowledge"
];
input.addEventListener("input", function (e) {
const value = document.getElementById(e.target.id).value;
hold_tags.replaceChildren();
if (value !== "") {
words.forEach(function (word) {
if (compare_strings(word, value) > value.length - 1) {
const tag = document.createElement("div");
tag.className = "tag";
tag.innerText = word;
hold_tags.append(tag);
}
});
}
});
function compare_strings(str1, str2) {
arr1 = str1.split("");
arr2 = str2.split("");
res = arr1.reduce((a, c) => a + arr2.includes(c), 0);
return res;
}
Результат :
Есть еще одна мера сходства, которую я когда-то реализовал в нашей системе и дал удовлетворительные результаты:
Пример использования
Есть запрос пользователя, который необходимо сопоставить с набором документов.
Алгоритм
- Извлеките ключевые слова из пользовательского запроса (соответствующие POS-ТЕГИ - существительное, существительное собственное).
- Теперь рассчитайте оценку на основе приведенной ниже формулы для измерения сходства между запросом пользователя и данным документом.
Для каждого ключевого слова, извлеченного из пользовательского запроса:-
- Начните поиск в документе данного слова и за каждое последующее вхождение этого слова в документ уменьшайте количество начисляемых баллов.
По сути, если первое ключевое слово встречается в документе 4 раза, оценка будет рассчитываться как:-
- первое вхождение принесет "1" балл.
- Второе вхождение добавит 1/2 к расчетному счету
- Третье вхождение добавит 1/3 к общему количеству
- Четвертое вхождение получает 1/4
Общая оценка сходства = 1 + 1/2 + 1/3 + 1/4 = 2,083
Аналогичным образом мы рассчитываем его для других ключевых слов в пользовательском запросе.
Наконец, общая оценка будет отражать степень сходства между запросом пользователя и данным документом.
Образец с использованием C# находится здесь.
public static void Main()
{
Console.WriteLine("Hello World " + LevenshteinDistance("Hello","World"));
Console.WriteLine("Choice A " + LevenshteinDistance("THE BROWN FOX JUMPED OVER THE RED COW","THE RED COW JUMPED OVER THE GREEN CHICKEN"));
Console.WriteLine("Choice B " + LevenshteinDistance("THE BROWN FOX JUMPED OVER THE RED COW","THE RED COW JUMPED OVER THE RED COW"));
Console.WriteLine("Choice C " + LevenshteinDistance("THE BROWN FOX JUMPED OVER THE RED COW","THE RED FOX JUMPED OVER THE BROWN COW"));
}
public static float LevenshteinDistance(string a, string b)
{
var rowLen = a.Length;
var colLen = b.Length;
var maxLen = Math.Max(rowLen, colLen);
// Step 1
if (rowLen == 0 || colLen == 0)
{
return maxLen;
}
/// Create the two vectors
var v0 = new int[rowLen + 1];
var v1 = new int[rowLen + 1];
/// Step 2
/// Initialize the first vector
for (var i = 1; i <= rowLen; i++)
{
v0[i] = i;
}
// Step 3
/// For each column
for (var j = 1; j <= colLen; j++)
{
/// Set the 0'th element to the column number
v1[0] = j;
// Step 4
/// For each row
for (var i = 1; i <= rowLen; i++)
{
// Step 5
var cost = (a[i - 1] == b[j - 1]) ? 0 : 1;
// Step 6
/// Find minimum
v1[i] = Math.Min(v0[i] + 1, Math.Min(v1[i - 1] + 1, v0[i - 1] + cost));
}
/// Swap the vectors
var vTmp = v0;
v0 = v1;
v1 = vTmp;
}
// Step 7
/// The vectors were swapped one last time at the end of the last loop,
/// that is why the result is now in v0 rather than in v1
return v0[rowLen];
}
Результат:
Hello World 4
Choice A 15
Choice B 6
Choice C 8