Ik moet strings vergelijken om te bepalen of ze hetzelfde vertegenwoordigen. Dit heeft betrekking op door mensen ingevoerde naamvallen waarbij afkortingen en andere kleine details kunnen verschillen. Beschouw bijvoorbeeld de volgende twee titels:
std::string first = "Henry C. Harper v. The Law Offices of Huey & Luey, LLP";
In tegenstelling tot:
std::string second = "Harper v. The Law Offices of Huey & Luey, LLP";
Een mens kan snel inschatten dat dit hoogstwaarschijnlijk één en hetzelfde is. De huidige aanpak die ik heb gevolgd, is om de tekenreeksen te normaliseren door alle letters in kleine letters te gebruiken en alle interpunctie en spaties te verwijderen, waardoor:
std::string firstNormalized = "henrycharpervthelawofficesofhueylueyllp";
En:
std::string secondNormalized = "harpervthelawofficesofhueylueyllp";
Als je in dit geval vergelijkt, is de ene een subreeks van de andere, maar je kunt je andere, meer complexe variaties voorstellen waar dat niet noodzakelijkerwijs gebeurt, maar ze hebben significante subreeksen gemeen. Er kunnen ook af en toe menselijke invoerfouten zijn, zoals getransponeerde letters en spelfouten.
Misschien kan een of ander character diff-programma helpen? Ik heb goede line diff-programma’s gezien voor het vergelijken van verschillen in code die moet worden ingecheckt, is er zoiets op karakterbasis, misschien in boost? Als u het aantal opeenvolgende tekens gemeenschappelijk zou kunnen tellen en de verhouding tot de niet-gedeelde tekens zou kunnen nemen, zou dat misschien een goede heuristiek zijn?
Uiteindelijk heb ik een Booleaanse beslissing nodig of ik ze als hetzelfde moet beschouwen of niet. Het hoeft niet perfect te zijn, maar het zou idealiter zelden verkeerd moeten zijn.
Welk algoritme kan ik gebruiken dat me een soort kwantificering geeft van hoe vergelijkbaar de twee strings met elkaar zijn, die ik vervolgens kan omzetten in een ja/nee-antwoord door middel van een heuristiek?
Antwoord 1, autoriteit 100%
Wat u zoekt, worden String Metric-algoritmen genoemd. Er is een aanzienlijkaantal van hen, velen met vergelijkbare kenmerken. Onder de meer populaire:
- Levenshtein Distance: het minimumaantal bewerkingen van één teken dat nodig is om één woord te wijzigen in de andere. Strings hoeven niet dezelfde lengte te hebben
- Hamming Distance: Het aantal tekens dat verschillend is in twee strings van gelijke lengte.
- Smith–Waterman: een familie van algoritmen voor het berekenen van variabele subreeksen overeenkomsten.
- Sørensen–Dice Coefficient: een overeenkomstalgoritme dat de verschilcoëfficiënten van aangrenzende tekenparen.
Bekijk deze en andere op de wiki-paginaover het onderwerp.
Antwoord 2, autoriteit 15%
Damerau Levenshtein-afstandis een ander algoritme voor het vergelijken van twee strings en het is vergelijkbaar met het Levenshtein-afstandsalgoritme. Het verschil tussen de twee is dat het ook transposities tussen karakters kan controleren en dus een beter resultaat kan geven voor foutcorrectie.
Bijvoorbeeld: de Levenshtein-afstand tussen nighten nightis 2
maar Damerau Levenshtein-afstand tussen nighten nightzal 1 zijn omdat het slechts een verwisseling van een paar tekens is.
Antwoord 3, autoriteit 7%
Daar zou je ngrams voor kunnen gebruiken. Transformeer bijvoorbeeld de twee strings in woordtrigrammen (meestal kleine letters) en vergelijk het percentage ervan dat gelijk is aan elkaar.
Uw uitdaging is om een minimumpercentage voor gelijkenis te definiëren.
http://en.wikipedia.org/wiki/n-gram
Antwoord 4, Autoriteit 2%
Een ander algoritme dat u kunt overwegen is de Simon White Gelijkeenheid:
def get_bigrams(string):
"""
Take a string and return a list of bigrams.
"""
if string is None:
return ""
s = string.lower()
return [s[i : i + 2] for i in list(range(len(s) - 1))]
def simon_similarity(str1, str2):
"""
Perform bigram comparison between two strings
and return a percentage match in decimal form.
"""
pairs1 = get_bigrams(str1)
pairs2 = get_bigrams(str2)
union = len(pairs1) + len(pairs2)
if union == 0 or union is None:
return 0
hit_count = 0
for x in pairs1:
for y in pairs2:
if x == y:
hit_count += 1
break
return (2.0 * hit_count) / union
Antwoord 5
U kunt het algoritme gebruiken van het berekenen van de lengte van de langste gemeenschappelijke subsequentie om het probleem op te lossen. Als de lengte van de langste gemeenschappelijke subsequentie voor zowel de invoerkoorden minder is dan de lengte van een van de snaren, zijn ze ongelijk.
U kunt de aanpak van dynamische programmering gebruiken om het probleem op te lossen en de ruimtecomplexiteit ook te optimaliseren voor het geval u de langste gemeenschappelijke subsequentie niet wilt achterhalen.