Dlaczego te (bezstratne) metody kompresji wielu podobnych obrazów png są nieskuteczne?

Właśnie natrafiłem na następującą rzecz: umieściłem wiele identycznych kopii obrazu png w folderze, a następnie próbowałem skompresować ten folder za pomocą następujących metod:

• tar czf folder.tar.gz folder/
• tar cf folder.tar folder/ && xz --stdout folder.tar > folder.tar.xz (ten działa dobrze dla identycznych obrazów, jednak dla podobnych obrazów zysk wynosi zero)
• zip -r folder.zip folder/

Kiedy sprawdził wielkość .tar.gz, .tar.xz, .zipzdałem sobie sprawę, że to jest prawie taki sam, jak jeden z folder/.
Rozumiem, że sam obraz png może mieć wysoki poziom kompresji i dlatego nie może być dalej kompresowany. Jednak podczas łączenia wielu podobnych (w tym przypadku nawet identycznych) obrazów png do archiwum, a następnie kompresji archiwum, oczekiwałbym znacznego zmniejszenia wymaganego rozmiaru. W przypadku identycznych obrazów spodziewałbym się rozmiaru mniej więcej wielkości pojedynczego obrazu.

Zobacz, jak działają algorytmy kompresji. Przynajmniej te z rodziny Lempel-Ziv ( gzip używa LZ77 , zipnajwyraźniej też tak robi i xz używa LZMA ) kompresują nieco lokalnie : Podobieństw, które leżą daleko od siebie, nie można zidentyfikować.

Szczegóły różnią się między metodami, ale sedno jest takie, że zanim algorytm osiągnie drugi obraz, już „zapomniał” początek pierwszego. I tak dalej.

Możesz spróbować ręcznie zmienić parametry metody kompresji; jeśli rozmiar okna (LZ77) lub. rozmiar bloku / porcji (późniejsze metody) jest co najmniej tak duży jak dwa obrazy, prawdopodobnie zobaczysz dalszą kompresję.

Zauważ, że powyższe tak naprawdę ma zastosowanie tylko wtedy, gdy masz identyczne obrazy lub prawie identyczne obrazy nieskompresowane . Jeśli występują różnice, skompresowane obrazy mogą nie wyglądać podobnie w pamięci. Nie wiem, jak działa kompresja PNG; możesz ręcznie sprawdzić reprezentacje szesnastkowe obrazów dla udostępnionych podłańcuchów.

Pamiętaj również, że nawet przy zmienionych parametrach i nadmiarowości do wykorzystania, nie sprowadzisz się do rozmiaru jednego obrazu. Większe słowniki oznaczają większy rozmiar słowa kodowego, a nawet jeśli dwa obrazy są dokładnie identyczne, może być konieczne zakodowanie drugiego za pomocą wielu słów kodowych (które wskazują na pierwsze).

Dlaczego tak się dzieje. W rzeczywistości występują tutaj dwa różne efekty:

• Każdy plik jest kompresowany niezależnie. Niektóre programy do archiwizacji - w tym zip - kompresują każdy plik niezależnie, bez pamięci z jednego pliku do drugiego. Innymi słowy, każdy plik jest osobno kompresowany, a następnie skompresowane pliki są łączone w archiwum.

