Formatos de compresión con un buen soporte para el acceso aleatorio dentro de los archivos?

Esto es similar a una pregunta anterior , pero las respuestas allí no satisfacen mis necesidades y mi pregunta es ligeramente diferente:

Actualmente uso la compresión gzip para algunos archivos muy grandes que contienen datos ordenados. Cuando los archivos no están comprimidos, la búsqueda binaria es una forma útil y eficiente para ayudar a buscar una ubicación en los datos ordenados.

Pero cuando los archivos están comprimidos, las cosas se vuelven complicadas. Recientemente Z_FULL_FLUSH opción Z_FULL_FLUSH zlib , que se puede usar durante la compresión para insertar “puntos de sincronización” en la salida comprimida ( inflateSync() puede comenzar a leer desde varios puntos del archivo). Esto está bien, aunque los archivos que ya tengo deberían recomprimirse para agregar esta característica (y extrañamente gzip no tiene una opción para esto, pero estoy dispuesto a escribir mi propio progtwig de compresión si es necesario).

Parece que, de una fuente, incluso Z_FULL_FLUSH no es una solución perfecta … no solo no es compatible con todos los archivos gzip, sino que la sola idea de detectar puntos de sincronización en los archivos puede producir falsos positivos (ya sea por coincidencia con el número mágico de puntos de sincronización, o debido al hecho de que Z_SYNC_FLUSH también produce puntos de sincronización pero no son utilizables para acceso aleatorio).

¿Hay una mejor solución? Me gustaría evitar tener archivos auxiliares para la indexación, si es posible, y sería útil una compatibilidad explícita y predeterminada para el acceso cuasialeatorio (incluso si es de gran tamaño, como la posibilidad de comenzar a leer en cada intervalo de 10 MB). ¿Hay otro formato de compresión con mejor soporte para lecturas aleatorias que gzip?

Editar : Como mencioné, deseo hacer una búsqueda binaria en los datos comprimidos. No necesito buscar una posición específica (sin comprimir), solo para buscar con cierta granularidad gruesa dentro del archivo comprimido. Solo quiero soporte para algo como “Descomprimir los datos comenzando aproximadamente el 50% (25%, 12.5%, etc.) del camino en este archivo comprimido”.

No conozco ningún formato de archivo comprimido que pueda admitir el acceso aleatorio a una ubicación específica en los datos sin comprimir (bueno, excepto en los formatos multimedia), pero puede elaborar el suyo propio.

Por ejemplo, los archivos comprimidos bzip2 están compuestos por bloques comprimidos independientes de tamaño <1 MB sin comprimir, que están delimitados por secuencias de bytes mágicos, por lo que puede analizar el archivo bzip2, obtener los límites del bloque y luego descomprimir el bloque correcto. Esto necesitaría cierta indexación para recordar dónde comienzan los bloques.

Aún así, creo que la mejor solución sería dividir el archivo en fragmentos de su elección y luego comprimirlo con algún archivador, como zip o rar, que soporte el acceso aleatorio a archivos individuales en el archivo.

Echa un vistazo a dictzip . Es compatible con gzip y permite un acceso aleatorio grueso.

Un extracto de su página man:

dictzip comprime los archivos usando el algoritmo gzip (1) (LZ77) de una manera que es completamente compatible con el formato de archivo gzip. Una extensión del formato de archivo gzip (Extra Field, descrito en 2.3.1.1 de RFC 1952) permite almacenar datos adicionales en el encabezado de un archivo comprimido. Los progtwigs como gzip y zcat ignorarán estos datos adicionales. Sin embargo, [dictzcat –start] hará uso de estos datos para realizar un acceso pseudoaleatorio en el archivo.

Tengo el paquete dictzip en Ubuntu. O su código fuente está en un dictd – *. Tar.gz. Su licencia es GPL. Eres libre de estudiarlo.

Actualizar:

Mejore dictzip para no tener límite de tamaño de archivo. Mi implementación está bajo licencia de MIT.

El formato de archivo .xz (que usa la compresión LZMA) parece ser compatible con esto:

Lectura de acceso aleatorio : los datos se pueden dividir en bloques comprimidos independientemente. Cada archivo .xz contiene un índice de los bloques, lo que hace posible la lectura limitada de acceso aleatorio cuando el tamaño del bloque es lo suficientemente pequeño.

Esto debería ser suficiente para su propósito. Un inconveniente es que la API de liblzma (para interactuar con estos contenedores) no parece estar bien documentada, por lo que puede tomar algún esfuerzo averiguar cómo acceder aleatoriamente a los bloques.

Existen soluciones para proporcionar acceso aleatorio a los archivos gzip y bzip2:

  • gzip zran.c del código fuente de ghostscript
  • bzip2 seek-bzip por James Taylor

( Estoy buscando algo para 7zip )

bgzip puede comprimir archivos en una variante gzip que es indexable (y gzip puede descomprimirla). Esto se usa en algunas aplicaciones de bioinformática, junto con el indexador de tabix .

Consulte las explicaciones aquí: http://blastedbio.blogspot.fr/2011/11/bgzf-blocked-bigger-better-gzip.html , y aquí: http://www.htslib.org/doc/tabix.html .

No sé en qué medida es adaptable a otras aplicaciones.

No estoy seguro de si esto sería práctico en su situación exacta, pero ¿no podría simplemente convertir gzip cada archivo grande en archivos más pequeños, digamos 10 MB cada uno? Usted terminaría con un grupo de archivos: archivo0.gz, archivo1.gz, archivo2.gz, etc. Basado en un desplazamiento dado dentro del tamaño original, podría buscar en el archivo llamado "file" + (offset / 10485760) + ".gz" . El desplazamiento dentro del archivo descomprimido se offset % 10485760 .

Como la compresión sin pérdida funciona mejor en algunas áreas que otras, si almacena datos comprimidos en bloques de BLOCKSIZE de longitud conveniente, aunque cada bloque tenga exactamente el mismo número de bytes comprimidos, algunos bloques comprimidos se expandirán a una pieza de texto plano mucho más larga que otros .

Puede consultar “Compresión: una clave para los sistemas de recuperación de texto de próxima generación” por Nivio Ziviani, Edleno Silva de Moura, Gonzalo Navarro y Ricardo Baeza-Yates en la revista Computer , noviembre de 2000 http://doi.ieeecomputersociety.org/10.1109 /2.881693

Su descompresor toma 1, 2 o 3 bytes completos de datos comprimidos y descomprime (utilizando una lista de vocabulario) en una palabra completa. Uno puede buscar directamente en el texto comprimido palabras o frases, que resulta incluso más rápido que buscar texto sin comprimir.

Su descompresor le permite señalar cualquier palabra en el texto con un puntero normal (byte) y comenzar a descomprimir inmediatamente desde ese punto.

Puede asignar a cada palabra un código único de 2 bytes, ya que probablemente tenga menos de 65,000 palabras únicas en su texto. (Hay casi 13,000 palabras únicas en la Biblia de KJV). Incluso si hay más de 65,000 palabras, es bastante simple asignar las primeras 256 palabras de “código” de dos bytes a todos los bytes posibles, para que pueda deletrear palabras que no están en el léxico de los 65,000 o menos “más frecuentes”. palabras y frases”. (La compresión obtenida al empaquetar palabras y frases frecuentes en dos bytes generalmente vale la “expansión” de deletrear ocasionalmente una palabra usando dos bytes por letra). Hay una variedad de formas de elegir un léxico de “palabras y frases frecuentes” que dará la compresión adecuada. Por ejemplo, podría ajustar un compresor LZW para volcar “frases” que usa más de una vez en un archivo de léxico, una línea por frase, y ejecutarlo sobre todos sus datos. O podría cortar arbitrariamente sus datos sin comprimir en frases de 5 bytes en un archivo léxico, una línea por frase. O puede cortar sus datos sin comprimir en palabras en inglés reales, y poner cada palabra, incluido el espacio al comienzo de la palabra, en el archivo del léxico. Luego use “ordenar – único” para eliminar las palabras duplicadas en ese archivo léxico. (¿Está escogiendo la lista de palabras del léxico “óptimo” perfecta que todavía se considera NP-hard?)

