Pytania otagowane jako information-theory

Pytania o teorię informacji, entropię i zawartość informacji z różnych źródeł

8
Czy kod Morse'a bez spacji jest jednoznacznie rozszyfrowywany?
Czy wszystkie ciągi kodu Morse'a są jednoznacznie rozszyfrowalne? Bez spacji ......-...-..---.-----.-..-..-.. może być, Hello Worldale być może pierwsza litera jest 5- w rzeczywistości wydaje się bardzo mało prawdopodobne, aby dowolna sekwencja kropek i myślników miała unikalne tłumaczenie. Można użyć nierówności Krafta, ale dotyczy to tylko kodów prefiksów . Kod Morse'a …
7
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ę …
6
Czy algorytmy kompresji bezstratnej zmniejszają entropię?
Według Wikipedii : Entropia Shannona mierzy informacje zawarte w wiadomości, a nie część wiadomości, która jest określona (lub przewidywalna). Przykłady tych ostatnich obejmują nadmiarowość w strukturze języka lub właściwości statystyczne związane z częstotliwościami występowania par liter lub słów, trojaczków itp. Zatem entropia jest miarą ilości informacji zawartych w wiadomości. Kodery …
2
Symulowanie prawdopodobieństwa 1 z 2 ^ N przy mniej niż N losowych bitach
Powiedz, że muszę zasymulować następujący rozkład dyskretny: P(X=k)={12N,1−12N,if k=1if k=0P(X=k)={12N,if k=11−12N,if k=0 P(X = k) = \begin{cases} \frac{1}{2^N}, & \text{if $k = 1$} \\ 1 - \frac{1}{2^N}, & \text{if $k = 0$} \end{cases} Najbardziej oczywistym sposobem jest narysowanie losowych bitów i sprawdzenie, czy wszystkie są równe (lub ). Jednak teoria …
6
Wydajna kompresja prostych danych binarnych
Mam plik zawierający uporządkowane liczby binarne od do 2 n - 1 :0002)n- 12n−12^n - 1 0000000000 0000000001 0000000010 0000000011 0000000100 ... 1111111111 7z nie skompresował tego pliku bardzo wydajnie (dla n = 20 22 MB zostało skompresowanych do 300 kB). Czy istnieją algorytmy, które potrafią rozpoznać bardzo prostą strukturę …
5
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 …
2
Co jest trudniejsze: tasowanie posortowanej talii lub sortowanie potasowanej talii?
Masz tablicę różnych elementów. Masz dostęp do komparatora (funkcja czarnej skrzynki, która bierze dwa elementy a i b i zwraca prawdziwy iff a &lt; b ) oraz naprawdę losowe źródło bitów (funkcja czarnej skrzynki nie przyjmuje argumentów i zwraca niezależnie jednakowo losowy bit). Rozważ następujące dwa zadania:nnnaaabbba&lt;ba&lt;ba < b Tablica …
4
Czy dane można skompresować do rozmiaru mniejszego niż limit kompresji danych Shannona?
Czytałem o algorytmach kompresji danych i teoretycznym limicie kompresji danych. Ostatnio spotkałem metodę kompresji zwaną „kombinatorycznym kodowaniem entropii”, główną ideą tej metody jest kodowanie pliku jako znaków przedstawionych w pliku, ich częstotliwości i indeksu permutacji tych znaków reprezentowanych przez plik. Te dokumenty mogą pomóc w wyjaśnieniu tej metody: https://arxiv.org/pdf/1703.08127 http://www-video.eecs.berkeley.edu/papers/vdai/dcc2003.pdf …
3
Różnica między „informacją” a „użyteczną informacją” w algorytmicznej teorii informacji
Według Wikipedii : Nieformalnie, z punktu widzenia algorytmicznej teorii informacji, zawartość informacyjna ciągu jest równoważna długości możliwie najkrótszej możliwej niezależnej reprezentacji tego ciągu. Jaka jest analogiczna nieformalna rygorystyczna definicja „użytecznych informacji”? Dlaczego „użyteczne informacje” nie są uważane za bardziej naturalne lub bardziej podstawowe pojęcie; naiwnie wydaje się, że czysto przypadkowy …
1
Skuteczne kodowanie łamigłówek sudoku
Określenie dowolnej dowolnej siatki 9x9 wymaga podania pozycji i wartości każdego kwadratu. Naiwne kodowanie tego może dać 81 (x, y, wartość) trypletów, wymagając 4 bitów dla każdego x, y i wartości (1-9 = 9 wartości = 4 bity) w sumie 81x4x3 = 972 bitów. Numerując każdy kwadrat, można zmniejszyć informację …
3
Shannon Entropia 0,922, 3 odrębne wartości
Biorąc pod uwagę ciąg wartości , Shannon Entropy w bazie log wynosi . Z tego, co rozumiem, w bazie Entropia Shannona zaokrąglona w górę to minimalna liczba bitów w systemie binarnym, która reprezentuje jedną z wartości.AAAAAAAABCAAAAAAAABCAAAAAAAABC2220.9220.9220.922222 Zaczerpnięte ze wstępu na tej stronie Wikipedii: https://en.wikipedia.org/wiki/Entropy_%28information_theory%29 Jak więc trzy wartości mogą być …
4
PRNG do generowania liczb z n dokładnie ustawionymi bitami
Obecnie piszę kod do generowania danych binarnych. W szczególności muszę wygenerować liczby 64-bitowe przy określonej liczbie ustawionych bitów; dokładniej, procedura powinna zająć około i zwrócić pseudolosową 64-bitową liczbę z dokładnie bitami ustawionymi na , a resztą ustawioną na 0.0 &lt; n &lt; 640&lt;n&lt;640 < n < 64nnn111 Moje obecne podejście …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.