在 Ionic 应用程序中加速 Levenshtein 距离计算

Question

我在做什么：我正在开发一款支持多种语言的移动词典应用程序
我是怎么做的：使用离子框架结合一些 angular 和一些纯 js（从相同语言的工作在线词典网站导入）
问题：我们的搜索功能是一种近似搜索，它使用 Levenstein 距离计算器根据查询形式对字典中的所有条目进行排名。当字典有多达 1,500 个单词时，这在手机上根本不是问题，但是当字典有大约 10,000 个单词时，在显示结果之前会有大约 5-8 秒的延迟，尽管它在网络上是即时的浏览器使用 "ionic serve"。当我运行 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

我正在自己处理 Levenstein 距离，但我没有找到提高性能的好方法，因此不建议在 non-batch 应用程序中使用它。

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

这些文章是一个不错的起点：

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。

Answer 2

首先，如果你有一本已知的字典，你会得到最快的解决方案，比如 Levenshtein Automata，这将在线性时间内解决这个问题，得到 all 考生。您无法通过通用实现来解决这个问题。

也就是说，这个编辑距离的实现比你的快几倍。

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

我也不会在getLeastEditDistance中使用map，它很慢。只需使用普通循环即可。另外 Math.min 参数很多，性能也不是很好。

在 Ionic 应用程序中加速 Levenshtein 距离计算

Speeding up Levenshtein distance calculation in Ionic app

javascript

performance

nlp

levenshtein-distance

ionic-framework