Algoritmos y Estructuras de Datos (página 3)

Si esta operación produce underflow en el nodo padre, se repite el procedimiento anterior un nivel más arriba. Finalmente, si la raíz queda vacía, ésta se elimina.

Costo de las operaciones de búsqueda, inserción y eliminación en el peor caso:

Arboles B

La idea de los árboles 2-3 se puede generalizar a árboles t – (2t-1), donde t>=2 es un parámetro fijo, es decir, cada nodo del árbol posee entre t y 2t-1 hijos, excepto por la raíz que puede tener entre 2 y 2t-1 hijos. En la práctica, t puede ser bastante grande, por ejemplo t = 100 o más. Estos árboles son conocidos como árboles B (Bayer).

Inserción en un árbol B

• Se agrega una nueva llave al nivel inferior.

• Si el nodo rebalsa (overflow), es decir, si queda con 2t hijos, se divide en 2 nodos con t hijos cada uno y sube un elemento al nodo padre. Si el padre rebalsa, se repite el procedimiento un nivel más arriba.

• Finalmente, si la raiz rebalsa, se divide en 2 y se crea una nueva raiz un nivel más arriba.

Eliminación en un árbol B

• Se elimina la llave, y su hoja respectiva, del nivel inferior.

• Si el nodo queda con menos de t hijos (underflow) se le piden prestados algunos al hermano, por ejemplo mitad y mitad.

• Si el hermano no tiene para prestar, entonces se fusionan los 2 nodos y se repite el procedimiento con el padre.

• Si la raíz queda vacía, se elimina.

Variantes de los árboles B

• Arboles B*: cuando un nodo rebalsa se trasladan hijos hacia el hermano, y sólo se crea un nuevo nodo cuando ambos rebalsan. Esto permite aumentar la utilización mínima de los nodos, que antes era de un 50%.

• Arboles B+: La información solo se almacena en las hojas, y los nodos internos contienen los separadores que permiten realizar la búsqueda de elementos.

Arboles digitales

Suponga que los elementos de un conjunto se pueden representar como una secuencia de bits:

X = b0b1b2…bk

Además, suponga que ninguna representación de un elemento en particular es prefijo de otra. Un árbol digital es un árbol binario en donde la posición de inserción de un elemento ya no depende de su valor, sino de su representación binaria. Los elementos en un árbol digital se almacenan solo en sus hojas, pero no necesariamente todas las hojas contienen elementos (ver ejemplo más abajo). Esta estructura de datos también es conocida como trie.

El siguiente ejemplo muestra un árbol digital con 5 elementos.

Búsqueda en un árbol digital

Para buscar un elemento X en un árbol digital se procede de la siguiente manera:

• Se examinan los bits bi del elemento X, partiendo desde b0 en adelante.

• Si bi = 0 se avanza por la rama izquierda y se examina el siguiente bit, bi+1.

• Si bi = 1 se avanza por la rama derecha y se examina el siguiente bit.

• El proceso termina cuando se llega a una hoja, único lugar posible en donde puede estar insertado X.

Inserción en un árbol digital

Suponga que se desea insertar el elemento X en el árbol digital. Se realiza una búsqueda infructuosa de X hasta llegar a una hoja, suponga que el último bit utilizado en la búsqueda fue bk. Si la hoja esta vacía, se almacena X en dicha hoja. En caso contrario, se divide la hoja utilizando el siguiente bit del elemento, bk+1, y se repite el procedimiento, si es necesario, hasta que quede solo un elemento por hoja.

Con este proceso de inserción, la forma que obtiene el árbol digital es insensible al orden de inserción de los elementos.

Eliminación en un árbol digital

Suponga que el elemento a eliminar es X. Se elimina el elemento de la hoja, y por lo tanto esta queda vacía. Si la hoja vacía es hermana de otra hoja no vacía, entonces ambas se fusionan y se repite el procedimiento mientras sea posible.

Costo promedio de búsqueda en un árbol digital

El costo promedio de búsqueda en un árbol digital es mejor que en un ABB, ya que en un árbol digital la probabilidad que un elemento se encuentre en el subárbol izquierdo o derecho es la misma, 1/2, dado que sólo depende del valor de un bit (0 o 1). En cambio, en un ABB dicha probabilidad es proporcional al "peso" del subárbol respectivo.

Hn son los números armónicos y P(n) es una función periódica de muy baja amplitud (O(10-6))

Arboles de búsqueda digital

En este tipo de árboles los elementos se almacenan en los nodos internos, al igual que en un ABB, pero la ramificación del árbol es según los bits de las llaves. El siguiente ejemplo muestra un árbol de búsqueda digital (ABD), en donde el orden de inserción es B, A, C, D, E:

Los ABD poseen un mejor costo promedio de búsqueda que los ABB, pero tambien es O(log(n)).

Skip lists

Al principio del capítulo se vio que una de las maneras simples de implementar el TDA diccionario es utilizando una lista enlazada, pero también se vio que el tiempo de búsqueda promedio es O(n) cuando el diccionario posee n elementos. La figura muestra un ejemplo de lista enlazada simple con cabecera, donde los elementos están ordenados ascendentemente:

Sin embargo, es posible modificar la estructura de datos de la lista y así mejorar el tiempo de búsqueda promedio. La siguiente figura muestra una lista enlazada en donde a cada nodo par se le agrega una referencia al nodo ubicado dos posiciones más adelante en la lista. Modificando ligeramente el algoritmo de búsqueda, a lo más nodos son examinados en el peor caso.

Esta idea se puede extender agregando una referencia cada cuatro nodos. En este caso, a lo más nodos son examinados:

El caso límite para este argumento se muestra en la siguiente figura. Cada 2i nodo posee una referencia al nodo 2i posiciones más adelante en la lista. El número total de referencias solo ha sido doblado, pero ahora a lo más nodos son examinados durante la búsqueda. Note que la búsqueda en esta estructura de datos es básicamente una búsqueda binaria, por lo que el tiempo de búsqueda en el peor caso es O(log n).

El problema que tiene esta estructura de datos es que es demasiado rígida para permitir inserciones de manera eficiente. Por lo tanto, es necesario relajar levemente las condiciones descritas anteriormente para permitir inserciones eficientes.

Se define un nodo de nivel k como aquel nodo que posee k referencias. Se observa de la figura anterior que, aproximadamente, la mitad de los nodos son de nivel 1, que un cuarto de los nodos son de nivel 2, etc. En general, aproximadamente n/2i nodos son de nivel i. Cada vez que se inserta un nodo, se elige el nivel que tendrá aleatoriamente en concordancia con la distribución de probabilidad descrita. Por ejemplo, se puede lanzar una moneda al aire, y mientras salga cara se aumenta el nivel del nodo a insertar en 1 (partiendo desde 1). Esta estructura de datos es denominada skip list. La siguiente figura muestra un ejemplo de una skip list:

Búsqueda en una skip list

