Jak mogę oszacować ściśliwość pliku bez kompresji?

Question

Używam serwera opartego na pętli zdarzeń w skręconym pythonie, który przechowuje pliki i chciałbym móc klasyfikować pliki zgodnie z ich kompresją.

Jeśli prawdopodobieństwo, że oni korzystać z kompresji jest wysoki, pójdą do katalogu z kompresją btrfs włączony, inaczej oni iść gdzie indziej.

nie muszę mieć pewność - dokładność 80% byłoby mnóstwo, i zaoszczędzić sporo miejsca. Ale ponieważ jest problem z CPU i wydajnością fs, nie mogę po prostu zapisać wszystkiego skompresowanego.

Pliki są w niskich megabajtów. Nie mogę przetestować - skompresować ich bez użycia ogromnej części procesora i nadmiernie opóźnić pętlę zdarzeń lub zreorganizować algorytm kompresji, aby pasował do pętli zdarzeń.

Czy istnieje najlepszych praktyk, aby dać szybkie oszacowanie ściśliwości? To, co wymyśliłem, zajmuje niewielką porcję (kilka KB) danych z początku pliku, przetestuj go (z prawdopodobnym opóźnieniem) i oprzyj moją decyzję na tym.

Wszelkie sugestie? Poradnik? Wady mojego rozumowania i/lub problemu?

Answer 1

Po prostu 1K z środkowy z pliku załatwi sprawę. Nie chcesz początku ani końca, ponieważ mogą one zawierać informacje nagłówka lub zwiastuna, które nie są reprezentatywne dla reszty pliku. 1K wystarcza, aby uzyskać pewną kompresję z dowolnym typowym algorytmem. To będzie przewidywać względną kompresję dla całego pliku, w takim stopniu, w jakim środkowy 1K jest reprezentatywny. Bezwzględny stosunek, który otrzymasz, nie będzie taki sam jak dla całego pliku, ale kwota, która różni się od braku kompresji, pozwoli ci ustawić próg. Po prostu eksperymentuj z wieloma plikami, aby zobaczyć, gdzie ustawić próg.

Jak już wspomniano, można zaoszczędzić czas, nie robiąc nic dla plików, które są oczywiście już skompresowane, np. .png. .jpg, .mov, .pdf, .zip, itp.

Pomiar entropii niekoniecznie jest dobrym wskaźnikiem, ponieważ daje jedynie szacunkową wartość ściśliwości rzędu zerowego. Jeśli entropia wskazuje, że jest wystarczająco ściśliwy, to jest w porządku. Jeśli entropia wskazuje, że nie jest wystarczająco ściśliwy, to może lub nie może być właściwa. Rzeczywista kompresor jest znacznie lepszym estymatorem ściśliwości. Uruchomienie go na 1K nie potrwa długo.

Answer 2

myślę co szukasz jest How to calculate the entropy of a file?

to pytanie zawiera wszelkiego rodzaju metod obliczania entropii pliku (i przez które można dostać „kompresji” pliku). Oto cytat z artykułu streszczenie this (Zależność między Entropia i Test Data Compression Kedarnath J. Balakrishnan, członek, IEEE i Nur A. Touba, Senior Member IEEE):

entropii zestawu danych jest miarą ilości informacji w nim zawartych. Obliczenia entropii dla w pełni wyspecyfikowanych danych zostały wykorzystane do uzyskania teoretycznego ograniczenia, o ile dane mogą być skompresowane. Artykuł ten rozszerza pojęcie entropii dla niepełnie określonych danych testowych (to znaczy, które mają nieokreślone lub nie obchodzi bity) i bada użycie entropii, aby pokazać, jak można obliczyć granice maksymalnej kompresji dla określonego podziału na symbole. Badano wpływ różnych sposobów podziału danych testowych na symbole na entropii. Dla klasy partycji, które używają znaków o stałej długości, opisany jest chciwy algorytm do określania, nie dbając o zmniejszenie entropii. Okazuje się, że jest to odpowiednik minimalnego problemu z pokrywą zestawu entropijnego, a zatem znajduje się w granicach stałego błędu addytywnego w odniesieniu do minimalnej entropii możliwej spośród wszystkich sposobów określania nie dba. Opisano algorytm wielomianowy, który można wykorzystać do przybliżenia obliczeń entropii. Różne techniki kompresji danych testowych zaproponowane w literaturze są analizowane w odniesieniu do granic entropii. Ograniczenia i zalety niektórych rodzajów strategii kodowania danych testowych są badane z wykorzystaniem teorii entropii

I być bardziej konstruktywne, kasa this miejsce dla realizacji Pythona obliczeń entropia kawałkami danych

Answer 3

skompresowane pliki zwykle don nie kompresuje się dobrze. Oznacza to, że prawie każdy plik multimedialny nie będzie kompresował się bardzo dobrze, ponieważ większość formatów multimediów zawiera kompresję. Wyraźnie istnieją wyjątki od tego, takie jak obrazy BMP i TIFF, ale prawdopodobnie można zbudować białą listę dobrze skompresowanych typów plików (PNG, MPEG i odejście od wizualnego nośnika - gzip, bzip2, itp.), Aby pominąć i założyć reszta plików, które napotkasz, będzie dobrze kompresować.

Jeśli masz ochotę się zakochać, możesz zbudować sprzężenie zwrotne w systemie (obserwuj wyniki dowolnej kompresji, którą wykonujesz i powiąż wynikowy stosunek z typem pliku). Jeśli natrafisz na typ pliku, który ma stale słabą kompresję, możesz dodać go do białej listy.

Pomysły te zależą od tego, czy potrafią zidentyfikować typ pliku, ale są też standardowe narzędzia, które wykonują całkiem niezłą robotę (zazwyczaj znacznie lepiej niż 80%) - file (1), /etc/mime.types, itp.