Ordenar una matriz por la "Distancia de Levenshtein" con el mejor rendimiento en Javascript

jquery sorting

Question

Así que tengo una matriz aleatoria de nombres de JavaScript ...

[@ larry, @ nicholas, @ notch] etc.

Todos comienzan con el símbolo @. Me gustaría ordenarlos por la distancia de Levenshtein para que los que están en la parte superior de la lista estén más cerca del término de búsqueda. Por el momento, tengo un javascript que usa .grep() jQuery en él usando el .match() javascript .match() alrededor del término de búsqueda ingresado al presionar la tecla:

(código editado desde la primera publicación)

limitArr = $.grep(imTheCallback, function(n){
    return n.match(searchy.toLowerCase())
});
modArr = limitArr.sort(levenshtein(searchy.toLowerCase(), 50))
if (modArr[0].substr(0, 1) == ''@'') {
    if (atRes.childred(''div'').length < 6) {
        modArr.forEach(function(i){
            atRes.append(''<div class="oneResult">'' + i + ''</div>'');
        });
    }
} else if (modArr[0].substr(0, 1) == ''#'') {
    if (tagRes.children(''div'').length < 6) {
        modArr.forEach(function(i){
            tagRes.append(''<div class="oneResult">'' + i + ''</div>'');
        });
    }
}

$(''.oneResult:first-child'').addClass(''active'');

$(''.oneResult'').click(function(){
    window.location.href = ''http://hashtag.ly/'' + $(this).html();
});

También tiene algunas sentencias if que detectan si la matriz contiene hashtags (#) o menciones (@). Ignora eso. El imTheCallback es la matriz de nombres, hashtags o menciones, luego modArr es la matriz ordenada. Luego los elementos .atResults y .tagResults son los elementos que anexa cada vez en la matriz, esto forma una lista de nombres basada en los términos de búsqueda ingresados.

También tengo el algoritmo de distancia de Levenshtein:

var levenshtein = function(min, split) {
    // Levenshtein Algorithm Revisited - WebReflection
    try {
        split = !("0")[0]
    } catch(i) {
        split = true
    };

    return function(a, b) {
        if (a == b)
            return 0;
        if (!a.length || !b.length)
            return b.length || a.length;
        if (split) {
            a = a.split("");
            b = b.split("")
        };
        var len1 = a.length + 1,
            len2 = b.length + 1,
            I = 0,
            i = 0,
            d = [[0]],
            c, j, J;
        while (++i < len2)
            d[0][i] = i;
        i = 0;
        while (++i < len1) {
            J = j = 0;
            c = a[I];
            d[i] = [i];
            while(++j < len2) {
                d[i][j] = min(d[I][j] + 1, d[i][J] + 1, d[I][J] + (c != b[J]));
                ++J;
            };
            ++I;
        };
        return d[len1 - 1][len2 - 1];
    }
}(Math.min, false);

¿Cómo puedo trabajar con algoritmo (o uno similar) en mi código actual para ordenarlo sin un mal rendimiento?

ACTUALIZAR:

Así que ahora estoy usando la función Lev Dist de James Westgate. Funciona WAYYYY rápido. Así que el rendimiento está resuelto, el problema ahora es usarlo con la fuente ...

modArr = limitArr.sort(function(a, b){
    levDist(a, searchy)
    levDist(b, searchy)
});

Mi problema ahora es la comprensión general sobre el uso del método .sort() . La ayuda es apreciada, gracias.

¡Gracias!

Answer 1

Acabo de escribir una nueva revisión: http://jsperf.com/levenshtein-algorithms/16

Esta revisión es más rápida que las otras. Funciona incluso en IE =)

Answer 2

Actualizado: http://jsperf.com/levenshtein-distance/5

La nueva Revisión aniquila todos los demás puntos de referencia. Estaba buscando específicamente el rendimiento de Chromium / Firefox ya que no tengo un entorno de prueba IE8 / 9/10, pero las optimizaciones realizadas deberían aplicarse en general a la mayoría de los navegadores.

Distancia Levenshtein

La matriz para realizar la distancia de Levenshtein se puede reutilizar una y otra vez. Este era un objetivo obvio para la optimización (pero tenga cuidado, esto ahora impone un límite en la longitud de la cadena (a menos que tuviera que cambiar el tamaño de la matriz de forma dinámica)).

La única opción para la optimización no perseguida en jsPerf Revisión 5 es la memorización. Dependiendo de su uso de Levenshtein Distance, esto podría ayudar drásticamente, pero se omitió debido a su naturaleza específica de implementación.

