Últimamente he estado estudiando los intentos de Patricia, y trabajando con un muy buen C++ implementation que puede usarse como un contenedor asociado ordenado por STL. Patricia intenta diferenciarse de los árboles binarios normales porque los nodos de las hojas tienen punteros que apuntan a los nodos internos. No obstante, es posible recorrer un Patricia trie en orden alfabético haciendo un recorrido en orden, si solo visita nodos internos a través de punteros posteriores de nodo hoja.STLish función low_bound para Radix/Patricia Trie
Lo que me lleva a la pregunta: ¿es posible implementar las funciones STL lower_bound y upper_bound con una Patricia trie? La implementación que estoy usando hace, de hecho, implementa estas funciones, pero no funcionan como se esperaba.
Por ejemplo:
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;
Esto da salida a BLQ, cuando yo esperaría que HCDA salida. (Un std::set, por ejemplo, ciertamente generaría HCDA aquí.)
Envié un correo electrónico al desarrollador que hizo esta biblioteca, pero nunca recibí una respuesta. A pesar de todo, siento que entiendo muy bien cómo Patricia intenta trabajar, y no puedo entender cómo algo como low_bound sería posible. El problema es que lower_bound parece depender de la capacidad de comparar lexicográficamente las dos cadenas. Como "GG" no existe en el árbol, tendríamos que averiguar qué elemento es> = a GG. Pero Radix/Patricia intenta no usar la comparación lexicográfica para pasar de un nodo a otro; más bien, cada nodo almacena un índice de bits que se usa para realizar una comparación de bits en la clave de búsqueda. El resultado de la comparación de bits te dice si mover hacia la izquierda o hacia la derecha. Esto hace que sea fácil encontrar un prefijo particular en el árbol. Pero si el prefijo no existe en el árbol (como en el caso de mi búsqueda de "GG"), no parece haber ningún camino, salvo una comparación lexicográfica, para obtener el límite inferior.
El hecho de que la implementación de C++ que estoy usando no parece implementar lower_bound correctamente confirma mi sospecha de que no sea posible. Aún así, el hecho de que pueda iterar sobre el árbol en orden alfabético me hace pensar que podría haber una manera de hacerlo.
¿Alguien tiene experiencia con esto, o sabe si es posible implementar una funcionalidad low_bound con una Patricia Trie?
Sin duda es posible, siempre que el contenedor esté ordenado. En el peor de los casos, puede: trie :: iterator it = ts.begin(); while (it! = ts.end() && * it <"GG") ++ it; Si puede hacerlo de manera más eficiente es otra cuestión. Me sorprendería si es imposible hacer un mejor uso de la estructura real de trie, pero no sé lo suficiente acerca de estos intentos para detectar un error en el código solo por la navegación. – aschepler