Capítulo 6: Cadenas en Algoritmos

Entrada:  ["dab", "cab", "fad", "bad", "dad", "ebb", "ace"]
Salida: ["ace", "bad", "cab", "dab", "dad", "ebb", "fad"]

Entrada:  ["4PGC938", "2IYE230", "3CIO720", "1ICK750", "1OHV845", "4JZY524", "1ICK750", "3CIO720", "1OHV845", "1OHV845", "2RLA629", "2RLA629", "3ATW723"]
Salida: ["1ICK750", "1ICK750", "1OHV845", "1OHV845", "1OHV845", "2IYE230", "2RLA629", "2RLA629", "3ATW723", "3CIO720", "3CIO720", "4JZY524", "4PGC938"]

Entrada:  ["she", "sells", "seashells", "by", "the", "sea", "shore", "the", "shells", "she", "sells", "are", "surely", "seashells"]
Salida: ["are", "by", "sea", "seashells", "seashells", "sells", "sells", "she", "she", "shells", "shore", "surely", "the", "the"]

     (raíz)
    /  |  \
   s   h   o
  / \     / \
 e   h   r   t
 |   |   |   |
 a   e   e   h
     |       |
     l       e
     |       |
     l       r
     |
     s

Texto:    "abacadabrabracabracadabrabrabracad"
Patrón: "abracadabra"
Salida:  [13]

