Árboles de búsqueda óptimos

Nuestro problema se puede describir como: encontrar un árbol de búsqueda para $A$ donde la profundidad promedio de una hoja sea $H$. Note que cada árbol de búsqueda que podamos diseñar sobre $A$ corresponde a un algoritmo, o a una estrategia, de búsqueda, mientras que cada búsqueda en concreto es un camino de comparaciones desde la raíz hasta la hoja correspondiente.

Algoritmos de Huffman y Hu-Tucker

El problema de, dado un conjunto de probabilidades $p_i$, encontrar el árbol binario que minimice $\sum p_i \ell_i$, donde $\ell_i$ es la profundidad de la hoja de probabilidad $p_i$, es conocido en compresión. Una estrategia que entrega el árbol óptimo es el algoritmo de Huffman, que puede describirse de la siguiente forma.

1. Crear un bosque con $n$ árboles, cada uno consistente de un único nodo $(u_i)$ de peso $w = p_i$.
2. Tomar los dos árboles $T_1$ y $T_2$ del bosque con menor peso, sean $w_1$ y $w_2$ esos pesos, y colocarlos como hijos izquierdo y derecho de un nuevo nodo.
3. Sacar $T_1$ y $T_2$ del bosque, y agregar el nuevo árbol, con peso $w_1+w_2$.
4. Volver al punto 2 a menos que el bosque contenga un solo árbol.

El árbol final que entrega este algoritmo tiene la propiedad de que minimiza $L = \sum p_i \ell_i$, y además puede demostrarse que $H \le L < H+1$, es decir, la profundidad promedio de las hojas es menos que la entropía más 1.

Antes de continuar, ¿cuánto tiempo requiere este algoritmo? Es fácil ver que se puede hacer en tiempo $O(n\log n)$, mediante almacenar los pesos de los árboles en una cola de prioridad, implementada por ejemplo con un heap. Se crea con $n$ elementos en tiempo $O(n)$ y luego se realizan $2n$ extracciones y $n$ reinserciones. ¿Puede hacerse mejor? No se sabe en general, pero si los elementos ya vienen ordenados por probabilidad, entonces puede hacerse en tiempo $O(n)$. Ponga los $n$ nodos iniciales en una cola, y prepare otra cola vacía de tamaño $n-1$ para encolar los árboles nuevos que va produciendo. Esta nueva cola también estará ordenada porque los pesos de los árboles que se van generando son siempre crecientes. Entonces, cuando tenga que extraer los dos nodos de peso mínimo, extráigalos de cualquiera de las dos colas (uno de cada una o los dos de una cola, según dónde estén los menores).

De todos modos, ¿el árbol de Huffman sirve como árbol de búsqueda? Supongamos $A[1,3]$ con probabilidades $p_1 = p_3 = \frac{1}{4}$ y $p_2 = \frac{1}{2}$. El árbol de Huffman tendrá un hijo de la raíz para la hoja $A[2]$ y el otro será un nodo interno, con hijos hoja para $A[1]$ y $A[3]$. No es posible hacer una comparación tipo "¿$A[i] \le x$?" para separar $A[2]$ de $A[1]$ y $A[3]$. La razón es que el algoritmo de Huffman desordena las hojas, por lo cual no necesariamente entrega un árbol de búsqueda.

Existe un algoritmo que entrega el mejor árbol posible sin desordenar las hojas, toma tiempo $O(n\log n)$ y garantiza que $H \le L < H+2$. Se llama algoritmo de Hu-Tucker. Esto significa que existe un algoritmo de búsqueda para arreglos ordenados que realiza en promedio menos de $2$ comparaciones por encima de la cota inferior de Teoría de la Información.

En realidad, podemos demostrar que la cota $H$ no es ajustada, y que lo más cercano ajustado es, precisamente, $H+2$. Considere $A[1,3]$ con probabilidades $p_1=p_3=\epsilon$ y $p_2 = 1-2\epsilon$, para $\epsilon>0$ tan pequeño como se quiera. Entonces vale $H=2\epsilon \log_2 \frac{1}{\epsilon} + (1-2\epsilon)\log_2 \frac{1}{1-2\epsilon}$, el cual tiende a cero cuando $\epsilon \rightarrow 0$. Sin embargo, el mejor árbol de búsqueda posible tiene al nodo $A[2]$ a profundidad $2$ y un costo promedio de búsqueda $2(1-2\epsilon) + 3\epsilon$, que tiende a $2$ cuando $\epsilon \rightarrow 0$.

No describiremos el algoritmo de Hu-Tucker en este apunte, por ser demasiado complicado y alejarse demasiado de nuestro tema principal. En cambio, veremos un algoritmo más costoso que resuelve un problema más general.

Construcción general

Consideremos un modelo distinto, en que procedemos por comparaciones pero éstas pueden ser $<$, $=$, ó $>$. Esto significa que podemos detenernos en un nodo interno del árbol de búsqueda si encontramos el elemento que buscamos. En este caso, en vez de comparaciones, contaremos la cantidad de accesos a $A$.

Para generalizar, supondremos que las búsquedas pueden ser exitosas o infructuosas. Una búsqueda exitosa encuentra lo que busca en el elemento $A[i]$ del arreglo, el cual se busca con probabilidad $p_i$. Una búsqueda infructuosa no encuentra lo que busca, sino que determina que debería estar entre los elementos $A[i]$ y $A[i+1]$ del arreglo, suponiendo implícitamente que $A[0] = -\infty$ y $A[n+1] = +\infty$. Diremos que esta búsqueda ocurre con probabilidad $q_i$. Tenemos entonces $\sum_{i=1}^n p_i + \sum_{j=0}^n q_j = 1$.

