gpt4 book ai didi

java - 该算法是否已正确实现?

转载 作者:塔克拉玛干 更新时间:2023-11-03 06:34:45 24 4
gpt4 key购买 nike

我目前正在实现 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;
}

我知道我运行循环的次数过多,我们可以调整搜索空间以加快查找速度。我只是不确定如何最好地做到这一点。

最佳答案

你的循环看起来大体上是正确的,虽然有点错综复杂。但是,您尝试改进停止条件(使用 tempdistance/maxdistance)是不正确的:BK 树的结构要求您探索当前节点的 levenshtein 距离 d-k 到 d+k 内的所有节点,如果您想找到所有结果,所以你不能那样修剪它。

是什么让您认为自己探索了太多的树?

您可以在 L evenshtein Automata 上找到我的后续帖子很有启发性,因为它们比 BK 树更有效。不过,如果您正在构建拼写检查器,我建议您遵循 Favonius 的建议并查看 this article。关于如何写一个。它比简单的字符串距离检查更适合拼写校正。

关于java - 该算法是否已正确实现?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/3865716/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com