Obtendo a correspondência de corda mais próxima

Eu preciso de uma maneira de comparar várias seqüências de caracteres para uma seqüência de teste e retornar a seqüência que se assemelha a ele:

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

(Se eu fiz isso corretamente) A string mais próxima da "STRING DO TESTE" deve ser "ESCOLHA C". Qual é a maneira mais fácil de fazer isso?

Planejo implementar isso em vários idiomas, incluindo VB.net, Lua e JavaScript. Neste ponto, o pseudocódigo é aceitável. Se você pode fornecer um exemplo para um idioma específico, isso também é apreciado!

Fui apresentado a esse problema há cerca de um ano, quando se tratava de procurar informações inseridas pelo usuário sobre uma plataforma de petróleo em um banco de dados de informações diversas. O objetivo era fazer algum tipo de pesquisa de string difusa que pudesse identificar a entrada do banco de dados com os elementos mais comuns.

Parte da pesquisa envolveu a implementação do algoritmo de distância de Levenshtein , que determina quantas alterações devem ser feitas em uma sequência ou frase para transformá-lo em outra sequência ou frase.

A implementação apresentada foi relativamente simples e envolveu uma comparação ponderada do tamanho das duas frases, o número de alterações entre cada frase e se cada palavra poderia ser encontrada na entrada de destino.

O artigo está em um site privado, então farei o possível para acrescentar o conteúdo relevante aqui:

Correspondência de seqüência difusa é o processo de realizar uma estimativa semelhante à humana da semelhança de duas palavras ou frases. Em muitos casos, envolve a identificação de palavras ou frases que são mais semelhantes entre si. Este artigo descreve uma solução interna para o problema de correspondência de seqüência de caracteres difusa e sua utilidade na solução de uma variedade de problemas que podem nos permitir automatizar tarefas que anteriormente exigiam o envolvimento tedioso do usuário.

Introdução

A necessidade de fazer a correspondência de seqüência difusa surgiu originalmente durante o desenvolvimento da ferramenta Validator do Golfo do México. O que existia era um banco de dados de plataformas e plataformas de petróleo conhecidas no Golfo do México, e as pessoas que compravam seguros nos forneciam algumas informações mal digitadas sobre seus ativos e tivemos que correspondê-las ao banco de dados de plataformas conhecidas. Quando havia poucas informações, o melhor que podíamos fazer era contar com um subscritor para "reconhecer" aquele a que se referiam e acessar as informações apropriadas. É aqui que esta solução automatizada é útil.

Passei um dia pesquisando métodos de correspondência de cordas difusas e acabei encontrando o muito útil algoritmo de distância de Levenshtein na Wikipedia.

Implementação

Depois de ler sobre a teoria por trás disso, implementei e encontrei maneiras de otimizá-la. É assim que meu código se parece no 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

Métrica simples, rápida e muito útil. Usando isso, criei duas métricas separadas para avaliar a semelhança de duas strings. Um eu chamo "valuePhrase" e outro eu chamo "valueWords". valuePhrase é apenas a distância de Levenshtein entre as duas frases, e valueWords divide a string em palavras individuais, com base em delimitadores como espaços, traços e qualquer outra coisa que você queira, e compara cada palavra com a outra, resumindo a menor Distância Levenshtein conectando duas palavras. Essencialmente, ele mede se as informações em uma "frase" estão realmente contidas em outra, exatamente como uma permutação em termos de palavras. Passei alguns dias como um projeto paralelo, apresentando a maneira mais eficiente possível de dividir uma string com base em delimitadores.

Função valueWords, valuePhrase e 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

Medidas de Similaridade

Usando essas duas métricas, e uma terceira que simplesmente calcula a distância entre duas seqüências, tenho uma série de variáveis ​​nas quais posso executar um algoritmo de otimização para obter o maior número de correspondências. A correspondência de cadeias nebulosas é, por si só, uma ciência nebulosa e, portanto, criando métricas linearmente independentes para medir a similaridade de cadeias, e tendo um conjunto conhecido de cadeias que desejamos combinar entre si, podemos encontrar os parâmetros que, para nossos estilos específicos de seqüências de caracteres, forneça os melhores resultados de correspondência difusa.

