Patricia Tririe zum schnellen Abrufen von IPv4-Adress- und Satellitendaten

Question

Ich schreibe ein Programm in C ++, das IP-Adressen (alle IPv4) erfordert, die aufgenommen und schnell aufbewahrt werden. Jede IP-Adresse hat eine mit ihm verbundene Daten. Falls es bereits im TRIE existiert, möchte ich die Daten der IP-Adresse im TRIE mit den neuen Adressendaten zusammenführen. Wenn es nicht anwesend ist, möchte ich es als einen neuen Eintrag zum Trio hinzufügen. Die Löschung der IP-Adresse ist nicht erforderlich.

Um dies umzusetzen, muss ich ein Patricia-Tri entwischen. Ich kann das Design jedoch nicht danach visualisieren. Es erscheint ziemlich naiv von mir, aber die einzige Idee, die mir in den Sinn kam, war, die IP-Adresse an ihre binäre Form zu ändern und dann den Tri zu verwenden. Ich bin jedoch ahnungslos über Wie genau um das Umsetzen zu bringen.

Ich wäre Ihnen wirklich dankbar, wenn Sie mir mit diesem helfen könnten. Bitte beachten Sie, dass ich eine ähnliche Frage gefunden habe a>. Die Frage oder genauer gesagt, die Antwort war nicht mein Verständnis, da der Code in der CPAN-Website für mich nicht klar genug war.

HINWEIS HINWEIS, meine Daten sind das folgende Format

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 versucht das Problem zu lösen, um das beste Abdeckpräfix für eine bestimmte IP-Adresse zu finden (sie werden von Router verwendet, um schnell zu bestimmen, dass 192.168.0.0/16 die beste Wahl für 192.168.14.63 ist beispielsweise).Wenn Sie nur versuchen, IP-Adressen genau zu stimmen, ist eine Hash-Tabelle eine bessere Wahl.

Answer 2

Ich denke, Sie beziehen sich auf eine radixtree .Ich habe eine Implementierung eines Radixtrie in Java, wenn Sie das als Startpunkt verwenden möchten, was den tatsächlichen Schlüssel zum Value-Mapping tut.Es verwendet eine patriciatrie Da es sich um die Stützstruktur handelt.

Beispiel mit den folgenden Saiten.

.
1. 10.10.101.2
2. 10.10.100.1
3. 10.10.110.3

trie Beispiel (unkomprimiert)

generasacodicetagpre.

patricia trie (komprimiert)

generasacodicetagpre.