Suponga que el elemento a buscar es X. Se comienza con la referencia superior de la cabecera. Se realiza un recorrido a través de este nivel (pasos horizontales) hasta que el siguiente nodo sea mayor que X o sea null. Cuando esto ocurra, se continúa con la búsqueda pero un nivel más abajo (paso vertical). Cuando no se pueda bajar de nivel, esto es, ya se está en el nivel inferior, entonces se realiza una comparación final para saber si el elemento X está en la lista o no.

Inserción en una skip list

Se procede como en la búsqueda, manteniendo una marca en los nodos donde se realizaron pasos verticales, hasta llegar al nivel inferior. El nuevo elemento se inserta en lo posición en donde debiera haberse encontrado, se calcula aleatoriamente su nivel y se actualizan las referencias de los nodos marcados dependiendo del nivel del nuevo nodo de la lista.

Costo de búsqueda en una skip list

El análisis del costo de búsqueda promedio en una skip list es complicado, pero se puede demostrar que en promedio es O(log n). También se puede demostrar que si se usa una moneda cargada, es decir, que la probabilidad que salga cara es p y la probabilidad que salga sello es q = 1-p, entonces el costo de búsqueda es mínimo para p = 1/e (e = base del logaritmo natural).

ABB óptimos

ABB con probabilidades de acceso no uniforme

Problema: dados n elementos X1 < X2 < … < Xn, con probabilidades de acceso conocidas p1, p2, …, pn, y con probabilidades de búsqueda infructuosa conocidas q0, q1, …, qn, se desea encontrar el ABB que minimice el costo esperado de búsqueda.

Por ejemplo, para el siguiente ABB con 6 elementos:

El costo esperado de búsqueda es:

C(q0,q6)=(2q0+2p1+4q1+4p2+4q2+3p3+4q3+4p4+4q4)+p5+(2q5+2p6+2q6)

=(q0+p1+q1+p2+q2+p3+q3+p4+q4+p5+q5+p6+q6)+

(1q0+1p1+3q1+3p2+3q2+2p3+3q3+3p4+3q4)+

(1q5+1p6+1q6)

=W(q0,q6)+C(q0,q4)+C(q5,q6)

Esto es, el costo del árbol completo es igual al "peso" del árbol más los costos de los subárboles. Si la raíz es k:

Ci,j = Wi,j + Ci,k-1 + Ck,j

Si el árbol completo es óptimo, entonces los subárboles también lo son, pero al revés no necesariamente es cierto, porque la raíz k puede haberse escogido mal. Luego, para encontrar el verdadero costo óptimo C_opti,j es necesario probar con todas las maneras posibles de elegir la raíz k.

C_opti,j = mini+1<=k<=j {Wi,j + C_opti,k-1 + C_optk,j}

C_opti,i = 0 para todo i=0..n

Note que el "peso" Wi,j no depende de la variable k.

Implementación de ABB óptimos

• Recursiva (equivalente a fuerza bruta): Calcular todos los árboles posibles (O(4n)).

• Usando programación dinámica (tabulación):

• for (i=0; i<=n; i++)

• {

• C[i,i]=0; // subarboles de tamaño 0

• W[i,i]=qi;

• }

• for (l=1; l<=n; l++)

• for (i=0; i<=n-l; i++)

• {

• j=i+l;

• W[i,j]=W[i,j-1]+pj+qj;

• C[i,j]=mini+1<=k<=j {W[i,j]+C[i,k-1]+C[k,j]}

• }

Tiempo: O(n3).

Una mejora: se define ri,j como el k que minimiza mini+1<=k<=j {W[i,j]+C[i,k-1]+C[k,j]}. Intuitivamente ri,j-1 <= ri,j <= ri+1,j, y como ri,j-1 y ri+1,j ya son conocidos al momento de calcular ri,j, basta con calcular minri,j-1 <= k <= ri+1,j {W[i,j]+C[i,k-1]+C[k,j]}.

Con esta mejora, se puede demostrar que el método demora O(n2) (Ejercicio: demostrarlo).

Splay Trees