• Pamięć krótkotrwała. Niektóre programy do archiwizacji mogą wykorzystywać informacje o jednym pliku, aby lepiej skompresować następny plik. Skutecznie łączą pliki, a następnie kompresują wynik. To jest poprawa.

  Zobacz także odpowiedź Nayuki, aby uzyskać więcej informacji na ten temat.

  Istnieje jednak drugi problem. Niektóre schematy kompresji - w tym zip, gzip i bzip2 - mają ograniczoną pamięć. Kompresują dane w locie i zapamiętują ostatnie 32 KB danych, ale nie pamiętają nic o danych, które pojawiły się znacznie wcześniej w pliku. Innymi słowy, nie mogą znaleźć zduplikowanych danych, jeśli duplikaty występują dalej niż 32 KB od siebie. W rezultacie, jeśli identyczne pliki są krótkie (krótsze niż około 32 KB), algorytm kompresji może usunąć zduplikowane dane, ale jeśli identyczne pliki są długie, algorytm kompresji zostaje ukryty i staje się bezwartościowy: nie może wykryć żadnego z duplikat danych. (Bzip pamięta dane z ostatnich 900 KB lub więcej, zamiast 32 KB).

  Wszystkie standardowe algorytmy kompresji mają pewien maksymalny rozmiar pamięci, poza którym nie wykrywają wzorców ... ale dla niektórych liczba ta jest znacznie większa niż dla innych. W przypadku Bzip jest to coś w rodzaju 900 KB. W przypadku XZ jest to coś w rodzaju 8 MB (z ustawieniami domyślnymi). W przypadku 7z jest to coś w rodzaju 2 GB. 2 GB jest więcej niż wystarczająco duże, aby rozpoznać zduplikowane kopie plików PNG (które zwykle są znacznie mniejsze niż 2 GB). Ponadto 7z stara się również sprytnie podchodzić do umieszczania w archiwum plików, które prawdopodobnie będą do siebie podobne, aby pomóc kompresorowi w pracy; tar nie wie o tym nic.

  Zobacz także odpowiedź Rafaela i odpowiedź Nayuki za uzyskać więcej wyjaśnienie tego efektu.

Jak to dotyczy twojego ustawienia. W twoim konkretnym przykładzie pracujesz z obrazami PNG. Obrazy PNG są kompresowane, więc każdy plik PNG można traktować jako sekwencję losowo wyglądających bajtów, bez żadnych wzorców lub duplikacji w pliku. Kompresor nie ma nic do wykorzystania, jeśli patrzy na pojedynczy obraz PNG. Dlatego jeśli spróbujesz skompresować pojedynczy plik PNG (lub utworzysz archiwum zip / tar / ... zawierające tylko jeden plik PNG), nie uzyskasz żadnej kompresji.

Teraz spójrzmy na to, co się stanie, jeśli spróbujesz przechowywać wiele kopii tego samego pliku PNG:

• Małe pliki Jeśli plik PNG jest bardzo mały, wszystko oprócz zip będzie działało świetnie. Zip zawiedzie spektakularnie: kompresuje każdy plik niezależnie, więc nie ma szansy wykryć nadmiarowości / duplikacji plików. Ponadto, gdy próbuje skompresować każdy plik PNG, nie osiąga żadnej kompresji; rozmiar archiwum zip będzie ogromny. Natomiast rozmiar archiwum tar (skompresowanego za pomocą gzip, bzip2 lub xz) i archiwum 7z będzie małe, ponieważ zasadniczo przechowuje jedną kopię pliku, a następnie zauważa, że ​​wszystkie pozostałe są identyczne - korzyści z zachowywania pamięci z jednego pliku do drugiego.

• Duże pliki. Jeśli plik PNG jest duży, tylko 7z działa dobrze. W szczególności zip nadal spektakularnie zawodzi. Ponadto pliki tar.zip i tar.bzip2 nie działają poprawnie, ponieważ rozmiar pliku jest większy niż okno pamięci kompresora: gdy kompresor widzi pierwszą kopię pliku, nie może go zmniejszyć (ponieważ został już skompresowany ); zanim zacznie widzieć początek drugiej kopii pliku, zapomniał już o sekwencjach bajtów widocznych na początku pierwszego pliku i nie może nawiązać połączenia, że ​​te dane są w rzeczywistości duplikatem.

  Natomiast tar.xz i 7z nadal świetnie sobie radzą z wieloma kopiami dużego pliku PNG. Nie mają ograniczenia „małego rozmiaru pamięci” i są w stanie zauważyć, że druga kopia pliku jest identyczna z pierwszą kopią, więc nie ma potrzeby przechowywania jej po raz drugi.

Co możesz na to poradzić. Użyj 7z. Ma kilka heurystyk, które pomogą wykryć identyczne lub podobne pliki i kompresować naprawdę dobrze w tym przypadku. Możesz także spojrzeć na lrzip z kompresją lzop.

Skąd mam wiedzieć? Udało mi się to zweryfikować, przeprowadzając eksperymenty ze 100 kopiami pliku zawierającego losowe bajty. Próbowałem 100 kopii pliku 4KB, 100 kopii pliku 1 MB i 100 kopii pliku 16 MB. Oto, co znalazłem:

