Как мне сбалансировать BK-дерево и нужно ли это?

Question

Я пытаюсь использовать алгоритм Edit Distance для реализации нечеткого поиска в базе данных имен.

Я нашел структуру данных, которая предположительно поможет ускорить это с помощью подхода "разделяй и властвуй" - деревья Беркхарда-Келлера. Проблема в том, что я не могу найти очень много информации об этом конкретном типе дерева.

Если я заполню свое BK-дерево произвольными узлами, насколько вероятно возникновение проблемы с балансом?

Если это возможно или вероятно для меня, чтобы иметь проблему баланса с деревьями BK, есть ли способ сбалансировать такое дерево после того, как оно было построено?

Как будет выглядеть алгоритм, чтобы правильно сбалансировать BK-дерево?

Мое мышление до сих пор:

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

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

• Начните с отсортированного в алфавитном порядке списка, затем поставьте очередь из середины. (Я не уверен, что это отличная идея, потому что алфавитирование - это не то же самое, что сортировка по расстоянию редактирования).
• Полностью перемешанные данные. (Это в значительной степени зависит от удачи, чтобы случайно выбрать "не такой ужасный" корень. Он может плохо потерпеть неудачу и может быть вероятностно гарантированно неоптимальным).
• Начните с произвольного слова в списке и отсортируйте остальные элементы по их расстоянию редактирования от этого элемента. Затем очередь из середины. (Я чувствую, что это будет дорого, но все равно будет плохо, поскольку не будет вычисляться метрическая связь между всеми словами - только каждым словом и одним ссылочным словом).
• Создайте исходное дерево любым методом, сгладьте его (в основном, как обход по предварительному заказу) и поставьте очередь из середины для нового дерева. (Это также будет дорого, и я думаю, что это все еще может быть плохо, так как оно не будет рассчитывать связность метрического пространства между всеми словами раньше времени и просто получит другое и все еще неравномерное распределение).
• Упорядочите по частоте названий, вставьте сначала самое популярное и отбросьте концепцию сбалансированного дерева. (Это может иметь смысл, так как мои данные распределены неравномерно, и у меня не будет чисто случайных слов).

К вашему сведению, в настоящее время я не беспокоюсь о проблеме синонимов имен (Билл против Уильяма). Я буду заниматься этим отдельно, и я думаю, что будут применяться совершенно разные стратегии.

Answer 1

В статье приведен пример использования lisp: http://cliki.net/bk-tree. Что касается разбалансировки дерева, я думаю, что структура данных и метод кажутся достаточно сложными, а также автор ничего не сказал о несбалансированном дереве. Когда вы испытываете несбалансированное дерево, может быть, это не для вас?