String Vergleich anhand von Ähnlichkeiten

1. offizieller Beitrag

    Ich würde gerne anhand eines Dateinamens eine automatisch Dropdownauswahl realisieren. Das Problem dabei ist, dass die Dateinamen sehr variabel sind und kein exakter Vergleich mit den Dropdown Einträgen möglich ist. Es gibt auch kein festes Muster in den Dateinamen, d.h. der gesuchte String kann vorgestellte und nachgestellte Zeichen haben und selbst die Teilstrings können mit unterschiedlichen Trennzeichen wie Punkt, Bindestrich, Leerzeichen getrennt sein oder auch am Stück ohne Trennzeichen sein.

    Hier mal ein Beispiel:

    Jemand Ideen wie man das am besten lösen könnte?
    Im Moment fällt mir nur eine etwas unschöne Lösung ein. Man könnte der Reihe nach alle Dropdowneinträge in substrings aufteilen und dann für jeden Dropdown Eintrag prüfen ob alle substrings im Dateinamen vorkommen, wenn nicht gehts mit dem nächsten weiter.

    Vielleicht hat ja jemand von euch eine bessere Idee. Mit Regexp kann man das doch sicher auch hinbekommen oder?

    Einmal editiert, zuletzt von misterspeed (6. März 2011 um 13:24)

    • Offizieller Beitrag

    Man könnte Dateinamen und Such-Array "auf den gleichen Nenner" bringen und dann per StringInStr suchen lassen:

    Spoiler anzeigen
    [autoit]


    Global $aNames[5] = ['Peter Soundso', 'Gabi von Gestern', 'Michael Mustermann', 'Michael Mittermeier', 'Muster Gestern']

    [/autoit] [autoit][/autoit] [autoit]

    Global $aFilenames[6] = ['mek249ß0320ß-d3.3s22Gabi-von.gestern.i92390dmdmer.doc', 'blaGabi.doc', '4711Gestern.txt', 'michaelmustermann92ß392ß3ß2sallsa.txt', '333wasarmichael-mittermeier.rtf', '0815Peter.exe']

    [/autoit] [autoit][/autoit] [autoit]

    For $i = 0 To UBound($aFilenames) - 1
    For $j = 0 To UBound($aNames) - 1
    If StringInStr(StringRegExpReplace($aFilenames[$i], '[\.,\+-\s]', ''), StringRegExpReplace($aNames[$j], '[\.,\+-\s]', '')) Then
    ConsoleWrite('Treffer: ' & $aFilenames[$i] & @CR)
    ExitLoop
    EndIf
    Next
    Next

    [/autoit]


    Das passt zumindest für die genannten Beispiele. Wenn da noch andere Zeichen zwischen den Namen stehen können, müsste man das RegExp-Pattern entsprechend anpassen.

    Hi,
    ggf bringt dich eine Ähnlichkeitssuche weiter. Bei Strings bietet sich die Levenshtein-Distanz an, um möglichst ähnliche Strings zu finden.
    Hier im Forum wirst du sicher fündig, Bernd hat imho eine dll dazu geschrieben.
    Schau mal hier [ offen ] Strings vergleichen und hier [ gelöst ] Strings vergleichen

    Danke euch beiden. Die Ähnlichkeitssuche mittels Levenshtein-Distanz schaut sehr interessant aus. Werde mal beide Methoden testen. Da es relativ wenig Einträge im Dropdown gibt (20-30) kommt vielleicht sogar die autoit Version der Levenshtein-Distanz in Frage.

    Ich denke ich kenne noch einen sehr viel einfacheren Weg:

    Alle Zeichen, außer A-Z und a-z aus den Dateinamen entfernen, dann zu Lowercase, so bekommst du z.B. aus 333wasarmichael-mittermeier.rtf ein wasarmichaelmittermeier und kannst es mit StrInStr und dem Namen "michaelmittermeier" abgleichen. ;)

    Ja das entspricht ja in etwa Oscars Lösung, sofern ich seine RegExp richtig verstehe. Werde mal schaun was performanter und zuverlässiger ist. Die Levenshtein-Distanz Lösung hat den Vorteil, dass sie auch bei Schreibfehlern noch ein wahrscheinliches Ergebnis liefert und möglicherweise sogar bei Abkürzungen noch funktioniert.

    • Offizieller Beitrag

    Bei der Levenshtein-Distanz Lösung bekommst Du einen Prozentwert für die Ähnlichkeit. Du musst also einen Schwellenwert einsetzen oberhalb dessen er einen Treffer erkennen soll.
    Das bedingt allerdings auch, dass es zu einem "false positive" kommen kann, wenn der Wert zu niedrig ist. Soll nicht abwertend gemeint sein (die DLL von Bernd670 ist klasse), nur als Hinweis.

    Ja das war mir klar soweit. Beim testen der DLL ist mir allerdings gerade aufgefallen, dass diese nur unter 32bit funktioniert. Könnte mir da vielleicht noch jemand eine 64bit Version compilieren? Hab mit C/C++ leider keine nennenswerten Erfahrungen...

    Source code ist dort zufinden: https://autoit.de/index.php?page…1603#post111603

    EDIT:

    Ok die Fehlerquote der DLL ist leider in meinem Fall doch recht hoch. Sofern man sich rein nach der prozentualen Übereinstimmung richtet und jeweils den höchsten Wert nimmt sind in meinem Test 11 von 21 Dateien falsch zugeordnet.
    Mal testen wie es mit der Methode von Oscar ausschaut, ggf. würde eine Kombination beder Varianten nochmals bessere Ergebnisse liefern.

    EDIT2:

    Hatte nur fehlerhafte bzw unvollständige Datensätze. Nun liefern beide Varianten nahezu 100% korrekte Treffer. Die DLL ist etwa 50% schneller, wobei das bei 40 bzw 60ms Gesamtzeit nicht der rede Wert ist.

    2 Mal editiert, zuletzt von misterspeed (6. März 2011 um 17:39)