Kompression-Formate mit guter Unterstützung für den zufälligen Zugriff, die in Archiven?

https://stackoverflow.com/questions/429987

07-07-2019
|

Frage

Dieses ist ähnlich wie ein Vorherige Frage, aber die Antworten, die es nicht befriedigen meine Bedürfnisse und meine Frage ist etwas anders:

Derzeit nutze ich die gzip-Komprimierung für einige sehr große Dateien enthalten, die sortierten Daten.Wenn die Dateien nicht komprimiert, die binäre Suche ist eine praktische und effiziente Art und Weise zu unterstützen suchen, um eine Stelle in der sortierten Daten.

Aber wenn die Dateien komprimiert werden, werden die Dinge knifflig.Vor kurzem fand ich heraus, über zlib's Z_FULL_FLUSH option, die verwendet werden können, die während der Komprimierung, um legen Sie die "sync-Punkte" in der komprimierten Ausgabe (inflateSync() kann dann beginnen, das Lesen von verschiedenen Punkten in der Datei).Das ist OK, obwohl die Dateien, die ich bereits habe, müsste stärker komprimiert, um hinzufügen diese Funktion (und merkwürdigerweise gzip nicht eine option dafür, aber ich bin bereit zu schreiben, meine eigenen Kompressions-Programm an, wenn ich muss).

Es scheint aus eine Quelle , dass auch Z_FULL_FLUSH ist keine perfekte Lösung...es ist nicht nur nicht von allen unterstützt gzip-Archive, aber genau die Idee, mit der Aufdeckung sync-Punkte in Archiven können Fehlalarme zu erzeugen (entweder durch Zufall mit der magischen Zahl für die sync-Punkte, oder aufgrund der Tatsache, dass Z_SYNC_FLUSH auch erzeugt sync-Punkte, aber Sie sind nicht geeignet für random-access).

Gibt es eine bessere Lösung?Ich möchte vermeiden, dass die zusätzlichen Dateien für die Indizierung, wenn möglich, und ausdrücklich, standardmäßige Unterstützung für quasi-random access würde hilfreich sein (auch wenn es großkörnigen--wie zu Beginn der Lektüre an jedem 10-MB-Intervall).Gibt es eine andere Kompression format mit besserer Unterstützung für zufällige lese-als gzip?

Bearbeiten:Wie ich bereits erwähnt habe, möchte ich tun binäre Suche in der komprimierten Daten.Ich brauche nicht zu suchen, um eine bestimmte (unkomprimiert) position-nur um dann zu versuchen, mit einigen groben Granularität in der komprimierten Datei.Ich möchte nur die Unterstützung für so etwas wie "Dekomprimieren Sie die Daten ab rund 50% (25%, 12.5%, etc.) der Weg in diese komprimierte Datei."

Lösung

Ich weiß nicht, von jedem komprimierten Dateiformat, das Direktzugriff zu einer bestimmten Stelle in den unkomprimierten Daten unterstützen würde (na ja, außer für Multimedia-Formate), aber Sie können Ihre eigene brauen.

Zum Beispiel bzip2 komprimierten Dateien aus unabhängigen komprimierten Blöcken mit einer Größe <1 MB unkomprimiert, die durch Sequenzen von Magie Bytes begrenzt werden, so dass Sie die bzip2-Datei nicht analysieren, die Blockgrenzen und dann dekomprimieren genau den richtigen Block. Dies würde eine Indizierung müssen sich daran erinnern, wo Sie die Blöcke beginnen.

Trotzdem denke ich, die beste Lösung, um Ihre Datei in Stücke Ihrer Wahl sein würde, spalten und dann mit einigen Archivierungs, wie zip oder rar, die zufällig Zugriff auf einzelne Dateien im Archiv zu unterstützen.

Komprimieren

Andere Tipps

Werfen Sie einen Blick auf dictzip . Es ist kompatibel mit gzip und ermöglicht es grob mit wahlfreiem Zugriff.

Ein Auszug aus seiner Manpage:

dictzip komprimiert Dateien, die gzip (1) Algorithmus (LZ77) in einer Weise verwendet, die ist vollständig mit dem gzip-Dateiformat kompatibel. Eine Erweiterung des gzip Dateiformat (Extra-Feld, in 2.3.1.1 von RFC 1952) ermöglicht zusätzliche Daten wird in der Kopfzeile einer komprimierten Datei gespeichert. Programme wie gzip und zcat wird diese Zusatzdaten ignorieren. Jedoch [dictzcat --start] wird Gebrauch machen dieser Daten pseudo-zufälligen Zugriff auf die Datei auszuführen.

Ich habe das Paket dictzip in Ubuntu. Oder sein Quellcode ist in einem dictd - *. Tar.gz . Seine Lizenz ist GPL. Sie sind frei, es zu studieren.

Update:

