Problema de etiquetado de listas

Un problema relacionado con la informática.

En informática , el problema de etiquetado de listas implica mantener un conjunto S totalmente ordenado que admita las siguientes operaciones:

• insert(X), que inserta X en el conjunto S;
• delete(X), que elimina X del conjunto S;
• label(X), que devuelve una etiqueta asignada a X sujeta a:
  • label(X) ${\displaystyle \in \{0,1,\ldots ,m-1\}}$
  • ${\displaystyle \forall }$X,Y S, X < Y implica ${\displaystyle \in }$label(X) < label(Y)

El costo de un algoritmo de etiquetado de listas es la cantidad de (re)asignaciones de etiquetas por inserción o eliminación. Los algoritmos de etiquetado de listas tienen aplicaciones en muchas áreas, incluido el problema de mantenimiento del orden , las estructuras de datos que no tienen en cuenta la memoria caché, ^[1] la persistencia de la estructura de datos , ^[2] los algoritmos de gráficos ^{[3] [4]} y las estructuras de datos tolerantes a fallas. ^[5]

En ocasiones, el problema del etiquetado de listas se presenta cuando S no es un conjunto de valores, sino un conjunto de objetos sujetos a un orden total. En este contexto, cuando se inserta un elemento en S, se especifica que sea el sucesor de algún otro elemento que ya se encuentra en S. Por ejemplo, esta es la forma en que se utiliza el etiquetado de listas en el problema de mantenimiento del orden . Las soluciones que se presentan a continuación se aplican a ambas formulaciones.

Límites superiores

El costo del etiquetado de listas está relacionado con , el rango de las etiquetas asignadas. Supongamos que no se almacenan más de elementos en la estructura de etiquetado de listas en ningún momento. Se han estudiado cuatro casos: ${\displaystyle m}$ ${\displaystyle n}$

• ${\displaystyle m=2^{\Omega (n)}}$
• ${\displaystyle m=n^{\Omega (1)}}$
• ${\displaystyle m=O(n)}$
• ${\displaystyle m=(1+\varepsilon )n}$

Etiquetas exponenciales

En el caso de la etiqueta exponencial, a cada elemento que se inserta se le puede asignar una etiqueta que sea el promedio de sus etiquetas vecinas. Se necesitan inserciones antes de que dos elementos estén en etiquetas adyacentes y no haya etiquetas disponibles para los elementos intermedios. Cuando esto sucede, todos los elementos se vuelven a etiquetar de manera uniforme a partir del espacio de todas las etiquetas. Esto genera un costo de reetiquetado. Por lo tanto, el costo de reetiquetado amortizado en este caso es . ^[6] ${\displaystyle \Omega (n)}$ ${\displaystyle O(n)}$ ${\displaystyle O(1)}$

Etiquetas polinómicas

Los otros casos de etiquetado de listas se pueden resolver mediante árboles binarios de búsqueda balanceados . Considere , un árbol binario de búsqueda en S de altura . Podemos etiquetar cada nodo en el árbol mediante una etiqueta de ruta de la siguiente manera: Sea la secuencia de bordes izquierdo y derecho en la ruta de raíz a , codificada como bits. Entonces, si está en el subárbol izquierdo de la raíz, el bit de orden superior de es , y si está en el subárbol derecho de la raíz, el bit de orden superior de es . Una vez que llegamos a , completamos hasta una longitud de de la siguiente manera. Si es una hoja, agregamos s como los bits de orden inferior hasta que tiene bits. Si es un nodo interno, agregamos uno y luego s como los bits de orden inferior hasta que tiene bits. ${\displaystyle T}$ ${\displaystyle h}$ ${\displaystyle \sigma (X)}$ ${\displaystyle X}$ ${\displaystyle X}$ ${\displaystyle \sigma (X)}$ ${\displaystyle 0}$ ${\displaystyle \sigma (X)}$ ${\displaystyle 1}$ ${\displaystyle X}$ ${\displaystyle \sigma (X)}$ ${\displaystyle h+1}$ ${\displaystyle X}$ ${\displaystyle 0}$ ${\displaystyle \sigma (X)}$ ${\displaystyle h+1}$ ${\displaystyle X}$ ${\displaystyle 0}$ ${\displaystyle 1}$ ${\displaystyle \sigma (X)}$ ${\displaystyle h+1}$

