Patricia Trie для быстрого поиска адреса IPv4 и спутниковых данных

Question

Я пишу программу в C ++, которая требует IP-адресов (все IPv4), которая будет выглядеть вверх и храниться быстро. Каждый IP-адрес имеет данные, связанные с ним. В случае, если это уже существует в TRIE, я намерен объединить данные IP-адреса в TRIE с новыми адресами данных. Если он не присутствует, я собираюсь добавить его как новую запись в TRIE. Удаление IP-адреса нет необходимости.

Для того, чтобы реализовать это, мне нужно разработать Patricia Tri. Однако я не могу визуализировать дизайн за пределы этого. Это кажется весьма наивным для меня, но единственная идея, которая на мой взгляд, должна была изменить IP-адрес в их двоичную форму, а затем использовать TRIE. Однако я не знаю, как точно реализовать это.

Я был бы действительно благодарен вам, если бы вы могли помочь мне с этим. Обратите внимание, что я нашел аналогичный вопрос

Answer 1

Patricia пытается решить проблему нахождения наилучшего префикса покрытия для данного IP-адреса (они используются маршрутизаторами для быстрого определения того, что 192.168.0.0.0/16 - лучший выбор на 192.168.14.63, например).Если вы просто пытаетесь сопоставить IP-адреса именно, хеш-таблица - лучший выбор.

Answer 2

Я думаю, что вы ссылаетесь на Radixtree .У меня есть реализация Radixtrie в Java, если вы хотите использовать это в качестве отправной точки, которая выполняет фактическую клавишу для сопоставления значения.Он использует patriciatrie Как это поддерживает конструкцию.

Пример, используя следующие строки.

1. 10.10.101.2
2. 10.10.100.1
3. 10.10.110.3

TRIE ПРИМЕР (несжатый)

└── 1
    └── 0
        └── .
            └── 1
                └── 0
                    └── .
                        └── 1
                            ├── 0
                            │   ├── 1
                            │   │   └── .
                            │   │       └── (2) 10.10.101.2
                            │   └── 0
                            │       └── .
                            │           └── (1) 10.10.100.1
                            └── 1
                                └── 0
                                    └── .
                                        └── (3) 10.10.110.3

.

<Сильная> Patricia TRIE (сжатый)

└── [black] 10.10.1
    ├── [black] 0
    │   ├── [white] (0.1) 00.1
    │   └── [white] (1.2) 01.2
    └── [white] (10.3) 10.10.110.3

.