优化Levenshtein距离算法

Question

优化Levenshtein距离算法

optimizationlevenshtein-distanceedit-distance

3

我有一个存储过程，它使用Levenshtein距离来确定与用户输入最接近的结果。影响速度的唯一因素是在选择距离最短的记录之前计算所有记录的Levenshtein距离的函数（我通过将调用Levenshtein函数的位置替换为0来验证了这一点）。表格有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

我该从哪里开始？

- Matt

你已经对此进行了分析并查看了你的索引吗？ - Rick

将计算出的值存储在每一行中，并在目标列更改时进行更新... - Mitch Wheat

我还没有对其进行分析...我得查一下如何做，这是我第一次尝试优化存储过程。我无法存储计算出的值，因为它用于搜索，搜索输入很少会重复。 - Matt

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Mike Dunlavey · Accepted Answer

过去我处理这种情况的方式是将“数据库”（实际上是一个拼写纠错字典）存储为trie。然后，我使用分支限界算法查找最近匹配条目。对于小的距离，所需时间与距离呈指数关系。对于大的距离，所需时间与字典大小呈线性关系，这正如您现在看到的那样。分支限界基本上是trie的深度优先树遍历，但具有误差预算。在每个节点上，您跟踪当前的Levenshtein距离，如果超过预算，则修剪该树的分支。首先，您使用零预算进行遍历。这只会找到完全匹配项。如果没有找到匹配项，则使用预算为1进行搜索。这将找到距离为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);
      }
    }
  }
}

基本上，您可以通过跳过一个字母并在相同节点搜索来模拟删除一个字母。您可以通过不推进s而降低trie来模拟插入一个字母。您可以通过表现为字母匹配而实际上它并不匹配来模拟替换一个字母。当您掌握这些技巧后，您可以添加其他可能的不匹配项，例如将0替换为O，1替换为L或I - 像这样的愚蠢内容。

您可能希望添加字符数组参数以表示您正在Trie中查找的当前单词。