Formats de compression prenant en charge l’accès aléatoire dans les archives?

https://stackoverflow.com/questions/429987

07-07-2019
|

Question

Ceci est similaire à une question précédente , mais les réponses ne répondent pas à mes besoins et ma question est légèrement différente. :

J'utilise actuellement la compression gzip pour certains très gros fichiers contenant des données triées. Lorsque les fichiers ne sont pas compressés, la recherche binaire est un moyen pratique et efficace de rechercher un emplacement dans les données triées.

Mais lorsque les fichiers sont compressés, les choses deviennent difficiles. J'ai récemment découvert l'existence de l'option Z_FULL_FLUSH de zlib , qui peut être utilisée lors de la compression pour insérer &. "points de synchronisation &" dans la sortie compressée (inflateSync() peut alors commencer à lire à partir de différents points du fichier). Ceci est correct, bien que les fichiers que j'ai déjà devront être recompressés pour ajouter cette fonctionnalité (et étrangement, gzip n'a pas d'option pour cela, mais je suis prêt à écrire mon propre programme de compression si je le dois).

Il semble qu'il s'agisse de une source qui Même si Z_SYNC_FLUSH n’est pas une solution parfaite ... non seulement elle n’est pas supportée par toutes les archives gzip, mais l’idée même de détecter des points de synchronisation dans les archives peut produire des faux positifs (soit par coïncidence avec le nombre magique pour les points de synchronisation, ou étant donné que <=> génère également des points de synchronisation mais qu’ils ne sont pas utilisables en accès aléatoire).

Y a-t-il une meilleure solution? J'aimerais éviter d'avoir si possible des fichiers auxiliaires pour l'indexation, et explicite, une prise en charge par défaut pour un accès quasi aléatoire serait utile (même si elle est volumineuse - comme pouvoir commencer à lire à chaque intervalle de 10 Mo). Existe-t-il un autre format de compression offrant une meilleure prise en charge des lectures aléatoires que gzip?

Modifier : comme je l'ai mentionné, je souhaite effectuer une recherche binaire dans les données compressées. Je n'ai pas besoin de chercher une position spécifique (non compressée) - seulement de chercher avec une granularité grossière dans le fichier compressé. Je souhaite simplement une prise en charge de quelque chose comme & "; Décompressez les données à partir de 50% environ (25%, 12,5%, etc.) du chemin dans ce fichier compressé. &";

La solution

Je ne connais aucun format de fichier compressé qui permette un accès aléatoire à un emplacement spécifique dans les données non compressées (ainsi, sauf pour les formats multimédia), mais vous pouvez créer votre propre fichier.

Par exemple, les fichiers compressés bzip2 sont composés de blocs compressés indépendants de taille < 1 Mo non compressés, délimités par des séquences d’octets magiques. Vous pouvez donc analyser le fichier bzip2, obtenir les limites du bloc, puis décompresser le bloc droit. Cela nécessiterait une certaine indexation pour se rappeler où commencent les blocs.

Néanmoins, je pense que la meilleure solution serait de scinder votre fichier en morceaux de votre choix, puis de le compresser avec un archiveur, tel que zip ou rar, permettant un accès aléatoire à des fichiers individuels de l'archive.

Autres conseils

Découvrez dictzip . Il est compatible avec gzip et permet un accès aléatoire grossier.

Un extrait de sa page de manuel:

dictzip compresse les fichiers à l'aide de l'algorithme gzip (1) (LZ77) de manière à est complètement compatible avec le format de fichier gzip. Une extension du gzip Le format de fichier (Extra Field, décrit au § 2.3.1.1 de la RFC 1952) autorise des données supplémentaires à stocker dans l'en-tête d'un fichier compressé. Des programmes comme gzip et zcat va ignorer ces données supplémentaires. Cependant, [dictzcat --start] utilisera de ces données pour effectuer un accès pseudo-aléatoire sur le fichier.

J'ai le paquet dictzip dans Ubuntu. Ou bien son code source se trouve dans un dictd - *. Tar.gz . Sa licence est GPL. Vous êtes libre de l'étudier.

Mise à jour:

J'ai amélioré dictzip pour ne pas avoir de limite de taille de fichier. Mon implémentation est sous licence MIT.

