Seite 1 von 1
Prozentuale Übereinstimmung zweier Strings
Verfasst: Mittwoch 11. Mai 2011, 19:54
von Gremlin
Hallo zusammen,
folgender Sachverhalt:
Ich habe einen String, und eine Liste mit weiteren Strings. Es wurde bereits ausgeschlossen, dass der String 1:1 in der Liste ist. Nun möchte ich wissen ob es Übereinstimmungen gibt die nicht 1:1 sind.
Zum Beispiel:
Code: Alles auswählen
to_be_found = 'eins_zwei_drei'
where_to_search = ['eins', 'eins_zwei', 'eins_zweidrei', 'einszweidrei', 'vier']
result = check_?(to_be_found, where_to_search)
result
[(0, 0.3), (1, 0.6), (2, 0.9), (3, 0.85), (4, 0.0)]
Gibt es da irgendwelche libs für? Ich würde ja bei Google suchen, aber ich weiß nicht wonach ich suchen soll.
Wenn nicht, wie gehe ich das am besten an wenn ich das selbst umsetzen wollen würde?
Re: Prozentuale Übereinstimmung zweier Strings
Verfasst: Mittwoch 11. Mai 2011, 20:07
von /me
Gremlin hat geschrieben:Ich habe einen String, und eine Liste mit weiteren Strings. Es wurde bereits ausgeschlossen, dass der String 1:1 in der Liste ist. Nun möchte ich wissen ob es Übereinstimmungen gibt die nicht 1:1 sind.
Dafür bietet sich die
Levenshtein-Distanz bzw. die Damerau-Levenshtein-Distanz an. Du erhältst dabei die Anzahl der Operationen (Einfügen, Löschen) die erforderlich sind um einen String in einen anderen zu überführen.
Ich hab' auch noch irgendwo ein Codesnippet dafür rumfliegen. Schau mal, ob das was ist was du gebrauchen kannst, dann suche ich bei Bedarf mal den Code.
[EDIT]Da ist er:
http://gytha.org/paste/3[/EDIT]
Re: Prozentuale Übereinstimmung zweier Strings
Verfasst: Mittwoch 11. Mai 2011, 20:08
von Hyperion
Schau mal bei wiki nach der
Hamming Distanz. Ob es da was fertiges gibt, weiß ich nicht. Evtl. mal bei pypi suchen?
Re: Prozentuale Übereinstimmung zweier Strings
Verfasst: Mittwoch 11. Mai 2011, 20:36
von Pekh
In der Standard-Bibliothek findet sich z.B. das Modul difflib.
Re: Prozentuale Übereinstimmung zweier Strings
Verfasst: Mittwoch 11. Mai 2011, 22:36
von Gremlin
Danke. Der SequenceMatcher ausm difflib gefällt mir am besten. Aber ich glaube ich verstehe jetzt warum diverse Fehlerkorrekturen hin und wieder sehr seltsame Vorschläge machen... denn angenommen ich suche nach "insel" und habe als Vergleichswerte "amsel" und "kleine_insel", dann hat die "amsel" die Nase vorn, hm...
Re: Prozentuale Übereinstimmung zweier Strings
Verfasst: Donnerstag 12. Mai 2011, 05:03
von snafu
Gremlin hat geschrieben:Aber ich glaube ich verstehe jetzt warum diverse Fehlerkorrekturen hin und wieder sehr seltsame Vorschläge machen... denn angenommen ich suche nach "insel" und habe als Vergleichswerte "amsel" und "kleine_insel", dann hat die "amsel" die Nase vorn, hm...
Das sind aber zwei Paar Schuhe. Korrekturvorschläge werden meist nach einer Suche gemacht, wenn halt angenommen wird, dass ein anderer Suchbegriff gemeint war, während "kleine_insel" eher eine Vervollständigung ist, die während der Eingabe in einem Popup gemacht werden kann. Dabei ist es natürlich abhängig von der Intelligenz des Completers, ob er nur Vorschläge macht, welche die Eingabe voran gestellt haben (z.B. "Inselgruppe") oder ob er gemäß deinem Beispiel auch Vervollständigungen anzeigt, welche den Suchbebegriff irgendwo im String haben.