Size of file      Size of compressed archive (with 100 copies)
                  zip  tar.gz  tar.bz2  tar.xz    7z
         4KB    414KB     8KB     10KB     5KB    5KB
         1MB    101MB   101MB    101MB     1MB    2MB
        16MB    1.6G    1.6GB    1.6GB   1.6GB  401MB

Jak widać, zip jest okropny bez względu na to, jak mały jest twój plik. 7z i xz są dobre, jeśli twoje obrazy nie są zbyt duże (ale xz będzie kruchy i zależy od kolejności umieszczania obrazów w archiwum, jeśli masz kilka duplikatów i niektóre nie-duplikaty zmieszane razem). 7z jest naprawdę dobry, nawet w przypadku dużych plików.

Bibliografia. Jest to również dobrze wyjaśnione w wielu postach na Super User. Spójrz:

• Dlaczego kompresja Gzip nie eliminuje duplikatów danych?
• Dlaczego Zip jest w stanie skompresować pojedynczy plik mniejszy niż wiele plików o tej samej zawartości?
• Kompresowanie wielu podobnych dużych plików
• Skutecznie kompresuj podobne pliki
• Czy istnieje program do kompresji lub archiwizacji dla systemu Windows, który również wykonuje deduplikację?
• Bardziej wydajny program do kompresji plików dla wielu identycznych plików?

Po pierwsze, zauważ, że format obrazu PNG to zasadniczo surowe piksele RGB (z pewnym filtrowaniem światła) przepchnięte przez format kompresji DEFLATE. Ogólnie rzecz biorąc, skompresowane pliki (PNG, JPEG, MP3 itp.) Nie zobaczą żadnej korzyści z ponownej kompresji. Dlatego ze względów praktycznych możemy traktować plik PNG jako nieściśliwe losowe dane do końca eksperymentu.

Po drugie, zauważ, że formaty ZIP i gzip również używają kodeka DEFLATE. (To by wyjaśniało, dlaczego skompresowanie pojedynczego pliku w porównaniu do gzipa spowoduje zasadniczo taki sam rozmiar wyjściowy).

Teraz pozwól mi skomentować każdy przypadek testowy indywidualnie:

• tar czf folder.tar.gz folder/

  Spowoduje to utworzenie (nieskompresowanego) pliku TAR, który połączy wszystkie identyczne pliki PNG (z niewielką ilością metadanych i dopełnienia). Następnie ten pojedynczy plik jest przesyłany przez kompresor gzip w celu utworzenia jednego skompresowanego pliku wyjściowego.

  Niestety format DEFLATE obsługuje tylko okno słownika LZ77 o wielkości 32768 bajtów. Więc nawet jeśli plik TAR zawiera powtarzalne dane, jeśli plik PNG jest większy niż 32 KiB, to na pewno kompresor DEFLATE nie może zapamiętać danych wystarczająco daleko, aby skorzystać z faktu, że powtarzają się identyczne dane.

  Z drugiej strony, jeśli powtórzysz eksperyment z, powiedzmy, 20-KB pliku PNG zduplikowanym 10 razy, bardzo prawdopodobne jest, że otrzymasz plik gzip tylko nieco większy niż 20 KB.

• tar cf folder.tar folder/ && xz --stdout folder.tar > folder.tar.xz

  Spowoduje to utworzenie pliku TAR, tak jak poprzednio, a następnie użycie formatu xz i kompresora LZMA / LZMA2. W tej sytuacji nie mogłem znaleźć informacji o LZMA, ale z 7-Zip dla Windows wiem, że może on obsługiwać duże okna wielkości słownika (np. 64 MiB). Możliwe więc, że korzystałeś z nieoptymalnych ustawień i że kodek LZMA mógł zmniejszyć plik TAR do rozmiaru jednego pliku PNG.

• zip -r folder.zip folder/

  Format ZIP nie obsługuje „stałych” archiwów; to znaczy każdy plik jest kompresowany niezależnie. Zakładamy, że każdy plik jest nieściśliwy. Dlatego nie można wykorzystać faktu, że każdy plik jest identyczny, a plik ZIP będzie tak duży, jak zwykła konkatenacja wszystkich plików.

