아카이브 내에서 임의 액세스를 잘 지원하는 압축 형식이 있습니까?

https://stackoverflow.com/questions/429987

07-07-2019
|

문제

이는 다음과 유사합니다. 이전 질문, 그러나 거기에 있는 답변은 내 요구 사항을 충족하지 않으며 내 질문은 약간 다릅니다.

나는 현재 정렬된 데이터를 포함하는 매우 큰 파일에 대해 gzip 압축을 사용하고 있습니다.파일이 압축되지 않은 경우 이진 검색은 정렬된 데이터에서 위치 검색을 지원하는 편리하고 효율적인 방법입니다.

그러나 파일이 압축되면 상황이 까다로워집니다.최근에 알게 된 사실 zlib'에스 Z_FULL_FLUSH 압축하는 동안 압축된 출력에 "동기화 지점"을 삽입하는 데 사용할 수 있는 옵션(inflateSync() 그런 다음 파일의 다양한 지점에서 읽기를 시작할 수 있습니다.)괜찮습니다. 하지만 이 기능을 추가하려면 이미 가지고 있는 파일을 다시 압축해야 합니다(그리고 이상하게도 gzip 이에 대한 옵션은 없지만 필요한 경우 자체 압축 프로그램을 작성할 의향이 있습니다.

그것은 것 같다 하나의 소스 심지어 Z_FULL_FLUSH 완벽한 솔루션은 아닙니다... 모든 gzip 아카이브에서 지원되지 않을 뿐만 아니라 아카이브에서 동기화 지점을 감지한다는 아이디어 자체가 잘못된 긍정을 생성할 수 있습니다(동기화 지점의 매직 넘버와 일치하거나 다음 사실로 인해). 저것 Z_SYNC_FLUSH 또한 동기화 포인트를 생성하지만 무작위 액세스에는 사용할 수 없습니다.

더 나은 해결책이 있습니까?가능하다면 인덱싱을 위한 보조 파일을 피하고 싶습니다. 그리고 준 무작위 액세스에 대한 명시적인 기본 지원이 도움이 될 것입니다(각각 10MB 간격으로 읽기를 시작할 수 있는 것과 같이 대규모일지라도).gzip보다 무작위 읽기를 더 잘 지원하는 또 다른 압축 형식이 있습니까?

편집하다:앞서 언급했듯이 압축된 데이터에서 이진 검색을 수행하고 싶습니다.특정(압축되지 않은) 위치를 탐색할 필요는 없습니다. 단지 압축된 파일 내에서 약간의 대략적인 세분성을 가지고 탐색하기만 하면 됩니다.저는 "이 압축 파일의 대략 50%(25%, 12.5% 등)부터 시작하는 데이터 압축을 푼다"와 같은 지원을 원합니다.

해결책

압축되지 않은 데이터의 특정 위치에 대한 임의 액세스를 지원하는 압축 파일 형식(멀티미디어 형식 제외)은 모르지만 직접 만들 수는 있습니다.

예를 들어, bzip2 압축 파일은 압축되지 않은 크기가 1MB 미만인 독립적인 압축 블록으로 구성되며, 이는 매직 바이트 시퀀스로 구분되므로 bzip2 파일을 구문 분석하고 블록 경계를 얻은 다음 올바른 블록의 압축을 풀 수 있습니다.블록이 시작되는 위치를 기억하려면 약간의 인덱싱이 필요합니다.

그럼에도 불구하고 가장 좋은 해결책은 파일을 원하는 덩어리로 분할한 다음 아카이브의 개별 파일에 대한 무작위 액세스를 지원하는 zip 또는 rar와 같은 일부 아카이버로 압축하는 것입니다.

다른 팁

보세요 dictzip.gzip과 호환되며 대략적인 무작위 액세스를 허용합니다.

매뉴얼 페이지에서 발췌:

dictzip 다음을 사용하여 파일을 압축합니다. gzip(1) GZIP 파일 형식과 완전히 호환되는 방식으로 알고리즘 (LZ77).GZIP 파일 형식 (RFC 1952의 2.3.1.1에 설명 된 엑스트라 필드)으로의 확장은 압축 파일의 헤더에 추가 데이터를 저장할 수 있습니다.GZIP 및 ZCAT와 같은 프로그램은이 추가 데이터를 무시합니다.그러나 [Dictzcat-Start]는이 데이터를 사용하여 파일에서 의사 랜덤 액세스를 수행합니다.

Ubuntu에 dictzip 패키지가 있습니다.또는 소스 코드가 다음 위치에 있습니다. dictd-*.tar.gz.라이센스는 GPL입니다.당신은 그것을 자유롭게 공부할 수 있습니다.

업데이트:

파일 크기 제한이 없도록 dictzip을 개선했습니다.내 구현 MIT 라이선스를 따릅니다.

