In letzter Zeit habe ich versucht, Patricia zu testen und mit einer wirklich guten C ++ - Implementierung zu arbeiten, die als ein STL Sortierter Assoziativer Container. Patricia-Versuche unterscheiden sich von normalen Binärbäumen, da Blattknoten Rückzeiger haben, die auf interne Knoten zeigen. Nichtsdestoweniger ist es möglich, einen Patricia-Trie in alphabetischer Reihenfolge zu durchlaufen, indem eine In-Order-Traversierung durchgeführt wird, wenn Sie nur interne Knoten durch Blattknoten-Rückzeiger besuchen.
Was mich zu der Frage führt: Ist es möglich, die Funktionen STL lower_bound und upper_bound mit einem Patricia Trie zu implementieren? Die Implementierung, die ich verwende tut tatsächlich, implementieren diese Funktionen, aber sie funktionieren nicht wie erwartet.
Zum Beispiel:
%Vor% Dies gibt BLQ aus, wenn ich erwarte, dass es HCDA ausgibt. (Ein std::set zum Beispiel würde sicherlich HCDA hier ausgeben.)
Ich habe dem Entwickler, der diese Bibliothek erstellt hat, eine E-Mail geschickt, aber nie eine Antwort erhalten. Egal, ich habe das Gefühl, dass ich ziemlich gut verstehe, wie Patricia funktioniert, und ich kann mir nicht vorstellen, dass sowas wie "lower_bound" überhaupt möglich wäre. Das Problem ist, dass sich lower_bound auf die Möglichkeit stützt, die beiden Strings lexikografisch zu vergleichen. Da "GG" in der Baumstruktur nicht existiert, müssten wir herausfinden, welches Element & gt; = zu GG ist. Aber Radix / Patricia-Versuche verwenden keinen lexikografischen Vergleich, um sich von Knoten zu Knoten zu bewegen; vielmehr speichert jeder Knoten einen Bitindex, der verwendet wird, um einen Bitvergleich auf dem Suchschlüssel durchzuführen. Das Ergebnis des Bitvergleichs sagt Ihnen, ob Sie sich nach links oder rechts bewegen sollen. Dies erleichtert das Auffinden eines bestimmten Präfixes in der Baumstruktur. Aber wenn das Präfix nicht im Baum existiert (wie bei meiner Suche nach "GG"), scheint es keinen Weg zu geben, einen lexikografischen Vergleich zu machen, um den unteren_Bound zu bekommen.
Die Tatsache, dass die C ++ - Implementierung, die ich benutze, low_bound nicht korrekt implementiert, bestätigt meinen Verdacht, dass es nicht möglich ist. Dennoch, die Tatsache, dass Sie in alphabetischer Reihenfolge über den Baum iterieren können, lässt mich denken, dass es einen Weg dafür gibt.
Hat jemand Erfahrung damit oder wissen Sie, ob es möglich ist, eine lower_bound Funktionalität mit einer Patricia Trie zu implementieren?
Ja, das ist möglich. Ich habe eine Variante implementiert, die dies tut, und D. J. Bernsteins Seite beschreibt das als eine der schnellen Operationen.
Im Prinzip stimmen Sie immer mit dem Präfix überein, bis Sie nicht mehr übereinstimmen können. Dann gehen Sie zum nächsten Wert, und dort ist der Knoten, nach dem Sie suchen.
Tags und Links c++ stl trie patricia-trie