User:Pazako Karu/ComputeLevenshteinDistance

This ComputeLevenshteinDistance(source, target) function computes the number of steps required to transform one string into another. This can be used to compare how similar two strings are.

See: Wikipedia and Microsoft Technet for details on function and source of implementation.

Its not rocket surgery

Code

integer ComputeLevenshteinDistance(string source, string target)
{
    source = llToLower(source);
    target = llToLower(target);
    integer sourceWordCount = llStringLength(source);
    integer targetWordCount = llStringLength(target);
    if (source == target) return sourceWordCount;
   
    if (sourceWordCount == 0)
        return targetWordCount;
   
    if (targetWordCount == 0)
        return sourceWordCount;
   
    list distance;
    integer r; // Row
    integer c; // Column
    sourceWordCount++; // Array/Grid is 1 wider than count
    targetWordCount++; // Array/Grid is 1 wider than count
    for (r = 0; r < sourceWordCount*targetWordCount; r++)// Generate faux 2d array
    {
        if (r < sourceWordCount)
            distance += [r];
        else if (r % sourceWordCount==0)
            distance += [r/sourceWordCount];
        else distance += [0];
    }
    for (r = 1; r < sourceWordCount; r++)
    {
        for (c = 1; c < targetWordCount; c++)
        {
            integer cost = !(llGetSubString(source, r-1, r-1) == llGetSubString(target, c-1, c-1));
            integer coord = r+c*sourceWordCount; // row + col*stride
            
            integer L = 1+llList2Integer(distance,coord-1); // Left
            integer U = 1+llList2Integer(distance,coord-sourceWordCount); // Up
            integer D =  cost+llList2Integer(distance,coord-sourceWordCount-1); // Diagonal
            
            integer min;
            if (L <= U)
                min = L;
            else min = U;
            if (min >= D)
                min = D;
            distance = llListReplaceList(distance, [min], coord, coord);
        }
    }
    return llList2Integer(distance, -1); // Last value in array is Lev dist
}
default
{
    state_entry()
    {
        llOwnerSay((string)ComputeLevenshteinDistance("kitten", "sitting")); // 3
        llOwnerSay((string)ComputeLevenshteinDistance("Saturday", "Sunday")); // 3
    }
}

License

You may use, abuse, and distribute this object in any way, other than simply repacking for sale. You may include this object as part of a sellable object in any form, including full permission. This was made with no promise of readability or assistance with modification.