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

38

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).

— DW
źródło

6

Ulepsz trochę swoje pytanie i nadal nie możesz skompresować każdego łańcucha (jak opisano w odpowiedziach poniżej), ale otrzymujesz Teorię Informacji Algorytmicznych ( en.wikipedia.org/wiki/Kolmogorov_complexity ). Zamień „PRNG” na „uniwersalna maszyna Turinga”, a „seed” na „taśmę wejściową zawierającą program, który generuje żądane wyjście”. Większość taśm wejściowych jest dłuższych niż generowane przez nie wyjścia, ale dla każdego wyjścia istnieje co najmniej jedno wejście, które generuje to wyjście.

— Wandering Logic

Nie, ale skompresowany rozmiar jest entropią źródła ^ _ ^

— Navin

5

Jeśli faktycznie to zaimplementujesz, znajdziesz ciekawą rzecz: aby zrekonstruować dowolne dane wejściowe, potrzebujesz seed + rng, który jest średnio tak samo duży jak oryginalne dane. Ups

— Mark

Kolejny sposób, aby zrozumieć, dlaczego to nie zadziała: chociaż PRNG może generować dowolnie długie dane wyjściowe, nie może generować arbitralnych danych wyjściowych. (Wyjście PRNG zawsze będzie jakimś stałym cyklem lub wzorem, ograniczonym rozmiarem jego stanu.)

— Pi Delport

@PietDelport, Dla każdego n istnieje PRNG, którego cykl jest znacznie większy, a postawione pytanie nie jest znane z góry. Nie jestem więc przekonany, że sam fakt, że PRNG są cykliczne, bezpośrednio rozwiązuje to pytanie.

43

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ę .

— Alexis Beingessner
źródło

13

Chłopcze, czy zabrzmię głupio, kiedy udajesz, że jestem mną. Dzięki Bogu mogę być dumny z odkrycia entropii. Żarty na bok, to dobra odpowiedź - Gdyby tylko ton nie był tak zabarwiony kpiną.

6

Nie zamierzałem kpić, po prostu bawiłem się ideą „14-latka opracowującego niesamowity algorytm kompresji”. :)

— Alexis Beingessner

3

Nie brzmiało to też dla mnie kpiąco :) To dość powszechny schemat wyjaśniania problemów w popularnej nauce (i kilku innych dziedzinach), chociaż prawdą jest, że „pytającym” jest zazwyczaj Alice lub Bob, a nie „prawdziwy” osoba: D Zobacz, jak łatwo możesz nagle zrozumieć, jak bardzo złożony jest problem! (nie wspominając o tym, że kiedy zastanawiam się nad złożoną kwestią w mojej głowie, używam tego samego procesu - wewnętrzny dialog jest niesamowicie dobry w symulacji „więcej głów wie więcej”)

— Luaan

2

@ SteveJessop, to fałszywa dychotomia i nie chodźmy tam. To dobra odpowiedź i być może jestem nadwrażliwy.

3

@chipmonkey, myślę, że wciąż obejmuje to odpowiedź Alexis na temat „gry entropii”. Być może liczba wymaganych algorytmów, które by to zrobiły, byłaby tak duża, że liczba bitów potrzebnych do określenia, który z nich został użyty, anulowałaby korzyść.

21

$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.

— Yuval Filmus
źródło

Nigdy nie patrzyłem na to w ten sposób, ale to właśnie mi się przydarzyło: w zasadzie Shannon mówi, że nawet najlepszy przypadek nie może być skompresowany arbitralnie, a Zasada Pigeonhole gwarantuje, że musi być najgorszy przypadek, którego nie można skompresować w ogóle. Czy to rozsądna charakterystyka?

— Jörg W Mittag

1

Najlepszy przypadek zawsze można skompresować, ponieważ można dołączyć ciąg znaków jako specjalny przypadek algorytmu kompresji. Ten argument działa nie tylko w najgorszym przypadku, ale także w przypadku średnim, pokazując, że średnia kompresja wynosi co najwyżej 2 bity.

