Patricia Trie per il recupero rapido dell'indirizzo IPv4 e dei dati satellitari
-
13-12-2019 - |
Domanda
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
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"
Soluzione
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.
Altri suggerimenti
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.