Хороший алгоритм для управления деревьями конфигурации с подстановочными знаками?

Question

Я ищу хороший алгоритм для управления переменными конфигурации в виде дерева с подстановочными знаками (xyz, x. .z, x. . * И т. Д.).

Есть ли что-то со временем поиска лучше, чем O (N)?(время вставки / удаления не так важно).

В настоящее время у меня есть плоский список (пары ключ => значение), и я ищу все подходящие значения, затем сортирую их по важности (в основном, больше подстановочных знаков =>менее важно) и выберите один с лучшим счетом.

Answer 1

Как указывает эпитафия, три или дерево-осветитель сделают свое дело. Основное дерево, как правило, будет более эффективно использовать пространство.

Полагаю, существует множество реализаций. Взгляните на мою реализацию здесь .

lookup () позволит вам найти данный ключ.

startwith () вернет все эти ключи и их соответствующие значения, которые начинаются с переданной строки. По сути, это поиск по шаблону.

Answer 2

То, что вы хотите, - это трехуровневая структура или радикальное дерево.Если вы хотите найти шаблон, просто используйте обратное дерево вместе с ним.Вы можете найти простое решение здесь: code.dogmap.org/kart.