Patricia Trie для быстрого поиска адреса IPv4 и спутниковых данных
-
13-12-2019 - |
Вопрос
Я пишу программу в C ++, которая требует IP-адресов (все IPv4), которая будет выглядеть вверх и храниться быстро. Каждый IP-адрес имеет данные, связанные с ним. В случае, если это уже существует в TRIE, я намерен объединить данные IP-адреса в TRIE с новыми адресами данных. Если он не присутствует, я собираюсь добавить его как новую запись в TRIE. Удаление IP-адреса нет необходимости.
Для того, чтобы реализовать это, мне нужно разработать Patricia Tri. Однако я не могу визуализировать дизайн за пределы этого. Это кажется весьма наивным для меня, но единственная идея, которая на мой взгляд, должна была изменить IP-адрес в их двоичную форму, а затем использовать TRIE. Однако я не знаю, как точно реализовать это.
Я был бы действительно благодарен вам, если бы вы могли помочь мне с этим. Обратите внимание, что я нашел аналогичный вопрос
Решение
Patricia пытается решить проблему нахождения наилучшего префикса покрытия для данного IP-адреса (они используются маршрутизаторами для быстрого определения того, что 192.168.0.0.0/16 - лучший выбор на 192.168.14.63, например).Если вы просто пытаетесь сопоставить IP-адреса именно, хеш-таблица - лучший выбор.
Другие советы
Я думаю, что вы ссылаетесь на Radixtree .У меня есть реализация Radixtrie в Java, если вы хотите использовать это в качестве отправной точки, которая выполняет фактическую клавишу для сопоставления значения.Он использует patriciatrie Как это поддерживает конструкцию.