— Yuval Filmus

Ach, oczywiście. if input.empty? then output_very_long_stringdałby nieskończony współczynnik kompresji jako najlepszy przypadek. W rzeczywistości istnieje nawet algorytm kompresji, który wykorzystuje to. (Zapomniałem nazwy, niestety). Jest on przeznaczony dla bardzo krótkich ciągów i ma specjalne kodowanie dla zakodowane jak podciągi http://, www., .comi tak dalej.

— Jörg W Mittag

Czy mogę pokonać ten argument, jeśli potrafię zaprojektować rodzinę PRNG w taki sposób, że sekwencje, których nie mogą wyrazić, są sekwencjami, które z góry wykluczam? (przychodzi na myśl kształtująca hałas).

3

H = \sum_{i} p_{i} l o g 1 / p_{i}

$H=\sum_ip_ilog1/p_i$

p_{i}

$p_i$

H

$H$

7

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

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

— Louis
źródło

Samo w sobie to nie dowodzi, że nie mogę zbudować PRNG, który po prostu generuje wybraną sekwencję jako jedno z możliwych wyników, wymagając przy tym znacznie mniej bitów. Jak rozumiem na podstawie innych odpowiedzi, entropia w sposób pewny wymusza dolną granicę wymaganej liczby bitów. Oznacza to, że po prostu nie mogę zrobić arbitralnie dobrze dla mojej wybranej sekwencji.

Wszystko to mówi, że jeśli stworzysz swój ulubiony PRNG, to mogę przyjść do ciebie z sekwencją, której nie produkuje, co już psuje twój pomysł. Silniejszym stwierdzeniem jest to, że istnieją sekwencje, które nie są emitowane przez żaden znacznie krótszy program. (Innymi słowy, nadal przegrywasz, nawet jeśli pozwolę ci zmienić funkcję po obejrzeniu mojej sekwencji. Tak właśnie nawiązuje Yuval z „złożonością Kołmogorowa”.)

— Louis

4

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.

— użytkownik1186178
źródło

1

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

— Davidmh
źródło

Myślę, że brakuje Ci, że do każdej skompresowanej wiadomości jest przypisane ziarno s. Wiadomość 01001011 z „s” 2348 będzie się różnić od tej samej wiadomości z „s” 3924. Chyba, że sam źle zrozumiałem algorytm foo1899.

— Azeirah

1

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.

— supercat
źródło

PRNG są wykorzystywane w ten sposób do kompaktowego reprezentowania (pseudo) losowych danych, na przykład w celu powtarzalności eksperymentów.

— Yuval Filmus

1

@YuvalFilmus: Dokładnie. Można ich również używać w niektórych sytuacjach, takich jak generowanie poziomów w grach wideo, w których niewielka część generowanych poziomów byłaby uznawana za akceptowalną, ale gdy projektant gier wideo może losowo generować poziomy, dopóki nie znajdzie takich, które mu się podobają, i zarejestruje nasiona, które wygenerowałem te. Bardzo przydatna koncepcja historycznie, gdy koduje maszynę do gier wideo ze 128 bajtami RAM, próbując dopasować program do kasety z 4096 bajtami ROM.

— supercat

To bardzo dobry przykład, pasuje do opisanego przeze mnie schematu szukania „dobrego” ziarna, ale wykorzystuje fakt, że w tym scenariuszu wiele możliwych komunikatów jest dobrych.

@ foo1899: Nawiasem mówiąc, gra „Pitfall” en.wikipedia.org/wiki/Pitfall ! zastosował wyżej wspomnianą technikę do wygenerowania 256-ekranowej mapy na kasecie z grami 4K na maszynie z 128 bajtami pamięci RAM.

— supercat

1

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ść.

— Cris
źródło