Patricia Trie per il recupero rapido dell'indirizzo IPv4 e dei dati satellitari

Question

Sto scrivendo un programma in C ++ che richiede indirizzi IP (tutti IPv4) da alzarsi e conservare in modo rapido. Ogni indirizzo IP ha un dato associato ad esso. Nel caso in cui esiste già nel trie, intendo unire i dati dell'indirizzo IP nel trie con i nuovi dati degli indirizzi. Se non è presente, intendo aggiungerlo come nuovo ingresso al trie. La cancellazione dell'indirizzo IP non è necessario.

Per implementare questo, ho bisogno di progettare un trie patricia. Tuttavia, non sono in grado di visualizzare il design oltre questo. Sembra piuttosto ingenua da parte mia, ma l'unica idea che mi è venuta in mente era cambiare l'indirizzo IP nella loro forma binaria e quindi usare il trie. Io sono comunque clueless per come esattamente per implementare questo.

Sarei davvero grato a te se potessi aiutarmi con questo. Siete pregati di notare che ho trovato una domanda simile qui . La domanda o più specificamente la risposta è stata oltre la mia comprensione in quanto il codice nel sito Web CPC non era abbastanza chiaro per me.

Nota anche, i miei dati sono il seguente formato

.

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 tenta a risolvere il problema della ricerca del miglior prefisso di copertura per un determinato indirizzo IP (sono utilizzati dai router per determinare rapidamente che 192.168.0/16 è la scelta migliore per il 192.168.14.63).Se stai solo cercando di abbinare esattamente gli indirizzi IP, una tabella Hash è una scelta migliore.

Answer 2

Penso che ti riferisca a un radixtree .Ho un'implementazione di un Radixtrie in Java, se si desidera utilizzare questo come punto di partenza, che fa il tasto effettivo per valutare la mappatura.Utilizza un patriciatrie Come è la struttura di supporto.

Esempio usando le seguenti stringhe.

.
1. 10.10.101.2
2. 10.10.100.1
3. 10.10.110.3

Trie Esempio (non compresso)

└── 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 (compresso)

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

.