Le format de fichier .xz (qui utilise la compression LZMA) semble prendre en charge cette fonctionnalité:

Lecture à accès aléatoire : les données peuvent être fractionnées en blocs compressés indépendamment. Chaque fichier .xz contient un index des blocs, ce qui permet une lecture en accès aléatoire limitée lorsque la taille du bloc est suffisamment petite.

Cela devrait suffire à vos fins. L’inconvénient est que l’API de liblzma (pour interagir avec ces conteneurs) ne semble pas très bien documentée. Il peut donc être difficile de trouver un moyen d’accéder de manière aléatoire aux blocs.

Il existe des solutions pour fournir un accès aléatoire aux archives gzip et bzip2:

gzip zran. c depuis le code source ghostscript
bzip2 seek-bzip de James Taylor

( Je cherche quelque chose pour 7zip )

bgzip peut compresser des fichiers dans une gzip variante indexable (et pouvant être décompressée par tabix). Ceci est utilisé dans certaines applications bioinformatiques, avec le <=> indexeur.

Voir les explications ici: http: // blastedbio .blogspot.fr / 2011/11 / bgzf-bloqués-plus-meilleurs-gzip.html , et ici: http://www.htslib.org/doc/tabix.html .

Je ne sais pas dans quelle mesure il est adaptable à d'autres applications.

Je ne sais pas si cela serait pratique dans votre situation exacte, mais ne pouvez-vous pas gzip chaque fichier volumineux en fichiers plus petits, par exemple 10 Mo chacun? Vous vous retrouveriez avec un tas de fichiers: fichier0.gz, fichier1.gz, fichier2.gz, etc. Sur la base d'un décalage donné dans le grand d'origine, vous pouvez rechercher dans le fichier nommé "file" + (offset / 10485760) + ".gz". Le décalage dans l'archive non compressée serait offset % 10485760.

La compression sans perte fonctionnant mieux sur certaines zones que d’autres, Si vous stockez des données compressées dans des blocs de longueur convenable BLOCKSIZE, même si chaque bloc contient exactement le même nombre d'octets compressés, certains blocs compressés deviendront un texte en texte clair beaucoup plus long que d'autres.

Vous pourriez regarder " Compression: une clé pour les systèmes de récupération de texte de nouvelle génération " par Nivio Ziviani, Edleno Silva de Moura, Gonzalo Navarro et Ricardo Baeza-Yates dans Magazine Computer de novembre 2000 http://doi.ieeecomputersociety.org/10.1109/2.881693

Leur décompresseur prend 1, 2 ou 3 octets complets de données compressées et les décompresse (à l'aide d'une liste de vocabulaire) en un mot entier. On peut rechercher directement dans le texte compressé des mots ou des phrases, ce qui s'avère être encore plus rapide que la recherche de texte non compressé.

Leur décompresseur vous permet de pointer n'importe quel mot du texte avec un pointeur normal (octet) et de commencer à décompresser immédiatement à partir de ce point.

Vous pouvez attribuer à chaque mot un code unique de 2 octets, car votre texte contient probablement moins de 65 000 mots uniques. (Il y a presque 13 000 mots uniques dans la Bible au format KJV). Même s'il y a plus de 65 000 mots, il est assez simple d'affecter les 256 premiers codes à deux octets & "Mots &"; afin de pouvoir épeler des mots qui ne figurent pas dans le lexique des quelque 65 000 & "; mots et expressions les plus fréquents &"; (La compression obtenue en compressant des mots et des phrases fréquents en deux octets vaut généralement le " expansion " épelant occasionnellement un mot en utilisant deux octets par lettre). Il existe différentes façons de choisir un lexique de & «Mots et expressions fréquents &»; cela donnera une compression adéquate. Par exemple, vous pouvez modifier un compresseur LZW pour vider & "Phrases &"; il utilise plusieurs fois un fichier de lexique, une ligne par phrase, et l'exécute sur toutes vos données. Vous pouvez également découper arbitrairement vos données non compressées en phrases de 5 octets dans un fichier de lexique, une ligne par phrase. Vous pouvez également découper vos données non compressées en mots anglais réels et placer chaque mot - y compris l'espace au début du mot - dans le fichier lexique. Ensuite, utilisez & "; Sort --unique &"; pour éliminer les mots en double dans ce fichier de lexique. (Est-ce que choisir la liste de mots & "Optimale optimale" du lexique est toujours considéré comme NP-difficile?)

