Алгоритм / шаги по поиску длинного префикса поиска в Патрисии Три
Я реализую попытки Патрисии для поиска префикса IP, я мог бы заставить код работать на полное совпадение ключей, но столкнулся с проблемами с поиском префиксов, когда есть ключи, которые являются префиксами других ключей, например:
1.2.3.0
1.2.0.0
Может ли кто-нибудь помочь мне с алгоритмом поиска префикса в приведенном выше случае. Должен ли я рассматривать их как ключи отдельной длины (т. Е. /24 и 16)?
3 ответа
Посмотрите на Net-Patricia. Это реализация программы Patricia для поиска IP-адресов. Интерфейс Perl, но основной код находится на C. Вот ссылка, но она должна быть у многих архивов CPAN:
http://cpansearch.perl.org/src/PHILIPP/Net-Patricia-1.15_07/libpatricia/patricia.c
Если вы используете этот набор для хранения IP-адресов в качестве элементов фиксированной длины, то это определенно не правильный путь. Дело в том, что 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". Поэтому убедитесь, что храните общие байты, а не биты.
В тестовом коде для LLVM есть довольно читаемая реализация C: https://llvm.org/svn/llvm-project/test-suite/trunk/MultiSource/Benchmarks/MiBench/network-patricia/