Problem polega na tym, że (większości) schematom kompresji brakuje wiedzy na temat posiadanych danych. Nawet jeśli zdekompresujesz swoje pliki PNG do map bitowych i skompresujesz je w archiwum, nie uzyskasz (znacząco) mniejszych wyników.

W przypadku wielu podobnych obrazów odpowiednim schematem kompresji byłby kodek wideo.

Używając bezstratnego kodowania, powinieneś osiągnąć prawie idealny wynik kompresji, którego oczekujesz.

Jeśli chcesz to przetestować, użyj czegoś takiego:

ffmpeg -i img%03d.png -c:v libx264 -c:v libx264 -profile:v high444 -crf 0 out.mp4

https://trac.ffmpeg.org/wiki/Create%20a%20video%20slideshow%20from%20images

PNG to kombinacja filtrów + LZ77 + Huffman (połączenie LZ77 + Huffman nazywa się Deflate) w następującej kolejności:

krok 1) jeśli filtr różni się od Brak, wartość pikseli jest zastępowana różnicą w stosunku do sąsiednich pikseli (więcej szczegółów patrz http://www.libpng.org/pub/png/book/chapter09.html ) . Zwiększa to kompresję obrazów z gradientami (więc ... 4 5 6 7 staje się ... 1 1 1 1) i może pomóc w obszarach tego samego koloru (... 3 3 3 5 5 5 5 5 staje się 0 0 0 2 0 0 0 0 0). Domyślnie filtry są włączone w obrazach 24-bitowych i wyłączone w obrazach 8-bitowych z paletą.

krok 2) dane są kompresowane za pomocą LZ77, który zastępuje powtarzające się (pasujące) ciągi bajtów krotką zawierającą odległość do dopasowania i długość dopasowania.

krok 3) wynik kroku 2 jest kodowany kodem Huffmana, który zastępuje symbole o stałej długości kodami o zmiennej długości, im częściej symbol, tym krótszy kod.

Istnieje wiele problemów:

Mała zmiana, która wpływa na kilka pikseli, spowoduje zmiany wyników z 3 kroków kompresji png:

1) Filtrowana wartość sąsiednich pikseli ulegnie zmianie (w zależności od zastosowanego filtra). To wzmocni efekty małych zmian.

2) Zmiana oznacza, że ​​dopasowania do tego obszaru będą się różnić. Na przykład zmiana 333333 na 333533 powoduje, że kolejne wystąpienie 333333 nie będzie już zgodne, więc wybierze kolejne dopasowanie do 333333 z inną odległością lub wybierze to samo dopasowanie, ale o krótszej długości, a następnie kolejne dopasowanie dla ostatnich 3 bajtów. Samo to bardzo zmieni wyniki.

3) Największym problemem jest krok 3. Kod huffmana używa zmiennej liczby bitów, więc nawet niewielka zmiana spowoduje, że wszystko, co następuje, nie będzie już wyrównane. AFAIK Większość algorytmów kompresji nie może wykryć dopasowań, które nie są wyrównane bajtowo, więc zapobiegnie (lub przynajmniej znacznie zmniejszy) kompresję już skompresowanych danych, które następuje po zmianie, chyba że kompresor wykryje dopasowania, które nie są wyrównane bajtowo.

Inne problemy są już objęte innymi odpowiedziami:

4) Gzip używa tego samego algorytmu Deflate ze słownikiem 32 KB, więc jeśli pliki png są większe niż 32 KB, dopasowania nie zostaną wykryte, nawet jeśli są identyczne. Bzip2 jest lepszy pod tym względem, ponieważ używa bloku 900 KB. XZ używa LZMA, którego IIRC ma słownik o wielkości 4 MB w domyślnym poziomie kompresji. 5) Format zip nie używa stałej kompresji, więc nie będzie lepiej kompresował podobnych lub identycznych plików.

Być może kompresory z rodziny PAQ lub PPMD ​​będą kompresować lepiej, ale jeśli potrzebujesz skompresować wiele podobnych plików obrazów, możesz rozważyć 3 podejścia:

1) Przechowuj obrazy nieskompresowane (z PNG -0 lub w formacie bez kompresji) i kompresuj za pomocą kompresora z dużym słownikiem lub rozmiarem bloku. (LZMA będzie działać dobrze)