El árbol de búsqueda se puede ver entonces como un árbol de $n$ nodos donde los nodos internos representan la lectura de un elemento, y entendemos que, si buscamos ese elemento, la búsqueda termina allí. Los $n+1$ punteros a nulo que salen de las hojas son las búsquedas infructuosas, cuyos resultados se deducen sólo al final del camino hacia una hoja. El costo de una búsqueda exitosa, medido en cantidad de accesos a $A$, es la profundidad del nodo interno correspondiente, y el de una búsqueda infructuosa es la profundidad del nodo hoja correspondiente (y es igual a la búsqueda exitosa para ese nodo). Nuestro modelo anterior se puede simular suponiendo un arreglo de tamaño $n-1$, cuyas $n-1$ búsquedas exitosas tienen probabilidad $p_i=0$, y sólo existen búsquedas infructuosas (que terminan en hojas).

Podemos construir el árbol binario óptimo para este problema mediante programación dinámica. Llamemos

$P_{i,j} ~=~ q_{i-1} + p_i + q_i + \ldots + p_j + q_j$

a la probabilidad de que la búsqueda recaiga sobre el rango $A[i,j]$, incluyendo las búsquedas infructuosas en sus extremos. Entonces, el costo óptimo para buscar en $A[i,j]$ se puede encontrar como $C_{i,i-1} = 0$ (arreglo vacío, búsqueda infructuosa), $C_{i,i} = 1$ (arreglo de 1 elemento, búsqueda exitosa o infructuosa), y, para $i<j$,

$$C_{i,j} ~=~ 1 + \min_{i \le k \le j} \frac{P_{i,k-1}}{P_{i,j}} \cdot C_{i,k-1} ~+~ \frac{P_{k+1,j}}{P_{i,j}} \cdot C_{k+1,j},$$

donde $k$ representa la raíz que elijamos para este subárbol de búsqueda, es decir, el elemento de $A$ sobre el que haremos la primera comparación. Debemos registrar dónde queda esta raíz, para luego poder reconstruir el árbol:

$$r(i,j) ~=~ \textrm{arg}\min_{i \le k \le j} \frac{P_{i,k-1}}{P_{i,j}} \cdot C_{i,k-1} ~+~ \frac{P_{k+1,j}}{P_{i,j}} \cdot C_{k+1,j}.$$

Una vez calculadas estas dos matrices (por ejemplo por diagonales, partiendo de la diagonal principal y la que está bajo ella, y progresando hasta la diagonal de largo 1 de la celda $C_{1,n}$), tendremos en $C_{1,n}$ el costo promedio de la búsqueda usando la mejor estrategia posible, y en $r(1,n)$ la raíz que debemos usar para esa estrategia (es decir, debemos partir examinando la celda $A[r(1,n)]$). El hijo izquierdo debe tener raíz $r(1,r(1,n)-1)$ y el derecho $r(r(1,n)+1,n)$, y así sucesivamente.

Note que, si bien el árbol final requiere de solamente $O(n)$ espacio, necesitamos $O(n^2)$ espacio para encontrarlo usando programación dinámica. El tiempo para calcular la matriz $P$ es también $O(n^2)$, pues cada celda puede calcularse con $P_{i,i-1} = q_{i-1}$ y luego $P_{i,j} = P_{i,j-1}+p_j+q_j$ para todo $j \ge i$. En cambio, las matrices $C$ y $r$ requieren tiempo $O(n^3)$, pues deben considerarse todos los $j-i+1$ posibles valores de $k$.

Cuando los costos de acceso son iguales (unitarios, en nuestro modelo), es posible calcular $C$ y $r$ en tiempo $O(n^2)$, mediante usar la importante propiedad (que no demostraremos en este apunte) de que

$r(i,j-1) ~\le~ r(i,j) ~\le~ r(i+1,j).$

Eso significa que podemos reescribir la fórmula para calcular las celdas $C_{i,j}$ como

$$C_{i,j} ~=~ 1 + \min_{r(i,j-1) \le k \le r(i+1,j)} \frac{P_{i,k-1}}{P_{i,j}} \cdot C_{i,k-1} ~+~ \frac{P_{k+1,j}}{P_{i,j}} \cdot C_{k+1,j},$$

y similarmente para $r(i,j)$. Para ver que esto reduce el costo total a $O(n^2)$, consideremos el costo a lo largo de una diagonal $d$ de la matriz, donde $j = i+d$. Entonces, calcular la celda $C_{i,j}$ cuesta

$r(i+1,j) - r(i,j-1) + 1 ~=~ r(i+1,i+d) - r(i,i+d-1) + 1.$

Calcular la siguiente celda de la diagonal cuesta

$r(i+2,j+1) - r(i+1,j) + 1 ~=~ r(i+2,i+d+1) - r(i+1,i+d) + 1.$

Y la siguiente cuesta

$r(i+3,j+2) - r(i+2,j+1) + 1 ~=~ r(i+3,i+d+2) - r(i+2,i+d+1) + 1.$

Si sumamos estos costos, puede verse que cada segundo término se cancela con el primer término anterior. Por lo tanto la suma es telescópica, y a lo largo de la diagonal $d$ el costo es a lo sumo $r(n-d,n) - r(1,d+1) + n-d \le 2n$. A lo largo de las $n$ diagonales, el costo suma $O(n^2)$. Este es otro pequeño ejemplo de análisis amortizado: una celda puede demorar $O(n)$ en calcularse, pero vemos que las $O(n^2)$ celdas no requieren más de $O(n^2)$ operaciones.