BK - Tree Search All

Question

A BK Trees (деревья Буркхарда-Келлера) связаны с поиском нечетких строк (например, проверка орфографии, рекомендации по словам). И все алгоритмы поиска BK Trees соответствуют описанным здесь. Цель - вернуть, например, "seek" и "peek", если я ищу "aeek".

Теперь мой вопрос: я пытаюсь использовать этот алгоритм поиска нечетких строк для поиска всех похожих элементов из данного словаря. Например, учитывая слово "искать", я хочу найти в словаре все похожие слова, например "выглядывать", "выродок", "место" и т. Д. Однако я обнаружил, что алгоритм поиска BK Trees, который используют все, не предназначен для этого.

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

Что я хочу, так это, используя мой приведенный выше пример теста с учетом любой из четырех книг по Python, SearchAll Функция всегда возвращает четыре книги Python, независимо от того, в каком порядке построен словарь или в каком порядке выполняется поиск.

Тем не менее, я пробовал много способов, но все не удалось (например, это один из них). Теперь я поднимаю руки и прошу помощи. Подойдет псевдокод или общий алгоритм описания. Спасибо.

Answer 1

У вас есть целочисленное переполнение в строках 77 и 106 bktree.go:

k: = d - r

Так как типы d а также r являются uint8, тип k это также uint8, так когда d < r, k в конечном итоге больше, чем d + rи следующий цикл не выполняется.

Вы можете исправить это так:

k := int16(d) - int16(r)
max_k  := int16(d) + int16(r)
if k < 1 {
    k = 1
}
for ; k <= max_k; k++ {
    ...
}