В последнее время я изучаю попытку Патрисии и работаю с действительно хорошим C++ implementation, который может использоваться как сортированный ассоциативный контейнер STL. Патрисия пытается отличаться от обычных двоичных деревьев, потому что листовые узлы имеют обратные указатели, которые указывают на внутренние узлы. Тем не менее, вы можете пересечь Patricia trie в алфавитном порядке, совершив обход в порядке, если вы посещаете только внутренние узлы с помощью указателей обратной ссылки на листовые узлы.Функция STLish lower_bound для Radix/Patricia Trie
Который подводит меня к вопросу: возможно ли реализовать функции STL lower_bound и upper_bound с Patricia trie? Реализация, которую я использую , делает на самом деле, реализовать эти функции, но они не работают должным образом.
Например:
typedef uxn::patl::trie_set<std::string> trie;
trie ts;
ts.insert("LR");
ts.insert("BLQ");
ts.insert("HCDA");
trie::iterator it = ts.lower_bound("GG");
std::cout << *it << std::endl;
Это выводит BLQ, когда я бы ожидать, что это выходной HCDA. (Например, std::set, конечно, вывести HCDA здесь.)
Я отправил по электронной почте разработчика, который сделал эту библиотеку, но так и не получил ответа. Несмотря на это, я чувствую, что у меня довольно хорошее понимание того, как Патрисия пытается работать, и я не могу понять, как что-то вроде lower_bound будет даже возможно. Проблема в том, что lower_bound, похоже, полагается на способность лексикографически сравнивать две строки. Поскольку «GG» не существует в дереве, нам нужно выяснить, какой элемент имеет значение = = GG. Но Radix/Patricia не использует лексикографическое сравнение для перехода от узла к узлу; скорее, каждый узел хранит бит-индекс, который используется для выполнения битного сравнения в ключе поиска. Результат сравнения бит указывает, следует ли перемещаться влево или вправо. Это упрощает поиск определенного префикса в дереве. Но если префикс не существует в дереве (как в случае с моим поиском для «GG»), похоже, что нет нигде, кроме лексикографического сравнения, чтобы получить lower_bound.
Тот факт, что реализация C++, которую я использую, кажется, не реализует lower_bound, правильно подтверждает мое подозрение, что это может быть невозможно. Тем не менее, факт, что вы можете перебирать дерево в алфавитном порядке, заставляет меня думать, что может быть способ сделать это.
У кого-нибудь есть опыт с этим или знаете, возможно ли реализовать функцию lower_bound с помощью Patricia Trie?
Это, безусловно, возможно, если контейнер действительно отсортирован. В худшем случае вы можете: trie :: iterator it = ts.begin(); while (it! = ts.end() && * it <"GG") ++ it; Если вы можете сделать это более эффективно, это еще один вопрос. Я был бы удивлен, если бы было невозможно сделать что-то лучше, используя фактическую структуру trie, но я не достаточно хорошо знаю об этих попытках обнаружить ошибку в коде только от просмотра. – aschepler