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ę...
Dawno temu czytałem artykuł w gazecie, w którym pewien profesor powiedział, że w przyszłości będziemy mogli skompresować dane do zaledwie dwóch bitów (lub czegoś takiego). To oczywiście nie jest poprawne (i może być tak, że moja pamięć tego, co dokładnie stwierdził, jest nieprawidłowa). Zrozumiałe...
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...
Chciałbym wyliczyć wszystkie niekierowane wykresy wielkości , ale potrzebuję tylko jednego wystąpienia każdej klasy izomorfizmu . Innymi słowy, chcę wyliczyć wszystkie nieizomorficzne (niekierowane) wykresy na wierzchołkach. W jaki sposób mogę to zrobić?nnnnnn Dokładniej, chcę algorytmu, który...
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ą...
Jakiś facet powiedział: Każdy, kto próbuje generować losowe liczby za pomocą deterministycznych środków, oczywiście żyje w stanie grzechu. To zawsze oznacza, że nie można wygenerować prawdziwych liczb losowych za pomocą samego komputera. Powiedział też, że gdy komputery były równoważnej...
Studiowałem coś na temat złożoności Kołmogorowa , przeczytałem kilka artykułów i książek Vitanyi i Li i wykorzystałem koncepcję znormalizowanej odległości kompresji, aby zweryfikować stilometrię autorów (określić, w jaki sposób każdy autor pisze niektóre dokumenty tekstowe i grupowe według ich...
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...
Jestem ciekawy, jak można bardzo kompaktowo skompresować domenę dowolnej nazwy hosta IDN (zgodnie z definicją w RFC5890 ) i podejrzewam, że może to stać się ciekawym wyzwaniem. Host lub nazwa domeny Unicode (etykieta U) składa się z ciągu znaków Unicode, zwykle ograniczonego do jednego języka w...
Właśnie natrafiłem na następującą rzecz: umieściłem wiele identycznych kopii obrazu png w folderze, a następnie próbowałem skompresować ten folder za pomocą następujących metod: tar czf folder.tar.gz folder/ tar cf folder.tar folder/ && xz --stdout folder.tar > folder.tar.xz (ten...
Porównując parę uporządkowaną (x, y) z parą nieuporządkowaną {x, y} (zestaw), a następnie teoretycznie, różnica wynosi tylko jeden bit, ponieważ to, czy x jest pierwsze, czy y wymaga dokładnie jednego bitu do przedstawienia. Więc jeśli otrzymamy zestaw {x, y}, gdzie x, y to dwie różne 32-bitowe...
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...
library(ggplot2) compress <- function(str) { length(memCompress(paste(rep("a", str), collapse=""), type="bzip2")) / nchar(paste(rep("a", str), collapse="")) } cr <- data.frame(i = 1:10000, r = sapply(1:10000, compress)) ggplot(cr[cr$i>=5000 & cr$i<=10000,], aes(x=i, y=r)) +...
Wiemy, że π jest nieskończone i całkiem prawdopodobne, że zawiera każdy możliwy skończony ciąg cyfr ( sekwencja rozłączna ). Ostatnio widziałem prototyp πfs, który zakłada, że każdy plik, który utworzyłeś (lub ktokolwiek inny) lub utworzysz, już tam jest, więc jest to kwestia wyodrębnienia go....
Próbując zrozumieć związki między kodowaniem Huffmana, kodowaniem arytmetycznym i kodowaniem zakresu, zacząłem myśleć o niedociągnięciach kodowania Huffmana związanych z problemem częściowego upakowania bitów . To znaczy, załóżmy, że masz 240 możliwych wartości dla symbolu i potrzebujesz zakodować...
Wymóg, aby kodowanie było wolne od prefiksów, skutkuje dużymi drzewami, ponieważ drzewo musi być kompletne. Czy istnieje próg, w którym niekodowane przechowywanie danych o stałej długości byłoby bardziej wydajne niż kodowanie