Ordenar uma matriz pela “Distância Levenshtein” com melhor desempenho em JavaScript

Então eu tenho uma matriz aleatória de nomes de javascript

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

Todos começam com o símbolo @. Eu gostaria de classificá-los pela Distância Levenshtein para que os que estão no topo da lista estejam mais próximos do termo de pesquisa. No momento, eu tenho algum javascript que usa o .grep() do jQuery nele usando o método .match() javascript ao redor do termo de pesquisa typescript ao pressionar a tecla:

(código editado desde a primeira publicação)

 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('
' + i + '
'); }); } } else if (modArr[0].substr(0, 1) == '#') { if (tagRes.children('div').length < 6) { modArr.forEach(function(i){ tagRes.append('
' + i + '
'); }); } } $('.oneResult:first-child').addClass('active'); $('.oneResult').click(function(){ window.location.href = 'http://hashtag.ly/' + $(this).html(); });

Ele também tem algumas instruções if detectando se a matriz contém hashtags (#) ou menções (@). Ignore isso. O imTheCallback é o array de nomes, seja hashtags ou menções, então modArr é o array ordenado. Em seguida, os elementos .tagResults e .tagResults são os elementos que ele acrescenta a cada vez na matriz, isso forma uma lista de nomes com base nos termos de pesquisa inseridos.

Eu também tenho o algoritmo de Distância 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); 

Como posso trabalhar com algoritmo (ou semelhante) no meu código atual para classificá-lo sem um desempenho ruim?

ATUALIZAR:

Então agora estou usando a function Lev Dist de James Westgate. Trabalha WAYYYY rápido. Então, o desempenho está resolvido, o problema agora é usá-lo com a fonte …

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

Meu problema agora é o entendimento geral sobre o uso do método .sort() . Ajuda é apreciada, obrigado.

Obrigado!

Eu escrevi um verificador ortográfico em linha alguns anos atrás e implementei um algoritmo Levenshtein – já que ele estava em linha e para o IE8 eu fiz bastante otimização de desempenho.

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

Eu cheguei a esta solução:

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

Veja também http://jsperf.com/levenshtein-distance/12

A maior velocidade foi obtida pela eliminação de alguns usos de array.

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

A nova revisão aniquila todos os outros benchmarks. Eu estava perseguindo especificamente o desempenho do Chromium / Firefox, pois não tenho um ambiente de teste do IE8 / 9/10, mas as otimizações feitas devem se aplicar em geral à maioria dos navegadores.

Distância Levenshtein

A matriz para executar a Distância de Levenshtein pode ser reutilizada de novo e de novo. Esse era um alvo óbvio para otimização (mas tenha cuidado, isso agora impõe um limite no tamanho da string (a menos que você redimensione a matriz dinamicamente)).

A única opção para otimização não perseguida no jsPerf Revision 5 é a memoisação. Dependendo do seu uso da Distância de Levenshtein, isso poderia ajudar drasticamente, mas foi omitido devido à sua natureza específica de implementação.

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

Distância Damerau-Levenshtein

jsperf.com/damerau-levenshtein-distance

A distância de Damerau-Levenshtein é uma modificação pequena à distância de Levenshtein para include transposições. Há muito pouco para otimizar.

 // 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 Ordenação

A segunda parte desta resposta é escolher uma function de sorting apropriada. Carregarei funções de sorting otimizadas para http://jsperf.com/sort em breve.

Eu definitivamente sugeriria usar um método melhor de Levenshtein como o da resposta do @James Westgate.

Dito isto, as manipulações de DOM são geralmente uma grande despesa. Você certamente pode melhorar seu uso do jQuery.

Seus loops são bem pequenos no exemplo acima, mas concatenar o html gerado para cada oneResult em uma única string e fazer um append no final do loop será muito mais eficiente.

Seus seletores são lentos. $('.oneResult') pesquisará todos os elementos no DOM e testará seu className em navegadores antigos do IE. Você pode querer considerar algo como atRes.find('.oneResult') para escopo da pesquisa.

No caso de adicionar os manipuladores de click , talvez seja melhor evitar manipuladores de configuração em todas as keyup . Você poderia aproveitar a delegação de events definindo um único manipulador em atRest para todos os resultados no mesmo bloco em que você está configurando o manipulador de keyup :

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

Veja http://api.jquery.com/on/ para mais informações.

A maneira óbvia de fazer isso é mapear cada string para um par (distância, string), depois classificar essa lista e, em seguida, soltar as distâncias novamente. Desta forma, você garante que a distância de leveza só tenha que ser calculada uma vez. Talvez mescle as duplicatas primeiro também.

Eu implementei uma implementação muito eficiente de cálculo de distância de levenshtein se você ainda precisar disso.

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

Foi a minha resposta a uma pergunta semelhante SO Fastest finalidade geral Levenshtein implementação JavaScript

Atualizar

Uma versão melhorada do acima está agora no github / npm veja https://github.com/gustf/js-levenshtein

Acabei de escrever uma nova revisão: http://jsperf.com/levenshtein-algorithms/16

Esta revisão é mais rápida que as outras. Funciona mesmo no IE =)