Un sitio personal para aprender desarrollo web

Crear un ZIP

Trazado de la creación de un ZIP

Para entender la estructura de un ZIP usaremos la herramienta ZIP. Su uso se explica en el tema Gestor ZIP. Nos permite crear y trazar un ZIP a partir de archivos del ordenador. Y también con una muestra de texto a modo de ejemplo para observar el trazado, como se observa en la imagen adjunta. La creación de un ZIP se genera en el módulo zip.js, cuyo uso para crear una aplicación vimos en el tema anterior.

Por ahora la aplicación está implementada para crear ZIP sin compresión ni cifrado. Las opciones se limitan al método de compresión almacenamiento (stored), uso de comentarios en archivos y en el ZIP, el uso del descriptor de datos (data descriptor), especificar que los nombres y comentarios de los archivos pudieran ir codificados en UTF-8, y uso de atributos internos y externos.

Descargando ZIP con 3142 archivos

El formato de archivo ZIP tiene por objetivo empaquetar varios archivos en un único archivo con objeto de facilitar su almacenamiento y transmisión, especialmente por Internet. Ese empaquetado puede hacerse con compresión sin pérdida y también con cifrado.

En este tema veremos como preparar los archivos para empaquetarlos en un ZIP con el módulo zip.js. Haremos un ejemplo interactivo básico para verlo en funcionamiento. En el tema siguiente explicaremos los fundamentos básicos para crear un ZIP. Para ello nos basaremos en la herramienta ZIP que nos permite trazar la creación de un ZIP. En el tema Gestor ZIP se explica el funcionamiento de esa herramienta.

En la imagen vemos una captura de una ejecución con una descarga de un ZIP con 3142 archivos y 63,77 MB. El límite máximo en esa aplicación es de 2,14 GB, aunque el formato ZIP permite hasta el doble de ese tamaño. Para tamaños inferiores a 100 MB los tiempos de ejecución no son muy grandes. Por ejemplo, la descarga de la Figura ocupó 1,847 segundos leyendo los archivos y 0,444 segundos creando el ZIP (en Chrome 89). Si se incrementa mucho el tamaño, la ejecución en la creación del ZIP se incrementa más que proporcionalmente. En una ejecución de prueba de un único archivo de 1,15 GB tarda 6,4 leyendo y 26,16 segundos creando el ZIP.

Gestor ZIP con trazado

En la herramienta Web Tools online: ZIP se presenta una utilidad para usar el módulo zip.js cuyo cometido se explica en el tema Aplicación para descargar ZIP. En ese tema se explica como funciona el ZIP. Y en el tema siguiente Crear un ZIP se explica como se estructura un ZIP. Mientras que este tema se orienta a explicar como funciona la herramienta para crear y trazar el proceso de generación del ZIP.

Cuando implementamos una aplicación compleja, especialmente basada en especificaciones, considero aconsejable dotarla de los recursos necesarios para que nos devuelva una traza del proceso. Esto tiene varias ventajas. Por un lado vamos entendiendo mejor la especificación y podemos irla implementando en fases, desde lo más simple a los más complejo. Por otro lado se localizan mejor los errores. Podemos aplicar mejoras en el futuro, pues la traza nos ayudará a recordar como funcionaba el proceso. Y, finalmente, podemos compatirla en Internet para alguién que esté interesado en conocer el funcionamiento de ese proceso.

En la imagen puede ver una captura de la traza. Si el panel está visible se trazará el proceso. Por defecto está limitada a un tamaño máximo de 10000 bytes de contenido de archivos. Para estudiar una traza con objeto de entender el funcionamiento no es nesario tamaños de archivos muy grandes.

Idiomas para la tabla de datos

Publiqué el componente tabla de datos en agosto 2019. Se trataba de un módulo JavaScript para crear una tabla de datos para uso general, especialmente como componente de una interfaz de usuario cuando tenemos que presentar o recibir datos tabulados. Al crear una tabla de datos podíamos pasar el argumento lang con los valores "en" para idioma inglés o "es" para español. Este último es el valor por defecto en caso de que no se especifique idioma. El idioma se aplica al panel de acciones y a la barra de navegación inferior en caso de que se muestre. Y también a los tool tip text o textos alternativos de los botones.

La mejora que presentamos ahora es poder incorporar más idiomas en el momento de crear la tabla. En la imagen puede ver una captura de un ejemplo que se expone en el tema, observándose que hemos agregado francés (FR) y alemán (DE). Además podemos traducir también los títulos de las columnas y el título de la tabla.

Parámetros CRC