Inicialmente, o objetivo da métrica era ter um baixo valor de pesquisa para uma correspondência exata e aumentar os valores de pesquisa para medidas cada vez mais permutadas. Em um caso impraticável, isso era bastante fácil de definir usando um conjunto de permutações bem definidas e projetando a fórmula final, de modo que eles obtivessem um aumento nos valores dos resultados da pesquisa, conforme desejado.

Na captura de tela acima, aprimorei minha heurística para criar algo que me pareceu muito bem dimensionado para a diferença percebida entre o termo e o resultado da pesquisa. A heurística usada Value Phrasena planilha acima foi =valuePhrase(A2,B2)-0.8*ABS(LEN(B2)-LEN(A2)). Eu estava efetivamente reduzindo a penalidade da distância de Levenstein em 80% da diferença no comprimento das duas "frases". Dessa forma, "frases" com o mesmo comprimento sofrem a penalidade total, mas "frases" que contêm 'informações adicionais' (mais longas), mas além disso ainda compartilham os mesmos caracteres, sofrem uma penalidade reduzida. Eu usei a Value Wordsfunção como está e, em seguida, minha SearchValheurística final foi definida como=MIN(D2,E2)*0.8+MAX(D2,E2)*0.2- uma média ponderada. Qualquer uma das duas pontuações mais baixas recebeu 80% e 20% da pontuação mais alta. Essa foi apenas uma heurística que se adequou ao meu caso de uso para obter uma boa taxa de correspondência. Esses pesos são algo que se pode ajustar para obter a melhor taxa de correspondência com os dados de teste.

Como você pode ver, as duas últimas métricas, que são métricas de correspondência de sequência difusa, já têm uma tendência natural de atribuir pontuações baixas às seqüências que devem corresponder (na diagonal). Isso é muito bom.

Aplicação Para permitir a otimização da correspondência nebulosa, eu peso cada métrica. Como tal, toda aplicação de correspondência de seqüência difusa pode ponderar os parâmetros de maneira diferente. A fórmula que define a pontuação final é uma simples combinação das métricas e seus pesos:

value = Min(phraseWeight*phraseValue, wordsWeight*wordsValue)*minWeight
      + Max(phraseWeight*phraseValue, wordsWeight*wordsValue)*maxWeight
      + lengthWeight*lengthValue

Usando um algoritmo de otimização (a rede neural é a melhor opção por ser um problema discreto e multidimensional), o objetivo agora é maximizar o número de correspondências. Eu criei uma função que detecta o número de correspondências corretas de cada conjunto, como pode ser visto nesta captura de tela final. Uma coluna ou linha obtém um ponto se a pontuação mais baixa é atribuída à sequência que deveria ser correspondida, e pontos parciais são dados se houver um empate para a pontuação mais baixa e a correspondência correta estiver entre as seqüências correspondentes. Eu então otimizei. Você pode ver que uma célula verde é a coluna que melhor corresponde à linha atual e um quadrado azul ao redor da célula é a linha que melhor corresponde à coluna atual. A pontuação no canto inferior é aproximadamente o número de correspondências bem-sucedidas e é isso que dizemos ao nosso problema de otimização para maximizar.

O algoritmo foi um sucesso maravilhoso, e os parâmetros da solução dizem muito sobre esse tipo de problema. Você notará que a pontuação otimizada foi 44 e a melhor pontuação possível é 48. As 5 colunas no final são iscas e não têm nenhuma correspondência com os valores da linha. Quanto mais chamarizes houver, mais difícil será naturalmente encontrar a melhor correspondência.

Nesse caso específico de correspondência, o comprimento das strings é irrelevante, porque esperamos abreviações que representem palavras mais longas; portanto, o peso ideal para o comprimento é -0,3, o que significa que não penalizamos as strings que variam em comprimento. Reduzimos a pontuação antecipando essas abreviações, dando mais espaço para correspondências parciais de palavras para substituir as correspondências que não sejam de palavras que simplesmente exigem menos substituições, porque a cadeia é mais curta.

O peso da palavra é 1,0, enquanto o peso da frase é de apenas 0,5, o que significa que penalizamos palavras inteiras que faltam em uma sequência e valorizamos mais a frase inteira intacta. Isso é útil porque muitas dessas seqüências têm uma palavra em comum (o perigo), onde o que realmente importa é se a combinação (região e perigo) é ou não mantida.

Finalmente, o peso mínimo é otimizado em 10 e o peso máximo em 1. O que isso significa é que, se a melhor das duas pontuações (frase de valor e palavras de valor) não for muito boa, a partida será muito penalizada, mas não penaliza bastante a pior das duas pontuações. Essencialmente, isso enfatiza a exigência de que o valueWord ou o valuePhrase tenham uma boa pontuação, mas não os dois. Uma espécie de mentalidade "pegue o que pudermos".

É realmente fascinante o que o valor otimizado desses 5 pesos diz sobre o tipo de correspondência de seqüência difusa que está ocorrendo. Para casos práticos completamente diferentes de correspondência de seqüência difusa, esses parâmetros são muito diferentes. Eu usei para 3 aplicativos separados até agora.

Embora não seja usado na otimização final, foi estabelecida uma planilha de benchmarking que combina colunas entre si para obter todos os resultados perfeitos na diagonal e permite que o usuário altere parâmetros para controlar a taxa na qual as pontuações divergem de 0 e observe as semelhanças inatas entre as frases de pesquisa ( que em teoria poderia ser usado para compensar falsos positivos nos resultados)

Outras aplicações

Essa solução pode ser usada em qualquer lugar em que o usuário deseje que um sistema de computador identifique uma string em um conjunto de strings em que não há uma combinação perfeita. (Como uma correspondência aproximada de vlookup para strings).

Portanto, o que você deve tirar disso é que você provavelmente deseja usar uma combinação de heurísticas de alto nível (encontrar palavras de uma frase na outra, comprimento de ambas as frases, etc.) juntamente com a implementação do algoritmo de distância de Levenshtein. Como decidir qual é a "melhor" correspondência é uma determinação heurística (difusa) - você precisará criar um conjunto de pesos para todas as métricas apresentadas para determinar a similaridade.

Com o conjunto apropriado de heurísticas e pesos, você terá seu programa de comparação rapidamente tomando as decisões que tomaria.

Esse problema aparece o tempo todo em bioinformática. A resposta aceita acima (que foi ótima por sinal) é conhecida em bioinformática como algoritmos Needleman-Wunsch (compare duas cadeias) e Smith-Waterman (encontre uma substring aproximada em uma cadeia mais longa). Eles funcionam muito bem e são cavalos de trabalho há décadas.

Mas e se você tiver um milhão de strings para comparar? Isso é um trilhão de comparações pareadas, cada uma das quais é O (n * m)! Os seqüenciadores de DNA modernos geram facilmente um bilhão de seqüências curtas de DNA, cada uma com cerca de 200 "letras" de DNA. Normalmente, queremos encontrar, para cada uma dessas cadeias, a melhor correspondência com o genoma humano (3 bilhões de letras). Claramente, o algoritmo Needleman-Wunsch e seus parentes não funcionam.

Esse chamado "problema de alinhamento" é um campo de pesquisa ativa. Atualmente, os algoritmos mais populares conseguem encontrar correspondências inexatas entre 1 bilhão de strings curtas e o genoma humano em questão de horas em hardware razoável (digamos, oito núcleos e 32 GB de RAM).

A maioria desses algoritmos funciona encontrando rapidamente correspondências exatas curtas (sementes) e depois estendendo-as para a cadeia completa usando um algoritmo mais lento (por exemplo, o Smith-Waterman). A razão pela qual isso funciona é que realmente estamos interessados ​​apenas em algumas partidas fechadas, por isso vale a pena se livrar dos 99,9 ...% dos pares que não têm nada em comum.

Como encontrar correspondências exatas ajuda a encontrar correspondências inexatas ? Bem, digamos que permitimos apenas uma única diferença entre a consulta e o destino. É fácil ver que essa diferença deve ocorrer na metade direita ou esquerda da consulta e, portanto, a outra metade deve corresponder exatamente. Essa idéia pode ser estendida a várias incompatibilidades e é a base para o algoritmo ELAND comumente usado com seqüenciadores de DNA Illumina.

