Trier un tableau par la "Distance de Levenshtein" avec les meilleures performances en Javascript

Question

Donc, j'ai un hasard javascript tableau de noms...

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

Ils commencent tous par le symbole@. Je tiens à les trier par la Distance de Levenshtein, de sorte que les ceux du haut de la liste sont les plus proches du terme de recherche. Pour le moment, j'ai un peu de javascript qui utilise jQuery .grep() sur l'aide de javascript .match() méthode autour de l'entrée terme de recherche sur la touche:

(code modifié 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 a aussi quelques si les déclarations de détecter si le tableau contient des hashtags (#) ou des mentions (@). Ignorez-le. L' imTheCallback , est le tableau des noms, soit des hashtags ou des mentions, alors modArr , est le tableau trié. Puis l' .atResults et .tagResults - éléments sont des éléments qu'il ajoute à chaque fois dans le tableau, ce qui constitue une liste de noms basé sur les termes de recherche entrés.

J'ai également avoir l'algorithme 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 algorithme (ou un similaire) dans mon code actuel, de sorte sans mauvaise performance?

Mise à JOUR:

Donc, je suis maintenant à l'aide de James Westgate Lev Dist fonction. Œuvres WAYYYY rapide. Si la performance est résolu, le problème est maintenant de l'utiliser avec une source...

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

Mon problème est maintenant une compréhension générale sur l'utilisation de l' .sort() méthode. L'aide est apprécié, merci.

Merci!

Answer 1

J'ai écrit un correcteur orthographique en ligne il y a quelques années et mis en œuvre un algorithme de Levenshtein. Comme il était en ligne et pour IE8, j'ai beaucoup optimisé les performances.

 //http://www.merriampark.com/ld.htm, http://www.mgilleland.com/ld/ldjavascript.htm, Damerau–Levenshtein distance (Wikipedia)
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 2

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

L'élimination de certaines utilisations de tableaux a permis de gagner beaucoup de rapidité.

Answer 3

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

La nouvelle Révision annihile tous les autres points de référence. Particulier, j'ai été chasser de Chrome/Firefox performance que je n'ai pas de IE8/9/10 environnement de test, mais les optimisations doivent s'appliquer en général à la plupart des navigateurs.

Levenshtein

La matrice pour effectuer la Distance de Levenshtein peuvent être réutilisés encore et encore. Cela a été une cible évidente pour l'optimisation (mais attention, ceci impose une limite sur la longueur de la chaîne (sauf si vous avez été à redimensionner la matrice dynamiquement)).

La seule option pour l'optimisation de la pas poursuivis en jsPerf Révision 5 est memoisation. En fonction de votre utilisation de Levenshtein, ce qui pourrait aider considérablement, mais a été omis en raison de sa mise en œuvre spécifique de la nature.

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

jsperf.com/damerau-levenshtein-distance

Distance de damerau-Levenshtein est une petite modification à Distance de Levenshtein pour inclure des transpositions. Il est très peu pour 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 optimisé fonctions de tri à http://jsperf.com/sort bientôt.

Answer 4

Je serais certainement vous suggérons d'utiliser un mieux Levenshtein méthode comme celle de @James Westgate la réponse.

Cela dit, les manipulations DOM sont souvent à grands frais. Vous pouvez certainement améliorer votre jQuery utilisation.

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

Votre sélecteurs sont lents. $('.oneResult') recherche tous les éléments dans le DOM et de tester leur className dans les anciens navigateurs IE. Vous souhaitez peut-être envisager quelque chose comme atRes.find('.oneResult') de l'étendue de la recherche.

Dans le cas de l'ajout de l' click des gestionnaires, nous voulons faire mieux éviter de définir des gestionnaires sur chaque keyup. Vous pourriez tirer parti de l'événement délégation par la fixation d'un seul conducteur, sur atRest pour tous les résultats dans le même bloc de réglage de l' keyup gestionnaire de:

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

Voir http://api.jquery.com/on/ pour plus d'info.

Answer 5

La méthode la plus simple consiste à mapper chaque chaîne sur une paire (distance, chaîne), puis à trier cette liste, puis à supprimer les distances. De cette façon, vous vous assurez que la distance de Levenstein ne doit être calculée qu'une seule fois. Peut-être aussi fusionner les doublons en premier.