Quels sont les algorithmes pour comparer à quel point deux chaînes sont similaires?
J'ai besoin de comparer les chaînes pour décider si elles représentent la même chose. Cela concerne les titres de cas saisis par les humains où les abréviations et autres petits détails peuvent différer. Par exemple, considérons les deux titres suivants:
std::string first = "Henry C. Harper v. The Law Offices of Huey & Luey, LLP";
, par opposition à:
std::string second = "Harper v. The Law Offices of Huey & Luey, LLP";
Un humain peut rapidement évaluer que ceux-ci sont très probablement une seule et même chose. L'approche actuelle que j'ai prise est de normaliser les chaînes en minuscules toutes les lettres et en supprimant toutes les ponctuations et les espaces donner:
std::string firstNormalized = "henrycharpervthelawofficesofhueylueyllp";
Et:
std::string secondNormalized = "harpervthelawofficesofhueylueyllp";
En comparant dans ce cas, l'une est une sous-séquence de l'autre, mais vous pouvez imaginer d'autres variations plus complexes où cela ne se produit pas nécessairement, mais elles ont des sous-séquences significatives en commun. Il pourrait également y avoir des erreurs d'entrée humaines occasionnelles telles que des lettres transposées et des fautes d'orthographe.
Peut-être qu'une sorte de programme de diff de caractères pourrait aider? J'ai vu de bons programmes de diff de ligne pour comparer les différences de code à vérifier en, y at-il quelque chose comme ça sur une base de caractère, peut-être dans boost? Si vous pouviez compter le nombre de caractères consécutifs en commun et prendre le rapport aux caractères non partagés, ce serait peut-être une bonne heuristique?
En fin de Compte, j'ai besoin d'une décision booléenne quant à savoir s'il faut les considérer comme identiques ou non. Il ne doit pas être parfait, mais il devrait idéalement rarement être faux.
Quel algorithme puis-je utiliser qui me donnera une sorte de quantification quant à la façon dont le deux chaînes sont l'une à l'autre que je peux ensuite convertir en une réponse oui/non par le biais d'une heuristique?
3 réponses
Ce que vous cherchez s'appellestring Metric algorithmes. Il y a un significatif Nombre d'entre eux, beaucoup avec des caractéristiques similaires. Parmi les plus populaires:
- Levenshtein Distance : Nombre minimum de modifications à un seul caractère nécessaires pour changer un mot en un autre. Les chaînes ne doivent pas avoir la même longueur
- Hamming Distance : le nombre de caractères qui sont différents dans deux longueurs égales chaîne.
- Smith-Waterman : une famille d'algorithmes pour calculer les similitudes de sous-séquence variable.
- Coefficient Sørensen-Dice : algorithme de similarité qui calcule les coefficients de différence de paires de caractères adjacentes.
Jetez un oeil à ceux-ci ainsi que d'autres sur la page wiki sur le sujet.
Damerau Levenshtein distance est un autre algorithme pour comparer deux chaînes et il est similaire à L'algorithme de distance Levenshtein. La différence entre les deux est qu'il peut également vérifier les transpositions entre les caractères et peut donc donner un meilleur résultat pour la correction d'erreur.
Par exemple: La distance de Levenshtein entre night et nigth est 2
mais Damerau Levenshtein distance entre night et nigth sera 1 parce que c'est juste un échange d'une paire de caractère.
Vous pouvez utiliser ngrams pour cela. Par exemple, transformez les deux chaînes en trigrammes de mots (généralement en minuscules) et comparez le pourcentage d'entre elles qui sont égales l'une à l'autre.
Votre défi consiste à définir un pourcentage minimum de similarité.