Wie extrahiere ich teilweise eine komprimierte, riesige Textdatei?

Ich habe eine Zip-Datei mit einer Größe von 1,5 GB.

Der Inhalt ist eine lächerlich große Nur-Text-Datei (60 GB), und ich habe derzeit nicht mehr genügend Speicherplatz auf meiner Festplatte, um alles zu extrahieren, noch möchte ich alles extrahieren, selbst wenn dies der Fall wäre.

Für meinen Anwendungsfall würde es ausreichen, wenn ich Teile des Inhalts einsehen kann.

Daher möchte ich die Datei als Stream entpacken und auf einen Bereich der Datei zugreifen (wie man es bei einer normalen Textdatei per Kopf und Schwanz tun kann).

Entweder nach Speicher (z. B. extrahieren Sie max. 100 KB ab 32 GB) oder nach Zeilen (geben Sie mir die Klartextzeilen 3700-3900).

Gibt es einen Weg, das zu erreichen?

Beachten Sie, dass Dateien gzipextrahiert werden zipkönnen (mindestens der erste Eintrag in der zipDatei). Wenn sich also nur eine große Datei in diesem Archiv befindet, können Sie Folgendes tun:

gunzip < file.zip | tail -n +3000 | head -n 20

Zum Beispiel, um die 20 Zeilen zu extrahieren, die mit der 3000er beginnen.

Oder:

gunzip < file.zip | tail -c +3000 | head -c 20

Für das Gleiche mit Bytes (vorausgesetzt eine headImplementierung, die dies unterstützt -c).

Für jedes beliebige Mitglied im Archiv auf eine Unixy-Weise:

bsdtar xOf file.zip file-to-extract | tail... | head...

Mit dem headBuilt-In von ksh93(wie wenn /opt/ast/bines voraus ist $PATH) können Sie auch Folgendes tun:

.... | head     -s 2999      -c 20
.... | head --skip=2999 --bytes=20

Beachten Sie, dass in jedem Fall gzip/ bsdtar/ unzipimmer dekomprimieren müssen (und Verwerfungs hier) der gesamte Abschnitt der Datei , dass führt zu dem Teil , die Sie extrahieren möchten. Das hängt davon ab, wie der Komprimierungsalgorithmus funktioniert.

Eine Lösung mit unzip -p und dd, zum Beispiel um 10kb mit 1000 Blöcken Versatz zu extrahieren:

$ unzip -p my.zip | dd ibs=1024 count=10 skip=1000 > /tmp/out

Hinweis: Ich habe das nicht mit wirklich riesigen Daten versucht ...

Wenn Sie die Kontrolle über die Erstellung dieser großen ZIP-Datei haben, können Sie eine Kombination aus gzipund verwenden zless.

Auf diese Weise können Sie zlessden Inhalt der Datei als Pager verwenden und anzeigen, ohne sich um das Extrahieren kümmern zu müssen.

Wenn Sie das Komprimierungsformat nicht ändern können, funktioniert dies offensichtlich nicht. Wenn ja, fühle ich mich zlesseher günstig.

Um bestimmte Zeilen der Datei anzuzeigen, leiten Sie die Ausgabe an den Unix-Stream-Editor sed weiter . Dadurch können beliebig große Datenströme verarbeitet und sogar zum Ändern der Daten verwendet werden. Führen Sie Folgendes aus, um die Zeilen 3700-3900 wie gewünscht anzuzeigen.

unzip -p file.zip | sed -n 3700,3900p

Ich fragte mich, ob es möglich war, etwas effizienteres zu tun, als vom Anfang der Datei bis zum Ende zu dekomprimieren. Es scheint, dass die Antwort nein ist. Bei einigen CPUs (Skylake) zcat | tailwird die CPU jedoch nicht auf die volle Taktrate hochgefahren. Siehe unten. Ein benutzerdefinierter Decoder könnte dieses Problem umgehen und die Aufrufe des Pipe-Schreibsystems speichern und möglicherweise ~ 10% schneller sein. (Oder ~ 60% schneller bei Skylake, wenn Sie die Energieverwaltungseinstellungen nicht anpassen).

