Algoritmos aproximados de correspondência de strings

Question

Aqui no trabalho, muitas vezes precisamos encontrar uma string na lista de strings que seja a mais próxima de alguma outra string de entrada.Atualmente, estamos usando o algoritmo Needleman-Wunsch.O algoritmo geralmente retorna muitos falsos positivos (se definirmos a pontuação mínima muito baixa), às vezes ele não encontra uma correspondência quando deveria (quando a pontuação mínima é muito alta) e, na maioria das vezes, precisamos verificar os resultados manualmente.Achamos que deveríamos tentar outras alternativas.

Você tem alguma experiência com os algoritmos?Você sabe como os algoritmos se comparam entre si?

Eu realmente aprecio alguns conselhos.

PS:Estamos codificando em C#, mas você não deveria se preocupar com isso - estou perguntando sobre os algoritmos em geral.

---

Ah, me desculpe, esqueci de mencionar isso.

Não, não o estamos usando para combinar dados duplicados.Temos uma lista de strings que procuramos - chamamos isso de lista de pesquisa.E então precisamos processar textos de várias fontes (como feeds RSS, sites, fóruns, etc.) - extraímos partes desses textos (existem conjuntos inteiros de regras para isso, mas isso é irrelevante) e precisamos combinar aqueles contra a lista de pesquisa.Se a string corresponder a uma das strings na lista de pesquisa - precisamos fazer algum processamento adicional da coisa (o que também é irrelevante).

Não podemos realizar a comparação normal, pois as strings extraídas de fontes externas, na maioria das vezes, incluem algumas palavras extras etc.

De qualquer forma, não é para detecção de duplicatas.

Answer 1

OK, Needleman-Wunsch(NW) é um alinhador clássico de ponta a ponta ("global") da literatura de bioinformática.Há muito tempo estava disponível como "align" e "align0" no pacote FASTA.A diferença era que a versão "0" não era tão tendenciosa em evitar end-gapping, o que muitas vezes permitia favorecer partidas internas de alta qualidade com mais facilidade.Smith-Waterman, suspeito que você saiba, é um alinhador local e é a base original do BLAST.A FASTA também tinha seu próprio alinhador local, que era um pouco diferente.Todos estes são essencialmente métodos heurísticos para estimar a distância de Levenshtein relevante para uma métrica de pontuação para pares de caracteres individuais (em bioinformática, muitas vezes dados por Dayhoff/"PAM", Henikoff&Henikoff, ou outras matrizes e geralmente substituídos por algo mais simples e mais razoavelmente reflexivo de substituições na morfologia linguística das palavras quando aplicada à linguagem natural).

Não sejamos preciosos com os rótulos:A distância de Levenshtein, pelo menos como referenciada na prática, é basicamente a distância de edição e você deve estimá-la porque não é viável calculá-la em geral e é caro calculá-la com exatidão, mesmo em casos especiais interessantes:ali a água fica profunda rapidamente e, portanto, temos métodos heurísticos de longa e boa reputação.

Agora, quanto ao seu próprio problema:há vários anos, tive que verificar a precisão de leituras curtas de DNA em relação à sequência de referência conhecida como correta e descobri algo que chamei de "alinhamentos ancorados".

A idéia é pegar seu conjunto de strings de referência e "digeri-lo", encontrando todos os locais onde ocorre uma determinada substring de N caracteres.Escolha N para que a tabela que você constrói não seja muito grande, mas também para que substrings de comprimento N não sejam muito comuns.Para alfabetos pequenos, como bases de DNA, é possível criar um hash perfeito em sequências de N caracteres e fazer uma tabela e encadear as correspondências em uma lista vinculada de cada compartimento.As entradas da lista devem identificar a sequência e a posição inicial da substring que mapeia para o compartimento em cuja lista elas ocorrem.Estas são "âncoras" na lista de strings a serem pesquisadas nas quais um alinhamento NW provavelmente será útil.

Ao processar uma string de consulta, você pega os N caracteres começando em algum deslocamento K na string de consulta, faz hash deles, procura seu compartimento e, se a lista desse compartimento não estiver vazia, você percorre todos os registros da lista e executa alinhamentos entre a string de consulta e a string de pesquisa referenciada no registro.Ao fazer esses alinhamentos, você alinha a string de consulta e a string de pesquisa no a âncora e extraia uma substring da string de pesquisa que tenha o mesmo comprimento da string de consulta e que contenha essa âncora no mesmo deslocamento, K.

Se você escolher um comprimento de âncora N longo o suficiente e um conjunto razoável de valores de deslocamento K (eles podem ser espalhados pela string de consulta ou restritos a deslocamentos baixos), você deverá obter um subconjunto de alinhamentos possíveis e geralmente obterá vencedores mais claros.Normalmente, você desejará usar o alinhador NW semelhante ao alinhador com menos polarização final.

