Welche Methode verwendet Unzip, um eine einzelne Datei in einem Archiv zu finden?

Nehmen wir an, ich erstelle 100 Dateien mit zufälligen Textdaten mit einer Größe von jeweils 30 MB. Jetzt erstelle ich ein Zip-Archiv mit 0-Komprimierung, dh zip dataset.zip -r -0 *.txt . Jetzt möchte ich nur eine Datei aus diesem Archiv extrahieren.

Wie hier beschrieben, gibt es zwei Möglichkeiten, Dateien aus Archiven zu entpacken/extrahieren:

1. Suchen Sie bis zum Ende der Datei und schlagen Sie im zentralen Verzeichnis nach. Verwenden Sie das dann für einen schnellen Direktzugriff auf die zu extrahierende Datei. (Amortized O(1) Komplexität)
2. Durchsuchen Sie jeden lokalen Header und extrahieren Sie den, bei dem es eine Übereinstimmung gibt. (O(n) Komplexität)

Welche Methode verwendet das Entpacken? Aus meinen Experimenten scheint es, als würde es Methode 2 verwenden?

Akzeptierte Antwort:

Bei der Suche nach einer einzelnen Datei in einem großen Archiv wird Methode 1 verwendet, die Sie mit strace sehen können :

open("dataset.zip", O_RDONLY)           = 3
ioctl(1, TIOCGWINSZ, 0x7fff9a895920)    = -1 ENOTTY (Inappropriate ioctl for device)
write(1, "Archive:  dataset.zip\n", 22Archive:  dataset.zip
) = 22
lseek(3, 943718400, SEEK_SET)           = 943718400
read(3, "\340P\356(s\342\306\205\201\27\360U[\250/2\207\346<\252+u\234\225\1[<\2310E\342\274"..., 4522) = 4522
lseek(3, 943722880, SEEK_SET)           = 943722880
read(3, "\3\f\225P\\ux\v\0\1\4\350\3\0\0\4\350\3\0\0", 20) = 20
lseek(3, 943718400, SEEK_SET)           = 943718400
read(3, "\340P\356(s\342\306\205\201\27\360U[\250/2\207\346<\252+u\234\225\1[<\2310E\342\274"..., 8192) = 4522
lseek(3, 849346560, SEEK_SET)           = 849346560
read(3, "D\262nv\210\343\240C\24\227\344\367q\300\223\231\306\330\275\266\213\276M\7I'&35\2\234J"..., 8192) = 8192
stat("rand-28.txt", 0x559f43e0a550)     = -1 ENOENT (No such file or directory)
lstat("rand-28.txt", 0x559f43e0a550)    = -1 ENOENT (No such file or directory)
stat("rand-28.txt", 0x559f43e0a550)     = -1 ENOENT (No such file or directory)
lstat("rand-28.txt", 0x559f43e0a550)    = -1 ENOENT (No such file or directory)
open("rand-28.txt", O_RDWR|O_CREAT|O_TRUNC, 0666) = 4
ioctl(1, TIOCGWINSZ, 0x7fff9a895790)    = -1 ENOTTY (Inappropriate ioctl for device)
write(1, " extracting: rand-28.txt        "..., 37 extracting: rand-28.txt             ) = 37
read(3, "\275\3279Y\206\223\217}\355W%:\220YNT\0\257\260z^\361T\242\2\370\21\336\372+\306\310"..., 8192) = 8192

unzip öffnet dataset.zip , sucht bis zum Ende und dann bis zum Anfang der angeforderten Datei im Archiv (rand-28.txt , bei Offset 849346560) und liest von dort.

Das zentrale Verzeichnis wird gefunden, indem die letzten 65557 Bytes des Archivs gescannt werden; Sehen Sie sich den Code an, der hier beginnt:

/*---------------------------------------------------------------------------
    Find and process the end-of-central-directory header.  UnZip need only
    check last 65557 bytes of zipfile:  comment may be up to 65535, end-of-
    central-directory record is 18 bytes, and signature itself is 4 bytes;
    add some to allow for appended garbage.  Since ZipInfo is often used as
    a debugging tool, search the whole zipfile if zipinfo_mode is true.
  ---------------------------------------------------------------------------*/