¿Formatos de compresión con buen soporte para acceso aleatorio dentro de archivos?

Question

Esto es similar a una pregunta anterior , pero las respuestas 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 práctica y eficiente de admitir la búsqueda de una ubicación en los datos ordenados.

Pero cuando los archivos están comprimidos, las cosas se ponen difíciles. Recientemente descubrí la opción zlib , que se puede usar durante la compresión para insertar " puntos de sincronización " en la salida comprimida (Z_FULL_FLUSH puede comenzar a leer desde varios puntos del archivo). Esto está bien, aunque los archivos que ya tengo tendrían que volver a comprimir para agregar esta función (y extrañamente inflateSync() no tiene una opción para esto, pero estoy dispuesto a escribir mi propio programa de compresión si es necesario).

Parece de una fuente que incluso gzip no es una solución perfecta ... no solo no es compatible con todos los archivos gzip, sino que la idea misma de detectar puntos de sincronización en archivos puede producir falsos positivos (ya sea por coincidencia con el número mágico para 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? Si es posible, me gustaría evitar tener archivos auxiliares para la indexación, y sería útil el soporte predeterminado explícito para el acceso cuasialeatorio (incluso si es de gran tamaño, como poder comenzar a leer en cada intervalo de 10 MB). ¿Existe 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 buscar con cierta granularidad gruesa dentro del archivo comprimido. Solo quiero soporte para algo como & Quot; Descomprima los datos comenzando aproximadamente el 50% (25%, 12.5%, etc.) en este archivo comprimido. & Quot;

Answer 1

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

Por ejemplo, los archivos comprimidos de bzip2 están compuestos de 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 simplemente descomprimir El bloque correcto. Esto necesitaría un poco de indexación para recordar dónde comienzan los bloques.

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

Answer 2

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

Un extracto de su página de manual:

  

dictzip comprime archivos usando el algoritmo gzip (1) (LZ77) de una manera que   es completamente compatible con el formato de archivo gzip. Una extensión al gzip   El formato de archivo (Campo adicional, descrito en 2.3.1.1 de RFC 1952) permite datos adicionales   para ser almacenado en el encabezado de un archivo comprimido. Programas como gzip y zcat   ignorará 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.

Actualización:

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

Answer 3

El formato de archivo .xz (que utiliza compresión LZMA) parece admitir esto:

  

Lectura de acceso aleatorio : los datos se pueden dividir en bloques comprimidos de forma independiente. Cada archivo .xz contiene un índice de los bloques, lo que hace posible una 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 descubrir cómo acceder a bloques al azar.

Answer 4

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

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

( Estoy buscando algo para 7zip )

Answer 5

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

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

No sé hasta qué punto es adaptable a otras aplicaciones.

Answer 6

No estoy seguro de si esto sería práctico en su situación exacta, pero ¿no podría simplemente descomprimir cada archivo grande en archivos más pequeños, digamos 10 MB cada uno? Terminaría con un montón de archivos: file0.gz, file1.gz, file2.gz, etc. Basado en un desplazamiento dado dentro del original grande, puede buscar en el archivo llamado "file" + (offset / 10485760) + ".gz". El desplazamiento dentro del archivo sin comprimir sería offset % 10485760.

Answer 7

Debido a que la compresión sin pérdida funciona mejor en algunas áreas que en otras, si almacena datos comprimidos en bloques de tamaño conveniente BLOCKSIZE, a pesar de que cada bloque tiene exactamente el mismo número de bytes comprimidos, algunos bloques comprimidos se expandirán a un texto plano mucho más largo que otros.

Puedes mirar " 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 Revista Computer Noviembre 2000 http://doi.ieeecomputersociety.org/10.1109/2.881693

Su descompresor toma 1, 2 o 3 bytes enteros de datos comprimidos y se descomprime (usando una lista de vocabulario) en una palabra completa. Se puede buscar directamente en el texto comprimido palabras o frases, que resulta ser 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 dar 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 KJV). Incluso si hay más de 65,000 palabras, es bastante simple asignar los primeros 256 códigos de dos bytes & Quot; palabras & Quot; a todos los bytes posibles, para que pueda deletrear palabras que no están en el léxico de las 65,000 más o menos " palabras y frases más frecuentes " ;. (La compresión obtenida al agrupar palabras y frases frecuentes en dos bytes generalmente vale la " expansión " de ocasionalmente deletrear una palabra usando dos bytes por letra). Hay una variedad de formas de elegir un léxico de & Quot; palabras y frases frecuentes & Quot; eso dará una compresión adecuada. Por ejemplo, podría ajustar un compresor LZW para volcar & Quot; frases & Quot; usa más de una vez para un archivo de léxico, una línea por frase, y lo ejecuta 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 podría cortar sus datos sin comprimir en palabras reales en inglés y poner cada palabra, incluido el espacio al principio de la palabra, en el archivo de léxico. Luego use & Quot; sort --unique & Quot; para eliminar palabras duplicadas en ese archivo léxico. (¿Escoger la perfecta & "; Óptima &"; La lista de palabras del léxico aún se considera NP-difícil?)

Almacene el léxico al comienzo de su enorme archivo comprimido, acóplelo a un tamaño de BLOQUEO conveniente y luego almacene el texto comprimido: una serie de dos bytes & "; palabras &"; - desde allí hasta el final del archivo. Presumiblemente, el buscador leerá este léxico una vez y lo mantendrá en un formato rápido de decodificación en RAM durante la descompresión, para acelerar la descompresión & "; Código de dos bytes &"; a " frase de longitud variable " ;. Mi primer borrador comenzaría con una simple lista de una línea por frase, pero luego podría cambiar para almacenar el léxico en una forma más comprimida utilizando algún tipo de codificación incremental o zlib.

Puede elegir cualquier desplazamiento aleatorio de bytes pares en el texto comprimido y comenzar a descomprimir desde allí. No creo que sea posible crear un formato de archivo comprimido de acceso aleatorio más fino.

Answer 8

Dos posibles soluciones:

1. Deje que el sistema operativo 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 sobre la compresión en su programa 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 & Quot; mkclicfs mytextfile mycompressedfile & Quot; siendo " gzip < mytextfile > mycompressedfile " y " clicfs mycompressedfile directory " como una forma de obtener acceso aleatorio a los datos a través del archivo "directory/mytextfile".

Answer 9

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

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

Answer 10

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

Answer 11

razip admite acceso aleatorio con un mejor rendimiento que gzip / bzip2, que deben modificarse para este soporte, lo que reduce la compresión a expensas de " ok " acceso aleatorio:

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

Answer 12

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 unidades de datos comprimidas 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. Las compensaciones, los metadatos y los datos genómicos comprimidos se concatenan en un solo archivo.

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

Para su caso, puede almacenar (10 MB, o lo que sea) compensaciones en un encabezado en un formato de archivo personalizado. Analiza el encabezado, recupera las compensaciones e incrementalmente fseek a través del archivo current_offset_sum + header_size.