Texto:    "abacadabrabr
```Aquí está la traducción al español del archivo Markdown, con los comentarios traducidos, pero sin traducir el código:

"acabracadabrabrabracad"
Patrón: "abracadabra"
Salida: [13]

El algoritmo KMP tiene un tiempo de ejecución de O(n + m), lo que lo hace mucho más eficiente que el enfoque de fuerza bruta para textos y patrones grandes.

### Algoritmo de Boyer-Moore

El algoritmo de Boyer-Moore es otro algoritmo eficiente de búsqueda de subcadenas que funciona mediante el preprocesamiento de la cadena de patrones. A diferencia de KMP, que comienza las comparaciones desde el principio del patrón, Boyer-Moore comienza desde el final y trabaja hacia atrás.

La idea clave detrás de Boyer-Moore es usar dos funciones precalculadas: la función "buen sufijo" y la función "mal carácter". Estas funciones nos permiten saltar hacia adelante en el texto cuando encontramos un desajuste, similar a KMP.

Aquí hay un ejemplo del algoritmo de Boyer-Moore:

Boyer-Moore tiene un tiempo de ejecución óptimo de O(n/m) y un tiempo de ejecución en el peor de los casos de O(n * m), pero en la práctica, a menudo es el algoritmo de búsqueda de subcadenas más rápido para alfabetos grandes.

## Expresiones regulares

Las expresiones regulares son una herramienta poderosa para describir patrones en cadenas. Proporcionan una notación concisa y flexible para hacer coincidir, buscar y manipular texto.

Una expresión regular es una secuencia de caracteres que define un patrón de búsqueda. La forma más simple de una expresión regular es una cadena literal, como "hola", que coincide exactamente con la cadena "hola". Sin embargo, las expresiones regulares también incluyen caracteres y construcciones especiales que permiten patrones más complejos:

- `.` (punto) coincide con cualquier carácter individual.
- `*` (asterisco) coincide con cero o más ocurrencias del carácter o grupo anterior.
- `+` (más) coincide con una o más ocurrencias del carácter o grupo anterior.
- `?` (signo de interrogación) coincide con cero o una ocurrencia del carácter o grupo anterior.
- `^` (acento circunflejo) coincide con el inicio de una línea.
- `$` (signo de dólar) coincide con el final de una línea.
- `[]` (corchetes) definen una clase de caracteres, que coincide con cualquier carácter individual.Aquí está la traducción al español del archivo Markdown, con los comentarios traducidos, pero sin traducir el código:

Aquí hay algunos ejemplos de expresiones regulares y los patrones que coinciden:

- `a.b` coincide con cualquier cadena de tres caracteres que comience con "a" y termine con "b", como "acb", "a5b" o "a b".
- `a*b` coincide con cualquier cadena que consista en cero o más caracteres "a" seguidos de un solo "b", como "b", "ab", "aab" o "aaab".
- `a+b` coincide con cualquier cadena que consista en uno o más caracteres "a" seguidos de un solo "b", como "ab", "aab" o "aaab", pero no "b".
- `a?b` coincide con "ab" o "b".
- `^a` coincide con cualquier cadena que comience con "a".
- `a$` coincide con cualquier cadena que termine con "a".
- `[aeiou]` coincide con cualquier carácter vocal.

Las expresiones regulares son compatibles con muchos lenguajes de programación y herramientas, incluyendo Java, Python y utilidades de Unix como grep y sed. Se utilizan ampliamente para tareas como validación de datos, procesamiento de texto y análisis de registros.

## Compresión de Datos

La compresión de datos es el proceso de codificar información utilizando menos bits que la representación original. Esto es útil para reducir los requisitos de almacenamiento y los tiempos de transmisión. Hay dos tipos principales de compresión: sin pérdida y con pérdida. La compresión sin pérdida permite reconstruir perfectamente los datos originales a partir de los datos comprimidos, mientras que la compresión con pérdida permite una cierta pérdida de información a cambio de una mayor relación de compresión.

### Codificación de Longitud de Ejecución

La codificación de longitud de ejecución (RLE) es una técnica de compresión sin pérdida simple que reemplaza las secuencias repetidas de símbolos idénticos (ejecuciones) con una sola instancia del símbolo y un recuento del número de veces que se repite.

Aquí hay un ejemplo de RLE:

RLE es efectivo para datos con muchas ejecuciones largas, como imágenes gráficas simples. Sin embargo, puede aumentar el tamaño de los datos si hay pocas o ninguna ejecución.

### Codificación de Huffman

La codificación de Huffman es un algoritmo de compresión sin pérdida que asigna códigos de longitud variable a los símbolos en función de su freAquí está la traducción al español del archivo Markdown, con los comentarios del código traducidos al español:

Frecuencias en los datos de entrada. Los símbolos más frecuentes se les asignan códigos más cortos, mientras que los símbolos menos frecuentes se les asignan códigos más largos.

El algoritmo funciona construyendo un árbol binario, llamado árbol de Huffman, de abajo hacia arriba. Cada nodo hoja representa un símbolo y su frecuencia, mientras que cada nodo interno representa la suma de las frecuencias de sus hijos. El árbol se construye fusionando repetidamente los dos nodos con las frecuencias más bajas hasta que solo quede un nodo.

Una vez que se construye el árbol, el código de cada símbolo se determina por la ruta desde la raíz hasta el nodo hoja correspondiente, donde una rama izquierda representa un "0" y una rama derecha representa un "1".

Aquí hay un ejemplo de codificación de Huffman:

En este ejemplo, "A" se le asigna el código "00", "B" se le asigna "01", "C" se le asigna "10", "D" se le asigna "110" y "E" se le asigna "111". La salida comprimida se obtiene reemplazando cada símbolo de la entrada con su código correspondiente.

La codificación de Huffman es un código prefijo óptimo, lo que significa que ningún código es prefijo de otro código. Esto permite la decodificación inequívoca de los datos comprimidos. La codificación de Huffman se utiliza ampliamente en varios formatos de archivo y herramientas de compresión, como JPEG, MP3 y ZIP.

### Compresión LZW

La compresión Lempel-Ziv-Welch (LZW) es un algoritmo de compresión basado en diccionario que construye un diccionario (o libro de códigos) de cadenas mientras comprime la entrada. LZW se utiliza ampliamente en utilidades de compresión de archivos y se utilizó en el formato de imagen GIF.

La idea clave detrás de LZW es reemplazar cadenas de caracteres con códigos únicos. Lee la cadena de entrada carácter por carácter y codifica la cadena en una representación compacta reemplazando cada código de longitud fija por un código de longitud variable. Cuanto más larga sea la cadena, más espacio se ahorrará al codificarla como un solo número.

Aquí hay unAquí está la traducción al español del archivo Markdown, con los comentarios del código traducidos:

Descripción paso a paso de cómo funciona la compresión LZW:

1. Inicializar el diccionario para que contenga todas las cadenas de un solo carácter.
2. Encuentra la cadena más larga W en el diccionario que coincida con la entrada actual.
3. Emitir el índice del diccionario para W a la salida y eliminar W de la entrada.
4. Agregar W seguido del siguiente símbolo en la entrada al diccionario.
5. Ir al Paso 2.

Consideremos un ejemplo. Supongamos que queremos comprimir la cadena "ABABABABA" usando LZW.

1. Inicializar el diccionario para que contenga "A" y "B".
2. La coincidencia más larga es "A". Emitir su índice (0) y eliminarla de la entrada. El diccionario ahora contiene "A", "B" y "AB".
3. La coincidencia más larga es "B". Emitir su índice (1) y eliminarla de la entrada. El diccionario ahora contiene "A", "B", "AB" y "BA".
4. La coincidencia más larga es "AB". Emitir su índice (2) y eliminarla de la entrada. El diccionario ahora contiene "A", "B", "AB", "BA" y "ABA".
5. La coincidencia más larga es "ABA". Emitir su índice (4) y eliminarla de la entrada. El diccionario ahora contiene "A", "B", "AB", "BA", "ABA" y "ABAB".
6. La coincidencia más larga es "BA". Emitir su índice (3). La entrada ahora está vacía.

La representación comprimida de "ABABABABA" es, por lo tanto, la secuencia de índices [1], que requiere menos bits para representarla que la representación ASCII original.

La descompresión funciona de manera similar, pero a la inversa:

1. Inicializar el diccionario para que contenga todas las cadenas de un solo carácter.
2. Leer un código X de la entrada.
3. Emitir la cadena para X desde el diccionario.
4. Si el código anterior existe, agregar la cadena anterior concatenada con el primer carácter de la cadena para X al diccionario.
5. Ir al Paso 2.

La compresión LZW es simple y rápida, lo que la convierte en una buena opción para muchas aplicaciones. Sin embargo, tiene algunas limitaciones. El tamaño del diccionario puede crecer bastante, consumiendo una cantidad significativa de memoria. Además, el diccionario se restablece después de cada bloque de entrada, lo que puede reducir la relación de compresión para archivos pequeños.

A pesar de estas limitaciones...Aquí está la traducción al español del archivo markdown, con los comentarios del código traducidos:

ns, LZW sigue siendo un algoritmo de compresión popular y eficaz, particularmente para aplicaciones donde la velocidad es más importante que lograr las relaciones de compresión más altas posibles.

## Conclusión

En este capítulo, exploramos varios algoritmos importantes de procesamiento de cadenas, incluyendo ordenamiento de cadenas, tries, búsqueda de subcadenas, expresiones regulares y compresión de datos. Estos algoritmos forman la base de muchas aplicaciones del mundo real y son herramientas esenciales para cualquier programador que trabaje con datos textuales.

Comenzamos discutiendo los ordenamientos de cadenas, que son algoritmos de ordenamiento optimizados que aprovechan las propiedades especiales de las cadenas. El conteo por clave indexada, el ordenamiento radix LSD y el ordenamiento radix MSD proporcionan métodos eficientes para ordenar cadenas en función de sus caracteres individuales.

A continuación, examinamos los tries, una estructura de datos en forma de árbol para almacenar y recuperar cadenas. Los tries permiten un emparejamiento de prefijos rápido y se utilizan comúnmente en aplicaciones como autocompletar y tablas de enrutamiento IP.

Los algoritmos de búsqueda de subcadenas, como los algoritmos de Knuth-Morris-Pratt y Boyer-Moore, nos permiten buscar eficientemente patrones dentro de cadenas más grandes. Estos algoritmos tienen numerosas aplicaciones en edición de texto, biología computacional y recuperación de información.

Las expresiones regulares proporcionan una forma poderosa y flexible de describir patrones de cadenas. Discutimos la sintaxis básica de las expresiones regulares y cómo se pueden usar para el emparejamiento de patrones y la manipulación de cadenas en varios lenguajes de programación y herramientas.

Finalmente, exploramos los algoritmos de compresión de datos, que reducen el tamaño de los datos explotando la redundancia y los patrones dentro de la entrada. Cubrimos la codificación de longitud de repetición, la codificación de Huffman y la compresión de Lempel-Ziv-Welch, cada uno de los cuales tiene sus propias fortalezas y aplicaciones.

Comprender estos algoritmos y estructuras de datos de procesamiento de cadenas es crucial para cualquiera que trabaje con datos textuales. A medida que la cantidad de datos no estructurados continúa creciendo, la capacidad de manipular, buscar y comprimir eficientemente la información se vuelve cada vez más importante.Aquí está la traducción al español del archivo Markdown:

Las cadenas de texto solo se volverán más valiosas. Al dominar las técnicas cubiertas en este capítulo, estarás bien equipado para enfrentar una amplia gama de desafíos de procesamiento de cadenas en tus propios proyectos y aplicaciones.

```python
# Función para contar la frecuencia de caracteres en una cadena
def count_chars(string):
    char_counts = {}
    for char in string:
        if char in char_counts:
            char_counts[char] += 1
        else:
            char_counts[char] = 1
    return char_counts

# Ejemplo de uso
text = "¡Hola, mundo!"
char_freq = count_chars(text)
print(char_freq)