Guarde el léxico al comienzo de su enorme archivo comprimido, acóplelo en BLOCKSIZE, y luego almacene el texto comprimido, una serie de “palabras” de dos bytes, desde allí hasta el final del archivo. Presumiblemente, el buscador leerá este léxico una vez y lo mantendrá en algún formato de desencoding rápida en la RAM durante la descompresión, para acelerar la descompresión de “código de dos bytes” a “frase de longitud variable”. Mi primer borrador comenzaría con una lista simple de una línea por frase, pero luego podría cambiar al almacenamiento del léxico en una forma más comprimida utilizando algún tipo de encoding incremental o zlib.

Puede elegir cualquier desplazamiento de bytes par aleatorio en el texto comprimido y comenzar a descomprimir desde allí. No creo que sea posible hacer un formato de archivo comprimido de acceso aleatorio de grano fino.

Dos posibles soluciones:

  1. Permita que el SO se ocupe de la compresión, cree y monte un sistema de archivos comprimido (SquashFS, clicfs, cloop, cramfs, e2compr o lo que sea) que contenga todos sus archivos de texto y no haga nada con la compresión en su progtwig de aplicación.

  2. Use clicfs directamente en cada archivo de texto (un clicfs por archivo de texto) en lugar de comprimir una imagen del sistema de archivos. Piense en “mkclicfs mytextfile mycompressedfile” como “gzip mycompressedfile” y “clicfs mycompressedfile directory” como una forma de obtener acceso aleatorio a los datos a través del archivo “directorio / mytextfile”.

No sé si ya se mencionó, pero el proyecto Kiwix había hecho un gran trabajo en este sentido. A través de su progtwig Kiwix, ofrecen acceso aleatorio a archivos de archivos ZIM. Buena compresión, también. El proyecto se originó cuando hubo una demanda de copias fuera de línea de la Wikipedia (que ha llegado a más de 100 GB en forma descomprimida, con todos los medios incluidos). Han tomado con éxito un archivo de 25 GB (una incorporación de un solo archivo de la wikipedia sin la mayoría de los medios) y lo comprimieron en un mísero archivo de archivos zim de 8 GB. Y a través del progtwig Kiwix, puede acceder a cualquier página de la Wikipedia, con todos los datos asociados, más rápido de lo que puede navegar en la red.

Aunque el progtwig Kiwix es una tecnología basada en la estructura de la base de datos de wikipedia, demuestra que puede tener excelentes índices de compresión y acceso aleatorio simultáneamente.

Esta es una pregunta muy antigua, pero parece que zindex podría proporcionar una buena solución (aunque no tengo mucha experiencia con ella)

razip admite acceso aleatorio con un mejor rendimiento que gzip / bzip2, que debe modificarse para este soporte, reduciendo la compresión a expensas del acceso aleatorio “correcto”:

http://sourceforge.net/projects/razip/

Soy el autor de una herramienta de código abierto para comprimir un tipo particular de datos biológicos. Esta herramienta, llamada starch , divide los datos por cromosoma y usa esas divisiones como índices para un acceso rápido a las unidades de datos comprimidos dentro del archivo más grande.

Los datos por cromosoma se transforman para eliminar la redundancia en las coordenadas genómicas, y los datos transformados se comprimen con algoritmos bzip2 o gzip . Los desplazamientos, los metadatos y los datos genómicos comprimidos se concatenan en un archivo.

El código fuente está disponible en nuestro sitio GitHub . Lo hemos comstackdo bajo Linux y Mac OS X.

Para su caso, puede almacenar (10 MB, o lo que sea) compensaciones en un encabezado a un formato de archivo personalizado. Se analiza el encabezado, se recuperan los desplazamientos y se desplaza gradualmente por el archivo por current_offset_sum + header_size .

    Intereting Posts