Prozentuale Übereinstimmung zweier Strings

[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?

[/me]

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]

[Hyperion]

Schau mal bei wiki nach der Hamming Distanz. Ob es da was fertiges gibt, weiß ich nicht. Evtl. mal bei pypi suchen?

[Pekh]

In der Standard-Bibliothek findet sich z.B. das Modul difflib.

[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...

[snafu]

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.