// Cache the matrix. Note this implementation is limited to
// strings of 64 char or less. This could be altered to update
// dynamically, or a larger value could be used.
var matrix = [];
for (var i = 0; i < 64; i++) {
    matrix[i] = [i];
    matrix[i].length = 64;
}
for (var i = 0; i < 64; i++) {
    matrix[0][i] = i;
}

// Functional implementation of Levenshtein Distance.
String.levenshteinDistance = function(__this, that, limit) {
    var thisLength = __this.length, thatLength = that.length;

    if (Math.abs(thisLength - thatLength) > (limit || 32)) return limit || 32;
    if (thisLength === 0) return thatLength;
    if (thatLength === 0) return thisLength;

    // Calculate matrix.
    var this_i, that_j, cost, min, t;
    for (i = 1; i <= thisLength; ++i) {
        this_i = __this[i-1];

        for (j = 1; j <= thatLength; ++j) {
            // Check the jagged ld total so far
            if (i === j && matrix[i][j] > 4) return thisLength;

            that_j = that[j-1];
            cost = (this_i === that_j) ? 0 : 1;  // Chars already match, no ++op to count.
            // Calculate the minimum (much faster than Math.min(...)).
            min    = matrix[i - 1][j    ] + 1;                      // Deletion.
            if ((t = matrix[i    ][j - 1] + 1   ) < min) min = t;   // Insertion.
            if ((t = matrix[i - 1][j - 1] + cost) < min) min = t;   // Substitution.

            matrix[i][j] = min; // Update matrix.
        }
    }

    return matrix[thisLength][thatLength];
};

Distancia Damerau-Levenshtein

jsperf.com/damerau-levenshtein-distance

Damerau-Levenshtein Distance es una pequeña modificación de la distancia de Levenshtein para incluir transposiciones. Hay muy poco para optimizar.

// Damerau transposition.
if (i > 1 && j > 1 && this_i === that[j-2] && this[i-2] === that_j
&& (t = matrix[i-2][j-2]+cost) < matrix[i][j]) matrix[i][j] = t;

Algoritmo de clasificación

La segunda parte de esta respuesta es elegir una función de clasificación apropiada. Subiré funciones de clasificación optimizadas a http://jsperf.com/sort pronto.

Answer 3

Definitivamente recomendaría usar un método mejor de Levenshtein como el que aparece en la respuesta de @James Westgate.

Dicho esto, las manipulaciones DOM a menudo son un gran gasto. Sin duda, puedes mejorar tu uso de jQuery.

Sus bucles son bastante pequeños en el ejemplo anterior, pero concatenar el html generado para cada oneResult en una sola cadena y hacer una append al final del bucle será mucho más eficiente.

Tus selectores son lentos $(''.oneResult'') buscará todos los elementos en el DOM y probará su className en navegadores IE más antiguos. Es posible que desee considerar algo como atRes.find(''.oneResult'') para determinar el alcance de la búsqueda.

En el caso de agregar los manejadores de click , es posible que deseemos evitar una configuración de manejadores en cada keyup . Puede aprovechar la delegación de eventos configurando un único controlador en atRest para todos los resultados en el mismo bloque en el que está configurando el controlador de keyup :

atRest.on(''click'', ''.oneResult'', function(){
  window.location.href = ''http://hashtag.ly/'' + $(this).html();
});

Ver http://api.jquery.com/on/ para más información.

Answer 4

Hace algunos años, escribí un corrector ortográfico en línea e implementé un algoritmo de Levenshtein, ya que estaba en línea y para IE8 hice bastante optimización del rendimiento.

var levDist = function(s, t) {
    var d = []; //2d matrix

    // Step 1
    var n = s.length;
    var m = t.length;

    if (n == 0) return m;
    if (m == 0) return n;

    //Create an array of arrays in javascript (a descending loop is quicker)
    for (var i = n; i >= 0; i--) d[i] = [];

    // Step 2
    for (var i = n; i >= 0; i--) d[i][0] = i;
    for (var j = m; j >= 0; j--) d[0][j] = j;

    // Step 3
    for (var i = 1; i <= n; i++) {
        var s_i = s.charAt(i - 1);

        // Step 4
        for (var j = 1; j <= m; j++) {

            //Check the jagged ld total so far
            if (i == j && d[i][j] > 4) return n;

            var t_j = t.charAt(j - 1);
            var cost = (s_i == t_j) ? 0 : 1; // Step 5

            //Calculate the minimum
            var mi = d[i - 1][j] + 1;
            var b = d[i][j - 1] + 1;
            var c = d[i - 1][j - 1] + cost;

            if (b < mi) mi = b;
            if (c < mi) mi = c;

            d[i][j] = mi; // Step 6

            //Damerau transposition
            if (i > 1 && j > 1 && s_i == t.charAt(j - 2) && s.charAt(i - 2) == t_j) {
                d[i][j] = Math.min(d[i][j], d[i - 2][j - 2] + cost);
            }
        }
    }

    // Step 7
    return d[n][m];
}

