我过去这样做的方法是将“数据库”(实际上是用于拼写纠正器的单词词典)存储为特里树。
然后我使用分支定界例程来查找最近的匹配条目。对于小距离,所花费的时间与距离呈指数关系。对于长距离,它与字典的大小成线性关系,就像您现在看到的那样。
分支定界基本上是 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 中找到的当前单词。