Las propiedades importantes de son que: estas etiquetas están en el rango ; y para dos nodos con claves y en si entonces . Para ver esta última propiedad, observe que la propiedad es verdadera si el ancestro mínimo común de y no es ni , porque y compartirán bits hasta su ancestro mínimo común. Si , entonces porque es un árbol de búsqueda, estará en el subárbol izquierdo y tendrá un siguiente bit de , mientras que estará en el subárbol derecho y tendrá un siguiente bit de . ${\displaystyle \sigma ()}$ ${\displaystyle \{0,1,\ldots ,2^{h+1}-1\}}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle T,}$ ${\displaystyle X<Y,}$ ${\displaystyle \sigma (X)<\sigma (Y)}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle \sigma (X)}$ ${\displaystyle \sigma (Y)}$ ${\displaystyle X<Y}$ ${\displaystyle T}$ ${\displaystyle X}$ ${\displaystyle 0}$ ${\displaystyle Y}$ ${\displaystyle 1}$

Supongamos en cambio que, sin pérdida de generalidad, el ancestro menos común de y es , y que tiene profundidad . Si está en el subárbol izquierdo de , entonces y comparten los primeros bits. Los bits restantes de son todos 1, mientras que los bits restantes de deben tener un , por lo que . Si en cambio está en el subárbol derecho de , entonces y comparten los primeros bits y el primer bit de es , mientras que el primer bit de es . Por lo tanto . ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle X}$ ${\displaystyle X}$ ${\displaystyle d}$ ${\displaystyle Y}$ ${\displaystyle X}$ ${\displaystyle \sigma (X)}$ ${\displaystyle \sigma (Y)}$ ${\displaystyle d+1}$ ${\displaystyle \sigma (X)}$ ${\displaystyle \sigma (Y)}$ ${\displaystyle 0}$ ${\displaystyle \sigma (Y)<\sigma (X)}$ ${\displaystyle Y}$ ${\displaystyle X}$ ${\displaystyle \sigma (X)}$ ${\displaystyle \sigma (Y)}$ ${\displaystyle d}$ ${\displaystyle d+1}$ ${\displaystyle \sigma (X)}$ ${\displaystyle 0}$ ${\displaystyle d+1}$ ${\displaystyle \sigma (Y)}$ ${\displaystyle 1}$ ${\displaystyle \sigma (X)<\sigma (Y)}$

Concluimos que la función cumple con la propiedad de monotonía de la función. Por lo tanto, si podemos equilibrar el árbol binario a una profundidad de , tendremos una solución al problema de etiquetado de listas para las etiquetas en el rango . ${\displaystyle \sigma ()}$label() ${\displaystyle (\log m)-1}$ ${\displaystyle \{0,\ldots ,m-1\}}$

Árboles con peso equilibrado

Para utilizar un árbol binario de búsqueda autoequilibrado para resolver el problema de etiquetado de listas, primero debemos definir la función de costo de una operación de equilibrio en la inserción o eliminación para que sea igual al número de etiquetas que se cambian, ya que cada operación de reequilibrio del árbol también tendría que actualizar todas las etiquetas de ruta en el subárbol con raíz en el sitio del reequilibrio. Entonces, por ejemplo, rotar un nodo con un subárbol de tamaño , lo que se puede hacer en tiempo constante en circunstancias normales, requiere actualizaciones de etiquetas de ruta. En particular, si el nodo que se rota es la raíz, entonces la rotación tomaría un tiempo lineal en el tamaño de todo el árbol. Con ese tiempo, se podría reconstruir todo el árbol. Veremos a continuación que hay estructuras de datos de árboles binarios de búsqueda autoequilibrados que causan una cantidad apropiada de actualizaciones de etiquetas durante el reequilibrio. ${\displaystyle k}$ ${\displaystyle \Omega (k)}$

Un árbol con equilibrio de peso BB[ ] se define de la siguiente manera. Para cada en un árbol raíz , defina como el número de nodos en el subárbol con raíz en . Sean los hijos izquierdo y derecho de y , respectivamente. Un árbol está equilibrado en peso si para cada nodo interno en , y ${\displaystyle \alpha }$ ${\displaystyle X}$ ${\displaystyle T}$ ${\displaystyle size(X)}$ ${\displaystyle X}$ ${\displaystyle X}$ ${\displaystyle X.left}$ ${\displaystyle X.right}$ ${\displaystyle T}$ ${\displaystyle \alpha }$ ${\displaystyle X}$ ${\displaystyle T}$ ${\displaystyle size(X.left)\geq \lfloor \alpha \cdot size(X.right)\rfloor }$ ${\displaystyle size(X.right)\geq \lfloor \alpha \cdot size(X.left)\rfloor .}$

