java这个算法是否正确实现了?
我目前正在实现一个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;
}
我知道我运行循环的次数过多,这是不必要的,我们可以调整搜索空间以加快查找速度。我只是不知道怎样才能最好地做到这一点
# 1 楼答案
如果有点拜占庭风格的话,你的循环看起来基本正确。但是,您试图优化停止条件(使用tempdistance/maxdistance)的尝试是不正确的:BK树的结构要求您探索当前节点的levenshtein距离d-k到d+k内的所有节点,如果您想找到所有结果,那么您不能像这样修剪它
是什么让你觉得你对这棵树的探索太多了
你可能会发现我在Levenshtein Automata上的后续帖子很有启发性,因为它们比BK树更有效。不过,如果你要建立一个拼写检查器,我建议你遵循法沃纽斯的建议,看看this article如何编写一个。它比简单的字符串距离检查更适合拼写纠正