Stockez le lexique au début de votre énorme fichier compressé, ajoutez-le à un bloc BLOCKSIZE, puis stockez le texte compressé - une série de mots & "de deux octets"! - de là à la fin du fichier. Vraisemblablement, le chercheur lira une fois ce lexique et le conservera dans un format de décodage rapide en mémoire vive pendant la décompression, pour accélérer la décompression de & "Code à deux octets &"; à " expression de longueur variable " ;. Mon premier brouillon commencerait par une simple liste d'une phrase par phrase, mais vous pourriez ultérieurement choisir de stocker le lexique sous une forme plus compressée à l'aide d'une sorte de codage incrémental ou zlib.

Vous pouvez choisir n'importe quel décalage d'octet pair aléatoire dans le texte compressé et commencer à décompresser à partir de là. Je ne pense pas qu'il soit possible de créer un format de fichier compressé avec un accès aléatoire plus fin.

Deux solutions possibles:

Laissez le système d'exploitation s'occuper de la compression, créez et montez un système de fichiers compressé (SquashFS, clicfs, cloop, cramfs, e2compr ou autre) contenant tous vos fichiers texte et ne faites rien concernant la compression dans votre programme d'application. .
Utilisez clicfs directement sur chaque fichier texte (un clicfs par fichier texte) au lieu de compresser une image du système de fichiers. Pensez à & Quot; mkclicfs montextfile mycompressedfile & Quot; étant & "; gzip < monfichier de texte > monfichier compressé &"; et " clicfs mon répertoire de fichiers compressés " pour obtenir un accès aléatoire aux données via le fichier " directory / mytextfile ".

Je ne sais pas si cela a déjà été mentionné, mais le projet Kiwix a fait un excellent travail à cet égard. Grâce à leur programme Kiwix, ils offrent un accès aléatoire aux archives de fichiers ZIM. Bonne compression aussi. Le projet a vu le jour à la suite de la demande de copies hors connexion de Wikipedia (dépassant 100 Go sous forme non compressée, tous supports inclus). Ils ont réussi à prendre un fichier de 25 Go (une réalisation de wikipedia en un seul fichier sans la plupart des supports) et à le compresser dans une archive de fichiers zim de 8 Go. Et grâce au programme Kiwix, vous pouvez appeler n’importe quelle page de Wikipedia, avec toutes les données associées, plus rapidement que vous ne pouvez surfer sur le net.

Même si le programme Kiwix est une technologie basée sur la structure de la base de données wikipedia, il prouve que vous pouvez obtenir d’excellents taux de compression et un accès aléatoire simultanément.

C’est une question très ancienne, mais il semble que zindex pourrait être une bonne solution (même si pas beaucoup d'expérience avec cela)

razip prend en charge l’accès aléatoire avec de meilleures performances que gzip / bzip2, qui doivent être peaufinées pour cette prise en charge, ce qui réduit la compression aux dépens de & "ok &"; accès aléatoire:

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

Je suis l'auteur d'un outil open-source permettant de compresser un type particulier de données biologiques. Cet outil, appelé starch, scinde les données par chromosome et utilise ces divisions comme indices pour un accès rapide aux unités de données compressées dans une archive plus grande.

Les données par chromosome sont transformées pour éliminer la redondance des coordonnées génomiques, et les données transformées sont compressées avec des algorithmes bzip2 ou gzip. Les décalages, les métadonnées et les données génomiques compressées sont concaténés dans un seul fichier.

Le code source est disponible sur notre site GitHub . Nous l'avons compilé sous Linux et Mac OS X.

Dans votre cas, vous pouvez stocker (10 Mo, ou peu importe) des décalages dans un en-tête vers un format d'archive personnalisé. Vous analysez l’en-tête, récupérez les décalages, puis incrémentez fseek dans le fichier de current_offset_sum + header_size.

Licencié sous: CC-BY-SA avec attribution

Non affilié à StackOverflow