在Ionic app中加快Levenshtein距离计算

Question

• 我正在做的事情:我正在为许多语言开发一个移动字典应用程序
• 我是如何做到这一点的:使用离子框架，结合一些角度和纯js (从相同语言的在线词典站点导入)
• 问题:我们的搜索函数是一个近似搜索，它使用Levenstein距离计算器对字典中有关查询表单的所有条目进行排序。当字典有多达1500个单词时，这在手机上一点问题都没有，但当字典有大约10000个单词时，结果显示前大约有5-8秒的延迟，尽管它在使用“离子服务”的网络浏览器上是即时的。当我运行firebug时，处理时间最长的javascript是距离计算，所以我的工作假设是这是我应该开始的地方，但我完全可以接受任何建议。

这是距离计算器：

/**
 * editDistance.js
 * 
 * A simple Levenshtein distance calculator, except weighted such
 * that insertions at the beginning and deletions at the end cost less.
 *
 * AUTHOR: Pat Littell
 * LAST UPDATED: 2015-05-16
 */

var distanceCalculator = {

insertionCost : 1.0,
deletionCost : 1.0,
insertionAtBeginningCost : 0.11,
deletionAtEndCost : 0.1,
substitutionCost : 1.0,

getEditDistance : function(a, b) {
  if(a.length === 0) return b.length; 
  if(b.length === 0) return a.length; 

  var matrix = [];
 // var currentInsertionCost, currentDeletionCost, currentSubstitutionCost = 0;

  // increment along the first column of each row
  var i;
  for(i = 0; i <= b.length; i++){
    matrix[i] = [i * this.insertionAtBeginningCost];
  }

  // increment each column in the first row
  var j;
  for(j = 0; j <= a.length; j++){
    matrix[0][j] = j;
  }

  // Fill in the rest of the matrix
  for(i = 1; i <= b.length; i++){
    for(j = 1; j <= a.length; j++){
        currentInsertionCost = matrix[i][j-1] + this.insertionCost;
        currentSubstitutionCost = matrix[i-1][j-1] + (b.charAt(i-1) != a.charAt(j-1) ? this.substitutionCost : 0);
        currentDeletionCost = matrix[i-1][j] + (j==a.length ? this.deletionAtEndCost : this.deletionCost);            
        matrix[i][j] = Math.min(currentSubstitutionCost, Math.min(currentInsertionCost, currentDeletionCost));

    }
  }

  return matrix[b.length][a.length];
},


// Given a query <a> and a series of targets <bs>, return the least distance to any target
getLeastEditDistance : function(a, bs) {
    var that = this;
    return Math.min.apply(null, bs.map(function(b) {
        return that.getEditDistance(a,b);
    }));
}
}

Answer 1

首先，如果您有一个已知的字典，您将得到最快的解决方案，比如一个Levenshtein自动机，它将在线性时间内解决这个问题，从而得到所有的候选项。您无法用通用的实现来克服这个问题。

尽管如此，levenshtein距离的实现速度是您的几倍。

function distance(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, py, a, b, c, d, e, f, k;

    var p = new Array(n);

    for (y = 0; y < n;) {
        p[y] = ++y;
    }

    for (; (x + 3) < m; x += 4) {
        var tx0 = t.charCodeAt(x);
        var tx1 = t.charCodeAt(x + 1);
        var tx2 = t.charCodeAt(x + 2);
        var tx3 = t.charCodeAt(x + 3);
        a = x;
        b = x + 1;
        c = x + 2;
        d = x + 3;
        e = x + 4;
        for (y = 0; y < n; y++) {
            k = s.charCodeAt(y);
            py = p[y];
            if (py < a || b < a) {
                a = (py > b ? b + 1 : py + 1);
            }
            else {
                if (tx0 !== k) {
                    a++;
                }
            }

            if (a < b || c < b) {
                b = (a > c ? c + 1 : a + 1);
            }
            else {
                if (tx1 !== k) {
                    b++;
                }
            }

            if (b < c || d < c) {
                c = (b > d ? d + 1 : b + 1);
            }
            else {
                if (tx2 !== k) {
                    c++;
                }
            }

            if (c < d || e < d) {
                d = (c > e ? e + 1 : c + 1);
            }
            else {
                if (tx3 !== k) {
                    d++;
                }
            }

            p[y] = e = d;
            d = c;
            c = b;
            b = a;
            a = py;
        }
    }

    for (; x < m;) {
        tx0 = t.charCodeAt(x);
        a = x;
        b = ++x;
        for (y = 0; y < n; y++) {
            py = p[y];
            if (py < a || b < a) {
                b = (py > b ? b + 1 : py + 1);
            }
            else {
                if (tx0 !== s.charCodeAt(y)) {
                    b = a + 1;
                }
                else {
                    b = a;
                }
            }
            p[y] = b;
            a = py;
        }
        f = b;
    }

    return f;
}

我也不会在map中使用getLeastEditDistance，它非常慢。用一个普通的循环。而且，具有许多参数的Math.min也不是很好的性能。

Answer 2

我自己正在使用Levenstein距离，我还没有找到一种提高性能的好方法，也不会建议在非批处理应用程序中使用它。

我建议您使用另一种方法，使用搜索树。二进制或三元搜索树也可以找到接近匹配。

一个很好的起点是这些文章：

http://www.codeproject.com/Articles/5819/Ternary-Search-Tree-Dictionary-in-C-Faster-String

或

http://www.codeproject.com/Articles/68500/Balanced-Binary-Search-Tree-BST-Search-Delete-InOr

代码是相对简单的sp，您不应该使用太多时间将它移植到JavaScript。