- Offizieller Beitrag
Es geht um mein Programm "MP3-Double-Finder".
Mal ein Beispiel:
String1 = Bruce Springsteen - 57 Channels (And Nothin' On).mp3
String2 = Bruce Springsten - 57 Channels (And Nothing On).mp3
Man sieht ja auf den ersten Blick, dass es sich dabei um die gleichen Lieder handelt, aber wie mache ich das programmtechnisch?
Ich möchte nun, dass die Funktion einen Wert ausgibt, wie ähnlich sich die beiden Strings sind (z.B. in Prozent).
Nun habe ich hier im Forum eine Funktion gefunden, die genau das macht:
Spoiler anzeigen
; FaTolStrComp00.AU3 fehlertoleranter Zeichenkettenvergleich für AutoIT3
; basiert auf der Levenshtein-Distanz, siehe dazu http://de.wikipedia.org/wiki/Levenshtein-Distanz
; Lutz Müller, FH Köln Campus Gummersbach (uuchip http://www.autoit.de)
; Inhalt
; min3($a,$b,$c) - Minimum aus drei Werten wird zurückgegben
; LevenshteinDistance($s, $t) - Gibt Levenshteinabstand der beide Zeichenketten zurück
; Für die Levenshtein-Distanz gelten einige obere und untere Schranken:
; * sie beträgt mindestens den Unterschied der Längen beider Strings
; * sie beträgt höchstens die Länge des längeren Strings
; * sie ist dann und nur dann 0, wenn beide Strings identisch sind
; CompTstr($s, $t) - toleranter Zeichenkettenvergleich als Wahrscheinlichkeit
; von Wert = 0 (totaler Ungleichheit) bis 1 (Gleichheit)
Func min3($a, $b, $c)
Local $dummy
$dummy = $a
If $b < $dummy Then $dummy = $b
If $c < $dummy Then $dummy = $c
Return $dummy
EndFunc ;==>min3
Func LevenshteinDistance($s, $t)
Local $n, $m
$n = StringLen($s)
$m = StringLen($t)
If $s = $t Then Return 0
If $s = "" Then Return $m
If $t = "" Then Return $n
Local $d[$n + 1][$m + 1], $i, $j, $cost
For $i = 0 To $n
$d[$i][0] = $i
Next
For $j = 0 To $m
$d[0][$j] = $j
Next
For $i = 1 To $n
For $j = 1 To $m
If StringMid($s, $i, 1) = StringMid($t, $j, 1) Then
$cost = 0
Else
$cost = 1
EndIf
$d[$i][$j] = min3($d[$i - 1][$j] + 1, $d[$i][$j - 1] + 1, $d[$i - 1][$j - 1] + $cost)
Next
Next
Return $d[$n][$m]
EndFunc ;==>LevenshteinDistance
Func CompTstr($s, $t)
Local $n, $m
$n = StringLen($s)
$m = StringLen($t)
If $n < $m Then $n = $m
Return ($n - LevenshteinDistance($s, $t)) / $n
EndFunc ;==>CompTstr
Das Problem ist bloß, dass diese Funktion zu lange dafür braucht. In einem Test mit ca. 9000 MP3s muss ich jeden Titel mit den anderen 9000 vergleichen. Das ergibt zwei ineinander verschachtelte Schleifen, bei der ein Durchlauf der äußeren Schleife ca. 15 Minuten dauert. 9000 mal 15 Minuten ist mir ehrlich gesagt zu lang, um darauf zu warten. Dann kann ich das gleich von Hand machen.
Gibt es nicht irgendeine andere Möglichkeit die Strings nach Ähnlichkeit zu bewerten?