Правильно ли реализован этот алгоритм?

Question

В настоящее время я использую 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;
}

Я знаю, что запускаю цикл излишне большое количество раз и что мы можем сократить пространство поиска, чтобы ускорить поиск. Я просто не знаю, как лучше всего это сделать.

Answer 1

Ваша петля выглядит в целом правильно, если немного византийской. Ваша попытка уточнить условие остановки (с помощью tempdistance/maxdistance) неверна, однако: структура BK-дерева требует, чтобы вы исследовали все узлы на расстоянии Левенштейна от dk до d + k текущего узла, если вы хотите найти все результаты, так что вы не можете обрезать это так.

Что заставляет вас думать, что вы слишком много исследуете дерева?

Вы можете посчитать мой пост на Lvenshtein Automata поучительным, так как они более эффективны, чем BK-деревья. Если вы создаете проверку орфографии, я бы порекомендовал следовать предложению Фавониуса и проверить эту статью о том, как ее написать. Это намного лучше подходит для исправления орфографии, чем наивная проверка расстояния строки.