그만큼 .xz 파일 형식 (LZMA 압축을 사용함)은 다음을 지원하는 것 같습니다.

무작위 접근 읽기:데이터는 독립적으로 압축된 블록으로 분할될 수 있습니다.모든 .xz 파일에는 블록 인덱스가 포함되어 있어 블록 크기가 충분히 작을 때 제한된 무작위 액세스 읽기가 가능합니다.

이는 귀하의 목적에 충분합니다.단점은 liblzma의 API(이러한 컨테이너와 상호 작용하기 위한)가 잘 문서화되어 있지 않은 것 같아서 블록에 무작위로 액세스하는 방법을 알아내는 데 약간의 노력이 필요할 수 있다는 것입니다.

gzip 및 bzip2 아카이브에 대한 무작위 액세스를 제공하는 솔루션이 있습니다.

gzip ghostscript 소스 코드의 zran.c
bzip2 James Taylor의 탐색-bzip

(7zip에 맞는 것을 찾고 있어요)

bgzip 파일을 압축할 수 있습니다. gzip 인덱싱이 가능한 변형입니다. gzip).이는 일부 생물정보학 응용 분야에서 다음과 함께 사용됩니다. tabix 인덱서.

여기에서 설명을 참조하세요. http://blastedbio.blogspot.fr/2011/11/bgzf-blocked-bigger-better-gzip.html, 그리고 여기: http://www.htslib.org/doc/tabix.html.

다른 응용 프로그램에 어느 정도 적용할 수 있는지는 모르겠습니다.

이것이 귀하의 정확한 상황에서 실용적일지는 잘 모르겠지만 각 큰 파일을 각각 10MB와 같은 작은 파일로 gzip할 수는 없습니까?결국에는 다음과 같은 파일이 많이 생성됩니다.file0.gz, file1.gz, file2.gz 등원본 대형 내의 주어진 오프셋을 기반으로 다음과 같은 파일을 검색할 수 있습니다. "file" + (offset / 10485760) + ".gz".압축되지 않은 아카이브 내의 오프셋은 다음과 같습니다. offset % 10485760.

손실이없는 압축은 다른 영역보다 일부 영역에서 더 잘 작동하기 때문에 압축 데이터가 편리한 길이 블록 크기 블록에 저장하면 각 블록이 정확히 같은 수의 압축 바이트를 가지고 있더라도 일부 압축 블록은 다른 것보다 훨씬 긴 일반 텍스트로 확장됩니다. .

"압축 :차세대 텍스트 검색 시스템의 핵심" 작성자 : Nivio Ziviani, Edleno Silva de Moura, Gonzalo Navarro 및 Ricardo Baeza-Yates 안으로 컴퓨터 잡지 2000년 11월http://doi.ieeecomputersociety.org/10.1109/2.881693

압축 해제기는 압축된 데이터의 1, 2 또는 3바이트 전체를 가져와서(어휘 목록을 사용하여) 전체 단어로 압축을 풉니다.압축된 텍스트에서 단어나 구를 직접 검색할 수 있습니다. 압축되지 않은 텍스트를 검색하는 것보다 훨씬 빠릅니다.

압축 해제기를 사용하면 일반(바이트) 포인터로 텍스트의 임의의 단어를 가리키고 해당 지점부터 즉시 압축 해제를 시작할 수 있습니다.

텍스트에 고유한 단어가 65,000개 미만이므로 모든 단어에 고유한 2바이트 코드를 부여할 수 있습니다.(KJV 성경에는 거의 13,000개의 독특한 단어가 있습니다.)65,000개 이상의 단어가 있더라도 처음 256개의 2바이트 코드 "단어"를 가능한 모든 바이트에 할당하는 것은 매우 간단하므로 65,000개 정도의 "가장 빈번한" 어휘집에 없는 단어를 철자할 수 있습니다. 단어와 문구".(빈번한 단어와 구를 2바이트로 압축하여 얻은 압축 일반적으로 문자 당 2 바이트를 사용하여 때때로 단어의 철자를 철자하는 "확장"의 가치가 있습니다.적절한 압축을 제공하는 "자주 사용되는 단어 및 구문"의 어휘집을 선택하는 방법은 다양합니다.예를 들어 LZW 압축기를 조정하여 두 번 이상 사용하는 "문구"를 구문당 한 줄씩 어휘 파일에 덤프하고 모든 데이터에 대해 실행할 수 있습니다.또는 압축되지 않은 데이터를 구문당 한 줄씩 어휘 파일의 5바이트 구문으로 임의로 잘라낼 수도 있습니다.또는 압축되지 않은 데이터를 실제 영어 단어로 잘라서 단어 시작 부분의 공백을 포함하여 각 단어를 어휘집 파일에 넣을 수도 있습니다.그런 다음 "sort --unique"를 사용하여 해당 어휘 파일에서 중복 단어를 제거하십시오.(완벽한 "최적" 어휘 목록을 선택하는 것이 여전히 NP 하드로 간주됩니까?)

