Ich muss Zeichenfolgen vergleichen, um zu entscheiden, ob sie dasselbe darstellen. Dies bezieht sich auf von Menschen eingegebene Falltitel, bei denen Abkürzungen und andere kleine Details abweichen können. Betrachten Sie beispielsweise die folgenden beiden Titel:

std::string first = "Henry C. Harper v. The Law Offices of Huey & Luey, LLP";

Im Gegensatz zu:

std::string second = "Harper v. The Law Offices of Huey & Luey, LLP";

Ein Mensch kann schnell einschätzen, dass dies höchstwahrscheinlich ein und dasselbe ist. Der aktuelle Ansatz, den ich gewählt habe, besteht darin, die Zeichenfolgen zu normalisieren, indem ich alle Buchstaben in Kleinbuchstaben schreibe und alle Satzzeichen und Leerzeichen entferne.

std::string firstNormalized = "henrycharpervthelawofficesofhueylueyllp";

Und:

std::string secondNormalized = "harpervthelawofficesofhueylueyllp";

Wenn man in diesem Fall vergleicht, ist eines eine Teilsequenz des anderen, aber Sie können sich andere komplexere Variationen vorstellen, bei denen dies nicht unbedingt der Fall ist, die jedoch signifikante Teilsequenzen gemeinsam haben. Es kann auch gelegentlich zu Eingabefehlern kommen, wie z. B. vertauschte Buchstaben und Rechtschreibfehler.

Vielleicht könnte eine Art Character Diff-Programm helfen? Ich habe gute Zeilendifferenz-Programme zum Vergleichen von Unterschieden im Code gesehen, die eingecheckt werden sollen. Gibt es so etwas auf Zeichenbasis, vielleicht im Boost-Modus? Wenn Sie die Anzahl der aufeinanderfolgenden Zeichen gemeinsam zählen und das Verhältnis zu den nicht freigegebenen Zeichen nehmen könnten, wäre das vielleicht eine gute Heuristik?

Am Ende brauche ich eine boolesche Entscheidung, ob ich sie gleich betrachten soll oder nicht. Es muss nicht perfekt sein, aber es sollte im Idealfall selten falsch sein.

Welchen Algorithmus kann ich verwenden, um zu quantifizieren, wie ähnlich die beiden Zeichenfolgen zueinander sind, und den ich dann mithilfe einer Heuristik in eine Ja / Nein-Antwort umwandeln kann?