Das Beste, was Sie mit einer angepassten zlib mit einer skipbytesFunktion tun können, ist, die Symbole in einem Komprimierungsblock zu analysieren, um zum Ende zu gelangen, ohne den dekomprimierten Block tatsächlich zu rekonstruieren. Dies könnte erheblich schneller sein (wahrscheinlich mindestens 2x) als der Aufruf der regulären Dekodierungsfunktion von zlib, um denselben Puffer zu überschreiben und in der Datei vorwärts zu gehen. Aber ich weiß nicht, ob jemand eine solche Funktion geschrieben hat. (Und ich denke, das funktioniert nicht wirklich, es sei denn, die Datei wurde speziell geschrieben, damit der Decoder an einem bestimmten Block neu gestartet werden kann.)

Ich hatte gehofft, es gäbe eine Möglichkeit, Deflate-Blöcke zu überspringen, ohne sie zu dekodieren, denn das wäre viel schneller. Der Huffman-Baum wird zu Beginn eines jeden Blocks gesendet, so dass Sie von Beginn eines jeden Blocks aus decodieren können (glaube ich). Oh, ich denke, der Decoder-Status ist mehr als der Huffman-Baum, es sind auch die vorherigen 32 kB decodierter Daten, und dies wird standardmäßig nicht über Blockgrenzen hinweg zurückgesetzt / vergessen. Dieselben Bytes können wiederholt referenziert werden, sodass sie in einer riesigen komprimierten Datei möglicherweise nur einmal buchstäblich vorkommen. (zB in einer Protokolldatei bleibt der Hostname im Komprimierungswörterbuch wahrscheinlich die ganze Zeit "heiß", und jede Instanz davon verweist auf die vorherige, nicht auf die erste).

Das zlibHandbuch besagt, dass Sie Z_FULL_FLUSHbeim Aufrufen verwenden müssen, deflatewenn der komprimierte Stream bis zu diesem Punkt durchsucht werden soll. Es "setzt den Komprimierungsstatus zurück", also denke ich, ohne das können Rückwärtsreferenzen in den / die vorherigen Block (e) gehen. Wenn Ihre ZIP-Datei also nicht mit gelegentlichen Full-Flush-Blöcken geschrieben wurde (wie jedes 1G oder etwas, das die Komprimierung vernachlässigbar beeinträchtigt), müssten Sie bis zu dem von Ihnen gewünschten Zeitpunkt mehr Dekodierungsarbeit leisten als ursprünglich Denken. Ich denke, Sie können wahrscheinlich nicht am Anfang eines Blocks beginnen.

Der Rest wurde geschrieben, während ich dachte, es wäre möglich, einfach den Anfang des Blocks zu finden, der das erste Byte enthält, das Sie wollen, und von dort zu dekodieren.

Leider gibt der Start eines Deflate-Blocks bei komprimierten Blöcken nicht an, wie lange er dauert . Inkomprimierbare Daten können mit einem unkomprimierten Blocktyp codiert werden, der vorne eine 16-Bit-Größe in Byte aufweist, komprimierte Blöcke jedoch nicht: RFC 1951 beschreibt das Format recht gut lesbar . Blöcke mit dynamischer Huffman-Codierung haben den Baum am Anfang des Blocks (damit der Dekomprimierer nicht im Stream suchen muss), daher muss der Komprimierer den gesamten (komprimierten) Block im Speicher behalten, bevor er ihn schreibt.

Die maximale Rückwärtsreferenzdistanz beträgt nur 32 kB, sodass der Kompressor nicht viele unkomprimierte Daten im Speicher behalten muss, die Blockgröße jedoch nicht begrenzt. Blöcke können mehrere Megabyte lang sein. (Dies ist groß genug, damit sich die Suche nach einer Festplatte auch auf einem Magnetlaufwerk lohnt, im Gegensatz zum sequentiellen Einlesen in den Speicher und zum Überspringen von Daten im RAM, wenn das Ende des aktuellen Blocks gefunden werden konnte, ohne ihn zu analysieren.)

zlib macht Blöcke so lang wie möglich: Laut Marc Adler startet zlib einen neuen Block erst dann, wenn der Symbolpuffer voll ist. In der Standardeinstellung sind dies 16.383 Symbole (Literale oder Übereinstimmungen).

