Algoritmo/procedura per trovare più Lungo Prefisso di ricerca in Patricia Trie

Question

Io sono l'attuazione di Patricia cerca per IP prefisso di ricerca, ho potuto ottenere i codice di lavoro per la completa corrispondenza con la chiave, ma affrontando i problemi con la ricerca di prefisso, quando c' sono le chiavi che sono prefissi di altri tasti, come:

1.2.3.0
1.2.0.0

Qualcuno mi può aiutare con l'algoritmo per il prefisso ricerche, nel caso di cui sopra Devo considerare questi come chiavi di separare la lunghezza (io.e, /24 e 16) ?

Answer 1

Date un'occhiata a Net-Patricia. Si tratta di un'implementazione di un trie Patricia per cercare gli indirizzi IP. L'interfaccia è perl, ma il codice sottostante è in C. Ecco un link, ma molti archivi CPAN dovrebbe avere:

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

Answer 2

Se si utilizza questa trie per la memorizzazione dei numeri IP come elementi della lunghezza fissa allora non è sicuramente la strada giusta. Il punto è che la PT è particolarmente utile per la memorizzazione di dati di lunghezza variabile.
Se si memorizzano parti di numeri IP, come prefissi di lunghezza variabile, allora PT è una buona scelta.
In questo caso sì le chiavi devono essere di lunghezza diversa.
Diciamo che si archiviano prefisso "192.168" in binario 0xC0 0xa8, si aggiunge questo come prima chiave.
Poi, durante la ricerca di IP 192.168.1.1 come è possibile ottenere le informazioni che il trie contiene 192.168, che è un prefisso di quello che cercate.
Tutto quello che dovete fare è quello di conservare la "parte comune" mentre attraversa il trie.
Questa è una piccola aggiunta alla questa implementazione . Basta fare in modo che, mentre scendendo trie di memorizzare la parte comune da qualche parte nei parametri della funzione ricorsiva.
Per una buona comprensione di Patricia trie vorrei suggerire la lettura di Robert Sedgewick algoritmi libro che è un grande fonte di conoscenza.

Modifica : C'è un problema quando la memorizzazione di stringhe C in PT. Questo trie è progettato per memorizzare dati binari, ma si è interessati solo a ottenere l'intero byte. Assicurarsi che si sta memorizzando parte comune del prefisso solo se la sua dimensione in bit è multiplo di 8. Per un esempio sbagliato: hai chiave nel tuo albero: 0xC0 0xA5 e siete alla ricerca fro 0xC0 0xA6. Il tuo attraversamento si arresta quando la parte comune "0xC0 0xA", ma si sono interessati a prendere solo "0xC0". Quindi assicuratevi di memorizzare byte comune, non bit.

Answer 3

C'è un modo abbastanza leggibile C attuazione del codice di test per LLVM: https://llvm.org/svn/llvm-project/test-suite/trunk/MultiSource/Benchmarks/MiBench/network-patricia/