AutoHotkey Community

Code: Select all

/*
Levenshtein Distance
Source Wikipedia.com
https://en.wikipedia.org/wiki/Levenshtein_distance
Originally written in C translated into AutoHotkey
*/

LDistance(s, t)
{ 
    ; degenerate cases
    if (StrLen( s ) = 0) 
		return StrLen( t )
	if ( StrLen( t ) = 0) 
		return StrLen( s )
	s := StrSplit( s )
	t := StrSplit( t )
    v0 := []
    Loop % t.Length() + 1
        v0[ A_Index ] := A_Index - 1
	v3 := [v0]
    Loop % s.Length()
    {
        ; calculate v1 (current row distances) from the previous row v0
		i := A_Index
		v1 := [i]
        ; use formula to fill in the rest of the row
        Loop % t.Length()
		{
			cost := !( s[ i ] == t[ A_Index ] )
			v1[ A_Index + 1 ] := _lMin( v1[ A_Index ] + 1
			, v0[ A_Index + 1 ] + 1
			, v0[ A_Index ] + cost )
		}
		v3.Push( v0 )
		v0 := v1
    }

    return v1[ t.Length() +1 ]
}

/*
Damerau-Levenshtein Distance
Source Wikipedia.com
https://en.wikipedia.org/wiki/Damerau%E2%80%93Levenshtein_distance
Originally written in Python translated into AutoHotkey
Thx to Helgef for correcting it.
*/

DLDistance( a, b )
{
    da := {}
    d := []
	a := StrSplit( a )
	b := StrSplit( b )
    maxdist := a.Length() + b.Length()
    d[-1, -1] := maxdist
    Loop % a.Length() + 1
	{
        i := A_Index - 1
		d[i, -1] := maxdist
        d[i, 0] := i
    }
	Loop % b.Length() + 1
	{
		j := A_Index - 1
		d[-1, j] := maxdist
        d[0, j] := j
	}
    Loop % a.Length()
	{
        db := 0
		i := A_Index
        Loop % b.Length()
		{
            j := A_Index
			k :=  da.HasKey(b[j]) ?  da[b[j]] : da[b[j]] := 0
            l := db
            if !( cost := !(a[i] == b[j]) )
				db := j
            d[i, j] := _lmin( d[i-1, j-1] + cost, d[i,   j-1] + 1, d[i-1, j  ] + 1, d[k-1, l-1] + (i-k-1) + 1 + (j-l-1 ) ) 
		}
        da[a[i]] := i
	}
    return d[a.Length(), b.Length()] ;I cant understand why but it always reports 1 more than it should. Since I'm a fan of easy solutions I just subtract 1 here
}

_lMin( p* )
{
	Ret := p.Pop()
	For each,Val in p
		if ( Val < Ret )
		{
			Ret := Val
		}
	return Ret
}

Code: Select all

Word := "tset"
WordList := "random,task,test,text,toast"
for each, Word in Sort(Score(Word,StrSplit(WordList,","),"D"))
   Result .= Word.score "-" Word.word "`n"
MsgBox % Substr(Result,1,-1)
ExitApp

Score(Word,WordArray,Func:="") {
   ScoredWords := []
   for Index, WordElement in WordArray
      ScoredWords.Push({word:WordElement, score:%Func%LDistance(Word,WordElement)})
   Return ScoredWords
}

Sort(ScoredWords) {
   for Index, Word in ScoredWords
      SortString .= Word.score " " Index "`n"
   SortString := SubStr(SortString,1,-1)
   Sort, SortString, N
   Indexes := []
   Loop, Parse, SortString, `n
   {  RegExMatch(A_LoopField, "O)(\d+) (\d+)", Match)
      Indexes[Match[1]] .= Match[2] "`n"
   }
   for Index in Indexes
   {  SortString := Substr(Indexes[Index],1,-1)
      Sort, SortString, N
      Indexes[Index] := SortString
   }
   SortedWords := []
   for Score, IndexList in Indexes
      for each, Index in StrSplit(IndexList,"`n")
         SortedWords.Push({word:ScoredWords[Index].word, score:Score})
   Return SortedWords
}

Code: Select all

2-test
2-text
3-task
3-toast
6-random

Code: Select all

1-test
2-text
3-task
3-toast
6-random

Code: Select all

for each, Word in Sort(Score(Word,StrSplit(WordList,","),""))

Code: Select all

for each, Word in Sort(Score(Word,StrSplit(WordList,","),"D"))

Code: Select all

DLDistance("test string","test string") ;returns 0
DLDistance("test string","Xest string") ;returns 0 too

Code: Select all

/*
algorithm DL-distance is
    input: strings a[1..length(a)], b[1..length(b)]
    output: distance, integer
    da := new array of |Σ| integers
    for i := 1 to |Σ| inclusive do
        da[i] := 0
    let d[−1..length(a), −1..length(b)] be a 2-d array of integers, dimensions length(a)+2, length(b)+2
    // note that d has indices starting at −1, while a, b and da are one-indexed.
    maxdist := length(a) + length(b)
    d[−1, −1] := maxdist
    for i := 0 to length(a) inclusive do
        d[i, −1] := maxdist
        d[i, 0] := i
    for j := 0 to length(b) inclusive do
        d[−1, j] := maxdist
        d[0, j] := j
    for i := 1 to length(a) inclusive do
        db := 0
        for j := 1 to length(b) inclusive do
            k := da[b[j]]
            ℓ := db
            if a[i] = b[j] then
                cost := 0
                db := j
            else
                cost := 1
            d[i, j] := minimum(d[i−1, j−1] + cost,  //substitution
                               d[i,   j−1] + 1,     //insertion
                               d[i−1, j  ] + 1,     //deletion
                               d[k−1, ℓ−1] + (i−k−1) + 1 + (j-ℓ−1)) //transposition
        da[a[i]] := i
    return d[length(a), length(b)]
*/

Code: Select all

msgbox % DLDistance("test string","test string") ;returns 0
msgbox % DLDistance("test string","Xest string") ;returns 1
msgbox % DLDistance("test string","XXst string")


DLDistance( a, b )
{
    da := {}
    d := []
	a := StrSplit( a )
	b := StrSplit( b )
    maxdist := a.Length() + b.Length()
    d[-1, -1] := maxdist
    Loop % a.Length() + 1
	{
        i := A_Index - 1
		d[i, -1] := maxdist
        d[i, 0] := i
    }
	Loop % b.Length() + 1
	{
		j := A_Index - 1
		d[-1, j] := maxdist
        d[0, j] := j
	}
    Loop % a.Length()
	{
        db := 0
		i := A_Index
        Loop % b.Length()
		{
            j := A_Index
			k :=  da.HasKey(b[j]) ?  da[b[j]] : da[b[j]] := 0
            l := db
            if !( cost := !(a[i] == b[j]) )
				db := j
            d[i, j] := _lmin( d[i-1, j-1] + cost, d[i,   j-1] + 1, d[i-1, j  ] + 1, d[k-1, l-1] + (i-k-1) + 1 + (j-l-1 ) ) 
		}
        da[a[i]] := i
	}
    return d[a.Length(), b.Length()] ;I cant understand why but it always reports 1 more than it should. Since I'm a fan of easy solutions I just subtract 1 here
}

_lMin( p* )
{
	Ret := p.Pop()
	For each,Val in p
		if ( Val < Ret )
		{
			Ret := Val
		}
	return Ret
}