52

だから私は名前のランダムなJavaScript配列を持っています...

[@larry、@nicholas、@notch] など。

それらはすべて @ 記号で始まります。リストの一番上にあるものが検索語に最も近いように、レーベンシュタイン距離でそれらを並べ替えたいと思います。現時点では、キーを押して入力された検索語の周りに.grep()javascriptメソッドを使用して、 jQueryを使用するjavascriptがあります。.match()

(最初の公開以降に編集されたコード)

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

また、配列にハッシュタグ (#) またはメンション (@) が含まれているかどうかを検出する if ステートメントもいくつかあります。それは無視してください。はimTheCallback、ハッシュタグまたはメンションのいずれかの名前の配列でありmodArr、並べ替えられた配列です。次に、要素.atResultsと.tagResults要素は、配列内で毎回追加される要素です。これは、入力された検索語に基づいて名前のリストを形成します。

レーベンシュタイン距離アルゴリズムもあります。

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

現在のコードにアルゴリズム (または類似のもの) を使用して、パフォーマンスを低下させずに並べ替えるにはどうすればよいですか?

アップデート：

そこで、James Westgate の Lev Dist 関数を使用しています。WAYYYYY 高速で動作します。パフォーマンスが解決されたため、問題はソースで使用しています...

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

私の問題は、.sort()メソッドの使用に関する一般的な理解です。助けていただければ幸いです。

ありがとう！

4

7 に答える 7

111

私は数年前にインライン スペル チェッカーを書き、レーベンシュタイン アルゴリズムを実装しました。 

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];
}
于 2012-08-14T18:28:39.970 に答える
6

更新: http://jsperf.com/levenshtein-distance/5

新しいリビジョンは、他のすべてのベンチマークを全滅させます。IE8/9/10 テスト環境を持っていないので、特に Chromium/Firefox のパフォーマンスを追跡していましたが、行われた最適化は一般にほとんどのブラウザーに適用されるはずです。

レーベンシュタイン距離

レーベンシュタイン距離を実行するための行列は、何度でも再利用できます。これは明らかに最適化の対象でした (ただし、これにより文字列の長さに制限が課されることに注意してください (行列のサイズを動的に変更しない限り))。

jsPerf リビジョン 5 で追求されていない最適化の唯一のオプションはメモ化です。レーベンシュタイン距離の使用方法によっては、これは大幅に役立つ可能性がありますが、実装固有の性質のために省略されました。

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

Damerau-Levenshtein Distance は、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;

ソートアルゴリズム

この回答の 2 番目の部分は、適切な並べ替え関数を選択することです。最適化されたソート機能をhttp://jsperf.com/sortにアップロードします。

于 2013-02-21T20:49:54.647 に答える
2

@James Westgateの回答にあるような、より優れたレーベンシュタイン法を使用することをお勧めします。

とはいえ、DOM の操作は多くの場合、多額の費用がかかります。jQuery の使用を確実に改善できます。

上記の例では、ループはかなり小さいですが、それぞれに対して生成されoneResultた html を単一の文字列に連結しappend、ループの最後で 1 つを実行すると、はるかに効率的になります。

あなたのセレクターは遅いです。DOM 内のすべての$('.oneResult')要素を検索し、古い IE ブラウザーでテストします。検索の範囲を設定するなどの検討が必要になる場合があります。classNameatRes.find('.oneResult')

ハンドラーを追加する場合、clickすべての にハンドラーを設定しないようにする方がよい場合がありますkeyup。atRestハンドラーを設定している同じブロック内のすべての結果に対して単一のハンドラーを設定することにより、イベント委任を活用できますkeyup。

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

詳細については、 http://api.jquery.com/on/を参照してください。

于 2012-08-18T05:37:08.553 に答える
2

これを行う明白な方法は、各文字列を (距離、文字列) ペアにマップし、このリストを並べ替えてから、距離を再度削除することです。このようにして、レーベンスタイン距離を 1 回だけ計算する必要があることを保証します。たぶん、重複も最初にマージします。

于 2012-08-16T14:28:45.270 に答える
1

新しいリビジョンを書きました: 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でも動作します=）

于 2013-07-31T13:41:40.960 に答える