optimization - 优化 Levenshtein 距离算法

Question

我有一个存储过程，它使用 Levenshtein 距离来确定最接近用户键入内容的结果。唯一真正影响速度的是在选择距离最短的记录之前计算所有记录的 Levenshtein 距离的函数(我通过用 0 代替对 Levenshtein 函数的调用来验证这一点)。该表有 150 万条记录，因此即使是最细微的调整也可能会缩短几秒钟的时间。现在整个过程运行超过 10 分钟。这是我正在使用的方法:

ALTER function dbo.Levenshtein
( 
    @Source nvarchar(200), 
    @Target nvarchar(200) 
) 
RETURNS int
AS
BEGIN
DECLARE @Source_len int, @Target_len int, @i int, @j int, @Source_char nchar, @Dist int, @Dist_temp int, @Distv0 varbinary(8000), @Distv1 varbinary(8000)

SELECT @Source_len = LEN(@Source), @Target_len = LEN(@Target), @Distv1 = 0x0000, @j = 1, @i = 1, @Dist = 0

WHILE @j <= @Target_len
BEGIN
    SELECT @Distv1 = @Distv1 + CAST(@j AS binary(2)), @j = @j + 1
END

WHILE @i <= @Source_len
BEGIN
    SELECT @Source_char = SUBSTRING(@Source, @i, 1), @Dist = @i, @Distv0 = CAST(@i AS binary(2)), @j = 1

WHILE @j <= @Target_len
BEGIN
    SET @Dist = @Dist + 1
    SET @Dist_temp = CAST(SUBSTRING(@Distv1, @j+@j-1, 2) AS int) +
                  CASE WHEN @Source_char = SUBSTRING(@Target, @j, 1) THEN 0 ELSE 1 END

    IF @Dist > @Dist_temp
    BEGIN
        SET @Dist = @Dist_temp
    END

    SET @Dist_temp = CAST(SUBSTRING(@Distv1, @j+@j+1, 2) AS int)+1

    IF @Dist > @Dist_temp SET @Dist = @Dist_temp
    BEGIN
        SELECT @Distv0 = @Distv0 + CAST(@Dist AS binary(2)), @j = @j + 1
    END
END

SELECT @Distv1 = @Distv0, @i = @i + 1
END

RETURN @Dist
END

我应该从这里去哪里？

Answer 1

我过去这样做的方法是将“数据库”(实际上是拼写校正器的单词字典)存储为一个特里树。

然后我使用分支定界例程来查找最近的匹配条目。对于小距离，它所花费的时间是距离的指数。对于大距离，它与字典的大小成线性关系，就像您现在看到的那样。

分支定界基本上是 trie 的深度优先树遍历，但有错误预算。在每个节点，您跟踪当前的 le​​venshtein 距离，如果它超出预算，您将修剪树的那个分支。

首先，您以零预算进行步行。那只会找到完全匹配的。如果您没有找到匹配项，那么您将以一个预算进行匹配。这将在距离为 1 处找到匹配项。如果找不到任何匹配项，则预算为 2，依此类推。这听起来效率低下，但由于每次步行比前一次步行花费的时间多得多，所以时间主要由您最后一次步行完成。

添加:代码大纲(请原谅我的 C):

// dumb version of trie node, indexed by letter. You can improve.
typedef struct tnodeTag {
  tnodeTag* p[128];
} tnode;

tnode* top; // the top of the trie

void walk(tnode* p, char* s, int budget){
  int i;
  if (*s == 0){
    if (p == NULL){
      // print the current trie path
    }
  }
  else if (budget >= 0){
    // try deleting this letter
    walk(p, s+1, budget-1);
    // try swapping two adjacent letters
    if (s[1]){
      swap(s[0], s[1]);
      walk(p, s, budget-1);
      swap(s[0], s[1]);
    }
    if (p){
      for (i = 0; i < 128; i++){
        // try exact match
        if (i == *s) walk(p->p[i], s+1, budget);
        // try replacing this character
        if (i != *s) walk(p->p[i], s+1, budget-1);
        // try inserting this letter
        walk(p->p[i], s, budget-1);
      }
    }
  }
}

基本上，您通过跳过字母并在同一节点搜索来模拟删除字母。您模拟通过下降 trie 而不前进 s 来插入字母。您模拟替换一个字母，就像字母匹配一样，即使它不匹配。当您掌握了它的窍门后，您可以添加其他可能的不匹配项，例如将 0 替换为 O，将 1 替换为 L 或 I - 诸如此类的愚蠢内容。

您可能想要添加一个字符数组参数来表示您在 trie 中找到的当前单词。