Existem muitos algoritmos muito bons para fazer a correspondência exata de cadeias. Dada uma sequência de consulta de comprimento 200 e uma sequência de destino de 3 bilhões (o genoma humano), queremos encontrar qualquer local no destino em que haja uma substring de comprimento k que corresponda exatamente a uma substring da consulta. Uma abordagem simples é começar indexando o destino: pegue todas as substrings com comprimento de k, coloque-as em uma matriz e classifique-as. Em seguida, pegue cada substring de k-long da consulta e pesquise o índice classificado. A classificação e a pesquisa podem ser feitas no tempo O (log n).

Mas o armazenamento pode ser um problema. Um índice da meta de 3 bilhões de letras precisaria conter 3 bilhões de ponteiros e 3 bilhões de palavras com comprimento de k. Parece difícil encaixar isso em menos de várias dezenas de gigabytes de RAM. Surpreendentemente, porém, podemos compactar bastante o índice, usando a transformação Burrows-Wheeler , e ele ainda poderá ser consultado com eficiência. Um índice do genoma humano pode caber em menos de 4 GB de RAM. Essa idéia é a base de alinhadores de sequência populares como Bowtie e BWA .

Como alternativa, podemos usar uma matriz de sufixos , que armazena apenas os ponteiros, mas representa um índice simultâneo de todos os sufixos na cadeia de destino (essencialmente, um índice simultâneo para todos os valores possíveis de k; o mesmo se aplica à transformação Burrows-Wheeler ) Um índice de matriz de sufixos do genoma humano terá 12 GB de RAM se usarmos ponteiros de 32 bits.

Os links acima contêm muitas informações e links para trabalhos de pesquisa primários. O link ELAND vai para um PDF com figuras úteis que ilustram os conceitos envolvidos e mostra como lidar com inserções e exclusões.

Finalmente, enquanto esses algoritmos basicamente resolveram o problema de (re) sequenciar genomas humanos únicos (um bilhão de cadeias curtas), a tecnologia de sequenciamento de DNA melhora ainda mais rápido que a lei de Moore, e estamos nos aproximando rapidamente de conjuntos de dados de trilhões de letras. Por exemplo, atualmente existem projetos em andamento para sequenciar os genomas de 10.000 espécies de vertebrados , cada um com um bilhão de letras ou mais. Naturalmente, queremos fazer uma correspondência inexata de pares aos dados ...

Eu contesto que a opção B esteja mais próxima da sequência de teste, pois possui apenas 4 caracteres (e 2 exclusões) de ser a sequência original. Considerando que você vê C como mais próximo, porque inclui marrom e vermelho. Teria, no entanto, uma maior distância de edição.

Existe um algoritmo chamado Distância de Levenshtein que mede a distância de edição entre duas entradas.

Aqui está uma ferramenta para esse algoritmo.

1. Tarifas escolha A como uma distância de 15.
2. Classifica a opção B como uma distância de 6.
3. Classifica a opção C como uma distância de 9.

Edição: Desculpe, eu continuo misturando seqüências de caracteres na ferramenta levenshtein. Atualizado para corrigir as respostas.

Implementação de Lua, para posteridade:

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

Você pode estar interessado nesta postagem do blog.

http://seatgeek.com/blog/dev/fuzzywuzzy-fuzzy-string-matching-in-python

Fuzzywuzzy é uma biblioteca Python que fornece medidas de distância fáceis, como a distância de Levenshtein para correspondência de cadeias. Ele é construído sobre o difflib na biblioteca padrão e fará uso da implementação C Python-levenshtein, se disponível.

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

Você pode achar esta biblioteca útil! http://code.google.com/p/google-diff-match-patch/

Atualmente, está disponível em Java, JavaScript, Dart, C ++, C #, Objective C, Lua e Python.

Também funciona muito bem. Eu o uso em alguns dos meus projetos Lua.

E não acho que seria muito difícil portá-lo para outros idiomas!

