Algorithme/étapes pour trouver la recherche du préfixe le plus long dans Patricia Trie

Question

J'implémente Patricia essais pour la recherche de préfixe IP, je pourrais faire fonctionner le code pour une correspondance complète, mais faire face à des problèmes de recherche de préfixe, lorsqu'il y a des clés qui sont des préfixes d'autres clés, comme:

1.2.3.0
1.2.0.0

Quelqu'un peut-il m'aider avec l'algorithme pour les recherches de préfixe dans le cas ci-dessus, devrais-je les considérer comme des clés de longueur séparée (c'est-à-dire, / 24 et 16)?

Answer 1

Jetez un oeil à Net-Patricia. Ceci est une mise en œuvre d'une structure arborescente Patricia pour rechercher des adresses IP. L'interface est perl, mais le code sous-jacent est en C. Voici un lien, mais beaucoup d'archives CPAN devrait avoir:

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

Answer 2

Si vous utilisez cette structure arborescente pour stocker les numéros IP comme des éléments de la longueur fixe alors il est certainement pas la bonne façon. Le point ici est que PT est particulièrement utile pour stocker des données de longueur variable.
Si vous stockez des parties de numéros IP, comme préfixes de longueur variable alors PT est un bon choix.
Dans ce cas, oui vos clés doivent être de longueur différente.
Disons que vous stockez préfixe « 192.168 » dans 0xC0 0xA8 binaire, vous ajoutez cela comme première clé.
Puis, lors de la recherche IP comme 192.168.1.1 vous pouvez obtenir des informations que votre contient 192.168 qui Trie est un préfixe de ce que vous recherchez.
Tout ce que vous devez faire est de stocker la partie « commune » en traversant la structure arborescente.
Ceci est un ajout mineur à la cette implémentation . Assurez-vous que tout en descendant la Trie vous stockez la partie commune quelque part dans les paramètres de la fonction récursive.
Pour une bonne compréhension de Patricia Trie Je vous suggère de lire Algorithmes livre de Robert Sedgewick qui est un grand source de connaissances.

EDIT : Il y a un problème lors de l'enregistrement des chaînes de C dans PT. Cette structure arborescente est conçu pour stocker des données binaires, mais vous êtes intéressés à obtenir que l'ensemble des octets. Assurez-vous stockez partie commune du préfixe que si sa taille en bits est multiple de 8. Pour un mauvais exemple: vous avez la clé dans votre arbre: 0xC0 0xA5 et vous cherchez vient 0xC0 0xA6. Votre traversal cessera quand la partie commune « 0xC0 0xA », mais vous êtes intéressé à prendre seulement « 0xC0 ». Donc, assurez-vous de stocker octets communs, pas de bits.

Answer 3

Il existe une implémentation C assez lisible dans le code de test pour LLVM : https://llvm.org/svn/llvm-project/test-suite/trunk/MultiSource/Benchmarks/MiBench/network-patricia/