Diferencias

Muestra las diferencias entre dos versiones de la página.

--- algoritmos-oia:trie [2017/12/13 00:08]
roman Primera edición - sin concluir
+++ algoritmos-oia:trie [2017/12/14 00:14] (actual)
roman Agregados algunos problemas y mejoras - página aún en construcción
@@ Línea 1: / Línea 1: @@
 ======= EN CONSTRUCCIÓN =======
+FIXME
 ====== Trie ======
 ===== Idea intuitiva =====
@@ Línea 63: / Línea 64: @@
 struct trie{
     map<char, trie> m;  // arcos
-    bool final = false; // una palabra termina en este nodo?
+    bool final = false; // ¿una palabra termina en este nodo?
     void agregar(char *s){
@@ Línea 109: / Línea 110: @@
 </file>
-Esta implementación está buena como primera idea porque es simple. Sin embargo, realiza demasiadas llamadas a función, lo cual realentiza nuestro programa. También, al buscar un nodo, me devuelve un puntero a él. Usar punteros puede no ser muy estratégico en ámbitos de competencia. A continuación se provee de una implementación iterativa que es más rápida y no usa punteros.
+Esta implementación está buena como primera idea porque es simple. Sin embargo, realiza demasiadas llamadas a función, lo cual realentiza nuestro programa. También, al buscar un nodo, devuelve un puntero a él. Usar punteros puede no ser una idea muy estratégica en ámbitos de competencia. A continuación se provee de una implementación iterativa que es más rápida y no usa punteros.
 ==== La iterativa ====
@@ Línea 123: / Línea 124: @@
 int proximo_libre;
-int sig[maxn][26]; // arcos (en este caso solo letras mayusculas)
+int sig[maxn][26]; // arcos (en este caso sólo letras mayusculas)
-bool final[maxn];  // una palabra termina en este nodo?
+bool final[maxn];  // ¿una palabra termina en este nodo?
 void agregar(const string &s, int raiz = 0){
@@ Línea 162: / Línea 163: @@
 int main(){
-    memset(sig, -1, sizeof(sig)); // seteamos en -1 todos los arcos
+    memset(sig, -1, sizeof(sig)); // seteamos en -1 todos los arcos para indicar que no existen
     agregar("CASA");
@@ Línea 206: / Línea 207: @@
 ==== String sorting en tiempo lineal ====
-Tomemos la lista de palabras que se quiere ordenar e ingresémosla en un trie. Un recorrido DFS que visita los arcos en orden alfabético recorrerá las palabras lexicográficamente. Recorrer los arcos en sentido inverso para ordenar las palabras en sentido contrario.
+Esto no es una mejora //per se,// pero muestra muy bien cómo se organizan las palabras dentro de un trie.\\ Tomemos la lista de palabras que se quiere ordenar e ingresémosla en un trie. Un recorrido DFS que visita los arcos en orden alfabético recorrerá las palabras lexicográficamente. Recorrer los arcos en sentido inverso para ordenar las palabras en sentido contrario.
 ==== Contador de prefijos ====
@@ Línea 217: / Línea 218: @@
   agregar("CASERO");
-  cuentaPrefijos("CA") --> 4
+  cuentaPrefijos("CA")   --> 4
   cuentaPrefijos("CASE") --> 1
   cuentaPrefijos("CASO") --> 0
+==== Puntero al siguiente nodo final ====
+Una vez construido el trie, un recorrido postorden en orden inverso nos permite calcular en una sola pasada para cada nodo cuál es el siguiente nodo final. Podemos mejorar así nuestra estructura trie agregando un campo ''sig'' a cada nodo. A continuación un pseudocódigo:
+  nodo calcularSiguiente(nodo yo, nodo s){
+      for(cada hijo en orden inverso)
+          s = calcularSiguiente(hijo, s);
+      yo.sig = s;
+      if( yo.final ) return yo
+      else           return yo.sig;
+  }
+y computamos los siguientes para todo el trie así: ''calcularSiguiente(raiz, NULL)''.
 ==== Trie de sufijos ====
   * Ejercicio: Dibujar el trie que contiene la palabra "CAMISA", y dibujar otro trie que contiene las palabras "CAMISA", "CAMIS", "CAMI", "CAM", "CA", y "C".
-Ambos son el mismo trie, ¿no? Esto es porque al ingresar una palabra, también ingresamos todos sus **prefijos.** La única diferencia es que en el primer caso, sólo un nodo es final, mientras que en el segundo todos los nodos son finales. Podemos escribir una función ''agregarPrefijos'' que sea exactamente igual a "agregar" pero que vaya marcando todos los nodos como finales. ¡Y mantenemos la complejidad $O(k)$!
+Ambos son el mismo trie, ¿no? Esto es porque al ingresar una palabra, también ingresamos todos sus **prefijos.** La única diferencia es que en el primer caso, sólo un nodo es final, mientras que en el segundo todos los nodos son finales. Podemos escribir una función ''agregarPrefijos'' que sea exactamente igual a //agregar// pero que vaya marcando todos los nodos como finales. ¡Y mantenemos la complejidad $O(k)$!
 Por lo tanto, si queremos insertar todos los substrings de un texto de longitud $T$, sólo necesitamos //agregarPrefijos// de sus $T$ **sufijos**, que tarda $O(T^2)$ en total. Una vez construido este trie de sufijos, muchas operaciones pueden realizarse eficientemente:
-=== String matching en $O(S)$ ===
+=== Cantidad de apariciones de un string $S$ en $O(S)$ ===
 Si tenemos un string $S$, la cantidad de apariciones en el texto es simplemente ''cuentaPrefijos(S)'' en el trie de sufijos.
-Adicionalmente, si en cada inserción además de marcar el nodo como final, guardamos el índice del substring, un recorrido del subtrie cuya raiz se corresponde a $S$ nos arrojará todos los índices en los cuales aparece $S$ con costo adicional $O(A)$ donde $A$ es la cantidad de apariciones.
+Adicionalmente, si en cada inserción además de marcar el nodo como final, guardamos el índice del substring y un puntero al siguiente nodo final, un recorrido de los nodos finales del subtrie cuya raiz se corresponde a $S$ nos arrojará todos los índices en los cuales aparece $S$ con costo adicional $O(A)$ donde $A$ es la cantidad de apariciones.
 === Substring más largo que se repite al menos $K$ veces en $O(T^2)$ ===
-Consideremos un recorrido ''DFS'' en el trie de sufijos. Un nodo de profundidad $l$ se corresponde con un string de largo $l$. Por lo que recorreremos el trie buscando un nodo de profundidad máxima cuyo contador sea mayor o igual a $K$.
+Consideremos un recorrido ''DFS'' en el trie de sufijos. Un nodo de profundidad $l$ se corresponde con un string de largo $l$, y el contador de un nodo indica cuántas veces aparece la palabra correspondiente a dicho nodo en el trie. Por lo que recorreremos el trie buscando un nodo de profundidad máxima cuyo contador sea mayor o igual a $K$.
 === Substring más largo que aparezca en al menos $K$ de $N$ palabras, en tiempo cuadrático ===
@@ Línea 244: / Línea 259: @@
 El costo de construcción de este trie de prefijos común es $O(s_1^2 + \dots + s_n^2)$, por lo que es cuadrático.
+==== Palabra más cercana ====
+Supongamos el siguiente problema: Tenemos dos palabras, de longitudes $N$ y $M$ respectivamente. Su distancia es la mínima cantidad de inerciones, reemplazos y eliminaciones para convertir la primera en la segunda. Por ejemplo, la distancia entre "PERRO" y "ERDOS" es 3: una inserción (S), un reemplazo (R->D) y un borrado (P).
+Cmo ya es sabido, la solución a este problema puede encontrarse mediante Programación Dinámica en tiempo $O(NM)$ rellenando una tabla.
+|^ ^E^R^D^O^S^
+^|0|1|2|3|4|5|
+^P|1|1|2|3|4|5|
+^E|2|1|2|3|4|5|
+^R|3|2|1|2|3|4|
+^R|4|3|2|2|3|4|
+^O|5|4|5|3|2|**3**|
+Pero qué pasaría si en lugar de querer calcular la distancia entre dos palabras, quisiera -dada una palabra fija $w$- encontrar otra palabra $w'$ perteneciente a un diccionario de tamaño $N$ cuya distancia $d(w,w')$ sea mínima?
+Repetir el algoritmo para cada palabra no sería muy útil, ya que estaríamos recalculando muchas veces la misma información. Consideremos que ahora, en lugar de comparar con "PERRO", queremos comparar con "PERROS". ¡La tabla que ya tengo armada me sirve! sólo tengo que agregar una fila adicional. Los tries son perfectos para esto ya que me dicen exactamente los prefijos en común entre varias palabras, que se reflejan en filas de mi tabla que no tengo que volver a recalcular.
 ==== Puntero al padre ====
-Consiste en guardar en cada nodo, cuál es su padre. Esto permite moverse en cualquier dirección dentro del trie, lo cual nos será útil en la siguiente mejora:
+Consiste en guardar en cada nodo, cuál es su padre. Es una mejora muy simple agregando una línea extra a la función agregar. Esto nos permite movernos en cualquier dirección dentro del trie, lo cual nos será útil en la siguiente mejora:
 ==== Trie de cosas locas ====
-En lugar de etiquetar los arcos con letras, se los puede etiquetar con cualquier otra cosa, por ejemplo: enteros. Si la cantidad de etiquetas distintas -llamémosla $E$- no está acotada, quizás haya que usar un ''map<int, trie>'' a costa de un $O(\log E)$ adicional.
+En lugar de etiquetar los arcos con letras, se los puede etiquetar con cualquier otra cosa, por ejemplo: enteros. Si la cantidad de etiquetas distintas -llamémosla $E$- no está acotada, quizás haya que usar un ''map<int, trie>'' a costa de un $O(\log E)$ adicional. Como la cantidad de arcos que salen de un nodo no suele ser muy grande, algunas veces es más rápido guardar un ''vector'' o un array pequño de arcos y hacer una búsqueda lineal.
 ==== Stack persistente ====
@@ Línea 268: / Línea 301: @@
   * ''push_persistente(s, x)'': insertar un arco y un nodo ''s''' con etiqueta x, luego la nueva pila es ''s'''.
+  * ''top()'': es el valor almacenado en ''s''
   * ''pop_persitente(s)'': sea ''s''' el padre de ''s'', la nueva pila es ''s'''.
-¡Estas operaciones persistentes siguen siendo constantes! $O(1)$
+¡Estas operaciones persistentes siguen siendo constantes! ((a menos que se use map<int, trie>)) $O(1)$
 ==== Trie binario ====
+Cuando pensamos en tries, pensamos en strings. Sin embargo, no hay que olvidarse que los enteros pueden pensarse también como strings binarios al mirar su representación en base 2. Así, 13 = "0...01101" con tantos 0 a la izquierda como queramos. Es útil como estructura de diccionario porque este tipo de trie siempre está balanceado, su altura es $O($//cantidad de bits de las claves//$)$.
 ----------
@@ Línea 277: / Línea 314: @@
 ===== Problemas =====
+=== OIA Nacional 2014 N2 - Verificando contraseñas ===
+Dado un diccionario de palabras, indicar para cada una cuántas otras palabras del diccionario son prefijos de ella.
+=== OIA Selectivo 2009 - Formando equipo ===
+Se tiene un diccionario con palabras. La afinidad $a$ de un subconjunto $S$ de palabras se define como $a =|S|\cdot p^2$ donde $|S|$ es la cantidad de palabras de $S$ y $p$ es el largo del prefijo común más largo a todas las palabras de $S$.
+Hallar la afinidad máxima posible y el prefijo común más largo asociado.
+=== UVa 12526 - Cellphone Typing ===
+Se tiene un diccionario de palabras y un teléfono viejo con predicción de palabra. El sistema de predicción es simple:
+  * El sistema nunca adivina la primer leta de una palabra, se debe presionar una tecla manualmente
+  * Si se ingresan letras $c_1c_2..c_r$ y **todas** las palabras que comienzan por $c_1c_2..c_r$ continúan con $c_{r+1}c_{r+2}..c_n$, entonces el sistema autocompleta la palabra a $c_1c_2..c_n$. Por ejemplo, si el diccionario es: "CAMARERO", "CAMARA", y "PLAYA", y el usuario ingresa "C", el sistema automáticamente completa a "CAMAR".
+Se quiere saber cuántas pulsasiones de teclas en promedio hay que apretar para escribir alguna palabra del diccionario. En nuestro pequeño ejemplo, 1.66 = (2 + 2 + 1).
+=== IOI 2008 - Type Printer ===
+Se dispone de una máquina de imprenta antigua que funciona poniendo manualmente piezas metálicas con letras para formar palabras. Una vez formada una palabra, se presiona contra un papel (cual sello) para imprimir. La imprenta permite realizar alguna de las siguientes operaciones:
+  * agregar una letra metálica al final de la palabra actual
+  * eliminar una letra metálica del final de la palabra actual
+  * imprimir la palabra formada por las piezas actualmente en la máquina
+Se dispone de un diccionario de palabras que se quiere imprimir al completo (no importa el orden). Inicialmente la imprenta está vacía. Como cada operación demora su tiempo, se quiere saber la menor cantidad de operaciones en las cuales es posible realizar la tarea.
+=== IOI 2012 - Scrivener ===
+Se dispone de una imprenta cangrejo: una máquina que soporta los siguientes comandos:
+  * agregar(L) : agrega una L metálica al final de la palabra actual
+  * deshacer(U) : deshace los últimos U comandos (inclusive los deshacer)
+Adicionalmente, también soporta la siguiente operación:
+  * imprimir(P) : imprime la p-ésima letra de la palabra actual. Esta operación no es un comando y por ende es ignorada por el comando deshacer
+^ Operación ^ Devuelve ^ Palabra actual|
+|agregar( a )| |a|
+|agregar( b )| |ab|
+|imprimir( 1 )|b|ab|
+|agregar( d )| |abd|
+|deshacer( 2 )| |a|
+|deshacer( 1 )| |abd|
+|imprimir( 2 )|d|abd|
+|agregar( e )| |abde|
+|deshacer( 1 )| |abd|
+|deshacer( 5 )| |ab|
+|agregar( c )| |abc|
+|imprimir( 2 )|c|abc|
+|deshacer( 2 )| |abd|
+|imprimir( 2 )|d|abd|
+Se te pide que hagas una simulación por software de la imprenta cangrejo.
+=== Codeforces Round #260 - A Lot of Games ===
+Se tiene un listado de palabras. Dos personas, A y B juegan al siguiente juego sobre un renglón de una hoja de papel:
+  * al principio, el renglón está vacío
+  * el juego es por turnos, comienza A
+  * cada jugada consiste en agregar una letra al final de la palabra, la jugada es válida si la palabra formada es un prefijo de alguna de las palabras del listado.
+  * aquel que no pueda jugar, pierde
+Si ambos jugadores juegan óptimamente, ¿quién gana?
+=== tries y xor ===
 max xor pair from set
 max xor subarray
 number of subarrays with xor less than K
-tries in game theory
-IOI 2008 type printer
-IOI 2012 scrivener
-OIA formando equipo
-??? cellphone prediction
 DP + trie

OIA-Wiki

Herramientas de usuario

Herramientas del sitio

Diferencias

Herramientas de la página