Patricia Trie pour une récupération rapide de l'adresse IPv4 et des données satellites

Question

J'écris un programme en C ++ nécessitant des adresses IP (tous IPv4) à regarder et stockées de manière rapide. Chaque adresse IP a une donnée associée à celle-ci. Si cela existe déjà dans la Trie, j'ai l'intention de fusionner les données de l'adresse IP dans la trie avec les nouvelles adresses. Si ce n'est pas présent, j'ai l'intention de l'ajouter comme une nouvelle entrée à la Trie. La suppression de l'adresse IP n'est pas nécessaire.

Pour mettre en œuvre cela, j'ai besoin de concevoir une trie Patricia. Cependant, je suis incapable de visualiser la conception au-delà de cela. Cela me semble assez naïf, mais la seule idée qui me suis venu à l'esprit était de changer l'adresse IP à leur forme binaire, puis d'utiliser la trie. Je suis toutefois désemparé sur comment exactement pour la mettre en œuvre.

Je serais vraiment reconnaissant avec vous si vous pouviez m'aider avec celui-ci. Veuillez noter que j'ai trouvé une question similaire ici . La question ou plus particulièrement la réponse était au-delà de ma compréhension car le code dans le site Web de CPAN n'était pas assez clair pour moi.

Notez également, mes données sont le format suivant

10.10.100.1: "Tom", "Jack", "Smith"

192.168.12.12: "Jones", "Liz"

12.124.2.1: "Jimmy", "George"

10.10.100.1: "Mike", "Harry", "Jennifer"

Answer 1

Patricia Triet résoudre le problème de la recherche du meilleur préfixe de couverture pour une adresse IP donnée (ils sont utilisés par des routeurs pour déterminer rapidement que 192.168.0.0/16 est le meilleur choix pour 192.168.14.63, par exemple).Si vous essayez simplement de faire correspondre exactement les adresses IP, une table de hachage est un meilleur choix.

Answer 2

Je pense que vous vous référez à un Radixtree .J'ai une implémentation d'un Radixtrie en Java, si vous souhaitez l'utiliser comme point de départ, qui fait la clé réelle de la cartographie de la valeur.Il utilise un Patriciatrie comme il s'agit de la structure de support.

exemple en utilisant les chaînes suivantes.

1. 10.10.101.2
2. 10.10.100.1
3. 10.10.110.3

Trie exemple (non compressé)

└── 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 (compressée)

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