Алгоритм / шаги по поиску длинного префикса поиска в Патрисии Три

Я реализую попытки Патрисии для поиска префикса IP, я мог бы заставить код работать для полного соответствия ключей, но столкнулся с проблемами с поиском префиксов, когда есть ключи, которые являются префиксами других ключей, например:

1.2.3.0
1.2.0.0

Может ли кто-нибудь помочь мне с алгоритмом поиска префиксов в приведенном выше случае. Должен ли я рассматривать их как ключи отдельной длины (т. Е., / 24 и 16)?

Ответы на вопрос(3)

ентов фиксированной длины, то это определенно не правильный путь. Дело в том, что PT особенно полезен для хранения данных переменной длины.

Если вы храните части IP-номеров в качестве префиксов переменной длины, то PT - хороший выбор.
В этом случае ваши ключи должны быть разной длины.
Допустим, вы храните префикс «192.168» в двоичном формате 0xC0 0xA8, вы добавляете его в качестве первого ключа.
Затем при поиске IP-адреса, например 192.168.1.1, вы можете получить информацию о том, что ваш файл содержит 192.168, что является префиксом того, что вы ищете.

Все, что вам нужно сделать, это сохранить «общую часть» при обходе дерева.
Это небольшое дополнение кэто реализация. Просто убедитесь, что при переходе вниз по дереву вы сохраняете общую часть где-то в параметрах рекурсивной функции.
Для хорошего понимания Patricia Trie я бы предложил прочитатьКнига Алгоритмов Роберта Седжвика который является отличным источником знаний.

РЕДАКТИРОВАТЬ: Существует одна проблема при хранении строк C в PT. Этот три предназначен для хранения двоичных данных, но вы заинтересованы только в получении целых байтов. Убедитесь, что вы храните общую часть префикса, только если его размер в битах кратен 8. Для неправильного примера: у вас есть ключ в вашем дереве: 0xC0 0xA5 и вы ищете 0xC0 0xA6. Ваш обход прекратится, когда общая часть "0xC0 0xA", но вы заинтересованы в принятии только "0xC0". Поэтому убедитесь, что храните общие байты, а не биты.

Решение Вопроса

ка IP-адресов. Интерфейс Perl, но основной код находится на C. Вот ссылка, но она должна быть у многих архивов CPAN:

http://cpansearch.perl.org/src/PHILIPP/Net-Patricia-1.15_07/libpatricia/patricia.c

Ваш ответ на вопрос