아카이브 내 랜덤 액세스를 잘 지원하는 압축 형식?

아카이브 내 랜덤 액세스를 잘 지원하는 압축 형식?

---

이것은 이전 질문 과 유사 하지만 거기에 대한 답변이 내 요구를 충족시키지 못하고 내 질문이 약간 다릅니다.

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

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

그것은에서 보이는 하나의 소스 도 Z_FULL_FLUSH...뿐만 아니라 그것은 모든 gzip을 아카이브에서 지원하지 않는 완벽한 솔루션이 아니라 아카이브에 동기화 포인트를 검출 아주 아이디어는 동기화를위한 마법의 번호와 일치에 의해 중 (오탐 (false positive)을 생성 할 수 또는 Z_SYNC_FLUSH동기 점도 생성하지만 임의 액세스에 사용할 수 없기 때문입니다.

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

편집 : 앞서 언급했듯이 압축 된 데이터에서 바이너리 검색을하고 싶습니다. 특정 (압축되지 않은) 위치를 찾을 필요가 없습니다. 압축 된 파일 내에서 약간의 세분성을 가지고 검색하기 위해서만 있습니다. "이 압축 파일로 들어가는 길이의 약 50 % (25 %, 12.5 % 등)에서 시작하는 데이터 압축 해제"와 같은 지원을 원합니다.

---

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

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

그래도 가장 좋은 해결책은 파일을 원하는 청크로 분할 한 다음 아카이브의 개별 파일에 대한 임의 액세스를 지원하는 zip 또는 rar와 같은 일부 아카이버로 압축하는 것입니다.

---

dictzip을 살펴 보십시오 . gzip과 호환되며 거친 임의 액세스를 허용합니다.

man 페이지에서 발췌 :

dictzip 은 gzip (1) 알고리즘 (LZ77)을 사용하여 gzip 파일 형식과 완전히 호환되는 방식으로 파일을 압축합니다 . 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 아카이브에 대한 임의 액세스를 제공하는 솔루션이 있습니다.

• ghostscript 소스 코드에서 gzip zran.c
• James Taylor의 bzip2 seek-bzip

( 저는 7zip에 대한 무언가를 찾고 있습니다 )

---

bgzipgzip인덱싱 가능한 변형으로 파일을 압축 할 수 있습니다 (그리고로 압축 해제 할 수 있음 gzip). 이것은 tabix인덱서 와 함께 일부 생물 정보학 응용 프로그램에서 사용됩니다 .

여기에서 설명을 참조하십시오 : http://blastedbio.blogspot.fr/2011/11/bgzf-blocked-bigger-better-gzip.html 및 여기 : http://www.htslib.org/doc/tabix.html .

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

---

이것이 당신의 정확한 상황에서 실용적인지 확실하지 않지만 각 큰 파일을 작은 파일로 gzip (예 : 각각 10MB) 할 수 없습니까? file0.gz, file1.gz, file2.gz 등의 파일로 끝납니다. 원래의 큰 크기 내에서 주어진 오프셋을 기반으로라는 파일에서 검색 할 수 "file" + (offset / 10485760) + ".gz"있습니다. 압축되지 않은 아카이브 내의 오프셋은입니다 offset % 10485760.

---

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

Nivio Ziviani, Edleno Silva de Moura, Gonzalo Navarro 및 Ricardo Baeza-Yates의 컴퓨터 잡지 2000 년 11 월 http://doi.ieeecomputersociety.org/10.1109의 "Compression : A Key for Next-Generation Text Retrieval Systems"를 볼 수 있습니다. /2.881693

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

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

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

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

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

---

두 가지 가능한 솔루션 :

1. Let the OS deal with compression, create and mount a compressed file system (SquashFS, clicfs, cloop, cramfs, e2compr or whatever) containing all your text files and don't do anything about compression in your application program.

2. Use clicfs directly on each text file (one clicfs per text file) instead of compressing a filesystem image. Think of "mkclicfs mytextfile mycompressedfile" being "gzip <mytextfile >mycompressedfile" and "clicfs mycompressedfile directory" as a way of getting random access to the data via the file "directory/mytextfile".

---

I dont know if its been mentioned yet, but the Kiwix project had done great work in this regard. Through their program Kiwix, they offer random access to ZIM file archives. Good compression, too. The project originated when there was a demand for offline copies of the Wikipedia (which has reached above 100 GB in uncompressed form, with all media included). They have successfully taken a 25 GB file (a single-file embodiment of the wikipedia without most of the media) and compressed it to a measly 8 GB zim file archive. And through the Kiwix program, you can call up any page of the Wikipedia, with all associated data, faster than you can surfing the net.

Even though Kiwix program is a technology based around the wikipedia database structure, it proves that you can have excellent compression ratios and random access simultaneously.

---

This is a very old question but it looks like zindex could provide a good solution (although I don't have much experience with it)

---

The gzip format can be randomly accessed provided an index has been previously created, as it is demonstrated on zlib's zran.c source code.

I've developed a command line tool upon zlib's zran.c which creates indexes for gzip files: https://github.com/circulosmeos/gztool

It can even create an index for a still-growing gzip file (for example a log created by rsyslog directly in gzip format) thus reducing in the practice to zero the time of index creation. See the -S (Supervise) option.

---

razip supports random access with better performance than gzip/bzip2 which have to be tweaked for this support - reducing compression at the expense of "ok" random access:

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

---

I am the author of an open-source tool for compressing a particular type of biological data. This tool, called starch, splits the data by chromosome and uses those divisions as indices for fast access to compressed data units within the larger archive.

Per-chromosome data are transformed to remove redundancy in genomic coordinates, and the transformed data are compressed with either bzip2 or gzip algorithms. The offsets, metadata and compressed genomic data are concatenated into one file.

Source code is available from our GitHub site. We have compiled it under Linux and Mac OS X.

For your case, you could store (10 MB, or whatever) offsets in a header to a custom archive format. You parse the header, retrieve the offsets, and incrementally fseek through the file by current_offset_sum + header_size.

ReferenceURL : https://stackoverflow.com/questions/429987/compression-formats-with-good-support-for-random-access-within-archives