Функция STLish lower_bound для Radix/Patricia Trie

Question

В последнее время я изучаю попытки Патриции и работаю с действительно хорошей реализацией C++, которую можно использовать в качестве сортированного STL-ассоциативного контейнера. Попытки Патрисии отличаются от обычных двоичных деревьев, потому что конечные узлы имеют обратные указатели, которые указывают на внутренние узлы. Тем не менее, можно пройти путь Патриции в алфавитном порядке, выполнив обход в порядке, если вы посещаете внутренние узлы только через указатели на конечные узлы.

Что подводит меня к вопросу: возможно ли реализовать STL lower_bound а также upper_bound работает с Патрицией? Реализация, которую я использую , фактически реализует эти функции, но они работают не так, как ожидалось.

Например:

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. (An std::set, например, конечно, вывел бы HCDA здесь.)

Я написал разработчику, который создал эту библиотеку, но не получил ответа. Несмотря на это, я чувствую, что у меня довольно хорошее понимание того, как Патрисия пытается работать, и я не могу понять, как что-то вроде lower_bound было бы возможно. Проблема в том, что lower_bound полагается на способность лексикографически сравнивать две строки. Поскольку "GG" не существует в дереве, нам нужно выяснить, какой элемент>= для GG. Но Radix/Patricia пытается не использовать лексикографическое сравнение для перемещения от узла к узлу; скорее, каждый узел хранит битовый индекс, который используется для сравнения битов ключа поиска. Результат сравнения битов говорит вам, двигаться ли влево или вправо. Это позволяет легко найти конкретный префикс в дереве. Но если префикс не существует в дереве (как в случае с моим поиском "GG"), кажется, нет никакого способа, кроме лексикографического сравнения, получить lower_bound.

Тот факт, что используемая мной реализация C++, похоже, не реализует lower_bound должным образом, подтверждает мое подозрение, что это может быть невозможно. Тем не менее, тот факт, что вы можете перебирать дерево в алфавитном порядке, заставляет меня думать, что может быть способ сделать это.

Кто-нибудь имеет опыт работы с этим или знает, возможно ли реализовать функциональность lower_bound с помощью Patricia Trie?

Answer 1

Да, это возможно. Я реализовал вариант, который делает это, и страница DJ Bernstein описывает это как одну из быстрых операций.

http://cr.yp.to/critbit.html

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