(MDLD)修改的Damerau-Levenshtein距离算法的Javascript版本

我想测试MDLD的性能,以便将一些浏览器内字符串比较集成到web应用程序中。该用例涉及到比较字符串,如“300mm,Packed Wall”和“Packed Wall-300mm”,因此我正在寻找模糊字符串匹配,它对标点和拼写有一定的容忍度,并允许块字符转换。

我无法在线找到Javascript的实现。我发现为PL/SQL编写的版本可以在 CSIRO's Taxamatch Wiki 。

这是我尝试将代码转换为JS;基本函数的结果似乎相当准确,但块转置计算并没有给出预期的结果。E、 g.“Hi-There”vs“There-Hi”返回“6”,无论块限制设置为什么。

如果有人知道一个有效的实现,你能给我指一下吗?或者,我的改编或源代码本身有什么问题?我所做的唯一主要更改是在两个示例中使用“Math.ceil()”,其中源代码似乎使用整数除法,这总是占主导地位--这会导致输入出现奇怪的问题,导致出现1个字符串--但似乎不会影响我测试过的其他案例的行为。

function mdld(str1, str2, block_lim)
{
    mycol = [];
    cost = 0;
    len1 = str1.length;
    len2 = str2.length;

    if( str1 === str2 )
        return 0;
    else if ( len1 === 0 || len2 === 0 )
        return Math.max(len1, len2);
    else if ( len1 === 1 && len2 === 1 && str1 !== str2 )
        return 1;
    else
    {
        // Temporary strings which will be pre-processed
        // Speeds up calcs & retains correct measurement
        temp1 = str1;
        temp2 = str2;

        // Trim any common initial characters
        while ( temp1.substr(0,1) === temp2.substr(0,1) )
        {
            temp1 = temp1.substr(1, temp1.length);
            temp2 = temp2.substr(1, temp2.length);
        }

        // Trim any trailing characters
        while ( temp1.substr(-1,1) === temp2.substr(-1,1) )
        {
            temp1 = temp1.substr(0,temp1.length-1);
            temp2 = temp2.substr(0,temp2.length-1);
        }

        len1 = temp1.length;
        len2 = temp2.length;

        // Calc Levenshtein Distance
        if (len1 === 0 || len2 === 0)
            return Math.max(len1, len2);
        else if (len1 === 1 && len2 === 1 && str1 !== str2)
            return 1;
        else
        {
            // Create columns
            var s, t;
            for(s = 0; s <= len1; s++)
                mycol[s] = [];

            // Enter values into leftmost column
            for(t = 0; t <= len2; t++)
                mycol[0][t] = t;

            // Populate remaining columns
            for(s = 1; s <= len1; s++)
            {
                mycol[s][0] = s;
                // Populate first row (each cell of one column)
                for(t = 1; t <= len2; t++)
                {
                    //Calculate cost
                    if (temp1.substr(s-1,1) === temp2.substr(t-1,1))
                        cost = 0;
                    else
                        cost = 1;

                    // extension to cover multiple character transpositions
                    // that includes calculation of original Levenshtein distance when no transposition 
                    tempBlockLen = Math.min( Math.ceil(len1/2), Math.ceil(len2/2), !block_lim ? 1 : block_lim );

                    while (tempBlockLen >= 1)
                    {
                        if ((s >= tempBlockLen * 2) && 
                            (t >= tempBlockLen * 2) &&
                            (temp1.substr(s-tempBlockLen*2, tempBlockLen) === temp2.substr(t-tempBlockLen, tempBlockLen)) &&
                            (temp1.substr(s-tempBlockLen, tempBlockLen) === temp2.substr(t-tempBlockLen*2, tempBlockLen)))
                        {
                            // Transposition found
                            mycol[s][t] = Math.min( mycol[s][t-1] + 1,
                                                    mycol[s-1][t] + 1,
                                                    mycol[s-tempBlockLen*2][t-tempBlockLen*2] + cost + tempBlockLen - 1 );
                            tempBlockLen = 0;
                        }
                        else if (tempBlockLen === 1)
                        {
                            // No Transposition
                            mycol[s][t] = Math.min( mycol[s][t-1] + 1,
                                                    mycol[s-1][t] + 1,
                                                    mycol[s-1][t-1] + cost );
                        }
                        tempBlockLen = tempBlockLen - 1;    
                    }
                }
            }
        }
        return mycol[len1][len2];
    }
}