#include <Array.au3>

; 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

; 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)

Global $aToCheck[1]
$aTemp = StringSplit(BinaryToString(InetRead('https://autoit.de/index.php/Thread/83972-Levenshtein-Distanz/')), ' ', 2)
Global $aToCheck[UBound($aTemp)][4]
For $i = 0 To UBound($aTemp) - 1
	$aToCheck[$i][0] = $aTemp[$i]
	$aSplit = StringSplit($aTemp[$i], '')
	_ArrayShuffle($aSplit, 1) ;kräfig durchschütteln /mischen
	For $j = 1 To $aSplit[0]
		$aToCheck[$i][1] &= $aSplit[$j]
	Next
Next
;Array zu vergleichender Wortpaare
;Col 0 + 1 zu vergleichende Wörter
;Col 2 Ergebnis BioShade
;Col 3 Ergebnis Bernd670

$tdStart = TimerInit()
;For $j=0 to 1000
For $i = 0 To UBound($aToCheck) - 1
	$aToCheck[$i][2] = __Levenshtein($aToCheck[$i][0], $aToCheck[$i][1])
Next
;Next
ConsoleWrite('BioShade: ' & TimerDiff($tdStart) & @CRLF)

$tdStart = TimerInit()
;For $j=1 to 1000
For $i = 0 To UBound($aToCheck) - 1
	$aToCheck[$i][3] = _LD_Bernd($aToCheck[$i][0], $aToCheck[$i][1])
Next
;Next
ConsoleWrite('Bernd670: ' & TimerDiff($tdStart) & @CRLF)
;_ArrayDisplay($aToCheck)

$bIdent = True
For $i = 0 To UBound($aToCheck) - 1
	If $aToCheck[$i][2] <> $aToCheck[$i][3] Then
		$bIdent = False
		ExitLoop
	EndIf
Next
ConsoleWrite('BioShade<=>Bernd570 Identische Ergebnisse? '&$bIdent&@CRLF)


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 _LD_Bernd($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   ;==>_LD_Bernd

Func CompTstr($s, $t)
	Local $n, $m
	$n = StringLen($s)
	$m = StringLen($t)
	If $n < $m Then $n = $m
	Return ($n - _LD_Bernd($s, $t)) / $n
EndFunc   ;==>CompTstr

Func __Levenshtein($s, $t)
	Local $m, $n, $iMaxM, $iMaxN
	$n = StringLen($s)
	$m = StringLen($t)
	$ss = StringSplit($s, "")
	$tt = StringSplit($t, "")
	$iMaxN = $n + 1
	$iMaxM = $m + 1
	Dim $d[$iMaxN + 1][$iMaxM + 1]
	$d[0][0] = 0
	If $n = 0 Then
		Return $m
	ElseIf $m = 0 Then
		Return $n
	EndIf
	For $i = 1 To $n
		$d[$i][0] = $d[$i - 1][0] + 1
	Next
	For $j = 1 To $m
		$d[0][$j] = $d[0][$j - 1] + 1
	Next
	For $i = 1 To $n
		For $j = 1 To $m
			$jj = $j - 1
			$ii = $i - 1
			Local $cost
			If (StringMid($s, $i, 1) = StringMid($t, $j, 1)) Then
				$cost = 0
			Else
				$cost = 1
			EndIf
			$d[$i][$j] = __Min(__Min($d[$ii][$j] + 1, $d[$i][$jj] + 1), $d[$ii][$jj] + $cost)
		Next
	Next
	Return $d[$n][$m]
EndFunc   ;==>__Levenshtein
Func __Min($iNum1, $iNum2)
	Return (Number($iNum1) > Number($iNum2)) ? Number($iNum2) : Number($iNum1)
EndFunc   ;==>__Min