Правильно ли реализован этот алгоритм? - PullRequest
Новая
       287

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

0 голосов
/ 05 октября 2010

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

1 голос
/ 06 октября 2010

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

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

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

...