En los temas anteriores hemos visto algoritmos para generar el CRC que hemos denominado básicos. Todos ellos se ejecutaban con tres argumentos: el array de bytes del archivo (arrayBytes), el ancho del polinomio (width) y el polinomio (poly). Pero en los algoritmos finales hay que contemplar cuatro argumentos más: init, refin, refout y xorout. En este temas haremos una implementación final del algoritmo reflejado con todos los argumentos. Dado que JavaScript maneja números binarios sólo hasta 32 bits, haremos también otra versión para manejar polinomios de anchos superiores. Completaremos el tema comentando como verificar en el destino un mensaje que nos llegue con el CRC agregado al final.

Algoritmo CRC reflejado con tabla

En los temas anteriores hemos aplicado mejoras empezando por el algoritmo de la división para obtener el resto, pasando al algoritmo del resto pues no nos interesaba el cociente de la división, mejorándolo con otro para evitar el aumento de la entrada y por último llegábamos al algoritmo con índice de un byte, donde pasábamos al tercer argumento de la función mod(x, y, z) un índice que era un valor binario entre 256 posibles.

Esta mejora que veremos en esta tema nos permitirá almacenar en una tabla esos 256 valores para no tener que estar calculándolos con cada byte del archivo. Finalmente veremos como se implementa el algoritmo reflejado con tabla cuyo esquema se observa en la imagen adjunta, algoritmo que es muy eficiente para ejecutar en JavaScript.

Algoritmo CRC básico

Generar el CRC es en esencia calcular el resto de la división entre un mensaje (el dividendo) y un polinomio (el divisor). En lugar de utilizar el algoritmo de la división usamos el algoritmo del resto, que es el mismo pero enfocándonos en obtener el resto más que el cociente.

En el último apartado del tema anterior resolvíamos con un algoritmo básico crcBytesBasic() el resto de un dividendo que podría ser muy largo, como todos los bytes de un archivo, tomando en cada paso un único byte y arrastrando el resto anterior en el tercer argumento del algoritmo del resto en módulo 2 o resto Mod2. La imagen representa un esquema de este algoritmo básico. Para realizar mejoras al algoritmo básico hemos de aplicar un poco de matemáticas. Empezaremos traduciendo este algoritmo del resto Mod2 en una función matemática que expresaremos como mod(x, y, z). Al finalizar el tema habremos obtenido un par de mejoras crcBytesBasic2() y crcBytesBasic3() que nos permitirán pasar a los algoritmos definitivos que trabajan con una tabla.

Algoritmo CRC

La verificación por redundancia cíclica (CRC) es una técnica que agrega información redundante a un mensaje con objeto de verificar en la recepción si el mensaje ha sido modificado no intencionadamente durante la transmisión. El CRC no sirve para verificar la autenticidad del mensaje, pues cualquiera puede modificar el mensaje y la información redundante, con lo que en el destino el mensaje parecerá correcto. Pero si sirve para verificar cambios ocasionados por errores en la transmisión.

Cuando intenté entender los algoritmos que ya existen para obtener el CRC me encontré con trozos de códigos como el de la imagen. Se trata de obtener el CRC de forma recurrente con un algoritmo reflejado iterando por los bytes de un archivo, de tal forma que cuando finalicemos tendremos el CRC. Esta serie de cuatro temas explica qué es el CRC y cómo generarlo sobre los bytes de un archivo.

Calculadora binaria

La calculadora binaria es una pieza de herramienta de Web Tools online para reunir varios recursos relacionados con el cálculo y manejo de números binarios. Tal como se observa en la imagen adjunta, cuenta con un convertidor decimal a binario o hexadecimal, la propia calculadora con números binarios, un convertidor a formato IEEE754 de números en coma flotante y un generador de checksums. Las primeras tres piezas son una reimplementación y mejora de las que ya había publicado en la serie de temas sobre los números en JavaScript: convertidor binario decimal, calculadora binaria y convertidor formato IEEE754.

Se agrega una nueva utilidad para generar un checksum o suma de verificación, que es un trozo de datos dentro un conjunto de datos mayor, cuyo propósito es verificar en el destino que no se han producido cambios accidentales durante la transmisión. Inicialmente incluye la generación de CRC.

Gestor tablas WXTABLE

En la serie de temas que publiqué en enero 2013 sobre Selectores CSS se presentaban unos ejemplos interactivos para poner en práctica los distintos conceptos sobre selectores CSS nivel 3. Ahora agrupo todos esos ejemplos en esta herramienta, incluyendo algunas mejoras, especialmente en lo que se refiere a los pseudoelementos y las pseudoclases estructurales.

