8 respuestas en este tema

[Delphius]

Hola.

Hoy vengo con una pregunta que quizá sea media peliaguda... admito que no la he pensado mucho, pero ahí va.

Estoy haciendo una prueba de concepto de algunas ideas para un proyecto en pendiente. Y por lo que estado averiguando sobre el tema, hay ciertas técnicas que pueden ayudar al momento de guardar mucha info de lo mismo. Y si pinta bien, quizá considere añadir esto para mi repertorio.

 

Trataré de explicarme.

Hagamos de cuenta que tengo cierta cantidad de data que va a ser "procesada" en bloques. Se puede ver a cada bloque como una lista de items. La información es relativamente sencilla, por ahora es sólo un identificador.

 

Entonces tendríamos algo como esto:

Bloque 1: data1, data2, ..., dataN

Bloque 2: data1, data2, ..., dataN

...

Bloque M: data1, data2, ..., dataN

 

En memoria tanto M como N son conocidos y ya está la estructura presente para usar.

Bueno, parece fácil. Basta con recorrer la estructura y empezar a meterlo.

 

Pero hay cosas que pueden aderezar esto, la data a almacenar puede que se repita y por tanto podría ser bastante útil aplicar RLE para reducir de peso el archivo. Es más, mis fuentes dicen que es lo más aconsejable.

Por si desconocen, RLE es un algoritmo bastante simple de "compresión". Lo que hace es almacenar la información en forma de pares <x,y> siendo x la cantidad de repetidos en la serie hasta encontrar un elemento diferente e y el valor correspondiente.

 

Entonces ya podría hacerse algo como esto:

 

Bloque 1: <cant1, data1><cant2, data2>...<cantx,datax>

Bloque 2: <cant1, data1><cant2, data2>...<cantx,datax>

...

Bloque M: <cant1, data1><cant2, data2>...<cantx,datax>

 

Siendo x una cantidad desconocida. Por diseño del algoritmo RLE cant1 + ... + cantx necesariamente debe ser N.

 

Justamente como la data puede "comprimirse" y que dicho archivo va a reutilizarse, cualquier cambio en la data va a alterar las cosas.

Por lo que estuve viendo, y entiendo para que la información no se "pise" entre cada bloque, lo que se suele hacer es reservar un espacio o tamaño para cada bloque, lo suficiente (al menos en lo mínimo) como para cubrir el peor escenario de RLE: que no haya secuencias de repetidos:

 

Bloque 1: <1, data1><1, data2>...<1, dataN>

Bloque 2: <1, data1><1, data2>...<1, dataN>

...

Bloque 1: <1, data1><1, data2>...<1, dataN>

 

En el mejor caso tendré:

 

Bloque 1: <cantN, data>

Bloque 2: <cantN, data>

...

Bloque M: <cantN, data>

 

Pero en la mayoría las cosas será diferente y variable:

 

Bloque 1: <cant1, data1><cant2, data2>...<cantx, datax>

Bloque 2: <cant1, data1><cant2, data2>

...

Bloque M: <cant1, data1><cant2, data2>...<canty, datay>

 

Entonces, como dije, se estila "reservar" espacio entre los bloques para que uno pueda expandirse y/o achicarse sin riesgos de pisar un bloque ajeno.

Visualmente, las cosas sería algo como:

 

Bloque 1: <cantN, data>------------------------------------------------------------------

Bloque 2: <cant1, data1><cant2, data2>...<cantx,datax>------------------------

...

Bloque M: <1, data1><1, data2>..................................................<1,dataN>

 

Siendo "..." información que no se ve por razones de simplicidad, y "---" la memoria reservada disponible.

 

Mi pregunta es, ¿Cómo se hace para trabajar así? Estaba pensando en que quizá se puede aplicar o aprovechar algo de lo que implementé para mi otro trabajo. Pero no he probado en tirar datos en "bloques".

 

Esto de "reservar" como que no cierra. ¿Hay que dar un tamaño concreto al archivo, digamos como calcular el peor escenario contando todos los bloques, y de ahí jugar con seek() para ubicarnos en cada bloque? ¿Es decir, mandar la estructura completa a guardar con "ceros"? Por ejemplo digamos que M=300, N=500. En total tenemos 300x500 x Size(Dato) = 150000 x Size(Dato). Digamos que el dato entra en un byte, cada bloque consta de 500 bytes.

 

Entonces, en la etapa inicial al momento de crear por primera vez el archivo, para "reservar" cualquier bloque ¿haría algo como esto?

delphi

for i := 1 to 500 do
  Datas[bloque, i] := 0;
Archivo.WriteBuffer(Datas[Bloque], 500); // No he probado realmente si acepta como buffer que se le indique la fila

En última, lo que podría hacerse, es ir uno a uno:

delphi

DataClear := 0;
for i := 1 to 500 do
  Archivo.WriteBuffer(DataClear, 1);
end;

Lo que obviamente hay que evitar.

 