I verbessert dictzip keine Dateigrößenbeschränkung zu haben. Meine Implementierung ist unter MIT-Lizenz.

Das .xz Dateiformat (die LZMA-Kompression verwendet) scheint dies zu unterstützen:

Random-Lesezugriff : Die Daten können in unabhängig voneinander komprimiert Blöcke aufgeteilt werden. Jede .xz Datei enthält einen Index der Blöcke, die begrenzten Schreib-Lese-Lesen möglich macht, wenn die Blockgröße klein genug ist.

Dies sollte für Ihre Zwecke ausreichend sein. Ein Nachteil ist, dass die API von liblzma (mit diesen Behältern in Wechselwirkung) scheint nicht, dass gut dokumentiert, so kann es einige Mühe, um herauszufinden, wie zufällig blockiert den Zugriff auf.

Es gibt Lösungen für die Bereitstellung von zufälligen Zugriff auf gzip und bzip2-Archive:

gzip Zran. c von der ghost Quellcode
bzip2 tiven bzip von James Taylor

( Ich bin auf der Suche nach etwas für 7zip )

bgzip kann Dateien komprimieren, die in einem gzip Variante, die mit Wendeschneidplatten (und dekomprimiert werden kann durch gzip).Dies ist in einigen Bioinformatik-Anwendungen, zusammen mit dem tabix indexer.

Erläuterungen finden Sie hier: http://blastedbio.blogspot.fr/2011/11/bgzf-blocked-bigger-better-gzip.html, und hier: http://www.htslib.org/doc/tabix.html.

Ich weiß nicht, in welchem Ausmaß es ist anpassungsfähig an andere Anwendungen.

Ich bin mir nicht sicher, ob dies in Ihre genaue Situation praktisch wäre, konnte aber nicht Sie gzip nur jede große Datei in kleinere Dateien, sagen wir 10 MB je? Sie würden mit einem Bündel von Dateien am Ende: file0.gz, file1.gz, file2.gz usw. Auf der Grundlage eines in den ursprünglichen großen angegebenen Offset, könnten Sie in der Datei mit dem Namen "file" + (offset / 10485760) + ".gz" suchen. Der Offset innerhalb des unkomprimierten Archiv würde offset % 10485760 werden.

Da verlustfreie Komprimierung funktioniert besser auf einigen Bereichen als andere, wenn Sie komprimierte Daten in Blöcke geeigneter Länge BLOCK speichern, obwohl jeder Block genau die gleiche Anzahl von komprimierten Bytes hat, einige komprimierte Blöcke werden zu einem viel längeren Stück Klartext erweitern als andere.

Sie können sehen "Komprimierung: Ein zentraler Aspekt für Next-Generation-Text Retrieval System" von Nivio Ziviani, Edleno Silva de Moura, Gonzalo Navarro und Ricardo Baeza-Yates im Computer Magazin November 2000 http://doi.ieeecomputersociety.org/10.1109/2.881693

Die Dekompressor dauern 1, 2 oder 3 ganzes Bytes von komprimierten Daten und dekomprimiert in ein ganzes Wort (eine Vokabelliste verwendet wird). Man kann den komprimierten Text nach Worten oder Phrasen direkt suchen, die erweist sich als noch schneller als unkomprimierte Textsuche.

Ihre Dekompressor können Sie im Text mit einem normalen (Byte) Zeiger auf ein beliebiges Wort zeigen und beginnen sofort von diesem Punkt zu dekomprimieren.

Sie können jedem Wort einen einzigartigen 2-Byte-Code geben, da Sie wahrscheinlich weniger als 65.000 eindeutige Worte in Ihrem Text. (Es gibt fast 13.000 einzigartige Wörter in der KJV Bibel). Auch wenn es mehr als 65.000 Worte sind, ist es ziemlich einfach, die ersten 256 Zwei-Byte-Code „Wörter“ auf alle möglichen Bytes zuweisen, so können Sie Wörter buchstabieren, die nicht im Lexikon der 65.000 oder so sind „am häufigsten Wörter und Sätze". (Die Kompression durch Packen häufige Wörter und Sätze in zwei Bytes gewonnen ist in der Regel die „Expansion“ der gelegentlich ein Wort mit zwei Bytes pro Buchstaben Buchstabieren) wert. Es gibt eine Vielzahl von Möglichkeiten, um ein Lexikon von „häufige Wörter und Sätze“ zu wählen, die eine angemessene Kompression geben. Zum Beispiel könnten Sie einen LZW Kompressor zwicken dump „Phrasen“ es nutzt als einmal zu einer Lexikondatei, eine Zeile pro Satz, und führen Sie es über alle Ihre Daten. Oder Sie könnten willkürlich hacken unkomprimierte Daten in 5-Byte-Sätze in einer Lexikon-Datei auf, eine Zeile pro Satz. Oder Sie könnten Ihre unkomprimierten Daten in tatsächliche englischen Worte zerhacken, und jedes Wort setzen - inklusive Leerzeichen am Anfang des Wortes - in die Lexikon-Datei. Dann nutzen „Art --Einzigartig“ doppelte Worte in dieser Lexikondatei zu beseitigen. (Kommissionierung der perfekte "optimale" Lexikon Wortliste noch als NP-hard?)

