Dernièrement, j'ai étudié les essais de Patricia, et de travailler avec un très bon C++ implementation qui peut être utilisé comme un conteneur associatif STL trié. Les essais de Patricia diffèrent des arbres binaires normaux parce que les nœuds de feuille ont des pointeurs arrière qui pointent vers des nœuds internes. Néanmoins, il est possible de traverser une Patricia trie par ordre alphabétique en effectuant une traversée en ordre, si vous ne visitez que des nœuds internes via des pointeurs back-node.STLish fonction de lower_bound pour Radix/Patricia Trie
Ce qui m'amène à la question: est-il possible de mettre en œuvre les fonctions STL lower_bound et upper_bound avec une Patricia Trie? L'implémentation que j'utilise fait en fait, implémente ces fonctions, mais elles ne fonctionnent pas comme prévu.
Par exemple:
typedef uxn::patl::trie_set<std::string> trie;
trie ts;
ts.insert("LR");
ts.insert("BLQ");
ts.insert("HCDA");
trie::iterator it = ts.lower_bound("GG");
std::cout << *it << std::endl;
Ce sorties BLQ, quand j'attendre à HCDA de sortie. (Un std::set, par exemple, produirait certainement HCDA ici.)
J'ai envoyé un courriel au développeur qui a créé cette bibliothèque, mais je n'ai jamais reçu de réponse. Peu importe, je sens que j'ai une très bonne compréhension de la façon dont Patricia essaie de travailler, et je ne peux pas comprendre comment quelque chose comme lower_bound serait même possible. Le problème est que lower_bound semble s'appuyer sur la possibilité de comparer lexicographiquement les deux chaînes. Puisque "GG" n'existe pas dans l'arbre, nous devons trouver quel élément est> = à GG. Mais Radix/Patricia essaie de ne pas utiliser la comparaison lexicographique pour passer d'un nœud à l'autre; chaque nœud stocke plutôt un index de bits qui est utilisé pour effectuer une comparaison de bits sur la clé de recherche. Le résultat de la comparaison des bits vous indique si vous souhaitez vous déplacer à gauche ou à droite. Cela facilite la recherche d'un préfixe particulier dans l'arborescence. Mais si le préfixe n'existe pas dans l'arbre, (comme dans le cas de ma recherche de "GG"), il ne semble pas y avoir de moyen, à part une comparaison lexicographique, d'obtenir le lower_bound.
Le fait que l'implémentation C++ que j'utilise ne semble pas implémenter lower_bound confirme ma suspicion que cela ne soit pas possible. Cependant, le fait que vous puissiez parcourir l'arbre par ordre alphabétique me fait penser qu'il pourrait y avoir un moyen de le faire.
Quelqu'un a-t-il de l'expérience ou sait-il s'il est possible d'implémenter une fonctionnalité de type "lower_bound" avec une Patricia Trie?
C'est certainement possible, tant que le conteneur est effectivement trié. Au pire, vous pouvez: trie :: iterator it = ts.begin(); while (it! = ts.end() && * it <"GG") ++ it; Si vous pouvez le faire plus efficacement est une autre question. Je serais surpris s'il est impossible de faire mieux en utilisant la structure trie réelle, mais je ne sais pas assez sur ces tentatives pour repérer un bug dans le code juste de la navigation. – aschepler