Алгоритм / шаги для поиска самого Длинного префикса поиска в Patricia Trie

Question

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

1.2.3.0
1.2.0.0

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

Answer 1

Взгляните на Net-Patricia.Это реализация Patricia trie для поиска IP-адресов.Интерфейс выполнен на perl, но базовый код написан на C.Вот ссылка, но она должна быть во многих архивах CPAN:

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

Answer 2

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

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

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

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

Answer 3

В тестовом коде для LLVM есть довольно читаемая реализация на языке Си: https://llvm.org/svn/llvm-project/test-suite/trunk/MultiSource/Benchmarks/MiBench/network-patricia/