Czy można używać PRNG do magicznej kompresji?

Pomysł ten przyszedł mi do głowy jako dziecko uczące się programowania i przy pierwszym spotkaniu z PRNG. Nadal nie wiem, jak realistyczne jest, ale teraz jest wymiana stosów.

Oto 14-letni schemat niesamowitego algorytmu kompresji:

Weź PRNG i zaszczep go ziarnem, saby uzyskać długą sekwencję pseudolosowych bajtów. Aby przekazać tę sekwencję innemu podmiotowi, musisz jedynie przekazać opis PRNG, odpowiednie ziarno i długość wiadomości. Dla wystarczająco długiej sekwencji opis ten byłby znacznie krótszy niż sama sekwencja.

Załóżmy teraz, że mógłbym odwrócić ten proces. Biorąc pod uwagę wystarczającą ilość czasu i zasobów obliczeniowych, mógłbym przeprowadzić wyszukiwanie z użyciem siły brutalnej i znaleźć ziarno (i PRNG, lub innymi słowy: program), który produkuje pożądaną sekwencję (powiedzmy zabawne zdjęcie kotów psotnych).

PRNG powtarzają się po wygenerowaniu wystarczająco dużej liczby bitów, ale w porównaniu do „typowych” cykli moja wiadomość jest dość krótka, więc nie wydaje się to dużym problemem.

Voila, skuteczny (jeśli rube-Goldbergowski) sposób kompresji danych.

Zakładając:

• Sekwencja, którą chcę skompresować, jest skończona i znana z góry.
• Nie brakuje mi gotówki ani czasu (tak długo, jak wymagana jest skończona kwota obu)

Chciałbym wiedzieć:

• Czy istnieje podstawowa wada w uzasadnieniu programu?
• Jaki jest standardowy sposób analizowania tego rodzaju eksperymentów myślowych?

Podsumowanie

Często zdarza się, że dobre odpowiedzi wyjaśniają nie tylko odpowiedź, ale o to, o co tak naprawdę pytałem. Dziękujemy za cierpliwość i szczegółowe odpowiedzi.

Oto moja n-ta próba podsumowania odpowiedzi:

• PRNG / kąt nasion nic nie wnosi, to nic więcej jak program, który wytwarza żądaną sekwencję jako wynik.
• Zasada szuflady: Jest o wiele więcej komunikatów o długości> k niż programów (generujących wiadomości) o długości <= k. Więc niektóre sekwencje po prostu nie mogą być wyjściem programu krótszym niż komunikat.
• Warto wspomnieć, że interpreter programu (wiadomości) jest koniecznie ustalony z góry. Jego konstrukcja określa (mały) podzbiór komunikatów, które mogą być generowane po odebraniu komunikatu o długości k.

W tym momencie pierwotny pomysł PRNG jest już martwy, ale należy rozstrzygnąć co najmniej jedno ostatnie pytanie:

• P: Czy mogę mieć szczęście i stwierdzić, że mój długi (ale skończony) komunikat jest po prostu wynikiem programu o długości <k bitów?

Ściśle mówiąc, nie jest to przypadek, ponieważ znaczenie każdej możliwej wiadomości (programu) musi być znane z góry. Albo to jest sens pewnym przesłaniem <k bitów lub nie .

Gdybym losowo wybrał losową wiadomość> = k bitów (dlaczego miałbym?), W każdym razie miałbym znikające prawdopodobieństwo, że będę w stanie wysłać ją przy użyciu mniej niż k bitów i prawie na pewno nie będę w stanie wysłać w ogóle używa mniej niż k bitów.

OTOH, jeśli wybiorę konkretny komunikat o wartości> = k bitów spośród tych, które są wynikiem programu o wartości mniejszej niż k bitów (zakładając, że taki komunikat jest), to w efekcie korzystam z bitów już przesłanych do odbiornik (projekt interpretera), który liczy się jako część przesłanej wiadomości.

Wreszcie:

• P: O co chodzi z tym biznesem złożoności entropii / kolmogorowa ?

Ostatecznie obaj mówią nam to samo, co (prostsza) zasada szuflady mówi nam o tym, ile możemy skompresować: być może wcale, może niektórzy, ale na pewno nie tak, jak nam się wydaje (chyba że oszukujemy).

Masz genialny nowy schemat kompresji, co? W porząsiu...

♫ Zagrajmy wszyscy, gra entropii ♫

$n$$n$

$01000111001$$k$$n$$n$$2^n$$0$$1$$2^n$$k$$k$$2^n$$2^n$$\log{2^n} = n$

Ups! Twój schemat kompresji wymaga komunikatów tak długo, jak kompresujesz!

$0$$1$

$1$$0$$10$$n$

$n$$\log{n}$$0$$\log{n}$

$\log{n}$$1$

$2^n$$2^n$$n$

$2^n$

$a=0000000011010$$b=111111110101000$$a\rightarrow 0$$b\rightarrow 1$$n=1$

„Haha!”, Mówisz, „ale mogę po prostu stwierdzić, że te głupie wiadomości są rzadkie! Sprawię, że te rzadkie będą duże, a pospolite małe! Wtedy wygrywam średnio!”

$n$$i$$p_i$$H = \sum_{i=1}^np_i\log(1/p_i)$$a=000111010101$$a\rightarrow0$$x\rightarrow1x$$1$$H$$H$

Wszystko, co twierdzi, że pokonuje entropię, prawdopodobnie nie zapewnia wystarczającej ilości informacji, aby jednoznacznie odzyskać skompresowaną wiadomość, lub jest po prostu błędne. Entropia jest tak potężną koncepcją, że możemy ograniczyć (a czasem nawet górną granicę) czas działania niektórych algorytmów, ponieważ jeśli działają one bardzo szybko (lub naprawdę wolno), muszą robić coś, co narusza entropię .

