Сортируйте массив по "расстоянию Левенштейна" с лучшей производительностью в Javascript

Ответ 1

Несколько лет назад я написал встроенную проверку орфографии и реализовал алгоритм Левенштейна - поскольку он был встроенным, а для IE8 я сделал довольно много оптимизации производительности.

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

Ответ 2

Я пришел к этому решению:

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

См. также http://jsperf.com/levenshtein-distance/12

Большая скорость была достигнута за счет устранения некоторых применений массивов.

Ответ 3

Обновлено: http://jsperf.com/levenshtein-distance/5

Новая редакция аннулирует все другие тесты. Я специально преследовал производительность Chromium/Firefox, так как у меня нет тестовой среды IE8/9/10, но сделанные оптимизации должны применяться в целом к ​​большинству браузеров.

Расстояние Левенштейна

Матрица для выполнения Левенштейна Расстояние может быть повторно использована снова и снова. Это была очевидная цель для оптимизации (но будьте осторожны, теперь это накладывает ограничение на длину строки (если вы не изменяете размер матрицы динамически)).

Единственный вариант оптимизации, не преследуемый в редакции jsPerf 5, - это memoisation. В зависимости от вашего использования расстояния Левенштейна это может решительно помочь, но было исключено из-за специфики его реализации.

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

Расстояние Дамерау-Левенштейна

jsperf.com/damerau-levenshtein-distance

Дамеру-Левенштейн Расстояние - небольшая модификация Левенштейна. Расстояние до включения транспозиций. Оптимизировать очень мало.

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

Алгоритм сортировки

Вторая часть этого ответа - выбрать подходящую функцию сортировки. Я скоро загружу оптимизированные функции сортировки в http://jsperf.com/sort.

Ответ 4

Я выполнил очень эффективную реализацию расчета расстояния Левенштейна, если вам все еще нужно.

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

Это был мой ответ на аналогичный вопрос SO Самая быстрая реализация Javascript для Leventhtein общего назначения

Обновление

Улучшенная версия выше теперь находится на github/npm, см. https://github.com/gustf/js-levenshtein

Ответ 5

Очевидный способ сделать это - сопоставить каждую строку с парой (расстояние, строка), затем отсортировать этот список, а затем снова отбросить расстояния. Таким образом, вы гарантируете, что расстояние в левенштайне должно быть рассчитано только один раз. Возможно, сначала слияние дубликатов.

Ответ 6

Я бы определенно предложил использовать лучший метод Левенштейна, подобный тому, который был в ответе @James Westgate.

Тем не менее, манипуляции с DOM часто являются большими расходами. Вы, безусловно, можете улучшить использование jQuery.

В приведенном выше примере ваши петли довольно малы, но конкатенация сгенерированного html для каждого oneResult в одну строку и выполнение одного append в конце цикла будет намного более эффективным.

Ваши селекторы работают медленно. $('.oneResult') будет искать все элементы в DOM и протестировать их className в старых браузерах IE. Вы можете рассмотреть что-то вроде atRes.find('.oneResult') для охвата поиска.

В случае добавления обработчиков click мы можем попытаться лучше избегать установки обработчиков на каждом keyup. Вы можете использовать делегирование событий, установив один обработчик на atRest для всех результатов в том же блоке, который вы устанавливаете обработчик keyup:

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

Подробнее см. http://api.jquery.com/on/.

Ответ 7

Я только что написал новую редакцию: http://jsperf.com/levenshtein-algorithms/16

function levenshtein(a, b) {
  if (a === b) return 0;

  var aLen = a.length;
  var bLen = b.length;

  if (0 === aLen) return bLen;
  if (0 === bLen) return aLen;

  var len = aLen + 1;
  var v0 = new Array(len);
  var v1 = new Array(len);

  var i = 0;
  var j = 0;
  var c2, min, tmp;

  while (i < len) v0[i] = i++;

  while (j < bLen) {
    c2 = b.charAt(j++);
    v1[0] = j;
    i = 0;

    while (i < aLen) {
      min = v0[i] - (a.charAt(i) === c2 ? 1 : 0);
      if (v1[i] < min) min = v1[i];
      if (v0[++i] < min) min = v0[i];
      v1[i] = min + 1;
    }

    tmp = v0;
    v0 = v1;
    v1 = tmp;
  }
  return v0[aLen];
}

Эта редакция быстрее, чем другие. Работает даже на IE =)