Mi pregunta son: ¿O es que hay una forma más simple, correcta, limpia, y directa, de decirle "Mirá, necesito que aquí me dejes X cantidad de bytes disponibles para cuando quiera usar"? Y no tener que tener "generarlo" poniendo ceros... Si la hay, ¿que hace, pone 0 o se vería un vacio en el archivo?

 

Otra muy buena ventaja de hacer esa "reserva" es que de forma natural es posible calcular donde comienza cada bloque por lo que con Seek() lo tenemos muy cómodo. Siguiendo con el ejemplo, el bloque 1 va del byte 1 al 500, el bloque 2 del 501 al 1000, etc.

 

¿Y en casos en que tras una reescritura al aplicar el RLE se detecte que hay menos pares, que se hace con esa "basura"? En principio se la podría ignorar. Después de todo no molesta en realidad.

 

Me gustaría explorar esto de la RLE, ya que se está pensando en mucha data... y si encima de esto uno le aplica 7ZIP... reduce mucho el resultado final.

¿Cómo le harían ustedes? ¿O que técnicas se pueden emplear cuando el archivo es cambiante? ¿Mandarían a reescribir todo cada vez?

 

Saludos,

[escafandra]

Cuando utilizas compresión no RLE no sabrá cómo hacerlo hasta tener los datos definitivos. Eso supone reescribir el archivo para comprimirlo. En realidad no se si quieres comprimir el archivo como un bloque o comprimar bloque por separado.
 
En este enlace tienes una forma directa y simple para reservar espacio a un archivo.

Saludos.

[Delphius]

Cuando utilizas compresión no RLE no sabrá cómo hacerlo hasta tener los datos definitivos. Eso supone reescribir el archivo para comprimirlo. En realidad no se si quieres comprimir el archivo como un bloque o comprimar bloque por separado.
 
En este enlace tienes una forma directa y simple para reservar espacio a un archivo.

Saludos.

 

Mi idea es aplicar RLE a la data bloque por bloque. Es decir, a cada bloque. De esta forma se evitaría (en la mayoría de las ocasiones) tener una lista completa.

En el mismo archivo tengo previsto añadir más información adicional pero que no es posible de "comprimir" con RLE.

De forma simplificada el archivo tendría una estructura así:

 

Info general

Data de los bloques

Más info

 

La idea de RLE es ahorrar lo más posible en estar añadiendo data repetida. Cada bloque de datos debe trabajarse por separado, por lo que no he previsto hasta el momento alguna utilidad de aplicar RLE a todo.

Mi gran duda es como manejar esta "separación" y espacios vacios entre cada bloque cuando la información está comprimida. Naturalmente si se presenta una secuencia de datos tal que cada elemento no repite el bloque tendrá su máximo tamaño.

 

Tanto M y N son pre-fijados y no podrán alterarse por lo que se conoce lo máximo y mínimo que puede ocupar todos y cada uno de los bloques. Esto me tranquiliza ya que si fuera posible alterarlos no sólo tendría que preveer los cambios dentro de los bloques, sino que debería contemplar añadir o borrar bloques nuevos bloques. Y eso complicaría las cosas el doble.

 

En cuanto pueda me pongo a leer el enlace que ofreces.

 

Saludos,

[escafandra]

Sí el tamaño de los bloque es indefinido por el uso de RLE, lo mejor es escribir una babel era de tamaño fijo con los tamaños de los bloques una vez comprimidos para localizarlos a la hora de su descompresión.

Saludos.

[Delphius]

Sí el tamaño de los bloque es indefinido por el uso de RLE, lo mejor es escribir una babel era de tamaño fijo con los tamaños de los bloques una vez comprimidos para localizarlos a la hora de su descompresión.

Saludos.

 

Déjame ver si entiendo,

¡Tu dices que quizá sea buena idea disponer una especie de "lista" con los tamaños de los bloques? Es decir algo como una especie de "cabecera" de los bloques, y me base en ello, a modo de Offset, para dezplazarme y localizar el inicio de cada uno:

 

Tam.Bloque-1

Tam.Bloque-2

...

TamBloque-M

Bloque-1 = <...>

Bloque-2 = <...>

...

Bloque-M = <...>

 

No estaría mal la idea. Había visto algo de esto en otro lado. De paso quizá también pueda serme útil este "header" para registrar también otras cosas relacionadas con los bloques.

 

Yo más pensaba esto de "reservar" el espacio máximo (el peor escenario para el RLE) necesario para cada bloque para no tener que estar "recalculando" y "pisando" los datos sobre los bloques. En ocasiones se necesita trabajar con un solo bloque, en otras con varios.

Por ejemplo, si el 5to bloque tiene únicamente esta data: <500, 325> e inmediatamente comienza el 6to bloque y tiene como data <1,224>...<500,785>. Si en un momento posterior tengo que modificar el 5to bloque y su data se ve "ampliada a esto: <10,654>...<123,96> deberé como mínimo reubicar todo el 6to bloque ¡Y quien sabe si no también deberé hacerlo con los demás!

 

