compression - tipos - la compresión de un archivo funciona a través de
¿Cuál es el mejor algoritmo de compresión que permite lecturas/escrituras aleatorias en un archivo? (7)
Ningún esquema de compresión permitirá acceso aleatorio de grano fino, por dos razones relacionadas:
- no se puede saber exactamente qué tan profundo está dentro del archivo comprimido la información que se desea, por lo tanto,
- no hay forma de saber dónde comienza un símbolo (en qué posición de bit para Huffman, peor para la codificación aritmética).
Solo puedo sugerir tratar el archivo como un flujo de difusión e insertar marcadores frecuentes de sincronización / posición, con una sobrecarga obvia (las marcas de sincronización no solo ocupan espacio sino que complican la codificación porque debe evitar las marcas de sincronización "accidentales"). Alternativamente, y para evitar buscar algo así como una búsqueda binaria (con la optimización de que puede adivinar mejor dónde comenzar que a la mitad), puede incluir una "tabla de contenido" al comienzo o al final del archivo.
En cuanto a la escritura de acceso aleatorio ... No puedo pensar en ninguna solución ordenada :(
¿Cuál es el mejor algoritmo de compresión que permite lecturas / escrituras aleatorias en un archivo?
Sé que cualquier algoritmo de compresión adaptativo estaría fuera de discusión.
Y sé que la codificación huffman estaría fuera de discusión.
¿Alguien tiene un mejor algoritmo de compresión que permita lecturas / escrituras aleatorias?
Creo que podrías usar cualquier algoritmo de compresión si lo escribes en bloques, pero idealmente no me gustaría tener que descomprimir un bloque completo a la vez. Pero si tiene sugerencias sobre una manera fácil de hacer esto y cómo conocer los límites del bloque, hágamelo saber. Si esto es parte de su solución, también déjeme saber qué hace cuando los datos que desea leer se encuentran en un límite de bloque.
En el contexto de sus respuestas, asuma que el archivo en cuestión es de 100GB, y algunas veces querré leer los primeros 10 bytes, y algunas veces querré leer los últimos 19 bytes, y algunas veces quiero leer 17 bytes en el medio. .
No sé de ningún algoritmo de compresión que permita lecturas aleatorias, sin importar las escrituras aleatorias. Si necesita ese tipo de habilidad, su mejor opción sería comprimir el archivo en fragmentos en lugar de hacerlo en conjunto.
p.ej
Primero veremos el caso de solo lectura. Digamos que divide su archivo en fragmentos de 8K. Comprimes cada fragmento y almacenas cada fragmento comprimido secuencialmente. Tendrá que registrar dónde está almacenado cada trozo comprimido y qué tan grande es. Luego, digamos que necesita leer N bytes comenzando en el desplazamiento O. Necesitará descubrir en qué trozo está (O / 8K), descomprimir ese trozo y tomar esos bytes. Los datos que necesita pueden abarcar varios fragmentos, por lo que debe lidiar con ese escenario.
Las cosas se complican cuando quieres poder escribir en el archivo comprimido. Tienes que lidiar con trozos comprimidos cada vez más grandes y más pequeños. Es posible que necesite agregar un relleno adicional a cada fragmento en caso de que se expanda (sigue siendo el mismo tamaño descomprimido, pero los datos diferentes se comprimirán en diferentes tamaños). Incluso puede necesitar mover fragmentos si los datos comprimidos son demasiado grandes para caber en el espacio original que se le dio.
Esto es básicamente cómo funcionan los sistemas de archivos comprimidos. Puede que sea mejor activar la compresión del sistema de archivos para sus archivos y simplemente leerlos / escribirlos normalmente.
La compresión consiste en eliminar la redundancia de los datos. Desafortunadamente, es poco probable que la redundancia se distribuya con uniformidad monótona en todo el archivo, y ese es el único escenario en el que podría esperar compresión y acceso aleatorio de grano fino.
Sin embargo, podría acercarse al acceso aleatorio manteniendo una lista externa, creada durante la compresión, que muestra la correspondencia entre los puntos elegidos en el flujo de datos sin comprimir y sus ubicaciones en el flujo de datos comprimido. Obviamente, debe elegir un método en el que el esquema de traducción entre el flujo de origen y su versión comprimida no varíe con la ubicación en el flujo (es decir, no LZ77 o LZ78; en su lugar, probablemente prefiera ir a Huffman o byte). codificación de pares.) Obviamente, esto supondría una gran sobrecarga, y usted tendría que decidir cómo quería negociar entre el espacio de almacenamiento necesario para los "puntos de marcador" y el tiempo de procesador necesario para descomprimir la secuencia a partir de una punto de marcador para obtener los datos que está buscando en la lectura.
En cuanto a la escritura de acceso aleatorio ... eso es casi imposible. Como ya se señaló, la compresión consiste en eliminar la redundancia de los datos. Si intenta reemplazar datos que podrían estar comprimidos porque era redundante con datos que no tienen la misma redundancia, simplemente no encajarán.
Sin embargo, dependiendo de la cantidad de escritura de acceso aleatorio que vaya a hacer, puede simularla manteniendo una matriz dispersa que represente todos los datos escritos en el archivo después de la compresión. En todas las lecturas, verificaría la matriz para ver si estaba leyendo un área en la que escribió después de la compresión. Si no, entonces iría al archivo comprimido para los datos.
Un esquema de compresión basado en el diccionario, con cada código de entrada de diccionario codificado con el mismo tamaño, permitirá comenzar a leer en cualquier múltiplo del tamaño del código, y las escrituras y actualizaciones son fáciles si los códigos no hacen uso de su contexto / vecinos
Si la codificación incluye una forma de distinguir el inicio o el final de los códigos, entonces no necesita que los códigos tengan la misma longitud, y puede comenzar a leer en cualquier parte del medio del archivo. Esta técnica es más útil si estás leyendo desde una posición desconocida en una secuencia.
Creo que Stephen Denne podría estar en algo aquí. Imagina:
- compresión tipo zip de secuencias a códigos
- un código de mapeo de diccionario -> secuencia
- archivo será como un sistema de archivos
- cada escritura genera un nuevo "archivo" (una secuencia de bytes, comprimida según el diccionario)
- "sistema de archivos" realiza un seguimiento de qué "archivo" pertenece a qué bytes (inicio, fin)
- cada "archivo" está comprimido según el diccionario
- lee trabajo en sentido de archivo, descomprime y recupera bytes según el "sistema de archivos"
- escribe que los "archivos" no son válidos, se añaden nuevos "archivos" para reemplazar los invalidados
- este sistema necesitará:
- mecanismo de desfragmentación del sistema de archivos
- compactando el diccionario de vez en cuando (eliminando los códigos no utilizados)
- hecho correctamente, la limpieza se puede hacer cuando nadie está mirando (tiempo de inactividad) o creando un nuevo archivo y "cambiando" eventualmente
Un efecto positivo sería que el diccionario se aplicaría a todo el archivo. Si puede ahorrar los ciclos de la CPU, puede verificar periódicamente las secuencias que se superponen a los límites del "archivo" y luego reagruparlas.
Esta idea es para lecturas verdaderamente aleatorias. Si solo vas a leer registros de tamaño fijo, algunas partes de esta idea podrían ser más fáciles.
El formato razip admite lecturas de acceso aleatorio con un mejor rendimiento que gzip / bzip2, que deben modificarse para este soporte:
Estoy sorprendido por la cantidad de respuestas que implican que tal cosa es imposible.
¿Alguna vez esta gente ha oído hablar de los "sistemas de archivos comprimidos", que existían desde antes de que Microsoft fuera demandado en 1993 por Stac Electronics por la tecnología de sistema de archivos comprimido?
Escuché que LZS y LZJB son algoritmos populares para las personas que implementan sistemas de archivos comprimidos, que necesariamente requieren tanto lecturas de acceso aleatorio como escrituras de acceso aleatorio.
Quizás lo más simple y lo mejor que se puede hacer es activar la compresión del sistema de archivos para ese archivo y dejar que el sistema operativo se encargue de los detalles. Pero si insistes en manejarlo manualmente, quizás puedas obtener algunos consejos al leer sobre la compresión de archivos transparente NTFS .
También consulte: ": formatos de compresión con buen soporte para el acceso aleatorio dentro de los archivos".