Este método tenta aumentar um pouco o NW restringindo sua entrada e isso tem um ganho de desempenho porque você faz menos alinhamentos e eles ficam mais frequentemente entre sequências semelhantes.Outra boa coisa a fazer com o seu alinhador NW é permitir que ele desista depois que ocorrer alguma quantidade ou comprimento de lacuna para reduzir custos, especialmente se você sabe que não verá ou não estará interessado em correspondências de qualidade mediana.

Finalmente, este método foi usado em um sistema com alfabetos pequenos, com K restrito às primeiras 100 ou mais posições na string de consulta e com strings de pesquisa muito maiores que as consultas (as leituras de DNA tinham cerca de 1000 bases e as strings de pesquisa estavam em a ordem de 10.000, então eu estava procurando correspondências aproximadas de substring justificadas por uma estimativa de distância de edição especificamente).Adaptar esta metodologia à linguagem natural exigirá uma reflexão cuidadosa:você perde no tamanho do alfabeto, mas ganha se as strings de consulta e de pesquisa tiverem comprimento semelhante.

De qualquer forma, permitir que mais de uma âncora de diferentes extremidades da string de consulta seja usada simultaneamente pode ser útil para filtrar ainda mais os dados alimentados no NW.Se você fizer isso, esteja preparado para possivelmente enviar cordas sobrepostas, cada uma contendo uma das duas âncoras, para o alinhador e depois reconciliar os alinhamentos...ou possivelmente modificar ainda mais o NW para enfatizar a manutenção de suas âncoras praticamente intactas durante um alinhamento usando modificação de penalidade durante a execução do algoritmo.

Espero que isso seja útil ou pelo menos interessante.

Answer 2

Relacionado à distância de Levenstein:você pode querer normalizá-lo dividindo o resultado pelo comprimento da string mais longa, para que você sempre obtenha um número entre 0 e 1 e para poder comparar a distância do par de strings de uma forma significativa (a expressão L( A, B) > L(A, C) - por exemplo - não tem sentido a menos que você normalize a distância).

Answer 3

Algoritmos alternativos a serem observados são concordo (Entrada da Wikipedia sobre agrep), FASTA e EXPLOSÃO algoritmos de correspondência de sequências biológicas.São casos especiais de correspondência aproximada de strings, também no Repositório de algoritmo Stony Brook.Se você puder especificar as diferenças entre as strings, provavelmente poderá se concentrar em um algoritmo personalizado.Por exemplo, aspell usa alguma variante de distância "soundslike" (soundex-metaphone) em combinação com uma distância de "teclado" para acomodar tanto soletradores quanto digitadores ruins.

Answer 4

Estamos usando o Distância Levenshtein método para verificar se há clientes duplicados em nosso banco de dados.Funciona muito bem.

Answer 5

Usar Índice FM com Backtracking, semelhante ao em Gravata borboleta alinhador difuso

Answer 6

Para minimizar incompatibilidades devido a pequenas variações ou erros ortográficos, usei o algoritmo Metaphone e, em seguida, a distância de Levenshtein (escalada de 0 a 100 como uma correspondência percentual) nas codificações Metaphone para medir a proximidade.Isso parece ter funcionado bastante bem.

Answer 7

Para expandir a resposta do Cd-MaN, parece que você está enfrentando um problema de normalização.Não é óbvio como lidar com pontuações entre alinhamentos com comprimentos variados.

Dado o seu interesse, você pode querer obter valores p para o seu alinhamento.Se você estiver usando Needleman-Wunsch, poderá obter esses valores p usando estatísticas de Karlin-Altschul http://www.ncbi.nlm.nih.gov/BLAST/tutorial/Altschul-1.html

O BLAST poderá fazer o alinhamento local e avaliá-los usando essas estatísticas.Se você está preocupado com a velocidade, esta seria uma boa ferramenta para usar.

Outra opção é usar o HMMER.HMMER usa modelos de Markov ocultos de perfil para alinhar sequências.Pessoalmente, penso que esta é uma abordagem mais poderosa, uma vez que também fornece informações posicionais. http://hmmer.janelia.org/

Answer 8

Eu costumava trabalhar com alguns dos dados mais sujos que você já encontrou.Uma média de cerca de 5.000 linhas de dados (equivalente a centenas de milhares de dólares) exigia correspondência totalmente exaustiva.Minha primeira experiência com correspondência difusa foi um algoritmo do Sr. Excel escrito em VBA.Havia certos problemas de consistência, pois as coisas que eu esperava que fossem zero por cento não eram e as coisas que eram cerca de 60 por cento pareciam mais com 90 por cento.Então, mudei-me para Levenshtein e depois para Damerau-Levenshtein.Esta foi uma grande melhoria, mas bastante lenta no Excel.Em seguida, passei para Jaro-Winkler, mas abandonei rapidamente logo depois.Finalmente, em 2016, escrevi o meu próprio (baseado em n-gram) e o refinei nos 2 anos seguintes.Hoje é um complemento chamado Flookup;você pode obtê-lo no Planilhas Google e ver como ele se comporta.