El documento W3C Selectors Level 3, que pasó a fase REC (Recommendation) el 06/11/2018, contiene la especificación de los selectores CSS. Lo expuesto en aquella serie de temas sobre selectores CSS y en esta nueva herramienta sigue lo expuesto en ese estándar. Actualmente se encuentra publicado el W3C Selectors Level 4 en fase WD (Working Draft). Este nuevo estándar contiene muchas cosas nuevas que quiero ir probando, permitiéndome la herramienta creada poner en práctica esas nuevas propiedades más fácilmente.

Gestor tablas WXTABLE

El Gestor de tablas WXTABLE tiene por objetivo principal crear tablas HTML. La idea partió de la necesidad de incorporar una muestra visual de una tabla. Hice la tabla en una aplicación de hoja de cálculo y capture la imagen para ponerla en ese tema. A partir de ahí pensé en crear una aplicación que pudiera generar y gestionar tablas HTML.

La facilidad para editar tablas HTML se basa en el uso de botones para combinar celdas. Y otros para aplicar funciones suma, multiplicación, etc. Se dota de barras de botones y menú contextual para ejecutar las acciones necesarias para editar la tabla. Además de HTML, permite importar y exportar en diversos formatos como TSV, CSV, texto y JSON. En HTML podemos hacer una visualización previa del resultado.

Programación dinámica: camino mínimo entre los nodos 1 y 3

Este problema trata de descubrir los caminos mínimos de todas las parejas de nodos de un un grafo con n nodos. En la imagen puede ver el camino mínimo entre el nodo 1 y el 3. Entre los tres caminos posibles tenemos 1→3 con valor 20, 1→4→3 con valor 13+2=15 y, finalmente, 1→2→4→3 con valor 3+8+2=13, siendo este último el de menor valor.

Vimos algo parecido en el tema del algoritmo de Dijkstra para descubrir el camino mínimo desde un nodo seleccionado, que denominábamos como nodo raíz, al resto de nodos. Podríamos modificar aquel algoritmo para iterar por un bucle de tal forma que en cada iteración designáramos como nodo seleccionado a cada uno de ellos. Aquel era un algoritmo voraz, pero usando programación dinámica podemos utilizar el algoritmo de Floyd que encuentra esos caminos de una forma más simple.

Mochila discreta 0-1

La forma en que podemos seleccionar n objetos con peso pi y valor vi para cargarlos en una mochila con un peso máximo P de tal forma que obtengamos el valor máximo V puede dar lugar a tres tipos de problemas. Uno es la Mochila fraccionable que maximice V donde los objetos no pueden repetirse y pueden fraccionarse para completar el peso máximo P. Se resuelve con un algoritmo voraz. Otro es la Mochila discreta 0-∞ que maximice V donde los objetos SI pueden repetirse y NO pueden fraccionarse para completar un peso que no supere el máximo P. Se resuelve con un algoritmo vuelta atrás. Por último la Mochila discreta 0-1 que maximice V donde los objetos NO pueden repetirse y NO pueden fraccionarse para completar un peso que no supere el máximo P. Se resuelve con programación dinámica, lo que nos ocupará este tema.

Tabla resultados intermedios en programación dinámica

Dividir un problema en subproblemas más sencillos para poder resolverlos y luego combinar sus soluciones para obtener la solución general, es una técnica que usamos para resolver problemas, como por ejemplo en los recursivos. Pero a veces los subproblemas se solapan o se calcula lo mismo en varios subproblemas, restando eficiencia a la ejecución de la solución final. Otras veces los algoritmos de optimización como los voraces no logran el resultado final óptimo para algunos conjuntos de datos.

La programación dinámica intenta resolver esta falta de eficiencia o eficacia planteándose como una técnica para evitar calcular lo mismo varias veces, siempre de una forma óptima. Usa una tabla de resultados intermedios mientras resolvemos los subproblemas, resultados óptimos que luego se utilizarán posteriormente para alcanzar la solución óptima final.

Editor grafos SVG: Modo matriz de adyacencia

He realizado una mejora en los módulos del Editor de Grafos SVG para que permita introducir la definición de un grafo con una matriz de adyacencia. Se trata de un array de dimensión n×n para un grafo de n nodos. La imagen muestra como introducimos una de 5 × 5 que define un grafo G con 5 nodos.

Cuando G[i][j]=null entonces es que no hay arista en la dirección de los nodos i → j. Si es distinto de nulo ese será el valor de la arista. Por ejemplo, G[0][4]=14 significa que hay una arista con valor 14 en la dirección 0→4. Por otro lado la posición G[4][0]=null nos dice que esa arista sólo va en esa dirección 0→4 y no en la contraria 4→0. Así se configuraría como un grafo dirigido.


...Ver más en el histórico