Habiendo leído algunos artículos sobre intentos
(también conocido como árboles de prefijo, también conocido como árboles de raíz), decidí escribir uno propio.
Hoy vamos a hablar sobre una implementación de trie en C ++. Lo haremos
También compare una búsqueda de cadenas con AVL y el árbol Radix.
Introducción
- ¿Por qué los finalistas de Topcoder no comparten su experiencia en los tutoriales de YouTube para principiantes? Cualquier principiante agradecería la ayuda para desarrollar sus habilidades para resolver problemas.
- ¿Cuáles son los parámetros que afectan el tiempo de ejecución de un algoritmo?
- ¿Cuál es la diferencia entre un árbol AVL y un árbol de búsqueda binario?
- Dado un problema, ¿cómo puedo decidir si usar un enfoque codicioso o dividir y conquistar?
- Cómo encontrar un segmento en una matriz con un número máximo de elementos con suma S
UNA
trie es una estructura de datos de árbol ordenada que se utiliza para almacenar una dinámica
conjunto o matriz asociativa donde las teclas suelen ser cadenas. Estamos
vamos a echar un vistazo a la implementación de árboles de prefijos para
almacenar cadenas ASCII. Cada cadena termina con un símbolo de terminal que
Nunca repita en una cadena de nuevo. Para indicar símbolos terminales en
fotos y ejemplos, usaremos el signo de dólar. Para indicarlos en
el código, vamos a usar el símbolo nulo. Así, en nuestro
implementación las cadenas serán las estándar C, lo que permite usar
la biblioteca estándar string.h. Todo lo mencionado anteriormente debe ser fácilmente
trasladado a otros alfabetos.
En un árbol de raíz normal, cada borde se asigna con algún símbolo.
En cuanto a los nodos raíz, almacenan cierta información de servicio (usuario). Por lo tanto, cualquier
la ruta desde la raíz de un árbol hasta una de sus hojas define precisamente solo una
cuerda. Esta cadena se considera almacenada en el árbol especificado.
Por ejemplo, un trie almacena el siguiente conjunto de cadenas: {abab $, aba $,
bc $, b $, bac $, baca $} (vea la imagen a continuación). La raíz está a la izquierda,
las hojas (su número coincide con el número de cadenas) están en el
Derecha. La raíz de baca $ string se resalta en rojo.
Un lector prudente notará que de esta manera un trie representa una máquina determinista regular de estado finito, cuyos estados corresponden a las hojas de un trie. La implementación de Trie en la biblioteca libdatrie se basa exactamente en este concepto. El autómata se representa con la ayuda de matrices.
A
hacer un autómata más pequeño, representar un trie en un medio comprimido
formar. Tal forma significa que todas las “colas” del árbol (áreas sin
ramas) se empaquetan en cadenas (vea la imagen A a continuación). También podemos
comprima de manera similar todas las cadenas sin ramas (imagen B).
En este caso, el árbol ya no será un autómata de estado finito, o
más bien seguirá siendo un autómata, pero para un alfabeto de cadenas,
No símbolos. Trabajar con un árbol como con un autómata depende de
hecho de que el tamaño del alfabeto es finito y podemos definir su serie
número por cualquier símbolo en el alfabeto en O (1) de tiempo (el mismo no
trabajo para cuerdas). Por lo tanto, su implementación con la ayuda de matrices
se vuelve problemático Pero cuando se implementa con la ayuda de punteros,
no debería haber problemas con el almacenamiento de cadenas.
Representando a un Trie Usando Punteros
Vamos
Vea cómo podemos usar punteros para representar los bordes del trie. En primer lugar, nosotros
debe darse cuenta de que en este caso, será realmente incómodo
almacenar información en bordes de trie. Por lo tanto, debemos reubicar el símbolo
cadenas de bordes a nodos raíz. Use una característica obvia de orientado
árboles: solo un borde entra en cualquier nodo, excepto el raíz.
Vamos a obtener la siguiente estructura:
Hay
Otro problema, ya que un grado de un nodo de árbol puede ser aleatorio (incluso de
el tamaño actual del alfabeto). Para resolver este problema, apliquemos un
Método estándar: almacenar una lista de nodos secundarios en cada nodo. La lista
se vincularán individualmente, por lo que almacenaremos solo una cabeza (hermana mayor) en un
nodo. Esto nos permitirá rechazar una raíz vacía. Ahora, un trie será
representado con un puntero al encabezado de la lista de nodos hijos del antiguo
raíz (es decir, reemplazamos un árbol con un bosque). Por lo tanto, cada nodo almacenará
precisamente dos punteros: enlace – al nodo más antiguo, al lado – a su hermana menor. La siguiente imagen muestra el proceso de tal transformación; las flechas azules corresponden a los punteros de enlace , las flechas rojas a los siguientes punteros.
En
para entender el principio de trabajar con un árbol, debes
tenga en cuenta el esquema que se presenta en la imagen de la izquierda.
Mientras tanto, la representación real de un árbol será como en el
imagen a la derecha.
Entonces, pasamos del árbol con un grado variable (un árbol regular) al árbol binario , en el que el enlace y el siguiente son punteros a los subárboles derecho e izquierdo, como en la imagen a continuación:
Ahora podemos pasar a la implementación. Un nodo de árbol es una cadena de símbolos clave , su longitud de len y enlace y luego
punteros No es necesario que la cadena termine con un símbolo de terminal, por lo que
Deberíamos saber su longitud. También hay un constructor mínimo que
crea un árbol trivial que consta de un nodo con una clave dada (para copiar
símbolos, use una función strncpy estándar) y una aún más mínima
incinerador de basuras.
struct node // una estructura para representar los nodos del árbol {char * key; int len; nodo * enlace; nodo * siguiente; nodo (char * x, int n): len (n), enlace (0), siguiente (0) {clave = nuevo char [n]; strncpy (clave, x, n); } ~ nodo () {eliminar [] clave; }};
Buscando llaves
La primera operación que veremos es insertar una nueva cadena en un árbol de prefijos. La idea de búsqueda es estándar. Nos moveremos desde la raíz del árbol. Si la raíz está vacía, la búsqueda no tiene éxito. De lo contrario, compararemos la clave en el nodo con una cadena x actual. Use la siguiente función que calculará la longitud del prefijo común más grande de dos cadenas de la longitud dada.
prefijo int (char * x, int n, char * key, int m) // longitud del prefijo común más grande de x y cadenas de clave {for (int k = 0; k <n; k ++) if (k == m || x [k]! = tecla [k]) return k; volver n;
Al buscar, nos interesan los siguientes casos:
- Un prefijo común puede estar vacío. En este caso, continuaremos buscando recursivamente en el nodo secundario del dado. es decir, pasaremos por la siguiente referencia;
- Si un prefijo común es igual a la cadena x buscada, la búsqueda es exitosa, hemos encontrado el nodo. Ahí es cuando usamos el hecho de que podemos encontrar el final de una cadena, que tiene un símbolo de terminal, solo en la hoja del árbol.
- Un prefijo común es congruente con la clave , pero no es congruente con x . En este caso, iremos recursivamente al nodo padre e hijo usando una referencia de enlace y pasándole una cadena x sin el prefijo encontrado.
Si hemos encontrado el prefijo común, pero no es congruente con la clave , la búsqueda tampoco tiene éxito.
node * find (node * t, char * x, int n = 0) // x búsqueda de teclas en t tree {if (! n) n = strlen (x) +1; si (! t) devuelve 0; int k = prefijo (x, n, t-> clave, t-> len); if (k == 0) devuelve find (t-> siguiente, x, n); // busquemos el nodo del niño if (k == n) return t; if (k == t-> len) devuelve find (t-> link, x + k, nk); // busquemos en el nodo del niño return 0; }
Por defecto, la longitud n de la cadena x es cero, por lo que podríamos llamar a la función de búsqueda especificando una raíz de árbol y una cadena de búsqueda.
… Nodo * p = encontrar (t, “baca”); …
La siguiente imagen muestra el proceso de búsqueda de tres cadenas (una de ellas es exitosa, las otras, no tanto) en el árbol proporcionado arriba.
Debemos tener en cuenta que, en caso de éxito, la función de búsqueda devuelve un puntero a la hoja del árbol, donde finalizó la búsqueda. Este nodo debe contener toda la información conectada con la cadena buscada.
Insertar llaves
Una nueva inserción de clave (así como en la búsqueda binaria) es similar a la búsqueda de clave. Por supuesto, hay algunas diferencias. En primer lugar, en el caso de un árbol vacío, deberíamos crear un nodo (un árbol trivial) con la clave definida y devolver un puntero a este nodo. En segundo lugar, si la longitud de un prefijo común de la clave actual y la cadena x actual es mayor que cero, pero menor que la longitud de la clave (el segundo caso de una búsqueda fallida), deberíamos dividir el nodo actual en dos, dejar el encontró el prefijo en el nodo primario y coloca la parte restante de la clave en el nodo p secundario. Para realizar esta operación, use la función de división . Después de dividir el nodo, continúe insertando una cadena x en un nodo p sin un prefijo encontrado.
El código de división del nodo:
división vacía (nodo * t, int k) // división del nodo t según el símbolo de la clave k {nodo * p = nuevo nodo (t-> clave + k, t-> len-k); p-> enlace = t-> enlace; t-> enlace = p; char * a = nuevo char [k]; strncpy (a, t-> clave, k); eliminar [] t-> clave; t-> clave = a; t-> len = k;}
Código de inserción:
nodo * insert (nodo * t, char * x, int n = 0) // insertando la clave x en el árbol t {if (! n) n = strlen (x) +1; if (! t) devuelve un nuevo nodo (x, n); int k = prefijo (x, n, t-> clave, t-> len); if (k == 0) t-> siguiente = insertar (t-> siguiente, x, n); más si (k <n) {if (k len) // cortar o no cortar? división (t, k); t-> enlace = insertar (t-> enlace, x + k, nk); } return t;}
La siguiente imagen representa la inserción de claves abaca $ y abcd $ en el árbol mencionado anteriormente:
Debe tener en cuenta que si la cadena x dada ya está en el árbol, no se realizará ninguna inserción. En este caso, un árbol de prefijos se comporta como un conjunto adecuado.
Eliminar claves
Como siempre, la eliminación de claves es la operación más difícil. Aunque en caso de intentos, no da tanto miedo. La cuestión es que cuando eliminamos una clave, eliminamos solo un nodo hoja correspondiente a algún sufijo de la clave. Al principio, debemos encontrar este nodo. Si la búsqueda es exitosa, la eliminamos y devolvemos el puntero a la hermana menor del nodo dado (dado que es una hoja, no tiene hijos, pero puede tener hermanas).
En ese momento, podríamos terminar el proceso de eliminación, pero hay un problema. Después de la eliminación del nodo, puede formar una cadena de nodos t y p , en los que el nodo t tiene solo un nodo hijo p . Por lo tanto, si queremos mantener el árbol comprimido, debemos unir estos dos nodos en uno mediante la operación de fusión.
El código de operación de fusión es bastante trivial. Creamos una nueva clave, luego movemos el subárbol de un nodo p a t y eliminamos el nodo p .
combinación vacía (nodo * t) // ty t-> los nodos de enlace fusionan {nodo * p = t-> enlace; char * a = nuevo char [t-> len + p-> len]; strncpy (a, t-> clave, t-> len); strncpy (a + t-> len, p-> clave, p-> len); eliminar [] t-> clave; t-> clave = a; t-> len + = p-> len; t-> enlace = p-> enlace; eliminar p;}
El nodo más antiguo se encarga de fusionarse ya que el más joven no tiene la información sobre su padre. La ejecución de fusión tiene los siguientes criterios:
- Eliminación de claves por referencia de enlace , no a continuación ;
- Después de la eliminación, una nueva referencia de enlace no tiene la siguiente referencia. Solo hay un nodo hijo, por lo que podemos fusionarlo con el actual.
nodo * remove (nodo * t, char * x, int n = 0) // eliminando la clave x del árbol t {if (! n) n = strlen (x) +1; si (! t) devuelve 0; int k = prefijo (x, n, t-> clave, t-> len); if (k == n) // eliminando una hoja {znode * p = t-> next; eliminar t; volver p; } if (k == 0) t-> siguiente = eliminar (t-> siguiente, x, n); de lo contrario if (k == t-> len) {t-> link = remove (t-> link, x + k, nk); if (t-> link &&! t-> link-> next) // ¿tiene t node solo un nodo hermano? articulación); } return t;}
Ejemplos de eliminación de claves sin fusionar:
con fusión:
Eficiencia
Se ha llevado a cabo una investigación computacional sobre la comparación de AVL y árboles de prefijos en cuanto a tiempo de operación y consumo de memoria. En cuanto a mí, el resultado fue un poco desconcertante. De todos modos, vamos paso a paso. Se han formado 8 conjuntos de cadenas de prueba. La siguiente tabla representa sus características:
En primer lugar, midieron el tiempo de construcción de un árbol de acuerdo con el conjunto dado de cadenas y el tiempo para buscar en él todas las claves del mismo conjunto (es decir, búsqueda exitosa solamente). El siguiente gráfico presenta la comparación del árbol de AVL y el tiempo de compilación de un árbol de prefijos (árbol de radix). Puede ver que un árbol de prefijos se acumula un poco más rápido.
El siguiente cuadro compara el tiempo dedicado a buscar en todas las claves los mismos dos árboles. Un árbol binario equilibrado pasa dos veces menos tiempo buscando que un prefijo.
Finalmente, echemos un vistazo a los requisitos de memoria para un símbolo. Los resultados se presentan en el siguiente gráfico:
En promedio, hay alrededor de 2 bytes por símbolo, lo que no está mal. Pero en el caso de las banderas, un árbol de prefijos gasta menos de 1 byte en 1 símbolo (hay muchos prefijos largos comunes).
Por lo tanto, no se ha encontrado ningún ganador. Vale la pena comparar el tiempo de operación de estos dos árboles en cuanto a la cantidad de cadenas. Pero de acuerdo con las tablas proporcionadas anteriormente, no habría nada revolucionario. Por supuesto, también sería interesante comparar estos dos enfoques con tablas hash …