Se você estiver fazendo isso no contexto de um mecanismo de pesquisa ou front-end em um banco de dados, considere usar uma ferramenta como o Apache Solr , com o plug- in ComplexPhraseQueryParser . Essa combinação permite pesquisar em um índice de cadeias com os resultados classificados por relevância, conforme determinado pela distância de Levenshtein.

Nós o usamos contra uma grande coleção de artistas e títulos de músicas quando a consulta recebida pode ter um ou mais erros de digitação e funcionou muito bem (e notavelmente rápido, considerando que as coleções estão na casa de milhões de strings).

Além disso, com o Solr, é possível pesquisar no índice sob demanda via JSON, para que você não precise reinventar a solução entre os diferentes idiomas que está procurando.

Um recurso muito, muito bom para esse tipo de algoritmo é o Simmetrics: http://sourceforge.net/projects/simmetrics/

Infelizmente, o site incrível que contém grande parte da documentação sumiu :( No caso de voltar a aparecer, seu endereço anterior era o seguinte: http://www.dcs.shef.ac.uk/~sam/simmetrics.html

Voila (cortesia de "Wayback Machine"): http://web.archive.org/web/20081230184321/http://www.dcs.shef.ac.uk/~sam/simmetrics.html

Você pode estudar a fonte do código, existem dezenas de algoritmos para esse tipo de comparação, cada um com uma troca diferente. As implementações estão em Java.

Para consultar um grande conjunto de texto de maneira eficiente, você pode usar o conceito de Editar distância / Editar distância do prefixo.

Distância de Edição ED (x, y): número mínimo de transfroms para ir do termo x ao termo y

Mas computar ED entre cada termo e texto da consulta consome muito tempo e recursos. Portanto, em vez de calcular ED para cada termo primeiro, podemos extrair possíveis termos correspondentes usando uma técnica chamada Qgram Index. e, em seguida, aplique o cálculo do ED nesses termos selecionados.

Uma vantagem da técnica de índice Qgram é que ele suporta a pesquisa difusa.

Uma abordagem possível para adaptar o índice QGram é criar um índice invertido usando Qgrams. Lá, armazenamos todas as palavras que consistem em um Qgram específico, sob esse Qgram (em vez de armazenar uma string completa, você pode usar um ID exclusivo para cada string). Você pode usar a estrutura de dados do Mapa de Árvore em Java para isso. A seguir, um pequeno exemplo de armazenamento de termos

col: col mbia, col ombo, gan col a, ta col ama

Em seguida, ao consultar, calculamos o número de Qgrams comuns entre o texto da consulta e os termos disponíveis.

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

número de q-gramas em comum = 4.

Para os termos com alto número de Qgrams comuns, calculamos o ED / PED com relação ao termo da consulta e, em seguida, sugerimos o termo para o usuário final.

você pode encontrar uma implementação dessa teoria no projeto a seguir (consulte "QGramIndex.java"). Sinta-se a vontade para fazer qualquer pergunta. https://github.com/Bhashitha-Gamage/City_Search

Para estudar mais sobre Editar Distância, Prefixo, Editar Índice Qgram de Distância, assista ao vídeo a seguir da Prof. Dra. Hannah Bast https://www.youtube.com/embed/6pUg2wmGJRo (A lição começa às 20:06)

O problema é difícil de implementar se os dados de entrada forem muito grandes (digamos, milhões de strings). Eu usei a pesquisa elástica para resolver isso.

Início rápido: https://www.elastic.co/guide/en/elasticsearch/client/net-api/6.x/elasticsearch-net.html

Basta inserir todos os dados de entrada no banco de dados e você pode pesquisar qualquer string com base em qualquer distância de edição rapidamente. Aqui está um trecho de código C # que fornecerá uma lista de resultados classificados por distância de edição (menor para maior)

var res = client.Search<ClassName>(s => s
    .Query(q => q
    .Match(m => m
        .Field(f => f.VariableName)
        .Query("SAMPLE QUERY")
        .Fuzziness(Fuzziness.EditDistance(5))
    )
));

Aqui você pode obter um POC golang para calcular as distâncias entre as palavras fornecidas. Você pode ajustar o minDistancee differencepara outros escopos.

Playground: 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)

}