Answer 5

Implementé una implementación muy eficiente de cálculo de distancia levenshtein si aún necesita esto.

function levenshtein(s, t) {
    if (s === t) {
        return 0;
    }
    var n = s.length, m = t.length;
    if (n === 0 || m === 0) {
        return n + m;
    }
    var x = 0, y, a, b, c, d, g, h, k;
    var p = new Array(n);
    for (y = 0; y < n;) {
        p[y] = ++y;
    }

    for (; (x + 3) < m; x += 4) {
        var e1 = t.charCodeAt(x);
        var e2 = t.charCodeAt(x + 1);
        var e3 = t.charCodeAt(x + 2);
        var e4 = t.charCodeAt(x + 3);
        c = x;
        b = x + 1;
        d = x + 2;
        g = x + 3;
        h = x + 4;
        for (y = 0; y < n; y++) {
            k = s.charCodeAt(y);
            a = p[y];
            if (a < c || b < c) {
                c = (a > b ? b + 1 : a + 1);
            }
            else {
                if (e1 !== k) {
                    c++;
                }
            }

            if (c < b || d < b) {
                b = (c > d ? d + 1 : c + 1);
            }
            else {
                if (e2 !== k) {
                    b++;
                }
            }

            if (b < d || g < d) {
                d = (b > g ? g + 1 : b + 1);
            }
            else {
                if (e3 !== k) {
                    d++;
                }
            }

            if (d < g || h < g) {
                g = (d > h ? h + 1 : d + 1);
            }
            else {
                if (e4 !== k) {
                    g++;
                }
            }
            p[y] = h = g;
            g = d;
            d = b;
            b = c;
            c = a;
        }
    }

    for (; x < m;) {
        var e = t.charCodeAt(x);
        c = x;
        d = ++x;
        for (y = 0; y < n; y++) {
            a = p[y];
            if (a < c || d < c) {
                d = (a > d ? d + 1 : a + 1);
            }
            else {
                if (e !== s.charCodeAt(y)) {
                    d = c + 1;
                }
                else {
                    d = c;
                }
            }
            p[y] = d;
            c = a;
        }
        h = d;
    }

    return h;
}

Fue mi respuesta a una pregunta SO similar. La implementación más rápida de Levenshtein Javascript.

Actualizar

Una versión mejorada de lo anterior está ahora en github / npm, consulte https://github.com/gustf/js-levenshtein

Answer 6

La forma más obvia de hacerlo es asignar cada cuerda a un par (distancia, cuerda), luego ordenar esta lista y luego volver a soltar las distancias. De esta manera usted asegura que la distancia de levenstein solo tiene que ser calculada una vez. Quizás combine los duplicados primero también.

Answer 7

Llegué a esta solución:

var levenshtein = (function() {
        var row2 = [];
        return function(s1, s2) {
            if (s1 === s2) {
                return 0;
            } else {
                var s1_len = s1.length, s2_len = s2.length;
                if (s1_len && s2_len) {
                    var i1 = 0, i2 = 0, a, b, c, c2, row = row2;
                    while (i1 < s1_len)
                        row[i1] = ++i1;
                    while (i2 < s2_len) {
                        c2 = s2.charCodeAt(i2);
                        a = i2;
                        ++i2;
                        b = i2;
                        for (i1 = 0; i1 < s1_len; ++i1) {
                            c = a + (s1.charCodeAt(i1) === c2 ? 0 : 1);
                            a = row[i1];
                            b = b < a ? (b < c ? b + 1 : c) : (a < c ? a + 1 : c);
                            row[i1] = b;
                        }
                    }
                    return b;
                } else {
                    return s1_len + s2_len;
                }
            }
        };
})();

Ver también http://jsperf.com/levenshtein-distance/12

La mayor velocidad se obtuvo al eliminar algunos usos del conjunto.