Ich habe den Ausgang von gzippt seq(der extrem redundant ist und daher wahrscheinlich kein großartiger Test), aber pv < /tmp/seq1G.gz | gzip -d | tail -c $((1024*1024*1000)) | wc -cauf einem Skylake i7-6700k mit 3,9 GHz und DDR4-2666 RAM läuft dieser mit nur ~ 62 MiB / s komprimierter Daten. Das sind 246 MB / s dekomprimierter Daten. Dies entspricht einer Änderung der Datenmenge im Vergleich zu einer memcpyGeschwindigkeit von ~ 12 GB / s bei Blockgrößen, die zu groß sind, um in den Cache zu passen.

(Mit energy_performance_preferenceder Standardeinstellung balance_poweranstelle von balance_performancewird der interne CPU-Governor von Skylake nur mit 2,7 GHz und einer komprimierten Datenrate von ~ 43 MiB / s betrieben. Ich sudo sh -c 'for i in /sys/devices/system/cpu/cpufreq/policy[0-9]*/energy_performance_preference;do echo balance_performance > "$i";done'optimiere ihn. Wahrscheinlich sehen solche häufigen Systemaufrufe nicht wie echte CPU-gebunden aus.) arbeiten an der Power-Management-Einheit.)

TL: DR: zcat | tail -cist CPU-gebunden, auch bei einer schnellen CPU, es sei denn, Sie haben sehr langsame Festplatten. gzip verwendete 100% der CPU, auf der es lief (und laut Angaben 1,81 Anweisungen pro Takt perf), und tailverwendete 0,162 der CPU, auf der es lief (0,58 IPC). Das System war sonst meist im Leerlauf.

Ich verwende Linux 4.14.11-1-ARCH, bei dem KPTI standardmäßig aktiviert ist , um Meltdown zu umgehen. Daher sind all diese writeSystemaufrufe gzipteurer als früher: /

Wenn die Suchfunktion in unzipoder integriert ist zcat(aber weiterhin die reguläre zlibDekodierungsfunktion verwendet) , werden alle diese Pipe-Schreibvorgänge gespeichert, und Skylake-CPUs werden mit voller Taktgeschwindigkeit ausgeführt. (Dieses Downclocking für einige Arten von Lasten ist nur für Intel Skylake und höher verfügbar, da diese die CPU-Frequenzentscheidung vom Betriebssystem trennen, da sie mehr Daten über die CPU-Aktivitäten haben und schneller hoch- und runterfahren können. Dies ist der Fall.) normalerweise gut, aber hier führt dies dazu, dass Skylake mit einer konservativeren Einstellung des Reglers nicht auf Hochtouren läuft.

Keine Systemaufrufe, nur das Umschreiben eines Puffers, der in den L2-Cache passt, bis Sie die gewünschte Start-Byte-Position erreicht haben, würde wahrscheinlich mindestens ein paar Prozent Unterschied bewirken. Vielleicht sogar 10%, aber ich mache hier nur Zahlen. Ich habe kein zlibdetailliertes Profil erstellt, um festzustellen, wie groß der Cache-Speicherbedarf ist und wie stark das Leeren des TLB (und damit das Leeren des UOP-Caches) bei jedem Systemaufruf mit aktiviertem KPTI schmerzt.

Es gibt einige Softwareprojekte, die dem gzip-Dateiformat einen Suchindex hinzufügen . Dies hilft Ihnen nicht, wenn Sie niemanden dazu bringen können, suchbare komprimierte Dateien für Sie zu generieren, aber andere zukünftige Leser können davon profitieren.

Vermutlich keines dieser Projekte haben eine Dekodierungsfunktion , die weiß , wie durch einen Deflate Strom ohne Index zu überspringen, weil sie nur an der Arbeit entworfen sind , wenn ein Index ist verfügbar.

• GZinga: Suchbarer und aufteilbarer Gzip . Ermöglicht große Blockgrößen.
• BGZF - Blocked, Bigger & Better GZIP! (Eine kleine maximale Blockgröße von 64 KB beeinträchtigt die Komprimierungsraten ein wenig. Entwickelt für die Verwendung mit Bioinformatikdaten wie FASTA, die häufig unkomprimiert verwendet werden, mit transparenter Unterstützung in einigen Python-Bibliotheken.)

Sie können die Zip-Datei in einer Python-Sitzung zf = zipfile.ZipFile(filename, 'r', allowZip64=True)öffnen. Wenn Sie diese geöffnet haben, können Sie jede Datei im Zip-Archiv zum Lesen öffnen und Zeilen usw. daraus lesen, als ob es sich um eine normale Datei handeln würde.