0

我目前正在实施BK-Tree来制作拼写检查器。我正在使用的字典非常大（数百万字），这就是为什么我根本无法承受任何低效率。但是，我知道我编写的查找函数（可以说是整个程序中最重要的部分）可以做得更好。我希望能找到一些同样的帮助。这是我写的查找：

public int get(String query, int maxDistance)
{
    calculateLevenshteinDistance cld = new calculateLevenshteinDistance();
    int d = cld.calculate(root, query);
    int tempDistance=0;

    if(d==0)
        return 0;

    if(maxDistance==Integer.MAX_VALUE)
        maxDistance=d;

    int i = Math.max(d-maxDistance, 1);
    BKTree temp=null;

    for(;i<=maxDistance+d;i++)
    {
        temp=children.get(i);
        if(temp!=null)
        {
            tempDistance=temp.get(query, maxDistance);
        }
        if(maxDistance<tempDistance)
            maxDistance=tempDistance;
    }

    return maxDistance;
}

我知道我不必要地多次运行循环，并且我们可以修剪搜索空间以加快查找速度。我只是不确定如何最好地做到这一点。

4

1 回答 1

1

如果有点拜占庭式，您的循环看起来通常是正确的。但是，您尝试细化停止条件（使用 tempdistance/maxdistance）是不正确的：BK-tree 的结构要求您探索在当前节点的 dk 到 d+k 的 levenshtein 距离内的所有节点，如果您想找到所有结果，所以你不能像那样修剪它。

是什么让你觉得你对这棵树的探索太多了？

你可能会发现我在 L evenshtein Automata上的后续帖子很有启发性，因为它们比 BK-trees 更有效。但是，如果您正在构建拼写检查器，我建议您遵循 Favonius 的建议并查看这篇关于如何编写拼写检查器的文章。它比简单的字符串距离检查更适合拼写纠正。

于 2010-10-06T12:39:15.783 回答