2) Inną opcją byłoby zachowanie filtrów, ale usunięcie kompresji Deflate z plików PNG. Można to zrobić na przykład za pomocą narzędzia ( AdvDef ). Następnie kompresujesz powstałe nieskompresowane pliki PNG. Po dekompresji możesz zachować nieskompresowany plik PNG lub skompresować go ponownie za pomocą AdvDef (ale zajmie to trochę czasu).

Musisz przetestować oba podejścia, aby zobaczyć, który kompresuje najbardziej.

3) Ostatnią opcją byłoby konwersja obrazów png w wideo, skompresowanie go za pomocą bezstratnego kompresora wideo, takiego jak x264 bezstratny (zwracając szczególną uwagę na użycie odpowiedniego formatu kolorów), a następnie po ekstrakcji wyodrębnij ramki do poszczególnych obrazów png. Można to zrobić za pomocą ffmpeg. Trzeba też zachować mapowanie między numerem klatki a oryginalną nazwą.

To byłoby najbardziej złożone podejście, ale jeśli wszystkie PNG są częścią animacji, może być najbardziej skuteczne. Jednak potrzebny będzie format wideo obsługujący przezroczystość, jeśli jest potrzebny.

Edycja: Istnieje również format MNG, który nie byłby często używany.

Kiedy masz specjalne zestawy danych, używasz specjalnych algorytmów, a nie narzędzi wielofunkcyjnych.

Odpowiedź jest taka, że ​​wybrane przez ciebie bezstratne kompresje nie są wykonane do tego, co robisz. Nikt nie oczekuje, że dwukrotnie skompresujesz ten sam obraz, a nawet jeśli to zrobisz (przypadkowo) sprawdzenie wszystkich poprzednich danych wejściowych sprawiłoby, że Twój algorytm O (n ^ 2) (może trochę lepiej, ale przynajmniej naiwne podejście byłoby n ^ 2).

Większość programów do kompresji, które testowałeś podczas pracy w O (n), podkreślają prędkość w stosunku do optymalnego współczynnika kompresji. Nikt nie chce uruchamiać swojego komputera przez 5 godzin, aby zaoszczędzić kilka MB, szczególnie w dzisiejszych czasach. Przy większych wejściach cokolwiek powyżej O (n) staje się kwestią czasu działania.

Inną kwestią jest baran. Nie możesz uzyskać dostępu do każdej części danych wejściowych w dowolnym momencie, gdy dane wejściowe stają się wystarczająco duże. Nawet nie zważając na to, większość ludzi nie chce rezygnować z całego pamięci RAM lub procesora, aby coś skompresować.

Jeśli masz w plikach wzorce, które chcesz skompresować, będziesz musiał wykonać na nich operacje manuel, napisać własną kompresję lub potencjalnie użyć kompresji typu „archiwum” (nano). Kompresja do długotrwałego przechowywania, która jest zbyt wolna do codziennego użytku.

Inną opcją może być bezstratna kompresja wideo.

Format pliku PNG korzysta już wewnętrznie z algorytmu kompresji DEFLATE. Jest to ten sam algorytm, którego używają xz, gzip i zip - tylko w niektórych odmianach. tar.gzi tar.xzskorzystaj z podobieństwa między plikami, co zipnie.

Tak więc faktycznie kompresujesz DEFLATE w stosunku do skompresowanych plików DEFLATE - dlatego pliki zachowują prawie oryginalny rozmiar.

bzip2Programu (także powiązany algorytm) jest lepszy jeśli chodzi o (prawie) identycznych plików.

# for i in $(seq 4); do cp test.png test$i.png; done
# tar -cjf archive.tar.bz2 *.png
# ls -l
-rw-r--r-- 1 abcde users  43813 15. Jul 08:45 test.png
-rw-r--r-- 1 abcde users  43813 15. Jul 08:45 test1.png
-rw-r--r-- 1 abcde users  43813 15. Jul 08:46 test2.png
-rw-r--r-- 1 abcde users  43813 15. Jul 08:46 test3.png
-rw-r--r-- 1 abcde users  43813 15. Jul 08:46 test4.png
-rw-r--r-- 1 abcde users  68115 15. Jul 08:47 archive.tar.bz2