Kompresja danych przy użyciu liczb pierwszych

Niedawno natknąłem się na następujący interesujący artykuł, który twierdzi, że skutecznie kompresuje losowe zestawy danych o zawsze ponad 50%, niezależnie od rodzaju i formatu danych.

Zasadniczo używa liczb pierwszych do unikalnego skonstruowania reprezentacji 4-bajtowych fragmentów danych, które są łatwe do zdekompresowania, biorąc pod uwagę, że każda liczba jest unikalnym produktem liczb pierwszych. W celu powiązania tych sekwencji z liczbami pierwszymi wykorzystuje słownik.

Moje pytanie brzmi:

• Czy to naprawdę możliwe, jak sugerują autorzy? Według artykułu ich wyniki są bardzo wydajne i zawsze kompresują dane do mniejszego rozmiaru. Czy rozmiar słownika nie będzie ogromny?
• Czy nie można tego użyć do iteracyjnego ponownego skompresowania skompresowanych danych przy użyciu tego samego algorytmu? Jest oczywiste i zostało wykazane, że takie techniki (w których skompresowane dane są ponownie kompresowane tyle razy, ile to możliwe, radykalnie zmniejszając rozmiar pliku) są niemożliwe; w istocie nie byłoby bijectu między zbiorem wszystkich danych losowych a danymi skompresowanymi. Dlaczego więc wydaje się to możliwe?
• Nawet jeśli technika ta nie jest jeszcze doskonała, można ją oczywiście zoptymalizować i znacznie ulepszyć. Dlaczego nie jest to bardziej znane / badane? Jeśli rzeczywiście te twierdzenia i wyniki eksperymentów są prawdziwe, czy nie zrewolucjonizuje to przetwarzania?

zawsze kompresuj losowe zestawy danych o ponad 50%

To niemożliwe. Nie możesz kompresować losowych danych, potrzebujesz struktury, aby z nich skorzystać. Kompresja musi być odwracalna, więc nie można kompresować wszystkiego o 50%, ponieważ łańcuchów o długości jest znacznie mniej niż o długości .$n/2$$n$

Z papierem wiąże się kilka poważnych problemów:

• Używają 10 plików testowych bez wskazania ich zawartości. Czy dane są naprawdę losowe? Jak zostały wygenerowane?

• Twierdzą, że osiągają współczynniki kompresji co najmniej 50%, podczas gdy ich dane testowe pokazują, że osiągają co najwyżej 50%.

Algorytm ten definiuje bezstratną strategię, która wykorzystuje liczby pierwsze występujące w systemie liczb dziesiętnych

• Co? Liczby pierwsze to liczby pierwsze niezależnie od podstawy.

• Problem nr 1 z dekompresją: rozkład na czynniki pierwsze jest trudnym problemem, jak to zrobić skutecznie?

• Problem nr 2 z dekompresją ( to jest kicker ): mnożą liczby pierwsze razem, ale w ten sposób tracisz informacje o kolejności, ponieważ . Nie sądzę, że można w ogóle dekompresować za pomocą ich techniki.$2\cdot 5 = 10 = 5\cdot 2$

Nie sądzę, że ten papier jest bardzo dobry.

Przejdę do Toma van der Zandena, który zdaje się czytać gazetę i odkrył słabość metody. Chociaż nie czytałem szczegółowo artykułu, wychodząc z abstraktu i tabeli wyników, wydaje się, że jest to całkowicie wiarygodne twierdzenie.

Twierdzą, że utrzymują spójny 50% współczynnik kompresji plików tekstowych (nie „wszystkich plików”), które, jak zauważają, są mniej więcej takie same jak LZW i około 10% gorsze niż (przypuszczalnie zerowego rzędu) kodowanie Huffmana. Kompresowanie plików tekstowych o 50% nie jest trudne do osiągnięcia przy użyciu stosunkowo prostych metod; jest to praca licencjacka na wielu kursach informatyki.

Zgadzam się, że artykuł nie jest zbyt dobry w stosunku do opublikowanych badań i nie sądzę, by dobrze oceniał recenzentów, że zostało to zaakceptowane. Poza oczywistymi brakującymi szczegółami, które uniemożliwiają odtworzenie wyników (np. Jakie były pliki tekstowe) i brak próby powiązania go z dziedziną kompresji, nie ma sensu, aby naprawdę rozumieli, co robi ich algorytm.

Witryna konferencji twierdzi, że przyjmuje współczynnik akceptacji 1: 4, co sprawia, że ​​zastanawiasz się, co odrzucili.

Ty pytasz:

• Czy to naprawdę możliwe, jak sugerują autorzy? Według artykułu ich wyniki są bardzo wydajne i zawsze kompresują dane do mniejszego rozmiaru. Czy rozmiar słownika nie będzie ogromny?