$2^N-1$$N$$2^N$$N$

W prawdziwym życiu często wiemy coś o sekwencji, którą kompresujemy, na przykład głos lub obraz. W przypadku kompresji bezstratnej twierdzenie Shannona o kodzie źródłowym pokazuje, że optymalna szybkość kompresji jest równa entropii źródła. W przypadku kodowania stratnego istnieją inne twierdzenia w teorii informacji (teoria szybkości zniekształcenia). Więc nawet w tym przypadku istnieje limit ilości kompresji danych.

$s$$k$$2^k$$n$$2^n$$n$$s$

(Jak zauważono w innej odpowiedzi, stanie się tak w przypadku dowolnej wybranej funkcji kompresji).

Oprócz innych już odebranych punktów, chcę tylko dodać ten link: https://www.schneier.com:443/blog/archives/2009/09/the_doghouse_cr.html

Teraz roczna produkcja energii naszego Słońca wynosi około 1,21 × 10 ^ 41 ergów. To wystarczy, aby zasilić około 2,7 × 10 ^ 56 pojedynczych zmian na naszym idealnym komputerze; wystarczająca liczba zmian stanu, aby licznik 187 bitów przejrzał wszystkie jego wartości. Gdybyśmy zbudowali kulę Dysona wokół Słońca i przechwycili całą jej energię przez 32 lata, bez żadnych strat, moglibyśmy zasilić komputer licząc do 2 ^ 192. Oczywiście nie byłoby energii do wykonania jakichkolwiek przydatnych obliczeń za pomocą tego licznika.

Tak więc tylko iteracja (bez porównania ...) w celu znalezienia prawidłowej 187-bitowej konstelacji pożądanych danych wymagałaby (w nieosiągalnych) idealnych warunkach więcej energii niż emituje słońce przez rok.

Bardzo szybki dowód, że uniwersalna sprężarka nie może istnieć. Załóżmy, że go tworzysz i kompresujesz dane wejściowe. Teraz, iteracyjnie kompresuj dane wyjściowe swojego programu. Jeśli zawsze możesz zmniejszyć rozmiar, będzie on coraz mniejszy z każdym krokiem, aż osiągniesz 1 bit.

Można argumentować, że być może dane wyjściowe algorytmu mają taką strukturę, że nie można go bardziej skompresować, ale wtedy można po prostu zastosować deterministyczne tasowanie * przed ponowną kompresją.

Przypis: Niektóre deterministyczne tasowanie faktycznie pomaga w niektórych schematach kompresji: http://pytables.github.io/usersguide/optimization.html?highlight=shuffling#shufflingoptim

Użycie PRNG do „kompresji” jest zasadniczo przydatne w jednej sytuacji: gdy konieczne jest użycie „losowej” wiązki danych i zwięzłe zapisanie, które dane zostały użyte. Większość generatorów pseudolosowych może wygenerować tylko niewielką część możliwych sekwencji, ale jeśli potrzebna jest tylko niewielka do umiarkowanej liczba sekwencji „losowych”, część możliwych sekwencji, które może wygenerować PRNG, będzie często więcej niż wystarczająca.

Jeśli sekwencja danych, które chcemy przechowywać, dzieje się przypadkowo, aby dopasować to, co wygenerowałby określony PRNG przy danym ziarnie, przechowywanie ziarna może być zwartą alternatywą dla przechowywania danych. O ile źródło danych nie jest takie, że takie dopasowania prawdopodobnie wystąpią, byłyby one jednak tak rzadkie, że poszukiwanie ich nie byłoby opłacalne.

Należy dodać do kakofonii odpowiedzi, które twierdzą, dlaczego istnieją ciągi, których nie można skompresować z powodu iniekcyjnej natury dekompresji i ograniczonego wszechświata skompresowanych ciągów, z których można wybrać reprezentowanie komunikatów: większości łańcuchów nie można skompresować, ponieważ istnieje znacznie więcej wysokich entropii, łańcuchów nieuporządkowanych niż łańcuchów niższych i strukturalnych, co powoduje, że w praktyce widzimy warunek: kompresja jest użyteczna, ponieważ wiadomości najczęściej chcą się skompresować, które najczęściej posiadają pewną porcję porządku i struktury, i dzięki temu są częścią znacznie mniejszego wszechświata obiektów o niższej entropii. Oznacza to, że wybierając odpowiednią długość wyjściową, możliwe jest wszystko możemy skompresować w mniejszym, ustrukturyzowanym wszechświecie. Określenie tutaj ustrukturyzowane, entropijne i uporządkowane jest celowo nieprecyzyjne, aby odzwierciedlić subiektywne definicje semantyki i użyteczności wiadomości, które chcielibyśmy skompresować.

I w bezpośredniej odpowiedzi na prośbę pytającego: * tak, możesz oczywiście po prostu mieć szczęście i znaleźć wynik PRNG to dokładna wiadomość, którą chcesz skompresować, po prostu tak często nie możesz tego znaleźć, ponieważ sama właściwość, która charakteryzuje PRNG, a mianowicie jego zdolność do produkowania (prawie) niekończącej się różnorodności ciągów, sprawia, że ​​jest mało prawdopodobne, aby wytworzyć twoje.

Oczywiście możesz złagodzić to mało prawdopodobne, używając PRNG, aby przejść przez „wykres domeny” przejścia między słowami, a także znacznie zwiększyć prawdopodobieństwo pojawienia się wiadomości, a także stwierdzić, że musisz teraz dodać wykres domeny do skompresowanej wiadomości długość.