SoloCodigo
Programación Específica => Diseño de Algoritmos => Mensaje iniciado por: su - en Domingo 21 de Mayo de 2006, 02:25
-
Hola.
Bueno, lo que quiero es saber la mejor forma de comprimir un archivo y tengo un idea, pero tiene sus problemas:
Tengo un archivo de X tamaño.
Leo sierto numero de bits que es determinado por el tamaño del archivo (tiene que ser asi, porque es la unica forma de que no se sature la memoria), a esto lo llamo bloque.
Tomo este bloque y lo "desdoblo" en un orden ascendente de bits (pack("b*", bloque)) y remplaso sierta combinacion de unos y ceros por otros numeros.
El problema es que al "desdoblarlo" el tamaño del archivo queda mucho mas grande y al remplasar, el archivo queda mas grande.
El error es que al pasarlo a bits cada caractel queda en 8 bits de tamaño (es decir, la letra "a" queda en 8 unos y ceros, que cada uno ocupa 8 bits de taño)
Entonces, como seria el algoritmo perfecto para esto?
Gracias.
-
yo hice un algoritmo de compresion medio choto que funciono, solo funciona para texto.
es asi:
el programa lee el archivo de texto, se fija los caracteres que no se usan y hace una tabla.
luego lee el archivo buscando las combinaciones de dos letras que mas se repiten y selecciona las N mas repetidas, elije los N primeros caracteres sin usar y remplaza esas duplas por estos caracteres, luego escribe una cabecera con la asignacion de caracteres y duplas.
si lo haces recursivamente sobre un archivo aleatorio ( yo usaba los man de linux :P ), podes llegar a comprimir un archivo al 60% de su tamaño.
eso es todo.
(no se mucho de algoritmos de compresion ese se me ocurrio y funciono)
-
Creo que asi funcionava el LZV1, pero encontr uno mejor:
http://en.wikipedia.org/wiki/LZO (http://en.wikipedia.org/wiki/LZO)
Gracias por la idea!
:hola:
-
Lo que decis se llama Huffman, y LZW es una libreria para esto, creo que las imagenes .gif usan este algoritmo
Aqui hay mas info:
http://www.perlmonks.org/?node_id=270016 (http://www.perlmonks.org/?node_id=270016)
:smartass:
-
:o Use aquella idea de combertir todo en bits y remplazarlo por caractles.
Es mu sinple, solo hago un loop que crea las caracteles ascii (33-256) y otro loop o bucle que toma el archivo, lo lee (con sysread) y crea sierto numero de bloques dependiendo de el tamaño del archivo.
Al final el resultado es comparable al del algoritmo compress de Unix, deve de funcionar con binarios o archivos ofuscados como base de datos.
Bueno, lo posteo por si sirve de algo ;)
:hola:
-
:P :P :P :P
WOW fascinante.
-
El problema es cuando el archivo es de 1M o menos, queda un poco mas grande por la diferencia en cada bloque. :rolleyes: