Получение наиболее близкого совпадения строк

Мне нужен способ сравнить несколько строк с тестовой строкой и вернуть строку, которая очень похожа на нее:

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. На этом этапе псевдокод является приемлемым. Если вы можете привести пример для конкретного языка, это также приветствуется!

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

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

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

Статья находится на частном сайте, поэтому я приложу все усилия, чтобы добавить соответствующее содержание здесь:

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-файл с полезными рисунками, иллюстрирующими вовлеченные концепции, и показывает, как обращаться со вставками и удалениями.

Наконец, хотя эти алгоритмы в основном решили проблему (повторного) секвенирования отдельных геномов человека (миллиард коротких строк), технология секвенирования ДНК улучшается даже быстрее, чем закон Мура, и мы быстро приближаемся к триллионным наборам данных. Например, в настоящее время ведутся проекты по секвенированию геномов 10 000 видов позвоночных , каждый длиной около миллиарда букв. Естественно, мы захотим выполнить попарно неточное сопоставление строк с данными ...

Я оспариваю, что вариант B ближе к тестовой строке, так как это всего 4 символа (и 2 удаления) из исходной строки. Принимая во внимание, что Вы видите C как более близкий, потому что это включает и коричневый и красный. Это, однако, будет иметь большее расстояние редактирования.

Есть алгоритм под названием Levenshtein Distance, который измеряет расстояние редактирования между двумя входами.

Вот инструмент для этого алгоритма.

1. Тарифы выбора А на расстоянии 15.
2. Ставки выбора Б на расстояние 6.
3. Оцените выбор 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://seatgeek.com/blog/dev/fuzzywuzzy-fuzzy-string-matching-in-python

Fuzzywuzzy - это библиотека Python, которая предоставляет простые меры расстояния, такие как расстояние Левенштейна для сопоставления строк. Он построен поверх difflib в стандартной библиотеке и будет использовать реализацию C Python-levenshtein, если она доступна.

http://pypi.python.org/pypi/python-Levenshtein/

Вы можете найти эту библиотеку полезной! http://code.google.com/p/google-diff-match-patch/

В настоящее время он доступен на Java, JavaScript, Dart, C ++, C #, Objective C, Lua и Python.

Это тоже работает довольно хорошо. Я использую это в нескольких моих проектах Lua.

И я не думаю, что было бы слишком сложно перенести его на другие языки!

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

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

Кроме того, с помощью Solr вы можете выполнять поиск по индексу по запросу через JSON, поэтому вам не придется заново изобретать решение между разными языками, на которые вы смотрите.

Очень, очень хороший ресурс для таких алгоритмов - 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.

Для эффективного запроса большого набора текста вы можете использовать концепцию Edit Distance / Prefix Edit Distance.

Редактировать расстояние ED (x, y): минимальное количество преобразований, которые нужно получить от термина x до термина y

Но вычисление ED между каждым термином и текстом запроса требует значительных ресурсов и времени. Поэтому вместо того, чтобы сначала вычислять ED для каждого термина, мы можем извлечь возможные совпадающие термины, используя технику, называемую индексом Qgram. а затем применить расчет ED на этих выбранных условиях.

Преимущество метода индексов Qgram - поддержка нечеткого поиска.

Одним из возможных подходов к адаптации индекса QGram является построение инвертированного индекса с использованием Qgrams. Там мы храним все слова, которые состоят из определенной Qgram, под этой Qgram (вместо хранения полной строки вы можете использовать уникальный идентификатор для каждой строки). Для этого вы можете использовать структуру данных Tree Map в Java. Ниже приведен небольшой пример хранения терминов.

col: col mbia, col ombo, gan col a, ta col 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)

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

Быстрый старт: https://www.elastic.co/guide/en/elasticsearch/client/net-api/6.x/elasticsearch-net.html

Просто вставьте все входные данные в БД, и вы сможете быстро найти любую строку на основе любого расстояния редактирования. Вот фрагмент кода 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))
    )
));

Здесь вы можете иметь POC GOLANG для расчета расстояния между заданными словами. Вы можете настроить 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)

}