거대한 압축 파일의 시작 부분에 어휘집을 저장하고 편리한 BLOCKSIZE로 채운 다음 거기에서 파일 끝까지 압축된 텍스트(일련의 2바이트 "단어")를 저장합니다.아마도 검색자는 이 어휘집을 한 번 읽고 압축을 푸는 동안 RAM에 빠른 디코딩 형식으로 보관하여 "2바이트 코드"를 "가변 길이 구문"으로 압축 해제하는 속도를 높일 것입니다.내 첫 번째 초안은 구문 목록당 한 줄씩 간단히 작성하는 것으로 시작하지만 나중에 일종의 증분 코딩이나 zlib를 사용하여 어휘를 더 압축된 형식으로 저장하도록 전환할 수도 있습니다.

압축된 텍스트에 임의의 짝수 바이트 오프셋을 선택하고 거기에서 압축 풀기를 시작할 수 있습니다.좀 더 세분화된 랜덤 액세스 압축 파일 형식을 만드는 것은 불가능하다고 생각합니다.

두 가지 가능한 솔루션:

OS가 압축을 처리하도록 하고 모든 텍스트 파일을 포함하는 압축 파일 시스템(SquashFS, clicfs, cloop,crafs, e2compr 등)을 생성 및 마운트하고 응용 프로그램의 압축에 대해 아무 작업도 수행하지 마십시오.
파일 시스템 이미지를 압축하는 대신 각 텍스트 파일에 직접 clicf를 사용하십시오(텍스트 파일당 하나의 clicf)."mkclicfs mytextfile mycompressedfile"이 "gzip <mytextfile >mycompressedfile"이고 "clicfs mycompressedfile 디렉토리"가 "directory/mytextfile" 파일을 통해 데이터에 무작위로 액세스하는 방법이라고 생각하세요.

아직 언급되었는지는 모르겠지만 Kiwix 프로젝트는 이와 관련하여 훌륭한 작업을 수행했습니다.Kiwix 프로그램을 통해 ZIM 파일 아카이브에 대한 무작위 액세스를 제공합니다.압축도 잘 되네요.이 프로젝트는 Wikipedia의 오프라인 사본(모든 미디어를 포함하여 비압축 형식으로 100GB 이상에 도달)에 대한 수요가 있을 때 시작되었습니다.그들은 25GB 파일(대부분의 미디어가 없는 Wikipedia의 단일 파일 구현)을 성공적으로 가져와 이를 8GB의 zim 파일 아카이브로 압축했습니다.그리고 Kiwix 프로그램을 통해 모든 관련 데이터가 포함된 Wikipedia의 모든 페이지를 인터넷 서핑보다 빠르게 불러올 수 있습니다.

Kiwix 프로그램은 위키피디아 데이터베이스 구조를 기반으로 한 기술임에도 불구하고 뛰어난 압축률과 랜덤 액세스를 동시에 가질 수 있음을 입증했습니다.

이것은 매우 오래된 질문이지만 다음과 같습니다. zindex 좋은 해결책을 제공할 수 있습니다(비록 경험이 많지는 않지만).

razip은 이 지원을 위해 조정해야 하는 gzip/bzip2보다 더 나은 성능으로 임의 액세스를 지원합니다. - "ok" 임의 액세스를 희생하여 압축을 줄입니다.

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

나는 특정 유형의 생물학적 데이터를 압축하기 위한 오픈 소스 도구의 저자입니다.이 도구는 starch, 데이터를 염색체별로 분할하고 이러한 분할을 더 큰 아카이브 내의 압축된 데이터 단위에 빠르게 액세스하기 위한 인덱스로 사용합니다.

염색체별 데이터는 게놈 좌표의 중복성을 제거하기 위해 변환되고 변환된 데이터는 다음 중 하나를 사용하여 압축됩니다. bzip2 또는 gzip 알고리즘.오프셋, 메타데이터 및 압축된 게놈 데이터가 하나의 파일로 연결됩니다.

소스 코드는 당사에서 제공됩니다. GitHub 대지.우리는 Linux와 Mac OS X에서 컴파일했습니다.

귀하의 경우 헤더에 오프셋(10MB 등)을 사용자 정의 아카이브 형식으로 저장할 수 있습니다.헤더를 구문 분석하고, 오프셋을 검색하고, 점진적으로 fseek 파일을 통해 current_offset_sum + header_size.

라이센스 : CC-BY-SA ~와 함께 속성

제휴하지 않습니다 StackOverflow