De todas formas, creo, que necesariamente deberé tener esa tabla/lista de Offset y tamaños. Ya sea que deba correr toda la data bloque a bloque como si reservara los "espacios en blanco". Aunque ahora que lo pienso, que sentido tendría aplicar RLE si al final tengo esos "ceros/vacios", el tamaño sería el mismo... Aunque para este caso quizá sea útil una comprensión con algo como 7ZIP para reducir el tamaño del archivo, y descomprimirlo cuando necesite volcar el contenido a la memoria.

 

Saludos,

[escafandra]

Exacto. No tiene sentido reservar el espacio sin comprimir. Lo mejor es comprimir el archivo al escribirlo una vez conocidos los tamaños finales. Otra forma es no comprimir por bloques sino el archivo final.

 

Saludos.

[Delphius]

Ummm. Quizá si se pueda tener un "equilibrio" entre comprensión RLE, cantidad de espacio de bloque, tamaño de archivo.

Estimo que será algo baja la posibilidad de que se diera el peor caso de RLE por lo que rara vez debería mover todos los bloques. Podría hacer que inicialmente cada bloque tenga un "espacio" "promedio" entre el mejor y peor caso de RLE.

 

EDITO:

 

había dicho:

 

Supongamos que N sea 500, en el peor caso: el espacio será de 500*Size(TipoDato) bytes, en el mejor de 1*Size(TipoDato) bytes y en el medio... 250*Size(TipoDato) bytes

 

No es correcto, ya que la dupla <cantidad,valor> es la que define el tamaño del "sector" a emplear. Si N = 500, y para tal se requiere de un smallint (2 bytes) es el tamaño del bloque y si decimos que por ejemplo el tipo de dato para el campo "valor" es un integer de 4 bytes:

 

Mejor caso: <cant,valor> = 2 bytes + 4 bytes = 6 bytes

Peor caso: <1, valor-1>...<1,valor-N> = 500*6 bytes = 3000 bytes

 

Para un "promedio" se tendría 250 pares, por lo que nos da 1500 bytes.

 

Ahora si por ejemplo tenemos M = 1500 bloques:

Total mejor = 6 * 1500 = 9000 bytes (aprox. 8.79 KB)

Total peor = 3000 bytes * 1500 = 4500000 bytes (aprox. 4.22 MB)

Total promedio = 1500 * 1500 = 2250000 bytes (aprox. 2.15 MB)

 

Creo que la solución "salomónica" no viene tan mal después de todo... A ver que opina el gran maestro escafandra.

 

Saludos,

[escafandra]

Quizás es más recomendable recomprimir el archivo cada vez o usar varios archivos. Aquí abría que pensar de que tamaño de archivo total estamos hablando, para que sea rentable no reescribirlo.

 

 

Saludos. 

[Delphius]

Quizás es más recomendable recomprimir el archivo cada vez o usar varios archivos. Aquí abría que pensar de que tamaño de archivo total estamos hablando, para que sea rentable no reescribirlo.

 

 

Saludos. 

 

No hice los números finales todavía como para saber de que tamaño será. Encima no he considerado el resto de la información adicional que será necesaria. Tentativamente, los primeros números que tengo son: M=392, N=67228, para el valor no está definido el tipo, quizá el byte me queda chico; aunque el smallint ya me sobra demasiado. Asi que pongamos un Size(Valor) = 2 bytes. Necesito otros 2 bytes para poder almacenar M y 4 bytes para N.

Los primeros números, y solamente para lo que son los bloques de data:

Mejor caso: (392 * 2 bytes) * Size(67228, Valor>) = 784 bytes x (4 bytes + 2 bytes) = 4704 bytes (aprox. 4,82 KB)

Peor caso: (392 * 2 byes) * <1,valor>...<1,valor> = 784 bytes x (67228 x (1 bit +  2 bytes) = 158120256 bytes (aprox. 150,80 MB)

 

Había descartado tener varios archivos. Tengo entendido que las operaciones I/O son más costosas, cuanto más archivos se tengan. Es preferible tener la info en un único archivo que dispersa en varios. Abrir, cerrar, varias veces varios archivos son un costo considerable.

 

Aunque ahora viendo el peor caso, ya me asusta un poco y no descarto la posibilidad de emplear subbloques. O que el enfoque de bloques independientes cambiarlo, y considerar a toda la data como un mega bloque y ahí comprimirlo entero.

 

Viendo ese número de peor caso, y aún sabiendo que rara vez se presentaría con más razón considero que se aplique al final un 7ZIP. Tengo que controlar mejor la cantidad de bloques, como el tamaño, Quizá si se pueda ajustar mejor los números podría ahorrarme la mitad.

 

Lo tengo esto en un estado muy experimental, y todavía no he tirado algo de código para ver como se comporta. Podría llegar a hacer una prueba el fin de semana.

 

Saludos,