Tak oczywiście. Nawet w przypadku ręcznie wybranego przykładu („SZYBKI SREBRNY lis skacze nad leniwym psem”) nie osiągają kompresji, ponieważ słownik zawiera każdy 4-bajtowy ciąg tekstu (minus 4 bajty za jedno powtórzenie „ THE „)… i„ skompresowana ”wersja tekstu musi zawierać cały słownik oraz wszystkie te bzdury z liczbami pierwszymi.

• Czy nie można tego użyć do iteracyjnego ponownego skompresowania skompresowanych danych przy użyciu tego samego algorytmu? Jest oczywiste i zostało wykazane, że takie techniki (w których skompresowane dane są ponownie kompresowane tyle razy, ile to możliwe, radykalnie zmniejszając rozmiar pliku) są niemożliwe; w istocie nie byłoby żadnego bijectu między zbiorem wszystkich danych losowych a danymi skompresowanymi. Dlaczego więc wydaje się to możliwe?

Znowu wydaje się, że masz dobrą intuicyjną wiedzę na temat sytuacji. Intuicyjnie zorientowałeś się, że żaden schemat kompresji nie może być skuteczny na wszystkich wejściach, ponieważ gdyby tak było, moglibyśmy go stosować w kółko, aby skompresować dane wejściowe do jednego bitu - a potem do nicości!

Innymi słowy: po skompresowaniu wszystkich plików .wav do .mp3, nie uzyskasz żadnej poprawy ich rozmiaru poprzez skompresowanie ich. Jeśli Twój kompresor MP3 wykonał swoją pracę, nie będzie żadnych wzorów do wykorzystania przez kompresor ZIP.

(To samo dotyczy szyfrowania: jeśli wezmę plik zer i zaszyfruję go zgodnie z moim wybranym algorytmem kryptograficznym, wynikowy plik lepiej nie będzie podlegał kompresji , w przeciwnym razie mój algorytm szyfrowania wycieknie „wzorzec” na wyjście!)

• Nawet jeśli technika ta nie jest jeszcze doskonała, można ją oczywiście zoptymalizować i znacznie ulepszyć. Dlaczego nie jest to bardziej znane / badane? Jeśli rzeczywiście te twierdzenia i wyniki eksperymentów są prawdziwe, czy nie zrewolucjonizuje to przetwarzania?

Te twierdzenia i wyniki eksperymentów nie są prawdziwe.

Jak już zauważył Tom van der Zanden, „algorytm kompresji” Chakraborty, Kar i Guchait ma wadę polegającą na tym, że nie tylko nie osiąga żadnego współczynnika kompresji, ale jest również nieodwracalny (w matematyce „nie bijective”): istnieją mnogość tekstów, które wszystkie „kompresują” do tego samego obrazu, ponieważ ich algorytm to w zasadzie mnożenie, a mnożenie jest przemienne.

Powinieneś czuć się dobrze, że intuicyjne zrozumienie tych pojęć doprowadziło cię natychmiast do właściwego wniosku. A jeśli możesz poświęcić czas, powinieneś współczuć autorom artykułu, którzy wyraźnie spędzili dużo czasu na myśleniu na ten temat, nie rozumiejąc go wcale.

Katalog plików jeden poziom powyżej opublikowanego adresu URL zawiera 139 „artykułów” o tej samej jakości, wszystkie najwyraźniej przyjęte w „Postępach międzynarodowej konferencji na temat nowych badań w dziedzinie informatyki, informacji, komunikacji i aplikacji”. Wydaje się, że jest to pozorna konferencja zwykłego typu. Celem takich konferencji jest umożliwienie nieuczciwym naukowcom domagania się „publikacji w czasopiśmie”, a jednocześnie pozbawienie skrupułów organizatorów do zarobienia mnóstwo pieniędzy. (Aby uzyskać więcej informacji na temat fałszywych konferencji, sprawdź ten wątek reddit lub różne posty StackExchange na ten temat .) W każdej dziedzinie istnieją fałszywe konferencje . Naucz się ufać swoim instynktom i nie wierzyć we wszystko, co czytasz w „postępowaniu konferencyjnym”, a wszystko będzie dobrze.

Entropia skutecznie ogranicza wydajność najsilniejszej możliwej kompresji bezstratnej. Dlatego nie ma algorytmu, który mógłby kompresować losowe zestawy danych o zawsze więcej niż 50%.

Metody kompresji, które można odtworzyć, na ogół znajdują wzór i wyrażają go w uproszczony sposób. Niektóre są bardzo sprytne, niektóre bardzo proste. W pewnym momencie nie ma wzorca. Proces (y) „zagotował” zestaw danych do najprostszego unikalnego wzorca. Wszelkie próby kompresji od tego momentu do przodu skutkują większym zestawem danych lub osłabiają wyjątkowość. W schematach kompresji liczb magicznych zawsze występuje wada, niewielka ręka lub strata. uważaj na każdy proces, który twierdzi, że nie wykonujesz najnowszej wersji WinZip lub RAR.