☰

압축 해제는 아카이브에서 단일 파일을 찾기 위해 어떤 방법을 사용합니까?

tag-icon • tag-icon zip archive
압축 해제는 아카이브에서 단일 파일을 찾기 위해 어떤 방법을 사용합니까?

100개의 파일을 생성한다고 가정해 보겠습니다. 각 파일에는 임의의 텍스트 데이터가 포함되어 있으며 크기는 30MB입니다. 이제 0으로 압축된 zip 아카이브, 즉 zip dataset.zip -r -0 *.txt. 이제 이 아카이브에서 파일 하나만 추출하고 싶습니다.

상술 한 바와 같이여기, 아카이브에서 파일의 압축을 풀거나 추출하는 방법에는 두 가지가 있습니다.

  1. 파일의 끝을 찾아 중앙 디렉터리를 찾습니다. 그런 다음 이를 사용하여 추출하려는 파일에 빠르게 무작위로 액세스하세요. (상각된 O(1)복잡성)
  2. 각 로컬 헤더를 보고 일치하는 헤더를 추출합니다. ( O(n)복잡성)

압축을 풀려면 어떤 방법이 사용됩니까? 내 실험에 따르면 방법 2를 사용하는 것 같나요?

답변1

대규모 아카이브에서 단일 파일을 검색할 때 다음을 사용하여 볼 수 있는 방법 1을 사용합니다 strace.

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를 열고 dataset.zip아카이브에서 요청된 파일의 끝과 시작 부분( rand-28.txt오프셋 849346560)을 찾아 거기에서 읽습니다.

아카이브의 마지막 65557바이트를 스캔하여 중앙 디렉토리를 찾으십시오.코드는 여기에서 시작됩니다.:

/*---------------------------------------------------------------------------
    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.
  ---------------------------------------------------------------------------*/

답변2

실제로는 혼합물입니다. unzip은 알려진 위치에서 일부 데이터를 읽은 다음 zip 파일의 대상 항목과 관련된(그러나 동일하지는 않은) 데이터 블록을 읽습니다.

zip/unzip의 디자인은 소스 파일의 주석에 설명되어 있습니다. 관련 내용입니다.extract.c:

/*--------------------------------------------------------------------------- 
    The basic idea of this function is as follows.  Since the central di- 
    rectory lies at the end of the zipfile and the member files lie at the 
    beginning or middle or wherever, it is not very desirable to simply 
    read a central directory entry, jump to the member and extract it, and 
    then jump back to the central directory.  In the case of a large zipfile 
    this would lead to a whole lot of disk-grinding, especially if each mem- 
    ber file is small.  Instead, we read from the central directory the per- 
    tinent information for a block of files, then go extract/test the whole 
    block.  Thus this routine contains two small(er) loops within a very 
    large outer loop:  the first of the small ones reads a block of files 
    from the central directory; the second extracts or tests each file; and 
    the outer one loops over blocks.  There's some file-pointer positioning 
    stuff in between, but that's about it.  Btw, it's because of this jump- 
    ing around that we can afford to be lenient if an error occurs in one of 
    the member files:  we should still be able to go find the other members, 
    since we know the offset of each from the beginning of the zipfile. 
  ---------------------------------------------------------------------------*/

형식 자체는 주로 PK-Ware 구현에서 파생되었으며 다음과 같이 요약됩니다.프로그래밍 정보 텍스트 파일. 이에 따르면 중앙 디렉터리에도 여러 유형의 레코드가 있으므로 unzip은 쉽게 파일 끝으로 이동하여 대상 파일을 찾기 위한 항목 배열을 생성할 수 없습니다.

이제...시간을 내어 소스 코드를 읽어보면 알게 될 것입니다.unzip8192바이트의 버퍼 읽기(찾기INBUFSIZ). 나는 상당히 큰 zip 파일에 대해서만 단일 파일 추출을 사용하지만(Java 소스 코드를 생각하고 있습니다), 더 작은 zip 파일에서도 버퍼 크기의 영향을 볼 수 있습니다. 이를 확인하기 위해 PuTTY의 Git 파일을 압축했습니다. 여기에는 2727개의 파일(git 로그의 복사본 포함)이 포함되어 있습니다. Java는 20년 전보다 더 커졌으며, 더 이상 작아지지 않습니다. zip 파일에서 로그를 추출합니다(알파벳순 인덱스의 끝에 있지 않고 로그가 올 수 있으므로 선택됨).아니요중앙 디렉터리에서 읽은 첫 번째 블록에서) 다음을 제공합니다.strace통화 의 경우 lseek:

lseek(3, -2252, SEEK_CUR)               = 1267
lseek(3, 120463360, SEEK_SET)           = 120463360
lseek(3, 120468731, SEEK_SET)           = 120468731
lseek(3, 120135680, SEEK_SET)           = 120135680
lseek(3, 270336, SEEK_SET)              = 270336
lseek(3, 120463360, SEEK_SET)           = 120463360

늘 그렇듯이 벤치마킹을 통해ymmv.

관련 정보