Ediciones ENI Editorial | líder en informática
Algoritmos aplicados a C++
Introducción
Este capítulo presenta algoritmos aplicados en C++ y que tratan problemas actuales en tres áreas: reconocimiento de patrones, búsqueda de la ruta más corta y compresión de datos.
Reconocimiento de patrones textuales
Para un problema dado, no existe un algoritmo universal. Algunos algoritmos solo son efectivos en un caso particular.
Aquí nos interesa encontrar patrones textuales, es decir, encontrar una subcadena en una cadena y presentaremos varias formas de algoritmos.
La STL, como boost, ofrece funciones para hacer esto, pero la lógica utilizada para la implementación no se especifica en el archivo de encabezado. Es útil conocer algunos algoritmos de referencia para aplicarlos sabiamente.
1. Enfoque directo
El enfoque ingenuo consiste en comparar carácter por carácter el patrón de búsqueda con el texto de entrada. Si todas las comparaciones tienen éxito desde el primer hasta el último carácter del patrón, se dice que el patrón está agotado y la búsqueda está completa.
Si la comparación difiere antes de llegar al final del patrón, no es necesario continuar con las comparaciones para el resto de caracteres posteriores. Cambiamos el patrón de un carácter y comenzamos la comparación nuevamente.
La implementación en C++ de este algoritmo no presenta ninguna dificultad. Debe verificar los caracteres uno a uno sin exceder el tamaño del patrón ni el tamaño del texto a analizar:
int buscar_patron_simple(string s, string m)
{
int pos = 0;
int p = 0;
while (pos < s.length())
{
if (s.at(pos) == m.at(0))
{
// primer carácter idéntico
p = 1;
// compara uno por uno los siguientes caracteres del patrón
while (
p + pos < s.length() &&
p < m.length() &&
s.at(pos...Búsqueda del camino más corto
Hay muchas situaciones en las que se debe buscar la ruta más corta; en el área de la logística, en conducción asistida por ordenador, en planificación y programación, en motores de escenarios de videojuegos, etc.
Antes de presentar tres algoritmos esenciales, cada uno de ellos naturalmente adaptado a aplicaciones particulares, aquí hay una pequeña introducción a los grafos.
1. Presentación de los grafos
En el capítulo La librería Standard Template Library, estudiamos una estructura dinámica llamada lista. Una lista consta de un elemento principal (un valor), adjunto a una lista llamada continuacion. Para navegar por la lista, usamos voluntariamente una función recursiva que se llama hasta llegar a la lista vacía.
Considerando que un elemento puede tener varios sucesores, obtenemos un árbol, formado por nodos. Los nodos tienen un único antepasado llamado padre y varios descendientes, llamados hijos. Los nodos terminales que no tienen hijos se llaman hojas, mientras que el elemento en la parte superior del árbol se llama raíz. Hay casos especiales de árboles, por ejemplo, aquellos que tienen como máximo dos hijos llamados árboles B o B-trees. La B significa en inglés binary por el número 2.
Un grafo generaliza aún más la construcción del árbol al admitir que un nodo (llamado vértice) tiene varios antepasados.
Los grafos se componen de dos tipos de elementos: vértices y arcos. Los vértices representan objetos y los arcos establecen relaciones entre ellos. Los arcos pueden llevar valores (o pesos), pero esta característica no es decisiva para el estudio de un grafo en sentido estricto.
Los grafos pueden estar orientados o no orientados. En el primer caso, los arcos están orientados y se representan mediante flechas. Si es necesario, un arco puede ser bidireccional, duplicándose para representar cada dirección. La numeración o la identificación de los vértices tampoco es una característica determinante, aunque sea habitual, al menos en las fases de estudio de un algoritmo.
Matemáticamente, un grafo está formado por un conjunto S y una relación A sobre S. Denotamos por G=(S,A). En el caso...
Comprimir archivos
La cuestión de ahorrar espacio para representar información surgió muy pronto. Si bien la tecnología ha realizado avances fantásticos, también lo han hecho en la misma medida las necesidades de comunicación y almacenamiento. Como resultado, intentamos constantemente reducir el tamaño de los archivos y el ancho de banda consumido.
Presentamos dos algoritmos muy conocidos y todavía muy utilizados, en particular en software de almacenamiento del mercado o en módulos de compresión, utilizados para Internet y para la nube.
1. Enfoque por estadística: el algoritmo de Huffman
También hablamos de la codificación Huffman, que lleva el nombre de su inventor. El principio de este algoritmo consiste en reducir el número de bits para codificar caracteres frecuentes (bytes) en el archivo a comprimir, y aumentar el resto.
En español, la letra E es la más frecuente, mientras que las letras K o Z son mucho menos habituales. Empíricamente, la codificación de E en 7 bits en lugar de 8 ahorrará 1 bit por cada ocurrencia.
Como siempre se necesitan 256 códigos diferentes para representar cada carácter ASCII (1 byte), se supondrá que las letras menos frecuentes tienen codificaciones más largas, por ejemplo, en 9 bits.
El algoritmo de Huffman construye una codificación binaria (un árbol de dos ramas o B-tree) a partir de las estadísticas de los caracteres. Según las implementaciones, las estadísticas están predefinidas en función del tipo de archivo o se calculan dinámicamente a partir del archivo a comprimir. Incluso las implementaciones más sofisticadas cambian la codificación actualizando las estadísticas a medida que se procesa el archivo.
a. Implementación de la codificación
La codificación comienza contando las ocurrencias de cada carácter (representado en un byte) en el archivo fuente. Para esto, usamos una matriz de la clase Nodo, que se usará para construir el árbol para la codificación:
class Nodo
{
public:
int codigo, lcodigo;
int frec, salva;
int hijo1, hijo2;
Nodo()
{ ...