Formaty kompresji z dobrą obsługą losowego dostępu do archiwów?

Spójrz na dictzip . Jest kompatybilny z gzip i umożliwia zgrubny losowy dostęp.

Fragment jego strony man:

Dictzip kompresuje pliki za pomocą algorytmu gzip (1) (LZ77) w sposób, który jest w pełni kompatybilny z formatem pliku gzip. Rozszerzenie do gzip format pliku (Dodatkowe pole, opisane w 2.3.1.1 RFC 1952) pozwala na dodatkowe dane do zapisania w nagłówku skompresowanego pliku. Programy takie jak gzip i zcat zignoruje te dodatkowe dane. Jednak [dictzcat --start] wykorzysta tych danych do wykonania pseudolosowego dostępu do pliku.

Mam pakiet dictzip w Ubuntu. Lub jego kod źródłowy jest w dictd -*.smoła.gz . Jego licencja to GPL. Możesz ją studiować.

Aktualizacja:

Poprawiłem dictzip, aby nie miał limitu rozmiaru pliku. moja implementacja jest na licencji MIT.

The .format pliku xz (który wykorzystuje kompresję LZMA) wydaje się wspierać to:

Random-access reading: dane mogą być podzielone na niezależnie skompresowane bloki. Każdy .plik xz zawiera indeks bloków, co umożliwia ograniczony dostęp losowy, gdy rozmiar bloku jest wystarczająco mały.

To powinno wystarczyć do twojego celu. Wadą jest to, że API liblzmy (do interakcji z tymi kontenerami) nie wydaje się, że dobrze udokumentowane, więc może zająć trochę wysiłku wymyślenie, jak losowo uzyskać dostęp do bloków.

Istnieją rozwiązania zapewniające losowy dostęp do archiwów gzip i bzip2:

• gzip zran.c z kodu źródłowego ghostscript
• bzip2 seek - Bzip by James Taylor

(szukam czegoś dla 7zip )

bgzip może kompresować pliki w wariancie gzip, który jest indeksowalny (i może być dekompresowany przez gzip). Jest to używane w niektórych aplikacjach bioinformatycznych, wraz z indeksatorem tabix.

Zobacz wyjaśnienia tutaj: http://blastedbio.blogspot.fr/2011/11/bgzf-blocked-bigger-better-gzip.html , a tu: http://www.htslib.org/doc/tabix.html .

Nie jestem pewien, czy byłoby to praktyczne w twojej sytuacji, ale czy nie mógłbyś po prostu gzipować każdy duży plik na mniejsze pliki, powiedzmy 10 MB każdy? Skończyłbyś z mnóstwem plików: file0.gz, file1.gz, file2.gz itp. Na podstawie podanego offsetu wewnątrz oryginalnego dużego można wyszukiwać w pliku o nazwie "file" + (offset / 10485760) + ".gz". Przesunięcie w nieskompresowanym archiwum wynosi offset % 10485760.

Ponieważ kompresja bezstratna działa lepiej na niektórych obszarach niż na innych, jeśli przechowujesz skompresowane dane w blokach o dogodnej długości, nawet jeśli każdy blok ma dokładnie taką samą liczbę skompresowanych bajtów, niektóre skompresowane bloki rozszerzą się do znacznie dłuższego kawałka zwykłego tekstu niż inne.

You might look at "Kompresja: klucz do systemów odzyskiwania tekstu nowej generacji" autor: Nivio Ziviani, Edleno Silva de Moura, Gonzalo Navarro i Ricardo Baeza-Yates w Computer magazine November 2000 http://doi.ieeecomputersociety.org/10.1109/2.881693

Ich dekompresor pobiera 1, 2 lub 3 całe bajty skompresowanych danych i dekompresuje (używając listy słowników) do całego słowa. Można bezpośrednio przeszukiwać skompresowany tekst pod kątem słów lub fraz, co okazuje się jeszcze szybsze niż przeszukiwanie nieskompresowanego tekstu.

Ich dekompresor pozwala wskazać dowolne słowo w tekście normalnym (bajtowym) wskaźnikiem i natychmiast rozpocznij dekompresję.

Możesz nadać każdemu słowu unikalny 2-bajtowy Kod, ponieważ prawdopodobnie masz mniej niż 65 000 unikalnych słów w tekście. (W Biblii KJV jest prawie 13 000 unikalnych słów). Nawet jeśli istnieje więcej niż 65,000 słów, jest to dość proste, aby przypisać pierwsze 256 dwubajtowy kod " słowa "do wszystkich możliwych bajtów, dzięki czemu można przeliterować słowa, które nie są w leksykonie 65,000 lub tak"najczęstszych słów i zwrotów". (Kompresja uzyskana przez pakowanie częstych słów i zwrotów na dwa bajty Zwykle warto "rozszerzyć" od czasu do czasu pisowni słowa za pomocą dwóch bajtów na literę). Istnieje wiele sposobów na wybranie leksykonu "częstych słów i zwrotów", który da odpowiednią kompresję. Na przykład możesz dostosować kompresor LZW, aby zrzucał "frazy", których używa więcej niż raz, do pliku leksykonu, po jednej linii na frazę i uruchamiał je na wszystkich danych. Możesz też dowolnie pociąć nieskompresowane dane na 5 bajtowe frazy w pliku leksykonu, po jednej linijce na frazę. Możesz też pociąć nieskompresowane dane na rzeczywiste angielskie słowa i umieścić każde słowo-łącznie ze spacją na początku słowa-w pliku leksykonu. Następnie użyj opcji "sort --unique", aby wyeliminować zduplikowane słowa w tym pliku leksykonu. (Czy wybranie idealnej" optymalnej " leksykonowej listy słów jest nadal uważane za np-trudne?)

