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

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

Чтобы реализовать это, мне нужно спроектировать Патрицию Три. Однако я не могу визуализировать дизайн за пределами этого. Мне это кажется довольно наивным, но единственная идея, которая пришла мне в голову, состояла в том, чтобы изменить IP-адрес на его двоичную форму и затем использовать три. Однако я не знаю, как именно это осуществить.

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

Также обратите внимание, мои данные в следующем формате

10.10.100.1: "Том", "Джек", "Смит"

192.168.12.12: "Джонс", "Лиз"

12.124.2.1: "Джимми", "Джордж"

10.10.100.1: "Майк", "Гарри", "Дженнифер"

Источник

2 ответа

Решение

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

Источник

Я думаю, что вы имеете в виду 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

Патриция Три (сжатая)

└── [black] 10.10.1
    ├── [black] 0
    │   ├── [white] (0.1) 00.1
    │   └── [white] (1.2) 01.2
    └── [white] (10.3) 10.10.110.3
Источник
Другие вопросы по тегам