Esta estructura garantiza que para cualquier secuencia de M operaciones en un árbol, empezando desde un árbol vacío, toma a lo más tiempo O(M log(N). A pesar que esto no garantiza que alguna operación en particular tome tiempo O(N), si asegura que no existe ninguna secuencia de operaciones que sea mala. En general, cuando una secuencia de M operaciones toma tiempo O(M f(N)), se dice que el costo amortizado en tiempo de cada operación es O(f(N)). Por lo tanto, en un splay tree los costos amortizados por operacion son de O(log(N)).

La idea básica de un splay tree es que después que un nodo es accesado éste se "sube" hasta la raíz del árbol a través de rotaciones al estilo AVL. Una manera de realizar esto, que NO funciona, es realizar rotaciones simples entre el nodo accesado y su padre hasta dejar al nodo accesado como raíz del árbol. El problema que tiene este enfoque es que puede dejar otros nodos muy abajo en el árbol, y se puede probar que existe una secuencia de M operaciones que toma tiempo O(M N), por lo que esta idea no es muy buena.

La estrategia de "splaying" es similar a la idea de las rotaciones simples. Si el nodo k es accesado, se realizaran rotaciones para llevarlo hasta la raíz del árbol. Sea k un nodo distinto a la raíz del árbol. Si el padre de k es la raíz del árbol, entonces se realiza una rotación simple entre estos dos nodos. En caso contrario, el nodo k posee un nodo padre p y un nodo "abuelo" a. Para realizar las rotaciones se deben considerar dos casos posibles (más los casos simétricos).

El primer caso es una inserción zig-zag, en donde k es un hijo derecho y p es un hijo izquierdo (o viceversa). En este caso, se realiza una rotación doble estilo AVL (ver figura superior).

El otro caso es una inseción zig-zig, en donde k y p son ambos hijos izquierdo o derecho. En este caso, se realiza la transformación indicada en la figura anterior.

El efecto del splaying es no sólo de mover el nodo accesado a la raíz, sino que sube todos los nodos del camino desde la raíz hasta el nodo accesado aproximadamente a la mitad de su profundidad anterior, a costa que algunos pocos nodos bajen a lo más dos niveles en el árbol.

El siguiente ejemplo muestra como queda el splay tree luego de accesar al nodo d.

El primer paso es un zig-zag entre los nodos d, b y f.

El último paso es un zig-zig entre los nodos d, h y j.

Para borrar un elemento de un splay tree se puede proceder de la siguiente forma: se realiza una búsqueda del nodo a eliminar, lo cual lo deja en la raíz del árbol. Si ésta es eliminada, se obtienen dos subárboles Sizq y Sder. Se busca el elemento mayor en Sizq, con lo cual dicho elemento pasa a ser su nueva raíz, y como era el elemento mayor Sizq ya no tiene hijo derecho, por lo que se cuelga Sder como subárbol derecho de Sizq, con lo que termina la operación de eliminación.

El análisis de los splay trees es complejo, porque debe considerar la estructura cambiante del árbol en cada acceso realizado. Por otra parte, los splay trees son más fáciles de implementar que un AVL dado que no hay que verificar una condición de balance.

Hashing

Suponga que desea almacenar n números enteros, sabiendo de antemano que dichos números se encuentran en un rango conocido 0, …, k-1. Para resolver este problema, basta con crear un arreglo de valores booleanos de tamaño k y marcar con valor true los casilleros del arreglo cuyo índice sea igual al valor de los elementos a almacenar. Es fácil ver que con esta estructura de datos el costo de búsqueda, inserción y eliminación es O(1).

Este enfoque tiene dos grandes problemas:

• El valor de k puede ser muy grande, y por lo tanto no habría cupo en memoria para almacenar el arreglo. Piense, por ejemplo, en todos los posibles nombres de personas.

• Los datos a almacenar pueden ser pocos, con lo cual se estaría desperdiciando espacio de memoria.

Una manera de resolver estos problemas es usando una función h, denominada función de hash, que transorme un elemento X, perteneciente al universo de elementos posibles, en un valor h(X) en el rango [0, …, m-1], con m << k. En este caso, se marca el casillero cuyo índice es h(X) para indicar indicar que el elemento X pertenece al conjunto de elementos. Esta estructura de datos es conocida como tabla de hashing.

La función h debe ser de tipo pseudoaleatorio para distribuir las llaves uniformemente dentro de la tabla, es decir, Pr( h(X) = z) = 1/m para todo z en [0, …, m-1]. La llave X se puede interpretar como un número entero, y las funciones h(X) típicas son de la forma:

donde c es una constante, p es un número primo y m es el tamaño de la tabla de hashing. Distintos valores para estos parámetros producen distintas funciones de hash.

Problema de este nuevo enfoque: colisiones.

La paradoja de los cumpleaños

¿Cuál es el número n mínimo de personas que es necesario reunir en una sala para que la probabilidad que dos de ella tengan su cumpleaños en el mismo día sea mayor que 1/2?

Sea dn la probabilidad que no haya coincidencia en dos fechas de cumpleaños. Se tiene que:

¿Cuál es el mínimo n tal que dn < 1/2?

Respuesta: n = 23 => dn = 0.4927. Note que 23 es una "pequeña" fracción de 365.

Esto quiere decir que con una pequeña fracción del conjunto de elementos es posible tener colisiones con alta probabilidad.

Para resolver el problema de las colisiones, existen dos grandes familias de métodos:

• Encadenamiento (usar estructuras dinámicas).

• Direccionamiento abierto (intentar con otra función de hash).

Encadenamiento

La idea de este método es que todos los elementos que caen en el mismo casillero se enlacen en una lista, en la cual se realiza una búsqueda secuencial.

Se define para un conjunto con n elementos:

• Cn: costo esperado de búsqueda exitosa.

• C'n: costo esperado de búsqueda infructuosa.

• factor de carga de la tabla.

Esto implica que el costo esperado de búsqueda sólo depende del factor de carga y no del tamaño de la tabla.

Hashing con listas mezcladas

En este caso no se usa área de rebalse, sino que los elementos se almacenan en cualquier lugar libre del área primaria.

Ejemplo: h(X)= X mod 10

Los costos esperados de búsqueda son:

Eliminación en tablas de hashing con encadenamiento

Con listas separadas el algoritmo es simple, basta con eliminar el elemento de la lista enlazada correspondiente. En el caso de las lista mezcladas, el algoritmo es más complejo (ejercicio).

Direccionamiento abierto

En general, esto puede ser visto como una sucesión de funciones de hash {h0(X), h1(X), …}. Primero se intenta con tabla[h0(X)], si el casillero está ocupado se prueba con tabla[h1(X)], y así sucesivamente.

Linear probing

Es el método más simple de direccionamiento abierto, en donde las funciones de hash se definen como:

Costo esperado de búsqueda:

Para una tabla llena:

Cuando la tabla de hashing está muy llena, este método resulta ser muy lento.

A medida que la tabla se va llenando, se observa que empiezan a aparecer clusters de casilleros ocupados consecutivos:

Si la función de hash distribuye los elementos uniformemente dentro de la tabla, la probabilidad que un cluster crezca es proporcional a su tamaño. Esto implica que una mala situación se vuelve peor cada vez con mayor probabilidad. Sin embargo, este no es todo el problema, puesto que lo mismo sucede en hashing con encadenamiento y no es tan malo. El verdadero problema ocurre cuando 2 clusters están separados solo por un casillero libre y ese casillero es ocupado por algún elemento: ambos clusters se unen en uno mucho más grande.

Otro problema que surge con linear probing es conocido como clustering secundario: si al realizar la búsqueda de dos elementos en la tabla se encuentran con el mismo casillero ocupado, entonces toda la búsqueda subsiguiente es la misma para ambos elementos.

Eliminación de elementos: no se puede eliminar un elemento y simplemente dejar su casillero vacío, puesto que las búsquedas terminarían en dicho casillero. Existen dos maneras para eliminar elementos de la tabla:

• Marcar el casillero como "eliminado", pero sin liberar el espacio. Esto produce que las búsquedas puedan ser lentas incluso si el factor de carga de la tabla es pequeño.

• Eliminar el elemento, liberar el casillero y mover elementos dentro de la tabla hasta que un casillero "verdaderamente" libre sea encontrado. Implementar esta operación es complejo y costoso.

Hashing doble

En esta estrategia se usan dos funciones de hash: una función conocida como dirección inicial, y una función conocida como paso. Por lo tanto:

Elegir m primo asegura que se va a visitar toda la tabla antes que se empiecen a repetir los casilleros. Nota: solo basta que m y s(X) sean primos relativos (ejercicio: demostralo por contradicción).

El análisis de eficiencia de esta estrategia es muy complicado, y se estudian modelos idealizados: muestreo sin reemplazo (uniform probing) y muestreo con reemplazo (random probing), de los cuales se obtiene que los costos de búsqueda esperado son:

Para una tabla llena:

Si bien las secuencias de casilleros obtenidas con hashing doble no son aleatorias, en la práctica su rendimiento es parecido a los valores obtenidos con los muestreos con y sin reemplazo.

Existen heurísticas para resolver el problema de las colisiones en hashing con direccionamiento abierto, como por ejemplo last-come-first-served hashing (el elemento que se mueve de casillero no es el que se inserta sino el que ya lo ocupaba) y Robin Hood hashing (el elemento que se queda en el casillero es aquel que se encuentre más lejos de su posición original), que si bien mantienen el promedio de búsqueda con respecto al método original (first-come-first-served) disminuyen dramáticamente su varianza.

Hashing en memoria secundaria

Cuando se almacena información en memoria secundaria (disco), la función de costo pasa a ser el número de accesos a disco. En hashing para memoria secundaria, la función de hash sirve para escoger un bloque (página) del disco, en donde cada bloque contiene b elementos. El factor de carga pasa a ser Por ejemplo, utilizando hashing encadenado:

Este método es eficiente para un factor de carga pequeño, ya que con factor de carga alto la búsqueda toma tiempo O(n). Para resolver esto puede ser necesario incrementar el tamaño de la tabla, y así reducir el factor de carga. En general esto implica reconstruir toda la tabla, pero existe un método que permite hacer crecer la tabla paulatinamente en el tiempo denominado hashing extendible.

Hashing extendible

Suponga que las páginas de disco son de tamaño b y una función de hash h(X)>=0 (sin límite superior). Sea la descomposición en binario de la función de hash h(X)=(… b2(X) b1(X) b0(X))2.

Inicialmente, todas las llaves se encuentran en una única página. Cuando dicha página se rebalsa se divide en dos, usando b0(X) para discriminar entre ambas páginas:

Cada vez que una página rebalsa, se usa el siguiente bit en la sequencia para dividirla en dos. Ejemplo:

El índice (directorio) puede ser almacenado en un árbol, pero el hashing extensible utiliza una idea diferente. El árbol es extendido de manera que todos los caminos tengan el mismo largo:

A continuación, el árbol es implementado como un arreglo de referencias:

Cuando se inserta un elemento y existe un rebalse, si cae en la página (D,E) esta se divide y las referencias de los casilleros 2 y 3 apuntan a las nuevas páginas creadas. Si la página (B,C) es la que se divide, entonces el árbol crece un nivel, lo cual implica duplicar el tamaño del directorio. Sin embargo, esto no sucede muy a menudo.

El tamaño esperado del directorio es ligeramente superlinear:

Compresión de datos

En esta sección veremos la aplicación de la teoría de árboles a la compresión de datos. Por compresión de datos entendemos cualquier algoritmo que reciba una cadena de datos de entrada y que sea capaz de generar una cadena de datos de salida cuya representación ocupa menos espacio de almacenamiento, y que permite -mediante un algoritmo de descompresión- recuperar total o parcialmente el mensaje recibido inicialmente. A nosotros nos interesa particularmente los algoritmos de compresión sin pérdida, es decir, aquellos algoritmos que permiten recuperar completamente la cadena de datos inicial.

Codificación de mensajes

Supongamos que estamos codificando mensajes en binario con un alfabeto de tamaño Para esto se necesitan bits por símbolo, si todos los códigos son de la misma longitud.

Ejemplo: para el alfabeto A,,Z de 26 letras se necesitan códigos de bits

Problema: Es posible disminuir el número promedio de bits por símbolo?

Solución: Asignar códigos más cortos a los símbolos más frecuentes.

Un ejemplo claro de aplicación de este principio es el código morse:

Se puede representar mediante un arbol binario:

Podemos ver en el árbol que letras de mayor probabilidad de aparición (en idioma inglés) están más cerca de la raíz, y por lo tanto tienen una codificación más corta que letras de baja frecuencia.

Problema: este código no es auto-delimitante

Por ejemplo, SOS y IAMS tienen la misma codificación

Para eliminar estas ambigüedades, en morse se usa un tercer delimitador (espacio) para separar el código de cada letra. Se debe tener en cuenta que este problema se produce sólo cuando el código es de largo variable (como en morse), pues en otros códigos de largo fijo (por ejemplo el código ASCII, donde cada caracter se representa por 8 bits) es directo determinar cuales elementos componen cada caracter.

La condición que debe cumplir una codificación para no presentar ambigüedades, es que la codificación de ningun caracter sea prefijo de otra. Esto nos lleva a definir árboles que sólo tienen información en las hojas, como por ejemplo:

Como nuestro objetivo es obtener la secuencia codificada más corta posible, entonces tenemos que encontrar la codificación que en promedio use el menor largo promedio del código de cada letra.

Problema: Dado un alfabeto tal que la probabilidad de que la letra aparezca en un mensaje es encontrar un código libre de prefijos que minimice el largo promedio del código de una letra.

Supongamos que a la letra se le asigna una codificación de largo entonces el largo esperado es:

es decir, el promedio ponderado de todas las letras por su probabilidad de aparición.

Ejemplo:

Entropía de Shannon

Shannon define la entropía del alfabeto como:

El teorema de Shannon dice que el número promedio de bits esperable para un conjunto de letras y probabilidades dadas se aproxima a la entropía del alfabeto. Podemos comprobar esto en nuestro ejemplo anterior donde la entropia de Shannon es:

que es bastante cercano al costo esperado de 2.38 que calculamos anteriormente. A continuación describiremos algoritmos que nos permitan encontrar representaciones que minimicen el costo total.

Algoritmo de Huffman

El algoritmo de Huffman permite construir un código libre de prefijos de costo esperado mínimo.

Inicialmente, comenzamos con hojas desconectadas, cada una rotulada con una letra del alfabeto y con una probabilidad (ponderacion o peso).

Consideremos este conjunto de hojas como un bosque. El algoritmo es:

while(nro de árboles del bosque > 1){

  - Encontrar los 2 árboles de peso mínimo y       unirlos con una nueva raíz que se crea para esto.

  - Arbitrariamente, rotulamos las dos 

    líneas como ´ 0´ y ´ 1´

  - Darle a la nueva raíz un peso que es       la suma de los pesos de sus subárboles.

  }

Ejemplo:

Si tenemos que las probabilidades de las letras en un mensaje son:

Entonces la construcción del árbol de Huffman es (los números en negrita indican los árboles con menor peso):

Se puede ver que el costo esperado es de 2,53 bits por letra, mientras que una codificación de largo fijo (igual número de bits para cada símbolo) entrega un costo de 3 bits/letra.

El algoritmo de codificación de Huffman se basa en dos supuestos que le restan eficiencia:

• supone que los caracteres son generados por una fuente aleatoria independiente, lo que en la práctica no es cierto. Por ejemplo, la probabilidad de encontrar una vocal después de una consonante es mucho mayor que la de encontrarla después de una vocal; después de una q es muy probable encontrar una u, etc

• Debido a que la codificación se hace caracter a caracter, se pierde eficiencia al no considerar las secuencias de caracteres más probables que otras.

Lempel Ziv

Una codificación que toma en cuenta los problemas de los supuestos enunciados anteriormente para la codificación de Huffman sería una donde no solo se consideraran caracteres uno a uno, sino que donde además se consideraran aquellas secuencias de alta probabilidad en el texto. Por ejemplo, en el texto:

aaabbaabaa

Obtendríamos un mayor grado de eficiencia si además de considerar caracteres como a y b, también considerásemos la secuencia aa al momento de codificar.

Una generalización de esta idea es el algoritmo de Lempel-Ziv. Este algoritmo consiste en separar la secuencia de caracteres de entrada en bloques o secuencias de caracteres de distintos largos, manteniendo una diccionario de bloques ya vistos. Aplicando el algoritmo de Huffman para estos bloques y sus probabilidades, se puede sacar provecho de las secuencias que se repitan con más probabilidad en el texto. El algoritmo de codificación es el siguiente:

1.- Inicializar el diccionario con todos los bloques de largo 1

2.- Seleccionar el prefijo más largo del mensaje que calce con alguna  secuencia W del diccionario y eliminar W del mensaje

3.- Codificar W con su índice en el diccionario

4.- Agregar W seguido del primer símbolo del próx bloque al diccionario

5.- Repetir desde el paso 2.

Ejemplo:

Si el mensaje es

la codificación y los bloques agregados al diccionario serían (donde los bloques reconocidos son mostrados entre paréntesis y la secuencia agregada al diccionario en cada etapa es mostrada como un subíndice):

Teóricamente, el diccionario puede crecer indefinidamente, pero en la práctica se opta por tener un diccionario de tamaño limitado. Cuando se llega al límite del diccionario, no se agregan más bloques.

Lempel-Ziv es una de las alternativas a Huffman. Existen varias otras derivadas de estas dos primeras, como LZW (Lempel-Ziv-Welch), que es usado en programas de compresión como el compress de UNIX.

Ordenación

El problema de ordenar un conjunto de datos (por ejemplo, en orden ascendente) tiene gran importancia tanto teórica como práctica. En esta sección veremos principalmente algoritmos que ordenan mediante comparaciones entre llaves, para los cuales se puede demostrar una cota inferior que coincide con la cota superior provista por varios algoritmos. También veremos un algoritmo de otro tipo, que al no hacer comparaciones, no está sujeto a esa cota inferior.

Cota inferior

Supongamos que deseamos ordenar tres datos A, B y C. La siguiente figura muestra un árbol de decisión posible para resolver este problema. Los nodos internos del árbol representan comparaciones y los nodos externos representan salidas emitidas por el programa.

Como se vio en el capítulo de búsqueda, todo árbol de decisión con H hojas tiene al menos altura log2 H, y la altura del árbol de decisión es igual al número de comparaciones que se efectúan en el peor caso.

En un árbol de decisión para ordenar n datos se tiene que H=n!, y por lo tanto se tiene que todo algoritmo que ordene n datos mediante comparaciones entre llaves debe hacer al menos log2 n! comparaciones en el peor caso.

Usando la aproximación de Stirling, se puede demostrar que log2 n! = n log2 n + O(n), por lo cual la cota inferior es de O(n log n).

Si suponemos que todas las posibles permutaciones resultantes son equiprobables, es posible demostrar que el número promedio de comparaciones que cualquier algoritmo debe hacer es también de O(n log n).

Quicksort

Este método fue inventado por C.A.R. Hoare a comienzos de los '60s, y sigue siendo el método más eficiente para uso general.

Quicksort es un ejemplo clásico de la aplicación del principio de dividir para reinar. Su estructura es la siguiente:

• Primero se elige un elemento al azar, que se denomina el pivote.

• El arreglo a ordenar se reordena dejando a la izquierda a los elementos menores que el pivote, el pivote al medio, y a la derecha los elementos mayores que el pivote:

• Luego cada sub-arreglo se ordena recursivamente.

La recursividad termina, en principio, cuando se llega a sub-arreglos de tamaño cero o uno, los cuales trivialmente ya están ordenados. En la práctica veremos que es preferible detener la recursividad antes de eso, para no desperdiciar tiempo ordenando recursivamente arreglos pequeños, los cuales pueden ordenarse más eficientemente usando Ordenación por Inserción, por ejemplo.

Costo promedio

Si suponemos, como una primera aproximación, que el pivote siempre resulta ser la mediana del conjunto, entonces el costo de ordenar está dado (aproximadamente) por la ecuación de recurrencia

T(n) = n + 2 T(n/2)

Esto tiene solución T(n) = n log2 n y es, en realidad, el mejor caso de Quicksort.

Para analizar el tiempo promedio que demora la ordenación mediante Quicksort, observemos que el funcionamiento de Quicksort puede graficarse mediante un árbol de partición:

Por la forma en que se construye, es fácil ver que el árbol de partición es un árbol de búsqueda binaria, y como el pivote es escogido al azar, entonces la raíz de cada subárbol puede ser cualquiera de los elementos del conjunto en forma equiprobable. En consecuencia, los árboles de partición y los árboles de búsqueda binaria tienen exactamente la misma distribución.

En el proceso de partición, cada elemento de los subárboles ha sido comparado contra la raíz (el pivote). Al terminar el proceso, cada elemento ha sido comparado contra todos sus ancestros. Si sumamos todas estas comparaciones, el resultado total es igual al largo de caminos internos.

Usando todas estas correspondencias, tenemos que, usando los resultados ya conocidos para árboles, el número promedio de comparaciones que realiza Quicksort es de:

1.38 n log2 n + O(n)

Por lo tanto, Quicksort es del mismo orden que la cota inferior (en el caso esperado).

Peor caso

El peor caso de Quicksort se produce cuando el pivote resulta ser siempre el mínimo o el máximo del conjunto. En este caso la ecuación de recurrencia es

T(n) = n – 1 + T(n-1)

lo que tiene solución T(n) = O(n2). Desde el punto de vista del árbol de partición, esto corresponde a un árbol en "zig-zag".

Si bien este peor caso es extremadamente improbable si el pivote se escoge al azar, algunas implementaciones de Quicksort toman como pivote al primer elemento del arreglo (suponiendo que, al venir el arreglo al azar, entonces el primer elemento es tan aleatorio como cualquier otro). El problema es que si el conjunto viene en realidad ordenado, entonces caemos justo en el peor caso cuadrático.

Lo anterior refuerza la importancia de que el pivote se escoja al azar. Esto no aumenta significativamente el costo total, porque el número total de elecciones de pivote es O(n).

Mejoras a Quicksort

Quicksort puede ser optimizado de varias maneras, pero hay que ser muy cuidadoso con estas mejoras, porque es fácil que terminen empeorando el desempeño del algoritmo.

En primer lugar, es desaconsejable hacer cosas que aumenten la cantidad de trabajo que se hace dentro del "loop" de partición, porque este es el lugar en donde se concentra el costo O(n log n).

Algunas de las mejoras que han dado buen resultado son las siguientes:

Quicksort con "mediana de 3"

En esta variante, el pivote no se escoge como un elemento tomado al azar, sino que primero se extrae una muestra de 3 elementos, y entre ellos se escoge a la mediana de esa muestra como pivote.

Si la muestra se escoge tomando al primer elemento del arreglo, al del medio y al último, entonces lo que era el peor caso (arreglo ordenado) se transforma de inmediato en mejor caso.

De todas formas, es aconsejable que la muestra se escoja al azar, y en ese caso el análisis muestra que el costo esperado para ordenar n elementos es

(12/7) n ln n = 1.19 n log2 n

Esta reducción en el costo se debe a que el pivote es ahora una mejor aproximación a la mediana. De hecho, si en lugar de escoger una muestra de tamaño 3, lo hiciéramos con tamaños como 7, 9, etc., se lograría una reducción aún mayor, acercándonos cada vez más al óptimo, pero con rendimientos rápidamente decrecientes.

Uso de Ordenación por Inserción para ordenar sub-arreglos pequeños

Tal como se dijo antes, no es eficiente ordenar recursivamente sub-arreglos demasiado pequeños.

En lugar de esto, se puede establecer un tamaño mínimo M, de modo que los sub-arreglos de tamaño menor que esto se ordenan por inserción en lugar de por Quicksort.

Claramente debe haber un valor óptimo para M, porque si creciera indefinidamente se llegaría a un algoritmo cuadrático. Esto se puede analizar, y el óptimo es cercano a 10.

Como método de implementación, al detectarse un sub-arreglo de tamaño menor que M, se lo puede dejar simplemente sin ordenar, retornando de inmediato de la recursividad. Al final del proceso, se tiene un arreglo cuyos pivotes están en orden creciente, y encierran entre ellos a bloques de elementos desordenados, pero que ya están en el grupo correcto. Para completar la ordenación, entonces, basta con hacer una sola gran pasada de Ordenación por Inserción, la cual ahora no tiene costo O(n2), sino O(nM), porque ningún elemento esta a distancia mayor que M de su ubicación definitiva.

Ordenar recursivamente sólo el sub-arreglo más pequeño

Un problema potencial con Quicksort es la profundidad que puede llegar a tener el arreglo de recursividad. En el peor caso, ésta puede llegar a ser O(n).

Para evitar esto, vemos primero cómo se puede programar Quicksort en forma no recursiva, usando un stack. El esquema del algoritmo sería el siguiente (en seudo-Java):

void Quicksort(Object a[])

{

Pila S = new Pila();

S.apilar(1,N); // límites iniciales del arreglo

while(!S.estaVacia())

{

(i,j) = S.desapilar(); // sacar límites

if(j-i>0) // al menos dos elementos para ordenar

{

p = particionar(a,i,j); // pivote queda en a[p]

S.apilar(i,p-1);

S.apilar(p+1,j);

}

}

}

Con este enfoque se corre el riesgo de que la pila llegue a tener profundidad O(n). Para evitar esto, podemos colocar en la pila sólo los límites del sub-arreglo más pequeño, dejando el más grande para ordenarlo de inmediato, sin pasar por la pila:

void Quicksort(Object a[])

{

Pila S = new Pila();

S.apilar(1,N); // límites iniciales del arreglo

while(!S.estaVacia())

{

(i,j) = S.desapilar(); // sacar límites

while(j-i>0) // al menos dos elementos para ordenar

{

p = particionar(a,i,j); // pivote queda en a[p]

if(p-i>j-p) // mitad izquierda es mayor

{

S.apilar(p+1,j);

j=p-1;

}

else

{

S.apilar(i,p-1);

i=p+1;

}

}

}

}

Con este enfoque, cada intervalo apilado es a lo más de la mitad del tamaño del arreglo, de modo que si llamamos S(n) a la profundidad de la pila, tenemos:

S(n) <= 1 + S(n/2)

lo cual tiene solución log2 n, de modo que la profundida de la pila nunca es más que logarítmica.

Un algoritmo de selección basado en Quicksort

Es posible modificar el algoritmo de Quicksort para seleccionar el k-ésimo elemento de un arreglo. Básicamente, la idea es ejecutar Quicksort, pero en lugar de ordenar las dos mitades, hacerlo solo con aquella mitad en donde se encontraría el elemento buscado.

Suponemos que los elementos están en a[1],…,a[n] y que k está entre 1 y n. Cuando el algoritmo termina, el k-ésimo elemento se encuentra en a[k]. El resultado es el siguiente algoritmo, conocido como Quickselect, el cual se llama inicialmente como Quickselect(a,k,1,N).

void Quickselect(Object a[], int k, int i, int j)

{

if(j-i>0) // aún quedan al menos 2 elementos

{

p = particionar(a,i,j);

if(p==k) // ¡bingo!

return;

if(k

Quickselect(a,k,i,p-1);

else

Quickselect(a,k,p+1,j);

}

}

Dado que en realidad se hace sólo una llamada recursiva y que ésta es del tipo "tail recursion", es fácil transformar esto en un algoritmo iterativo (hacerlo como ejercicio).

El análisis de Quickselect es difícil, pero se puede demostrar que el costo esperado es O(n). Sin embargo, el peor caso es O(n2).

Heapsort

A partir de cualquier implementación de una cola de prioridad es posible obtener un algoritmo de ordenación. El esquema del algoritmo es:

• Comenzar con una cola de prioridad vacía.

• Fase de construcción de la cola de prioridad: Traspasar todos los elementos del conjunto que se va a ordenar a la cola de prioridad, mediante n inserciones.

• Fase de ordenación: Sucesivamente extraer el máximo n veces. Los elementos van apareciendo en orden decreciente y se van almacenando en el conjunto de salida.

Si aplicamos esta idea a las dos implementaciones simples de colas de prioridad, utilizando lista enlazada ordenada y lista enlazada desordenada, se obtienen los algoritmos de ordenación por Inserción y por Selección, respectivamente. Ambos son algoritmos cuadráticos, pero es posible que una mejor implementación lleve a un algoritmo más rápido. En el capítulo de Tipos de Datos Abstractos se vió que una forma de obtener una implementación eficiente de colas de prioridad es utilizando una estructura de datos llamada heap.

Implementación de Heapsort

Al aplicar heaps en la implementación de cola de prioridad para construir un algoritmo de ordenación, se obtiene un algoritmo llamado Heapsort, para el cual resulta que tanto la fase de construcción de la cola de prioridad, como la fase de ordenación, tienen ambas costo O(n log n), de modo que el algoritmo completo tiene ese mismo costo.

Por lo tanto, Heapsort tiene un orden de magnitud que coincide con la cota inferior, esto es, es óptimo incluso en el peor caso. Nótese que esto no era así para Quicksort, el cual era óptimo en promedio, pero no en el peor caso.

De acuerdo a la descripción de esta familia de algoritmos, daría la impresión de que en la fase de construcción del heap se requeriría un arreglo aparte para el heap, distinto del arreglo de entrada. De la misma manera, se requeriría un arreglo de salida aparte, distinto del heap, para recibir los elementos a medida que van siendo extraídos en la fase de ordenación.

En la práctica, esto no es necesario y basta con un sólo arreglo: todas las operaciones pueden efectuarse directamente sobre el arreglo de entrada.

En primer lugar, en cualquier momento de la ejecución del algoritmo, los elementos se encuentran particionados entre aquellos que están ya o aún formando parte del heap, y aquellos que se encuentran aún en el conjunto de entrada, o ya se encuentran en el conjunto de salida, según sea la fase. Como ningún elemento puede estar en más de un conjunto a la vez, es claro que, en todo momento, en total nunca se necesita más de n casilleros de memoria, si la implementación se realiza bien.

En el caso de Heapsort, durante la fase de construcción del heap, podemos utilizar las celdas de la izquierda del arreglo para ir "armando" el heap. Las celdas necesarias para ello se las vamos "quitando" al conjunto de entrada, el cual va perdiendo elementos a medida que se insertan en el heap. Al concluir esta fase, todos los elementos han sido insertados, y el arreglo completo es un solo gran heap.

En la fase de ordenación, se van extrayendo elementos del heap, con lo cual este se contrae de tamaño y deja espacio libre al final, el cual puede ser justamente ocupado para ir almacenando los elementos a medida que van saliendo del heap (recordemos que van apareciendo en orden decreciente).

Optimización de la fase de construcción del heap

Como se ha señalado anteriormente, tanto la fase de construcción del heap como la de ordenación demoran tiempo O(n log n). Esto es el mínimo posible (en orden de magnitud), de modo que no es posible mejorarlo significativamente.

Sin embargo, es posible modificar la implementación de la fase de construcción del heap para que sea mucho más eficiente.

La idea es invertir el orden de las "mitades" del arreglo, haciendo que el "input" esté a la izquierda y el "heap" a la derecha.

En realidad, si el "heap" está a la derecha, entonces no es realmente un heap, porque no es un árbol completo (le falta la parte superior), pero sólo nos interesa que en ese sector del arreglo se cumplan las relaciones de orden entre a[k] y {a[2*k],a[2*k+1]}. En cada iteración, se toma el último elemento del "input" y se le "hunde" dentro del heap de acuerdo a su nivel de prioridad.

Al concluir, se llega igualmente a un heap completo, pero el proceso es significativamente más rápido.

La razón es que, al ser "hundido", un elemento paga un costo proporcional a su distancia al fondo del árbol. Dada las características de un árbol, la gran mayoría de los elementos están al fondo o muy cerca de él, por lo cual pagan un costo muy bajo. En un análisis aproximado, la mitad de los elementos pagan 0 (ya están al fondo), la cuarta parte paga 1, la octava parte paga 2, etc. Sumando todo esto, tenemos que el costo total está acotado por

lo cual es igual a n.

Bucketsort

Los métodos anteriores operan mediante comparaciones de llaves, y están sujetos, por lo tanto, a la cota inferior O(n log n). Veremos a continuación un método que opera de una manera distinta, y logra ordenar el conjunto en tiempo lineal.

Supongamos que queremos ordenar n números, cada uno de ellos compuesto de k dígitos decimales. El siguiente es un ejemplo con n=10, k=5.

73895

93754

82149

99046

04853

94171

54963

70471

80564

66496

Imaginando que estos dígitos forman parte de una matriz, podemos decir que a[i,j] es el j-ésimo del i-ésimo elemento del conjunto.

Es fácil, en una pasada, ordenar el conjunto si la llave de ordenación es un solo dígito, por ejemplo el tercero de izquierda a derecha:

99046

82149

94171

70471

66496

80564

93754

73895

04853

54963

Llamemos j a la posición del dígito mediante el cual se ordena. La ordenación se puede hacer utilizando una cola de entrada, que contiene al conjunto a ordenar, y un arreglo de 10 colas de salida, subindicadas de 0 a 9. Los elementos se van sacando de la cola de entrada y se van encolando en la cola de salida Q[dj], donde dj es el j-ésimo dígito del elemento que se está transfiriendo.

Al terminar este proceso, los elementos están separados por dígito. Para completar la ordenación, basta concatenar las k colas de salida y formar nuevamente una sola cola con todos los elementos.

Este proceso se hace en una pasada sobre los datos, y toma tiempo O(n).

Para ordenar el conjunto por las llaves completas, repetimos el proceso dígito por dígito, en cada pasada separando los elementos según el valor del dígito respectivo, luego recolectándolos para formar una sola cola, y realimentando el proceso con esos mismos datos. El conjunto completo queda finalmente ordenado si los dígitos se van tomando de derecha a izquierda (¡esto no es obvio!).

Como hay que realizar k pasadas y cada una de ellas toma tiempo O(n), el tiempo total es O(k n), que es el tamaño del archivo de entrada (en bytes). Por lo tanto, la ordenación toma tiempo lineal en el tamaño de los datos.

El proceso anterior se puede generalizar para cualquier alfabeto, no sólo dígitos (por ejemplo, ASCII). Esto aumenta el número de colas de salida, pero no cambia sustancialmente el tiempo que demora el programa.

Archivos con records de largo variable

Si las líneas a ordenar no son todas del mismo largo, es posible alargarlas hasta completar el largo máximo, con lo cual el algoritmo anterior es aplicable. Pero si hay algunas pocas líneas desproporcionadamente largas y otras muy cortas, se puede perder mucha eficiencia.

Es posible, aunque no lo vamos a ver aquí, generalizar este algoritmo para ordenar líneas de largo variable sin necesidad de alargarlas. El resultado es que la ordenación se realiza en tiempo proporcional al tamaño del archivo.

Mergesort y Ordenamiento Externo

Si tenemos dos archivos que ya están ordenados, podemos mezclarlos para formar un solo archivo ordenado en tiempo proporcional a la suma de los tamaños de los dos archivos.

Esto se hace leyendo el primer elemento de cada archivo, copiando hacia la salida al menor de los dos, y avanzando al siguiente elemento en el archivo respectivo. Cuando uno de los dos archivos se termina, todos los elementos restantes del otro se copian hacia la salida. Este proceso se denomina "mezcla", o bien "merge", por su nombre en inglés.

Como cada elemento se copia sólo una vez, y con cada comparación se copia algún elemento, es evidente que el costo de mezclar los dos archivos es lineal.

Si bien es posible realizar el proceso de mezcla de dos arreglos contiguos in situ, el algoritmo es muy complicado y no resulta práctico. Por esta razón, el proceso se implementa generalmente copiando de un archivo a otro.

Usando esta idea en forma reiterada, es posible ordenar un conjunto. Una forma de ver esto es recursivamente, usando "dividir para reinar". El siguiente seudo-código ilustra esta idea:

mergesort(S) # retorna el conjunto S ordenado

{

if(S es vacío o tiene sólo 1 elemento)

return(S);

else

{

Dividir S en dos mitades A y B;

A'=mergesort(A);

B'=mergesort(B);

return(merge(A',B'));

}

}

El tiempo total está dado aproximadamente por la ecuación de recurrencia

T(n) = 2 T(n/2) + n

la cual tiene solución O(n log n), de modo que el algoritmo resulta ser óptimo.

Esto mismo se puede implementar en forma no recursiva, agrupando los elementos de a dos y mezclándolos para formar pares ordenados. Luego mezclamos pares para formar cuádruplas ordenadas, y así sucesivamente hasta mezclar las últimas dos mitades y formar el conjunto completo ordenado. Como cada "ronda" tiene costo lineal y se realizan log n rondas, el costo total es O(n log n).

La idea de Mergesort es la base de la mayoría de los métodos de ordenamiento externo, esto es, métodos que ordenan conjuntos almacenados en archivos muy grandes, en donde no es posible copiar todo el contenido del archivo a memoria para aplicar alguno de los métodos estudiados anteriormente.

En las implementaciones prácticas de estos métodos, se utiliza el enfoque no recursivo, optimizado usando las siguientes ideas:

• No se comienza con elementos individuales para formar pares ordenados, sino que se generan archivos ordenados lo más grandes posibles. Para esto, el archivo de entrada se va leyendo por trozos a memoria y se ordena mediante Quicksort, por ejemplo.

• En lugar de mezclar sólo dos archivos se hace una mezcla múltiple (con k archivos de entrada. Como en cada iteración hay k candidatos a ser el siguiente elemento en salir, y siempre hay que extrar al mínimo de ellos y sustituirlo en la lista de candidatos por su sucesor, la estructura de datos apropiada para ello es un heap.

En caso que no baste con una pasada de mezcla múltiple para ordenar todo el archivo, el proceso se repite las veces que sea necesario. Al igual que en los casos anteriores, el costo total es O(n log n).

Búsqueda en texto

La búsqueda de patrones en un texto es un problema muy importante en la práctica. Sus aplicaciones en computación son variadas, como por ejemplo la búsqueda de una palabra en un archivo de texto o problemas relacionados con biología computacional, en donde se requiere buscar patrones dentro de una secuencia de ADN, la cual puede ser modelada como una secuencia de caracteres (el problema es más complejo que lo descrito, puesto que se requiere buscar patrones en donde ocurren alteraciones con cierta probabilidad, esto es, la búsqueda no es exacta).

En este capítulo se considerará el problema de buscar la ocurrencia de un patrón dentro de un texto. Se utilizarán las siguientes convenciones:

• n denotará el largo del texto en donde se buscará el patrón, es decir, texto = a1 a2 … an.

• m denotará el largo del patrón a buscar, es decir, patrón = b1 b2 … bm.

Por ejemplo:

• Texto = "analisis de algoritmos".

• Patrón = "algo".

Algoritmo de fuerza bruta

Se alinea la primera posición del patrón con la primera posición del texto, y se comparan los caracteres uno a uno hasta que se acabe el patrón, esto es, se encontró una ocurrencia del patrón en el texto, o hasta que se encuentre una discrepancia.

Si se detiene la búsqueda por una discrepancia, se desliza el patrón en una posición hacia la derecha y se intenta calzar el patrón nuevamente.

En el peor caso este algoritmo realiza comparaciones de caracteres.

Algoritmo Knuth-Morris-Pratt (KMP)

Suponga que se está comparando el patrón y el texto en una posición dada, cuando se encuentra una discrepancia.

Sea X la parte del patrón que calza con el texto, e Y la correspondiente parte del texto, y suponga que el largo de X es j. El algoritmo de fuerza bruta mueve el patrón una posición hacia la derecha, sin embargo, esto puede o no puede ser lo correcto en el sentido que los primeros j-1 caracteres de X pueden o no pueden calzar los últimos j-1 caracteres de Y.

La observación clave que realiza el algoritmo Knuth-Morris-Pratt (en adelante KMP) es que X es igual a Y, por lo que la pregunta planteada en el párrafo anterior puede ser respondida mirando solamente el patrón de búsqueda, lo cual permite precalcular la respuesta y almacenarla en una tabla.

Por lo tanto, si deslizar el patrón en una posición no funciona, se puede intentar deslizarlo en 2, 3, …, hasta j posiciones.

Se define la función de fracaso (failure function) del patrón como:

Intuitivamente, f(j) es el largo del mayor prefijo de X que además es sufijo de X. Note que j = 1 es un caso especial, puesto que si hay una discrepancia en b1 el patrón se desliza en una posición.

Si se detecta una discrepancia entre el patrón y el texto cuando se trata de calzar bj+1, se desliza el patrón de manera que bf(j) se encuentre donde bj se encontraba, y se intenta calzar nuevamente.

Suponiendo que se tiene f(j) precalculado, la implementación del algoritmo KMP es la siguiente:

// n = largo del texto

// m = largo del patron

// Los indices comienzan desde 1

int k=0;

int j=0;

while (k<n && j<m)

{

while (j>0 && texto[k+1]!=patron[j+1])

{

j=f[j];

}

if (texto[k+1])==patron[j+1]))

{

j++;

}

k++;

}

// j==m => calce, j el patron estaba en el texto

Ejemplo:

El tiempo de ejecución de este algoritmo no es difícil de analizar, pero es necesario ser cuidadoso al hacerlo. Dado que se tienen dos ciclos anidados, se puede acotar el tiempo de ejecución por el número de veces que se ejecuta el ciclo externo (menor o igual a n) por el número de veces que se ejecuta el ciclo interno (menor o igual a m), por lo que la cota es igual a ¡que es igual a lo que demora el algoritmo de fuerza bruta!.

El análisis descrito es pesimista. Note que el número total de veces que el ciclo interior es ejecutado es menor o igual al número de veces que se puede decrementar j, dado que f(j)<j. Pero j comienza desde cero y es siempre mayor o igual que cero, por lo que dicho número es menor o igual al número de veces que j es incrementado, el cual es menor que n. Por lo tanto, el tiempo total de ejecución es Por otra parte, k nunca es decrementado, lo que implica que el algoritmo nunca se devuelve en el texto.

Queda por resolver el problema de definir la función de fracaso, f(j). Esto se puede realizar inductivamente. Para empezar, f(1)=0 por definición. Para calcular f(j+1) suponga que ya se tienen almacenados los valores de f(1), f(2), …, f(j). Se desea encontrar un i+1 tal que el (i+1)-ésimo carácter del patrón sea igual al (j+1)-ésimo carácter del patrón.

Para esto se debe cumplir que i=f(j). Si bi+1=bj+1, entonces f(j+1)=i+1. En caso contrario, se reemplaza i por f(i) y se verifica nuevamente la condición.

El algoritmo resultante es el siguiente (note que es similar al algoritmo KMP):

// m es largo del patron

// los indices comienzan desde 1

int[] f=new int[m];

f[1]=0;

int j=1;

int i;

while (j

{

i=f[j];

while (i>0 && patron[i+1]!=patron[j+1])

{

i=f[i];

}

if (patron[i+1]==patron[j+1])

{

f[j+1]=i+1;

}

else

{

f[j+1]=0;

}

j++;

}

El tiempo de ejecución para calcular la función de fracaso puede ser acotado por los incrementos y decrementos de la variable i, que es

Por lo tanto, el tiempo total de ejecución del algoritmo, incluyendo el preprocesamiento del patrón, es

Algoritmo Boyer-Moore

Hasta el momento, los algoritmos de búsqueda en texto siempre comparan el patrón con el texto de izquierda a derecha. Sin embargo, suponga que la comparación ahora se realiza de derecha a izquierda: si hay una discrepancia en el último carácter del patrón y el carácter del texto no aparece en todo el patrón, entonces éste se puede deslizar m posiciones sin realizar niguna comparación extra. En particular, no fue necesario comparar los primeros m-1 caracteres del texto, lo cual indica que podría realizarse una búsqueda en el texto con menos de n comparaciones; sin embargo, si el carácter discrepante del texto se encuentra dentro del patrón, éste podría desplazarse en un número menor de espacios.

El método descrito es la base del algoritmo Boyer-Moore, del cual se estudiarán dos variantes: Horspool y Sunday.

Boyer-Moore-Horspool (BMH)

El algoritmo BMH compara el patrón con el texto de derecha a izquierda, y se detiene cuando se encuentra una discrepancia con el texto. Cuando esto sucede, se desliza el patrón de manera que la letra del texto que estaba alineada con bm, denominada c, ahora se alinie con algún bj, con j<m, si dicho calce es posible, o con b0, un carácter ficticio a la izquierda de b1, en caso contrario (este es el mejor caso del algoritmo).

Para determinar el desplazamiento del patrón se define la función siguiente como: