Eu preciso comparar strings para decidir se elesrepresentam a mesma coisa. Isso se relaciona com os títulos de casos inseridos por seres humanos, onde as abreviações e outros pequenos detalhes podem ser diferentes. Por exemplo, considere os dois títulos a seguir:
std::string first = "Henry C. Harper v. The Law Offices of Huey & Luey, LLP";
Ao contrário de:
std::string second = "Harper v. The Law Offices of Huey & Luey, LLP";
Um humano pode avaliar rapidamente que estes são maisprovavelmente um e o mesmo. A abordagem atual que tomei é normalizar as strings diminuindo todas as letras e removendo todas as pontuações e espaços que dão:
std::string firstNormalized = "henrycharpervthelawofficesofhueylueyllp";
E:
std::string secondNormalized = "harpervthelawofficesofhueylueyllp";
Comparando, neste caso, uma é uma subseqüência deo outro, mas você pode imaginar outras variações mais complexas onde isso não ocorre necessariamente, mas elas têm sub-sequências significativas em comum. Também pode haver erros ocasionais de entrada humana, como letras transpostas e erros de ortografia.
Talvez algum tipo de programa de diferenças de personagensSocorro? Eu tenho visto bons programas de comparação de linhas para comparar as diferenças no código a ser verificado, há algo assim em caráter, talvez em aumento? Se você pudesse contar o número de caracteres consecutivos em comum e levar a razão para os caracteres não compartilhado, talvez isso seja uma boa heurística?
No final, preciso de uma decisão booleana para considerá-los iguais ou não. Não precisa ser perfeito, mas idealmente, raramente deveria estar errado.
Que algoritmo posso usar que me dará algum tipo de quantificação de como as duas sequências são semelhantes umas às outras que eu posso então converter em uma resposta sim / não por meio de alguma heurística?
Respostas:
61 para resposta № 1O que você está procurando é chamado String Metric algoritmos. Existe um significativo número deles, muitos com características semelhantes. Entre os mais populares:
- Distância Levenshtein : O número mínimo de edições de caracteres únicos necessárias para alterar uma palavra para outra. Strings não precisam ter o mesmo comprimento
- Distância Hamming : O número de caracteres que são diferentes em duas seqüências de comprimento igual.
- Smith-Waterman : Uma família de algoritmos para calcular semelhanças de subseqüências variáveis.
- Coeficiente Sørensen – Dice : Um algoritmo de similaridade que calcula coeficientes de diferença de pares de caracteres adjacentes.
Dê uma olhada nestes e em outros no página wiki sobre o assunto.
10 para resposta № 2
Damerau Levenshtein distância é outro algoritmo para comparar duas stringse é semelhante ao algoritmo de distância de Levenshtein. A diferença entre os dois é que ele também pode verificar transposições entre os caracteres e, portanto, pode dar um melhor resultado para a correção de erros.
Por exemplo: A distância de Levenshtein entre night e nigth é 2 mas Damerau Levenshtein distância entre night e nigth será 1 porque é apenas uma troca de um par de caracteres.
2 para resposta № 3
Você poderia usar ngrams para isso. Por exemplo, transforme as duas strings em trigramas de palavras (geralmente em minúsculas) e compare a porcentagem delas que são iguais entre si.
Seu desafio é definir uma porcentagem mínima para a similaridade.
http://en.wikipedia.org/wiki/N-gram