Trier un tableau par la "distance Levenshtein" avec la meilleure performance en Javascript

donc j'ai un tableau javascript aléatoire de noms...

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

Ils commencent tous par le symbole@. J'aimerais les Trier par la Distance de Levenshtein pour que ceux qui sont en haut de la liste soient les plus proches du terme recherché. Pour le moment, j'ai du javascript qui utilise le .grep() de jQuery avec la méthode javascript .match() autour du terme de recherche entré sur la touche press:

(code édité depuis la première publication)

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

il contient aussi des instructions if pour détecter si le tableau contient des hashtags (#) ou des mentions (@). Ignorez-le. Le imTheCallback , est le tableau des noms, soit des hashtags ou des mentions, puis modArr est le tableau trié. Ensuite ,les éléments .atResults et .tagResults sont les éléments qu'il ajoute à chaque fois dans le tableau, ce qui forme une liste de noms basés sur les termes de recherche entrés.

i aussi ont l'algorithme de distance 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);

Comment puis-je travailler avec un algorithme (ou un algorithme similaire) dans mon code actuel pour le trier sans mauvaises performances?

mise à jour:

donc j'utilise la fonction Lev Dist de James Westgate. Œuvres WAYYYY rapide. Donc la performance est résolue, le problème est maintenant de l'utiliser avec la source...

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

mon problème il est maintenant généralement entendu sur l'utilisation de la méthode .sort() . L'aide est apprécié, merci.

Merci!

42
demandé sur icedwater 2012-08-12 05:37:47

7 réponses

j'ai écrit un correcteur orthographique en ligne il y a quelques années et j'ai mis en œuvre un algorithme de Levenshtein - depuis qu'il était en ligne et pour IE8 j'ai fait pas mal d'optimisation des performances.

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];
}
95
répondu James Westgate 2016-07-15 03:15:00

je suis venu à cette solution:

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

Voir aussi http://jsperf.com/levenshtein-distance/12

la plupart de la vitesse a été gagnée en éliminant certaines utilisations des réseaux.

11
répondu Marco de Wit 2013-08-29 16:36:14

mise à jour: http://jsperf.com/levenshtein-distance/5

La nouvelle Révision annihile tous les autres points de référence. Je poursuivais spécifiquement les performances Chromium/Firefox car je n'ai pas D'environnement de test IE8/9/10, mais les optimisations faites devraient s'appliquer en général à la plupart des navigateurs.

Levenshtein

la matrice pour effectuer la Distance Levenshtein peut être réutilisée encore et encore. Ceci était un objectif évident pour l'optimisation (mais attention, cela impose maintenant une limite à la longueur de la chaîne (sauf si vous deviez redimensionner la matrice dynamiquement)).

la seule option d'optimisation non utilisée dans la révision 5 de jsPerf est la mémorisation. Selon votre utilisation de la Distance de Levenshtein, cela pourrait aider drastiquement, mais a été omis en raison de sa nature spécifique de mise en œuvre.

// 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];
};

Distance De Damerau-Levenshtein Distance

jsperf.com/damerau-levenshtein-distance

distance de damerau-Levenshtein est une petite modification à Distance de Levenshtein pour inclure des transpositions. Il y a très peu à optimiser.

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

Algorithme De Tri

La deuxième partie de cette réponse est de choisir une fonction de tri. Je vais télécharger des fonctions de tri optimisées vers http://jsperf.com/sort bientôt.

6
répondu TheSpanishInquisition 2013-02-21 23:58:31

je suggérerais certainement d'utiliser une meilleure méthode Levenshtein comme celle de la réponse de @James Westgate.

cela dit, les manipulations de DOM sont souvent une grande dépense. Vous pouvez certainement améliorer votre utilisation de jQuery.

vos boucles sont plutôt petites dans l'exemple ci-dessus, mais concaténer le html généré pour chaque oneResult en une seule chaîne et faire une append à la fin de la boucle sera beaucoup plus efficace.

vos sélecteurs sont lents. $('.oneResult') va rechercher tous éléments dans le DOM et de tester leur className dans les navigateurs plus anciens IE. Vous pourriez vouloir considérer quelque chose comme atRes.find('.oneResult') pour couvrir la recherche.

dans le cas de l'ajout des handlers click , nous pourrions vouloir faire une meilleure éviter de mettre des handlers sur chaque keyup . Vous pouvez tirer parti de la délégation d'événement en mettant un gestionnaire unique sur atRest pour tous les résultats dans le même bloc vous définissez le keyup handler:

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

voir http://api.jquery.com/on / pour plus d'information.

3
répondu Jacob Swartwood 2012-08-18 05:37:08

j'ai implémenté une implémentation très performante du calcul de distance de levenshtein si vous en avez encore besoin.

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

c'était ma réponse à une question similaire

""

mise à Jour

une version améliorée de ce qui précède est maintenant sur github / npm voir https://github.com/gustf/js-levenshtein

3
répondu gustf 2017-05-26 19:38:31

la façon évidente de faire ceci est de mapper chaque chaîne à une paire (distance, chaîne), puis de trier cette liste, puis de laisser tomber les distances à nouveau. De cette façon, vous vous assurez que la distance de levenstein ne doit être calculée qu'une seule fois. Peut-être fusionner les doublons d'abord.

2
répondu Anony-Mousse 2012-08-16 14:28:45

je viens d'écrire une nouvelle révision: http://jsperf.com/levenshtein-algorithms/16

Cette révision est plus rapide que les autres. Fonctionne même sur IE=)

1
répondu gtournie 2013-07-31 13:41:40