优化编辑距离算法

Question

我有一个存储过程，它使用编辑距离来确定最接近用户键入内容的结果。唯一真正影响速度的是在选择距离最小的记录之前计算所有记录的 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 的深度优先树遍历，但有错误预算。在每个节点，您跟踪当前的编辑距离，如果超出预算，则修剪树的该分支。

首先，您以零预算进行步行。这只会找到完全匹配的结果。如果你没有找到匹配的，那么你就以 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);
      }
    }
  }
}

基本上，您通过跳过字母并在同一节点搜索来模拟删除它。您可以通过降序排列 trie 而不前进 s 来模拟插入字母。您可以通过表现得好像字母匹配来模拟替换字母，即使事实并非如此。当你掌握了它的窍门后，你可以添加其他可能的不匹配，例如用 O 替换 0，用 L 或 I 替换 1 - 像这样的愚蠢的东西。

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