Przechowuj leksykon na początku swojego ogromnego skompresowanego pliku, umieść go w wygodnym rozmiarze bloku, a następnie przechowuj skompresowany tekst -- seria dwubajtowych "słów" -- stamtąd do końca pliku. Prawdopodobnie poszukiwacz przeczyta ten leksykon raz i zachowa go w jakimś szybkim formacie do dekodowania w pamięci RAM podczas dekompresji, aby przyspieszyć dekompresję "kodu dwubajtowego"do" wyrażenia o zmiennej długości". Mój pierwszy szkic zaczynałby się od prostej jednej linijki na listę fraz, ale możesz później przełączyć się na przechowywanie leksykonu w bardziej skompresowanej formie za pomocą jakiegoś kodowania przyrostowego lub zlib.

Możesz wybrać dowolny losowe przesunięcie parzystych bajtów do skompresowanego tekstu i rozpoczęcie dekompresji stamtąd. Nie wydaje mi się, aby możliwe było stworzenie drobnoziarnistego, losowego formatu skompresowanego pliku.

Dwa możliwe rozwiązania:

1. Niech system operacyjny zajmuje się kompresją, tworzy i montuje skompresowany system plików (SquashFS, clicfs, cloop, cramfs, e2compr lub cokolwiek innego) zawierający wszystkie Twoje pliki tekstowe i nie rób nic z kompresją w programie aplikacji.

2. Użyj clicfs bezpośrednio na każdym pliku tekstowym (jeden clicfs na plik tekstowy) zamiast kompresji obrazu systemu plików. Pomyśl o "mkclicfs mytextfile mycompressedfile "jako" gzip mycompressedfile " i "clicfs katalog mycompressedfile" jako sposób uzyskania losowego dostępu do danych poprzez plik "directory/mytextfile".

Nie wiem, czy już o nim wspomniano, ale projekt Kiwix wykonał w tym zakresie świetną robotę. Poprzez swój program Kiwix, oferują one losowy dostęp do archiwów plików ZIM. Dobra kompresja. Projekt powstał, gdy pojawiło się zapotrzebowanie na kopie offline Wikipedii (która osiągnęła ponad 100 GB w nieskompresowanej formie, z uwzględnieniem wszystkich mediów). Udało im się pobrać plik o pojemności 25 GB (jednoplikowe wcielenie Wikipedii bez większości mediów) i skompresować go do archiwum plików zim 8 GB. Dzięki programowi Kiwix możesz wywołać dowolną stronę Wikipedii, wraz ze wszystkimi powiązanymi danymi, szybciej niż możesz surfować po sieci.

Mimo że program Kiwix jest technologią opartą na strukturze bazy danych Wikipedii, dowodzi to, że można mieć doskonałe współczynniki kompresji i dostęp losowy jednocześnie.

To bardzo stare pytanie, ale wygląda na to, że zindex mógłby dostarczyć dobrego rozwiązania (choć nie mam z nim dużego doświadczenia)

Razip obsługuje dostęp losowy z lepszą wydajnością niż gzip/bzip2, które muszą być poprawione dla tego wsparcia-zmniejszając kompresję kosztem" ok " dostępu losowego:

Http://sourceforge.net/projects/razip/

Jestem autorem narzędzia open-source do kompresji określonego typu danych biologicznych. To narzędzie, zwane starch, dzieli dane na chromosomy i wykorzystuje te podziały jako wskaźniki do szybkiego dostępu do skompresowanych jednostek danych w większym archiwum.

Dane na chromosomy są przekształcane w celu usunięcia redundancji we współrzędnych genomowych, a przekształcone dane są kompresowane za pomocą algorytmów bzip2 lub gzip. Offsety, metadane i skompresowane dane genomowe są łączone w jednym pliku.

Kod źródłowy jest dostępny na naszej stronie GitHub. Skompilowaliśmy go pod Linuksem i Mac OS X.

W Twoim przypadku możesz przechowywać (10 MB lub cokolwiek innego) offsety w nagłówku do niestandardowego formatu archiwum. Analizujesz nagłówek, pobierasz offsety i stopniowo fseek przez plik przez current_offset_sum + header_size.