Speichern Sie das Lexikon zu Beginn Ihrer großen komprimierten Datei, Pad es für einigen bequemen BLOCK, und speichern Sie dann den komprimierten Text - eine Reihe von zwei Byte „Worten“ - von dort bis zum Ende der Datei. Vermutlich wird der Sucher dieses Lexikon einmal gelesen und hält sich in einem gewissen schnell zu dekodieren Format im RAM während der Dekompression „Zwei-Byte-Code“ auf „variabler Länge Phrase“ zu beschleunigen dekomprimieren. Mein erster Entwurf mit einer einfachen eine Zeile pro Satz Liste beginnen würde, aber Sie könnten später schalten Sie das Lexikon in einer komprimierten Form unter Verwendung einer Art von inkrementellen Codierung oder zlib zu speichern.

Sie können jede beliebige Zufalls holen sogar Byte in den komprimierten Text versetzt, und von dort aus starten dekomprimieren. Ich glaube nicht, es ist möglich, ein feineres Random Access komprimiertes Dateiformat zu machen.

Zwei mögliche Lösungen:

das OS Deal mit Kompression lassen, erstellen und einbinden, um ein komprimiertes Dateisystem (SquashFS, clicfs, cloop, cramfs, e2compr oder was auch immer) alle Textdateien enthalten, und tun nichts über Kompression in Ihrem Anwendungsprogramm .
Mit clicfs direkt auf jeder Textdatei (eine clicfs pro Textdatei) anstelle ein Dateisystem-Image zu komprimieren. Denken Sie an "mkclicfs mytextfile mycompressedfile" Sein "gzip mycompressedfile" und "clicfs mycompressedfile Verzeichnis" als eine Möglichkeit des Erhaltens zufälligen Zugriff auf die Daten über die Datei "Verzeichnis / mytextfile".

Ich weiß nicht, ob seine noch erwähnt, aber das Kiwix Projekt große Arbeit in dieser Hinsicht getan hatte. Durch ihr Programm Kiwix bieten sie wahlfreien Zugriff auf ZIM Dateiarchiven. Gute Kompression auch. Das Projekt entstand, als es eine Nachfrage für die Offline-Kopien der Wikipedia war (die über 100 GB in unkomprimierter Form erreicht hat, mit allen Medien enthalten). Sie haben erfolgreich eine 25 GB-Datei (eine Einzeldatei Ausführungsform der wikipedia ohne die meisten Medien) und verdichtet es auf einen measly 8 GB zim Dateiarchiv entnommen. Und durch die Kiwix Programm können Sie jede Seite der Wikipedia, mit allen zugehörigen Daten aufrufen, schneller als man im Internet surfen können.

Auch wenn Kiwix Programm eine Technologie, um die wikipedia Datenbank-Struktur basiert, erweist es sich, dass Sie gleichzeitig hervorragende Verdichtungsverhältnisse und Direktzugriff haben.

Dies ist eine sehr alte Frage, aber es sieht aus wie zindex könnte eine gute Lösung bieten (obwohl ich don ‚t mit ihm viel Erfahrung haben)

razip unterstützt Direktzugriff mit einer besseren Leistung als gzip / bzip2, die für diese Unterstützung gezwickt werden müssen - Verringerung Kompression auf Kosten von „ok“ random access:

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

Ich bin der Autor eines Open-Source-Tool für eine bestimmte Art von biologischen Daten zu komprimieren. Dieses Tool, genannt starch, spaltet die Daten von Chromosom und verwendet diese Divisionen als Indizes für den schnellen Zugriff auf komprimierte Dateneinheiten innerhalb des größeren Archiv.

Per-Chromosom Daten Redundanz in genomischen Koordinaten entfernen transformiert und die transformierten Daten werden komprimiert mit entweder bzip2 oder gzip Algorithmen. Die Offsets, Metadaten und komprimierte genomischen Daten werden in einer Datei verknüpft.

Der Quellcode ist aus unserer GitHub Ort zur Verfügung. Wir haben es kompiliert unter Linux und Mac OS X.

Für Ihren Fall könnten Sie speichern (10 MB, oder was auch immer) Offsets in einem Header zu einem benutzerdefinierten Archivformat. Sie haben die Header analysieren, rufen Sie die Offsets und fseek schrittweise durch die Datei von current_offset_sum + header_size.

Lizenziert unter: CC-BY-SA mit Zuschreibung

Nicht verbunden mit StackOverflow