Algoritmos de similaridade de string?

Eu preciso comparar duas seqüências de caracteres e calcular sua semelhança, para filtrar uma lista das seqüências mais semelhantes.

Por exemplo. procurando por “dog” retornaria

  1. cachorro
  2. doggone
  3. pântano
  4. névoa
  5. nebuloso

Por exemplo. procurando por “crack” retornaria

  1. rachar
  2. piada
  3. prateleira
  4. Jack
  5. charlatão

Eu me deparei com:

  • Mercúrio
  • Metal líquido

Você conhece mais algum algoritmo de similaridade de string?

Parece que você está precisando de algum tipo de correspondência difusa. Aqui está a implementação java de algum conjunto de métricas de similaridade http://www.dcs.shef.ac.uk/~sam/stringmetrics.html . Aqui está uma explicação mais detalhada das métricas de string http://www.cs.cmu.edu/~wcohen/postscript/ijcai-ws-2003.pdf depende de quão confuso e rápido a sua implementação deve ser.

A distância de Levenshtein é o algoritmo que eu recomendaria. Calcula o número mínimo de operações que você deve fazer para alterar uma string para outra. Quanto menos alterações, mais as seqüências de caracteres são semelhantes …

Se o foco for no desempenho, eu implementaria um algoritmo baseado em uma estrutura trie
(funciona bem para encontrar palavras em um texto, ou para ajudar a corrigir uma palavra, mas no seu caso você pode encontrar rapidamente todas as palavras que contêm uma determinada palavra ou todas, exceto uma letra, por exemplo).

Por favor, siga primeiro o link da Wikipedia acima. Tries é o método de sorting de palavras mais rápido ( n palavras, search s , O ( n ) para criar o trie, O (1) para pesquisar s (ou se você preferir, se a é o comprimento médio, O ( an ) para o trie e O ( s ) para a pesquisa)).

Uma implementação rápida e fácil (a ser otimizada) do seu problema (palavras semelhantes) consiste em

  • Faça o trie com a lista de palavras, tendo todas as letras indexadas frente e verso (veja exemplo abaixo)
  • Para pesquisar s , repita de s [0] para encontrar a palavra no trie, depois s [1] etc …
  • No trie, se o número de letras encontradas for len ( s ) – k a palavra é exibida, onde k é a tolerância (1 letra faltando, 2 …).
  • O algoritmo pode ser estendido para as palavras na lista (veja abaixo)

Exemplo, com as palavras car , vars .

Construindo o trio (letra grande significa que uma palavra termina aqui, enquanto outra pode continuar). O > é pós-índice (ir para frente) e < é pré-índice (vai para trás). Em outro exemplo, podemos ter que indicar também a letra inicial, não é apresentado aqui para maior clareza.
O < e > em C ++, por exemplo, seria Mystruct *previous,*next , significando de a > c < r , você pode ir diretamente de a para c e, inversamente, também de a para R

  1. c < a < R 2. a > c < R 3. > v < r < S 4. R > a > c 5. > v < S 6. v < a < r < S 7. S > r > a > v 

Olhando estritamente para o carro o trie lhe dá access a partir de 1., e você encontra o carro (você teria encontrado também tudo começando com carro , mas também qualquer coisa com carro dentro - não está no exemplo - mas vigário por exemplo teria sido encontrado de c > i > v < a < R ).

Para pesquisar enquanto permite tolerância errada / faltante de uma letra, você faz uma iteração de cada letra de s e conta o número de letras consecutivas - ou ignorando 1 letra - que você obtém de s na lista.

procurando car ,

  • c : pesquisando o trie por c < a e c < r (falta de letra em s ). Para aceitar uma letra errada em uma palavra w , tente pular em cada iteração a letra errada para ver se ar está para trás, isso é O ( w ). Com duas letras, O ( w ²) etc ... mas outro nível de índice poderia ser adicionado ao trie para levar em conta o salto sobre as letras - tornando o complexo complexo, e ganancioso em relação à memory.
  • a , então r : o mesmo que acima, mas procurando também

Isto é apenas para fornecer uma idéia sobre o princípio - o exemplo acima pode ter algumas falhas (eu verificarei novamente amanhã).

Você poderia fazer isso:

 Foreach string no palheiro
     deslocamento : = -1;
     matchedCharacters : = 0;
     Foreach char na agulha Do
         offset : = PositionInString ( string , caractere , deslocamento +1);
         Se offset = -1 então
             Pausa ;
         Fim ;
         matchedCharacters : = matchedCharacters + 1;
     Fim ;
     Se correspondidoCaracteres > 0 Então
        Correspondência // parcial encontrada
     Fim ;
 Fim ;

Com os caracteres de correspondência, você pode determinar o “grau” da correspondência. Se for igual ao comprimento da agulha , todos os caracteres na agulha também estarão em seqüência . Se você também armazenar o deslocamento do primeiro caractere correspondente, também poderá classificar o resultado pela “densidade” dos caracteres correspondentes, subtraindo o deslocamento do primeiro caractere correspondente do deslocamento do último deslocamento do caractere correspondente; quanto menor a diferença, mais densa é a correspondência.

 class Program { static int ComputeLevenshteinDistance(string source, string target) { if ((source == null) || (target == null)) return 0; if ((source.Length == 0) || (target.Length == 0)) return 0; if (source == target) return source.Length; int sourceWordCount = source.Length; int targetWordCount = target.Length; int[,] distance = new int[sourceWordCount + 1, targetWordCount + 1]; // Step 2 for (int i = 0; i <= sourceWordCount; distance[i, 0] = i++); for (int j = 0; j <= targetWordCount; distance[0, j] = j++); for (int i = 1; i <= sourceWordCount; i++) { for (int j = 1; j <= targetWordCount; j++) { // Step 3 int cost = (target[j - 1] == source[i - 1]) ? 0 : 1; // Step 4 distance[i, j] = Math.Min(Math.Min(distance[i - 1, j] + 1, distance[i, j - 1] + 1), distance[i - 1, j - 1] + cost); } } return distance[sourceWordCount, targetWordCount]; } static void Main(string[] args){ Console.WriteLine(ComputeLevenshteinDistance ("Stackoverflow","StuckOverflow")); Console.ReadKey(); } }