Algorithmus/Schritte zur Suche nach dem längsten Präfix in Patricia Trie

Question

Ich implementiere Patricia -Versuche für die Suche nach IP -Präfix, ich könnte den Code für die vollständige Schlüsselübereinstimmung bearbeiten, aber wenn es darum geht, Probleme mit der Präfix -Suche zu haben, wenn es Schlüssel gibt, die Präfixe anderer Schlüssel sind, wie beispielsweise:

1.2.3.0
1.2.0.0

Kann mir jemand mit dem Algorithmus für Präfix -Suche im obigen Fall helfen, sollte ich diese als Schlüssel mit separater Länge betrachten (dh /24 und 16)?

Answer 1

Hier finden Sie aktuelle Net-Patricia. Dies ist eine Implementierung einer Patricia Trie-IP-Adressen zu suchen. Die Schnittstelle ist Perl, aber der zugrunde liegende Code ist in C. Hier ist ein Link, aber viele CPAN Archive sollten es haben:

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

Answer 2

Wenn Sie diese trie verwenden für IP-Nummern als Elemente der festen Länge zu speichern, dann ist es auf jeden Fall nicht der richtige Weg. Der Punkt hier ist, dass PT besonders nützlich ist, mit variabler Länge zum Speichern von Daten.
Wenn Sie Teile von IP-Nummern speichern, als Präfixe variabler Länge dann ist PT eine gute Wahl.
In diesem Fall ja Ihre Schlüssel sollten unterschiedlich lang sein.
Angenommen, Sie Präfix „192.168“ in binären 0xC0 0xA8 speichern, fügen Sie diese als erster Schlüssel.
Wenn dann für IP wie 192.168.1.1 der Suche können Sie Informationen erhalten, dass Ihre Trie enthält 192.168, das ist ein Präfix von dem, was Sie suchen.
Alles, was Sie tun müssen, ist den „gemeinsamen Teil“ zu speichern, während die Trie überquert.
Dies ist eine kleinere Neben dem dieser Implementierung. So stellen Sie sicher, dass während der Trie Sie den gemeinsamen Teil irgendwo in den Parametern der rekursiven Funktion speichern hinunter.
Für ein gutes Verständnis von Patricia Trie würde ich Robert Sedgewick Algorithmen Buch empfehlen zu lesen, die eine groß ist Quelle des Wissens.

Bearbeiten : Es gibt ein Problem, wenn C-Strings in PT speichern. Diese trie ist so konzipiert, um binäre Daten zu speichern, aber Sie sind nur daran interessiert, die ganze Bytes zu bekommen. Stellen Sie sicher, gemeinsamen Teil des Präfix sind die Speicherung nur dann, wenn seine Größe in Bits Vielfaches von 8 ist. Für ein falsches Beispiel: haben Sie Schlüssel in Ihrem Baum: 0xC0 0xA5 und Sie suchen fro 0xC0 0xA6. Ihre Traversal stoppen, wenn der gemeinsame Teil „0xC0 0xA“, aber Sie daran interessiert sind nur „0xC0“ zu nehmen. So stellen Sie sicher gemeinsames Bytes zu speichern, nicht Bits.

Answer 3

Im Testcode für LLVM gibt es eine einigermaßen lesbare C-Implementierung: https://llvm.org/svn/llvm-project/test-suite/trunk/MultiSource/Benchmarks/MiBench/network-patricia/