优化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.

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

分支和绑定基本上是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);
      }
    }
  }
}

基本上,您通过跳过并在同一节点上搜索来模拟删除字母.你模拟插入一个字母,通过降低trie而不推进s.你可以模仿替换字母,就像字母匹配一样,即使它没有.当你掌握它时,你可以添加其他可能的不匹配,比如用O替换0,用L或I代替0 - 这样的哑巴.

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