La altura de un árbol BB[ ] con nodos es como máximo Por lo tanto, para resolver el problema de etiquetado de listas, necesitamos lograr una profundidad de ${\displaystyle \alpha }$ ${\displaystyle n}$ ${\displaystyle \log _{1/(1-\alpha )}n=-\log(n)/\log(1-\alpha ).}$ ${\displaystyle \alpha =1-1/(1-n^{-1/(\log(m)-1)})}$ ${\displaystyle \log(m)-1.}$

Un árbol de chivo expiatorio es un árbol con equilibrio de peso en el que, siempre que un nodo ya no satisface la condición de equilibrio de peso, se reconstruye todo el subárbol con raíz en ese nodo. Este esquema de reequilibrio es ideal para el etiquetado de listas, ya que el costo del reequilibrio ahora es igual al costo del reetiquetado. El costo amortizado de una inserción o eliminación es Para el problema de etiquetado de listas, el costo se convierte en: ${\displaystyle (1+1/(1-2\alpha ))\log _{1/1-\alpha }n+O(1).}$

• ${\displaystyle m=n^{\Omega (1)}}$: , el coste del etiquetado de las listas se amortiza (Folklore, modificación de Itai, Konheim y Rodeh. ^[7] ) ${\displaystyle \alpha =O(1)}$ ${\displaystyle O(\log n).}$
• ${\displaystyle m=O(n)}$: , el costo del etiquetado de listas se amortiza. Este límite fue alcanzado por primera vez por Itai, Konheim y Rodeh ^[7] y desamortizado por Willard. ^[8] ${\displaystyle \alpha =1+\Theta (1/\log n)}$ ${\displaystyle O(\log ^{2}n).}$
• ${\displaystyle m=(1+\varepsilon )n}$: Si es una potencia de dos, entonces podemos establecer , y el costo del etiquetado de la lista es . Un algoritmo más cuidadoso puede lograr este límite incluso en el caso en que no sea una potencia de dos. ${\displaystyle m}$ ${\displaystyle \alpha =1+\Theta (\varepsilon /\log n)}$ ${\displaystyle O(\varepsilon ^{-1}\log ^{2}n)}$ ${\displaystyle m}$

Límites inferiores y problemas abiertos

En el caso en que se ha establecido un límite inferior de ^{[9] para el etiquetado de listas. Este límite inferior se aplica a algoritmos aleatorios, por lo que los límites conocidos para este caso son estrictos.} ${\displaystyle m=n^{1+\Theta (1)}}$ ${\displaystyle \Omega (\log n)}$

En el caso donde , hay un límite inferior del costo de etiquetado de lista para algoritmos deterministas. ^[6] Además, el mismo límite inferior se aplica a algoritmos suaves , que son aquellos cuya única operación de reetiquetado asigna etiquetas de manera uniforme en un rango de elementos ^[10] Este límite inferior es sorprendentemente fuerte ya que se aplica en los casos fuera de línea donde todas las inserciones y eliminaciones se conocen de antemano. ${\displaystyle m={(1+\Theta (1))}n}$ ${\displaystyle \Omega (\log ^{2}n)}$

Sin embargo, el mejor límite inferior conocido para el caso lineal de algoritmos que pueden ser no suaves y aleatorios es . De hecho, ha sido un problema abierto desde 1981 cerrar la brecha entre el límite superior y el en el caso lineal. ^{[7] [11]} Bender et al. han logrado algunos avances en este problema y dan un límite superior aleatorio de . ^[12] ${\displaystyle \Omega (\log n)}$ ${\displaystyle O(\log ^{2}n)}$ ${\displaystyle \Omega (\log n)}$ ${\displaystyle O(\log ^{1.5}n)}$

Aplicaciones

Las aplicaciones más conocidas del etiquetado de listas son el problema de mantenimiento del orden y las matrices de memoria empaquetada para estructuras de datos que no tienen en cuenta la memoria caché . El problema de mantenimiento del orden consiste en mantener una estructura de datos en una lista enlazada para responder a consultas de orden: dados dos elementos en la lista enlazada, ¿cuál está más cerca del principio de la lista? Este problema se puede resolver directamente mediante el etiquetado de listas polinomiales por inserción y eliminación y tiempo por consulta, asignando etiquetas que sean monótonas con el rango en la lista. El tiempo para inserciones y eliminaciones se puede mejorar a tiempo constante combinando el etiquetado de listas polinomiales exponenciales con el etiquetado de listas exponenciales en listas pequeñas. ${\displaystyle O(\log n)}$ ${\displaystyle O(1)}$

La matriz de memoria empaquetada es una matriz de tamaño para almacenar elementos de modo que cualquier submatriz de tamaño contenga elementos. Esto se puede resolver directamente mediante el caso del etiquetado de listas, utilizando las etiquetas como direcciones en la matriz, siempre que la solución garantice que el espacio entre los elementos sea . Las matrices de memoria empaquetada se utilizan en estructuras de datos que no tienen en cuenta la memoria caché para almacenar datos que deben indexarse ​​y escanearse. Los límites de densidad garantizan que un escaneo a través de los datos sea asintóticamente óptimo en el modelo de memoria externa para cualquier tamaño de transferencia de bloques. ${\displaystyle (1+\varepsilon )n}$ ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle \Theta (k)}$ ${\displaystyle m=(1+\varepsilon )n}$ ${\displaystyle O(1)}$

Referencias

1. Bender, Michael A. ; Demaine, Erik D. ; Farach-Colton, Martin (2005), "Árboles B ajenos a la memoria caché" (PDF) , SIAM Journal on Computing , 35 (2): 341–358, doi :10.1137/S0097539701389956, MR  2191447.
2. Driscoll, James R.; Sarnak, Neil; Sleator, Daniel D .; Tarjan, Robert E. (1989), "Hacer que las estructuras de datos sean persistentes", Journal of Computer and System Sciences , 38 (1): 86–124, doi : 10.1016/0022-0000(89)90034-2 , MR  0990051.
3. Eppstein, David ; Galil, Zvi ; Italiano, Giuseppe F. ; Nissenzweig, Amnon (1997), "Esparcimiento: una técnica para acelerar los algoritmos de gráficos dinámicos", Journal of the ACM , 44 (5): 669–696, doi : 10.1145/265910.265914 , MR  1492341, S2CID  263324404.
4. Katriel, Irit; Bodlaender, Hans L. (2006), "Ordenamiento topológico en línea", ACM Transactions on Algorithms , 2 (3): 364–379, CiteSeerX 10.1.1.78.7933 , doi :10.1145/1159892.1159896, MR  2253786, S2CID  6552974 .
5. Aumann, Yonatan; Bender, Michael A. (1996), "Estructuras de datos tolerantes a fallos", Actas del 37.º Simposio anual sobre fundamentos de la informática (FOCS 1996) , págs. 580-589, doi :10.1109/SFCS.1996.548517, ISBN 978-0-8186-7594-2, S2CID80348 ​.
6. Bulánek, Jan; Koucký, Michal; Saks, Michael E. (2015), "Límites inferiores estrictos para el problema del etiquetado en línea", SIAM Journal on Computing , vol. 44, págs. 1765–1797.
7. Itai, Alon; Konheim, Alan G.; Rodeh, Michael (1981), "Una implementación de colas de prioridad mediante tablas dispersas", ICALP , págs. 417–431
8. Willard, Dan E. (1992), "Un algoritmo de control de densidad para realizar inserciones y eliminaciones en un archivo ordenado secuencialmente en el peor de los casos", Información y computación , vol. 97, págs. 150-204.
9. Dietz, Paul F.; Seiferas, Joel I.; Zhang, Ju (1994), "Un límite inferior ajustado para el etiquetado de listas monótonas en línea", Algorithm theory—SWAT '94 (Aarhus, 1994) , Lecture Notes in Computer Science, vol. 824, Berlín: Springer, págs. 131–142, doi :10.1007/3-540-58218-5_12, ISBN 978-3-540-58218-2, Sr.  1315312.
10. Dietz, Paul F.; Zhang, Ju (1990), "Límites inferiores para el etiquetado de listas monótonas", Teoría de algoritmos—SWAT '90 , págs. 173-180.
11. Saks, Michael (2018), "Etiquetado en línea: algoritmos, límites inferiores y preguntas abiertas", Simposio internacional de informática en Rusia , págs. 23-28.
12. Bender, Michael A.; Conway, Alex; Farach-Colton, Martin; Komlos, Hanna; Kuszmaul, William; Wein, Nicole (octubre de 2022). "Etiquetado de listas en línea: rompiendo la barrera log2n". 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS) . IEEE. págs. 980–990. arXiv : 2203.02763 . doi :10.1109/focs54457.2022.00096. ISBN 978-1-6654-5519-0.S2CID247292594  .​