Czy losowe dane karty

Mam prawdziwe dane, których używam do symulowanej gry karcianej. Interesują mnie tylko szeregi kart, a nie ich kolory. Jest to jednak standardowa talia $52$ kart, dlatego w talii są możliwe tylko $4$ z każdej rangi. Talia jest dobrze tasowana dla każdej ręki, a następnie wysyłam całą talię do pliku. Tak więc istnieje jedynie $13$ możliwych znaków pliku wyjściowego, które są $2,3,4,5,6,7,8,9,T,J,Q,K,A$ . ( $T$= dziesięć stopni). Oczywiście możemy je spakować bitami, używając $4$ bitów na symbol, ale wtedy marnujemy $3$ z $16$ możliwych kodowań. Możemy zrobić lepiej, jeśli zgrupujemy $4$ symbole na raz, a następnie skompresujemy je, ponieważ $13^4$ = $28,561$ i to może zmieścić się raczej „ściśle” w $15$ bitach zamiast $16$ . Teoretyczny limit pakowania bitów to log ( $13$ ) / log ( $2$ ) = $3.70044$ dla danych z $13$ losowymi symbolami dla każdej możliwej karty. Nie możemy jednak mieć $52$królowie na przykład w tej talii. MUSIMY mieć tylko $4$ z każdej rangi w każdej talii, więc kodowanie entropii spada o około pół bita na symbol do około $3.2$ .

Ok, oto o czym myślę. Te dane nie są całkowicie losowe. Wiemy, że są $4$ z każdej rangi, więc w każdym bloku $52$ kart (nazywamy to potasowaną talią), więc możemy dokonać kilku założeń i optymalizacji. Jednym z nich jest to, że nie musimy kodować ostatniej karty, ponieważ będziemy wiedzieć, co to powinna być. Kolejne oszczędności byłyby, gdybyśmy skończyli na jednej pozycji; na przykład, jeśli ostatnie $3$ karty w talii to $777$ , nie musielibyśmy ich kodować, ponieważ dekoder zliczałby karty do tego momentu i widziałby, że wszystkie pozostałe szeregi zostały zapełnione, i przyjmuje $3$ ” brakujące karty to $7$ s.

Tak więc moje pytanie do tej witryny brzmi: jakie inne optymalizacje są możliwe, aby uzyskać jeszcze mniejszy plik wyjściowy dla tego rodzaju danych, a jeśli ich użyjemy, czy kiedykolwiek uda nam się pokonać teoretyczną (prostą) entropię $3.70044$ bitów wynoszącą 3.70044 bitów na symbol lub zbliżyć się nawet do ostatecznego limitu entropii średnio około $3.2$ bitu na symbol? Jeśli tak to jak?

Kiedy używam programu typu ZIP (na przykład WinZip), widzę tylko kompresję $2:1$ , która mówi mi, że robi „leniwy” pakiet bitów do $4$ bitów. Jeśli „wstępnie skompresuję” dane przy użyciu własnego pakietu bitów, wydaje mi się, że to mi się bardziej podoba, ponieważ wtedy, gdy uruchamiam to za pomocą programu zip, uzyskuję nieco ponad $2:1$ kompresji. Chodzi mi o to, dlaczego samemu nie wykonać całej kompresji (ponieważ mam większą wiedzę na temat danych niż program Zip). Zastanawiam się, czy uda mi się pokonać „limit” entropii log ( $13$ ) / log ( $2$ ) = $3.70044$. Podejrzewam, że potrafię z kilkoma „sztuczkami”, o których wspomniałem, i kilkoma innymi, których prawdopodobnie się dowiem. Plik wyjściowy oczywiście nie musi być „czytelny dla człowieka”. Tak długo, jak kodowanie jest bezstratne, jest ważne.

Oto link do $3$ milionów tasowanych talii czytelnych dla ludzi ( $1$ na linię). Każdy może „ćwiczyć” na małym podzbiorze tych linii, a następnie pozwolić mu zgrać cały plik. Będę aktualizować mój najlepszy (najmniejszy) rozmiar pliku na podstawie tych danych.

https://drive.google.com/file/d/0BweDAVsuCEM1amhsNmFITnEwd2s/view

Nawiasem mówiąc, jeśli jesteś zainteresowany typem gry karcianej, do którego są wykorzystywane te dane, oto link do mojego aktywnego pytania (z nagrodą za punktów). Powiedziano mi, że jest to trudny problem do rozwiązania (dokładnie), ponieważ wymagałby ogromnej ilości miejsca do przechowywania danych. Kilka symulacji zgadza się jednak z przybliżonymi prawdopodobieństwami. Nie podano (jeszcze) rozwiązań czysto matematycznych. To chyba zbyt trudne.$300$

/math/1882705/probability-2-player-card-game-with-multiple-patterns-to-win-who-has-the-arcza

Mam dobry algorytm, który pokazuje bitów do zakodowania pierwszej talii w moich przykładowych danych. Te dane zostały wygenerowane losowo przy użyciu algorytmu losowania Fisher-Yates. To prawdziwe losowe dane, więc mój nowo utworzony algorytm działa BARDZO dobrze, co mnie cieszy.$168$

Jeśli chodzi o „wyzwanie” kompresji, obecnie mam około 160 bitów na talię. Myślę, że mogę zejść do może 158. Tak, próbowałem i mam 158,43 bitów na talię. Myślę, że zbliżam się do limitu mojego algorytmu, więc udało mi się spaść poniżej 166 bitów na talię, ale nie udało mi się uzyskać 156 bitów, czyli 3 bitów na kartę, ale było to zabawne ćwiczenie. Być może w przyszłości wymyślę coś, co zmniejszy każdą talię średnio o 2,43 bity lub więcej.

Kolejna rzecz do rozważenia: jeśli zależy ci tylko na skompresowaniu pełnego zestawu kilku milionów decków, a także nie zależy od tego, w jakiej kolejności się znajdują, możesz zyskać dodatkową elastyczność kodowania, odrzucając informacje o uporządkowaniu zestawu decków . Tak byłoby na przykład, jeśli trzeba załadować zestaw, aby wyliczyć wszystkie talie i przetworzyć je, ale nie przejmuj się kolejnością, w jakiej są przetwarzane.

Zaczynasz od zakodowania każdej talii osobno, jak opisano w innych odpowiedziach. Następnie posortuj te zakodowane wartości. Przechowuj serię różnic między posortowanymi zakodowanymi wartościami (gdzie pierwsza różnica zaczyna się od zakodowanej talii „0”). Biorąc pod uwagę dużą liczbę talii, różnice będą zwykle mniejsze niż pełny zakres kodowania, więc możesz użyć jakiejś formy kodowania varint, aby obsłużyć sporadyczne duże różnice, a jednocześnie skutecznie przechowywać mniejsze różnice. Odpowiedni schemat varint będzie zależał od tego, ile talii masz w zestawie (określając w ten sposób średni rozmiar różnicy).

Niestety nie znam matematyki, jak bardzo pomogłoby to w kompresji, ale pomyślałem, że warto rozważyć ten pomysł.

Oto kompletny algorytm, który osiąga teoretyczny limit.

Prolog: Kodowanie sekwencji całkowitych

Sekwencja 13 liczb całkowitych "liczba całkowita z górną granicą , liczba całkowita z górną granicą b - 1 ," liczba całkowita z górną granicą c - 1 , liczba całkowita z górną granicą d - 1 , ... liczba całkowita z górną granicą m - 1 " zawsze można kodować z doskonałą wydajnością.$a-1$$b-1$$c-1$$d-1$$m-1$

1. Weź pierwszą liczbę całkowitą, pomnóż ją przez , dodaj drugą, pomnóż wynik przez c , dodaj trzecią, pomnóż wynik przez d ,… pomnóż wynik przez m , dodaj trzynastą - a to da unikalną liczbę między 0 oraz a b c d e f g h i j k l m - 1 .$b$$c$$d$$m$$0$$abcdefghijklm-1$
2. Zapisz tę liczbę dwójkowo.

Odwrotna sytuacja jest również łatwa. Podziel przez a reszta to trzynasta liczba całkowita. Podziel wynik przez l, a reszta to dwunasta liczba całkowita. Kontynuuj, aż podzielisz się przez b : reszta to druga liczba całkowita, a iloraz to pierwsza liczba całkowita.$m$$l$$b$

Aby więc zakodować karty w najlepszy możliwy sposób, wszystko, co musimy zrobić, to znaleźć idealną zgodność między 13-liczbowymi sekwencjami (z podanymi górnymi limitami) a układem tasowanych kart.

Oto jak to zrobić.

Zgodność między tasowaniami a ciągami liczb całkowitych

Zacznij od sekwencji 0 kart na stole przed tobą.

Krok 1

Weź cztery 2 z paczki i połóż je na stole.

Jakie masz możliwości? Kartę lub karty można umieścić na początku sekwencji już na stole lub po dowolnej z kart w tej sekwencji. W takim przypadku oznacza to, że istnieje możliwe miejsce do umieszczenia kart.$1+0=1$

Łączna liczba sposobów umieszczenia 4 kart w 1 miejscu to . Zakoduj każdy z tych sposobów jako liczbę od 0 do 1 - 1 . Jest 1 taki numer.$1$$0$$1-1$

Dostałem 1 biorąc pod uwagę sposoby pisania 0 jako sumy 5 liczb całkowitych: jest to .$\frac{4\times 3\times 2 \times 1}{4!}$

Krok 2

Weź cztery trójki z paczki i połóż je na stole.

Jakie masz możliwości? Kartę lub karty można umieścić na początku sekwencji już na stole lub po dowolnej z kart w tej sekwencji. W takim przypadku oznacza to, że istnieje możliwych miejsc do umieszczenia kart.$1+4=5$

Łączna liczba sposobów umieszczenia 4 kart w 5 miejscach wynosi . Kodować każde z tych sposobów, jak liczbę między 0 i 70 - 1 . Istnieje 70 takich liczb.$70$$0$$70-1$

Dostałem 70, biorąc pod uwagę sposoby pisania 4 jako sumy 5 liczb całkowitych: jest to .$\frac{8\times 7\times 6 \times 5}{4!}$

Krok 3

Weź cztery 4 z paczki i połóż je na stole.

Jakie masz możliwości? Kartę lub karty można umieścić na początku sekwencji już na stole lub po dowolnej z kart w tej sekwencji. W takim przypadku oznacza to, że istnieje możliwych miejsc do umieszczenia kart.$1+8=9$

Łączna liczba sposobów umieszczenia 4 kart w 9 miejscach to . Zakodować każdy z tych sposobów jako liczbę między 0 a 495 - 1 . Istnieje 495 takich liczb.$495$$0$$495-1$

Otrzymałem 495, biorąc pod uwagę sposoby pisania 8 jako sumy 5 liczb całkowitych: jest to .$\frac{12\times 11\times 10 \times 9}{4!}$

I tak dalej, aż ...

Krok 13

Weź cztery asy z paczki i połóż je na stole.

Jakie masz możliwości? Kartę lub karty można umieścić na początku sekwencji już na stole lub po dowolnej z kart w tej sekwencji. W takim przypadku oznacza to, że istnieje możliwych miejsc do umieszczenia kart.$1+48=49$

Łączna liczba sposobów umieszczenia 4 kart w 49 miejscach to . Kodować każdej z tych sposobów jako liczbę między 0 a 270725 - 1 . Istnieje 270725 takich liczb.$270725$$0$$270725-1$

Otrzymałem 270725, biorąc pod uwagę sposoby pisania 48 jako sumy 5 liczb całkowitych: jest to .$\frac{52\times 51\times 50 \times 49}{4!}$

Ta procedura daje zgodność 1-do-1 pomiędzy (a) tasowaniami kart, w których nie zależy ci na kolorze, i (b) sekwencjami liczb całkowitych, gdzie pierwsza jest między a 1 - 1 , druga między 0 a 70 - 1 , trzeci jest między 0 i 495 - 1 , i tak dalej aż do trzynastego, która znajduje się pomiędzy 0 i 270725 - 1 .$0$$1-1$$0$$70-1$$0$$495-1$$0$$270725-1$

Odnosząc się do „Kodowania sekwencji liczb całkowitych”, widać, że taka sekwencja liczb całkowitych jest w 1-1 korespondująca z liczbami od do ( 1 × 70 × 495 × … × 270725 ) - 1 . Jeśli spojrzysz na „iloczyn podzielony przez silnię” wyrażenia każdej z liczb całkowitych ( jak opisano kursywą na końcu każdego kroku ), zobaczysz, że oznacza to liczby od 0 do 52 $0$$(1\times 70\times 495\times … \times 270725)-1$$0$co pokazała moja poprzednia odpowiedź była najlepsza z możliwych.

Mamy więc idealną metodę kompresji twoich przetasowanych kart.

Algorytm

Oblicz z góry listę wszystkich sposobów zapisu 0 jako sumy 5 liczb całkowitych, zapisu 4 jako sumy 5 liczb całkowitych, zapisu 8 jako sumy 5 liczb całkowitych,… zapisu 48 jako sumy 5 liczb całkowitych. Najdłuższa lista zawiera 270725 elementów, więc nie jest szczególnie duża. (Wstępne obliczenia nie są absolutnie konieczne, ponieważ można łatwo zsyntetyzować każdą listę w razie potrzeby: próbowanie z Microsoft QuickBasic, nawet przeglądanie listy 270725 elementów było szybsze, niż mogło to zobaczyć)

Aby przejść z tasowania do sekwencji liczb całkowitych:

Te 2 nic nie wnoszą, więc zignorujmy je. Zapisz liczbę od 0 do 1-1.

3: Ile jest 2 przed pierwszymi 3? Ile przed drugim? trzeci? czwarty? po czwartym? Odpowiedź to 5 liczb całkowitych, które oczywiście sumują się do 4. Więc spójrz na tę sekwencję 5 liczb całkowitych na liście „zapisywanie 4 jako suma 5 liczb całkowitych” i zanotuj jej pozycję na tej liście. Będzie to liczba od 0 do 70-1. Zapisz to.

4: ile jest 2 lub 3 przed pierwszymi 4? Ile przed drugim? trzeci? czwarty? po czwartym? Odpowiedź to 5 liczb całkowitych, które oczywiście sumują się do 8. Więc spójrz na tę sekwencję 5 liczb całkowitych w górę na liście „zapisywanie 8 jako suma 5 liczb całkowitych” i zanotuj jej pozycję na tej liście. Będzie to liczba od 0 do 495-1. Zapisz to.

I tak dalej, aż ...

Asy: ile kart innych niż as jest przed pierwszym asem? Ile przed drugim? trzeci? czwarty? po czwartym? Odpowiedź to 5 liczb całkowitych, które oczywiście sumują się do 48. Spójrz więc na tę sekwencję 5 liczb całkowitych w liście „zapisywanie 48 jako suma 5 liczb całkowitych” i zanotuj jej pozycję na tej liście. Będzie to liczba od 0 do 270725-1. Zapisz to.

Zapisałeś teraz 13 liczb całkowitych. Zakoduj je (jak opisano wcześniej) w jednym numerze od do 52 $0$ . Zapisz ten numer binarnie. Zajmie to nieco mniej niż 166 bitów.$\frac{52!}{(4!)^{13}}$

Jest to najlepsza możliwa kompresja, ponieważ osiąga limit teoretyczny.

Dekompresja jest prosta: przejdź od dużej liczby do sekwencji 13 liczb całkowitych, a następnie użyj ich do zbudowania sekwencji kart, jak już opisano.

Zamiast próbować zakodować każdą kartę osobno w 3 lub 4 bity, sugeruję zakodowanie stanu całej talii w 166 bitach. Jak wyjaśnia Martin Kochański , istnieje mniej niż możliwych układów kart ignorujących kolory, co oznacza, że ​​stan całej talii można zapisać w 166 bitach.$2^{166}$

Jak efektywnie wykonywać tę kompresję i dekompresję w sposób algorytmiczny? Sugeruję użycie porządku leksykograficznego i wyszukiwania binarnego. Umożliwi to wydajną kompresję i dekompresję (zarówno w przestrzeni, jak i czasie), bez konieczności posiadania dużej tabeli odnośników lub innych nierealistycznych założeń.

Bardziej szczegółowo: uporządkujmy talie za pomocą porządku leksykograficznego na nieskompresowanej reprezentacji talii, tj. Talię reprezentujemy w formie nieskompresowanej jako ciąg znaków, taki jak 22223333444455556666777788889999TTTTJJJJQQQQKKKKAAAA; możesz je zamówić zgodnie z porządkiem leksykograficznym. Teraz załóżmy, że masz procedurę, która dała talię , liczy liczbę talii, które ją poprzedzają (w kolejności leksykograficznej). Następnie możesz użyć tej procedury do kompresji talii: biorąc pod uwagę talię D , kompresujesz do 166-bitowej liczby poprzez zliczenie liczby talii, które są przed nią, a następnie wyprowadzenie tej liczby. Ta liczba jest skompresowaną reprezentacją talii.$D$$D$

Aby zdekompresować, użyj wyszukiwania binarnego. Biorąc pod uwagę liczbę , chcesz znaleźć n- tą talię w porządku leksykograficznym wszystkich talii. Możesz to zrobić, stosując procedurę wzdłuż wyszukiwania binarnego: wybierz talię D 0 , policz liczbę talii przed D 0 i porównaj ją z n . To powie ci, czy dostosować D $n$$n$$D_0$$D_0$$n$$D_0$przyjść wcześniej lub później. Sugeruję, aby spróbować iteracyjnie uzyskać odpowiedni symbol: jeśli chcesz odzyskać ciąg taki jak 22223333444455556666777788889999TTTTJJJJQQQQKKKKAAAA, najpierw wyszukaj, aby użyć tego jako pierwszego symbolu w ciągu (wypróbuj wszystkie 12 możliwości lub użyj wyszukiwania binarnego ponad 12 możliwości ), a następnie po znalezieniu właściwej wartości dla pierwszego symbolu wyszukaj, aby znaleźć drugi symbol itd.

Pozostaje wymyślić skutecznego postępowania policzyć liczbę pokładów, które przychodzą przed leksykograficznie . To wygląda na proste, ale żmudne ćwiczenie kombinatoryczne. W szczególności sugeruję zbudowanie podprogramu dla następującego problemu: biorąc pod uwagę prefiks (jak 222234), policz liczbę talii rozpoczynających się od tego prefiksu. Odpowiedź na ten problem wygląda na dość łatwe ćwiczenie w dwumianowych współczynnikach i silnych. Następnie można wywołać podprogram niewielką liczbę razy, aby policzyć liczbę pokładów, które przychodzą przed D .$D$$D$

Liczba możliwych układów kart ignorujących kolory wynosi którego podstawa logarytmu 2 wynosi 165,976 lub 3,1919 bitów na kartę, co jest lepsze niż podany limit.

Żadne ustalone kodowanie „bitów na kartę” nie będzie miało sensu, ponieważ, jak zauważasz, ostatnia karta może być zawsze zakodowana w bitach, aw wielu przypadkach może być również kilka ostatnich kart. Oznacza to, że dla sporej drogi do „ogona” paczki liczba bitów potrzebnych dla każdej karty będzie znacznie mniejsza niż myślisz.$0$

Zdecydowanie najlepszym sposobem na kompresowanie danych byłoby znalezienie 59 bitów innych danych, które i tak chcesz spakować danymi karty (właściwie 59,6 bitów) i zapisanie tych 59 bitów jako 13-cyfrowej liczby modulo 24 (= ), Przypisz kolor do każdej karty (jedna cyfra wybiera między 4 ! Sposobami przypisywania kolorów asom, inna robi to samo dla królów i tak dalej). Następnie masz pakiet 52 całkowicie odrębnych kart. 52 ! możliwości można bardzo łatwo zakodować w 225,58 bitach.$4!$$4!$$52!$

Ale robienie tego bez korzystania z okazji do kodowania tych dodatkowych bitów jest również w pewnym stopniu możliwe i pomyślę o tym, ponieważ jestem pewien, że wszyscy inni są. Dziękujemy za naprawdę interesujący problem!

To długo rozwiązany problem.

Kiedy rozdajesz talię 52 kart, każda rozdana karta ma jedną z maksymalnie 13 rang ze znanymi prawdopodobieństwami. Prawdopodobieństwa zmieniają się z każdą rozdaną kartą. Jest to obsługiwane optymalnie przy użyciu starożytnej techniki zwanej adaptacyjnym kodowaniem arytmetycznym, co stanowi ulepszenie kodowania Huffmana. Zwykle jest to używane do znanych, niezmiennych prawdopodobieństw, ale równie dobrze może być wykorzystane do zmiany prawdopodobieństw. Przeczytaj artykuł w Wikipedii na temat kodowania arytmetycznego:

https://en.wikipedia.org/wiki/Arithmetic_coding

Zarówno DW, jak i Martin Kochański opisali już algorytmy konstruowania bijectionu między układami a liczbami całkowitymi w zakresie , ale wydaje się, że żadne z nich nie zredukowało problemu do najprostszej postaci. (Notatka 1)$[0, {52!\over(4!)^{13}})$

Załóżmy, że mamy (częściowe) talię opisaną przez uporządkowanej listy , gdzie i jest liczba kart typu í . W PO początkowa talia jest opisana listą 13 elementów, z których każdy ma wartość 4. Liczba wyraźnych przetasowań takiej talii wynosi$a$$a_i$$i$

co jest prostym uogólnieniem współczynników dwumianowych, i rzeczywiście można to udowodnić, po prostu układając obiekty po jednym typie na raz, jak sugeruje Martin Kochański. (Patrz poniżej, uwaga 2)

Teraz, dla każdego takiego (częściowego) pokładu, możemy wybrać losowego jednej karty na raz, przy użyciu dowolnego , dla których I > 0 . Liczba unikatowych losowań rozpoczynających się od i wynosi$i$$a_i>0$$i$

i według powyższej formuły mamy

Następnie możemy ponownie przechodzić (lub iterować) przez talię do momentu zakończenia losowania, obserwując, że liczba losowań odpowiadająca przedrostkowi leksykograficznie mniejsza niż przedrostek do wynosi$i$

Napisałem to w Pythonie, aby zilustrować algorytm; Python jest rozsądnym pseudokodem, jak każdy inny. Zauważ, że większość arytmetyki wymaga rozszerzonej precyzji; wartości (reprezentujące porządek losowy) i n (całkowita liczba możliwych losowań dla pozostałej częściowej talii) są 166-bitowymi bignami. Aby przetłumaczyć kod na inny język, konieczne będzie użycie biblioteki bignum.$k$$n$

Ponadto używam po prostu listy liczb całkowitych zamiast nazw kart i - w przeciwieństwie do powyższych obliczeń - liczby całkowite są oparte na 0.

Aby zakodować losowanie, przechodzimy przez losowanie, gromadząc w każdym punkcie liczbę losowań, które zaczynają się od mniejszej karty przy użyciu powyższej formuły:

from math import factorial
T = factorial(52) // factorial(4) ** 13

def encode(vec):
    a = [4] * 13
    cards = sum(a)
    n = T
    k = 0
    for idx in vec:
        k += sum(a[:idx]) * n // cards
        n = a[idx] * n // cards
        a[idx] -= 1
        cards -= 1
    return k

Dekodowanie liczby 166-bitowej to prosta odwrotność. Na każdym kroku mamy opis częściowej talii i porządek; musimy pominąć przetasowania zaczynając od mniejszych kart niż ta, która odpowiada porządkowi, a następnie obliczamy wyjście wybranej karty, usuwamy ją z pozostałej talii i dostosowujemy liczbę możliwych przetasowań z wybranym prefiksem:

def decode(k):
    vec = []
    a = [4] * 13
    cards = sum(a)
    n = T
    while cards > 0:
        i = cards * k // n
        accum = 0
        for idx in range(len(a)):
            if i < accum + a[idx]:
                k -= accum * n // cards
                n = a[idx] * n // cards
                a[idx] -= 1
                vec.append(idx)
                break
            accum += a[idx]
        cards -= 1
    return vec

Nie próbowałem optymalizować powyższego kodu. Uruchomiłem go dla całego pliku 3mil.TXT, sprawdzając, czy to encode(decode(line))spowodowało oryginalne kodowanie; zajęło to niespełna 300 sekund. (Siedem linii można zobaczyć w teście on-line na ideone .) Przepisywanie w języku niższego poziomu i optymalizacja podziału (co jest możliwe) prawdopodobnie skróciłoby ten czas do czegoś możliwego do zarządzania.

Ponieważ zakodowana wartość jest po prostu liczbą całkowitą, może być wyprowadzana w 166 bitach. Usunięcie wiodących zer nie ma żadnej wartości, ponieważ nie byłoby sposobu, aby dowiedzieć się, gdzie zakończyło się kodowanie, więc tak naprawdę jest to kodowanie 166-bitowe.

Warto jednak zauważyć, że w praktycznym zastosowaniu prawdopodobnie nigdy nie jest konieczne kodowanie losowe; losowe odtwarzanie losowe można wygenerować, generując losową liczbę 166-bitową i dekodując ją. I tak naprawdę nie jest konieczne, aby wszystkie 166 bitów były losowe; możliwe byłoby na przykład rozpoczęcie od 32-bitowej losowej liczby całkowitej, a następnie wypełnienie 166 bitów przy użyciu dowolnego standardowego RNG zaszczepionego liczbą 32-bitową. Jeśli więc celem jest po prostu możliwość odtworzenia dużej liczby losowych losowych zmian, możesz mniej lub bardziej dowolnie zmniejszyć zapotrzebowanie na pamięć dla poszczególnych transakcji.

$N$$\log_2 N$

$N$ $k$

1. $p$$\log_2 N$

2. $2^p$$k$$p$$k-p$$N*(k-p)$

3. $2^p$$0$$0$$1$$2^p+N$$2^p$ $1$$N$ $0$

$0$$1$

$N*(k-p) + N + 2^p$$N*(k-p) + N + N$$N*(k-p+2)$$k-p+2$

Notatki

1. $52!\over(4!)^{13}$$92024242230271040357108320801872044844750000000000$$\log_2 {52!\over(4!)^{13}}$$165.9765$$166$
2. $S_k$$\sum\limits_{i=k}^n a_i$$a_1$$1$$S_1 \choose a_1$$2$$S_2 \choose a_2$${S_i \choose a_i}={S_i! \over a_i!(S_i - a_i)!}={S_i!\over {a_i!S_{i+1}!}}$

co upraszcza powyższą formułę.

Jako alternatywne rozwiązanie tego problemu, mój algorytm używa złożonych ułamkowych bitów (niecałkowitych) na kartę dla grup kart w talii w oparciu o liczbę pozostałych niewypełnionych szeregów. Jest to dość elegancki algorytm. Sprawdziłem ręcznie mój algorytm kodowania i wygląda dobrze. Koder wyprowadza coś, co wydaje się być poprawnym ciągiem bitów (dla uproszczenia w formie bajtów).

$3$$7$$54A236J$$7$$13$$13^7$$26$$13^7$$62,748,517$$2^{26}$$67,108,864$$2$$4$$13$$13^4$$28,561$$2^{15}$$32,768$$15/4 = 3.75$$26/7 = 3.714$$26/7$

$54A236J$$23456789TJQKA$$5$$4$$7$$13$$10$$15,565,975$$26$$00111011011000010010010111$

$26$$15,565,975$$13$$54A236J$$7$

$13, 12, 11 ..., 2, 1)$$13,12,11...$$2$$13$$12$$12$$2$$12^5$$248,832$$2^{18}$$262,144$$18/5$$3.6$$13$$26/7$$3.714$$5555$$3333$

Oto moja pełna lista kosztów (liczba bitów na kartę) dla wszystkich możliwych # rang do wyświetlenia:

$13~~~~26/7 = 3.714 = 3~~5/7$
$12~~~~18/5 = 3.600 = 3~~3/5$
$11~~~~~~7/2 = 3.500 = 3~~1/2$
$10~~~~10/3 = 3.333 = 3~~1/3$
$~~9~~~~16/5 = 3.200 = 3~~1/5$
$~~8~~~~~~3/1 = 3.000 = 3$
$~~7~~~~17/6 = 2.833 = 2~~5/6$
$~~6~~~~13/5 = 2.600 = 2~~3/5$
$~~5~~~~~~7/3 = 2.333 = 2~~1/3$
$~~4~~~~~~2/1 = 2.000 = 2$
$~~3~~~~~~5/3 = 1.667 = 1~~2/3$
$~~2~~~~~~1/1 = 1.000 = 1$
$~~1~~~~~~0/1..4 = 0.0 = 0$

$7$$5,6,7,7,7,7,K$$K$$13$$12$$7$$13$$K$$2$$1,2,3...$$3$$13$$1$$7$$20$

$168$$13, 12, 11$

$1$$0$$7777$$48$$7$$4$$7$s. Jeśli talia kończy się na parze (np. 77), potrójnej / secie (np. 777) lub quadzie (np. 7777), uzyskujemy dodatkowe oszczędności dla tej talii przy użyciu mojego algorytmu.

$32$$2^{26}$$13$$16$$32$$32$

W pierwszej talii w pliku danych kodowanie kart wygląda następująco (schemat pojawi się później). Format to (tryb grupowania, bitów, kodowania rang):

$7,26,13$$7$$26$$13$
$7,26,13$
$7,26,13$
$5,18,12$
$5,18,12$
$3,10,10$
$3,~~9,~~8$
$6,17,~~7$
$5,13,~~6$
$3,~~5,~~3$
$1,~~0,~~1$

$52$$168$$3.23$

$18$$1/3$$3.2$$3.2$$54545454722772277...$$3$$22223333444455556666777788889999TTTTJJJJQQQQKKKKAAAA$$4$$0$

$1$$10$$3,7$$K$$8$$10$$1$karta pozostała. Jest to ważne, ponieważ sprawia, że ​​proces kodowania jest bardziej wydajny, gdy dekoder może przyjmować prawidłowe założenia bez konieczności przesyłania przez koder dodatkowych komunikatów.

$3$$13$$12$$11$$10$

54 A 236 J 87726 Q 3 3969 A A A Q J K 7 T 9292 Q 36 K $~~~~~~~~~26~~~~~~~~~~~~~26~~~~~~~~~~~~~26~~~~~~~~~~~~18~~~~~~~~~18~~~~~~~10~~~~~~9~~~~~~~~~~17~~~~~~~~~~~13~~~~~~~~5~~~~~0$
$~~~~54A236J~~87726Q3~~3969AAA~~QJK7T~~9292Q~~36K~~J57~~~T8TKJ4~~48Q8T~~55K~~4$
$13~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~12~~~~~~~~~~~~~~~~~~~~xy~~~~~98~~~~~~~~~7~~~~~~~~~~~~~~6~~~~~~~~543~~~~~2~1~~0$

$2$$166$$175$$168$bitów Zauważ, że mamy tylko jeden 4 na końcu talii, ale jeśli zamiast tego mamy tam wszystkie cztery 4, to jest lepszy przypadek i potrzebowalibyśmy tylko 161 bitów do zakodowania tej talii, przypadek, w którym opakowanie faktycznie pokonuje entropia prostego kodu binarnego jego pozycji porządkowej.

Teraz mam zaimplementowany kod do obliczania wymagań bitowych i pokazuje mi on średnio około 175 bitów na talię z niskim 155 i wysokim 183 dla pliku testowego z 3 milionami talii. Więc mój algorytm wydaje się używać 9 dodatkowych bitów na talię w porównaniu z prostym kodem binarnym metody pozycji porządkowej. Nieźle jak na tylko 5,5% dodatkowej przestrzeni dyskowej. 176 bitów to dokładnie 22 bajty, więc jest to nieco więcej niż 52 bajty na talię. Najlepsza talia (nie pokazała się w 3 milionach plików testowych) paczki do 136 bitów, a najgorsza talia (pokazała się w pliku testowym 8206 razy), to 183 bity. Analiza pokazuje, że najgorszym przypadkiem jest sytuacja, w której pierwszy kwadrant nie zbliża się do karty 40 (lub w jej pobliżu). Następnie, gdy tryb kodowania chce szybko spaść, blokujemy wypełnianie bloków (nawet 7 kart) wyższy tryb kodowania bitów. Można by pomyśleć, że nie otrzymanie żadnych quadów, dopóki karta 40 nie byłaby rzadka przy użyciu dobrze potasowanej talii, ale mój program mówi mi, że zdarzyło się to 321 razy w pliku testowym 3 milionów talii, tak że jest to około 1 na 9346 talii. Tak często się spodziewałam. Mógłbym sprawdzić ten przypadek i obsłużyć go mniejszą ilością bitów, ale jest to tak rzadkie, że nie wpłynęłoby to wystarczająco na średnią liczbę bitów.

Również tutaj jest coś bardzo interesującego. Jeśli posortuję talię na podstawie surowych danych talii, długość prefiksów, które powtarzają znaczącą liczbę razy, wynosi tylko około 6 (na przykład 222244). Jednak w przypadku spakowanych danych ta długość wzrasta do około 16. Oznacza to, że jeśli posortuję spakowane dane, powinienem być w stanie uzyskać znaczne oszczędności, po prostu wskazując dekoderowi 16-bitowy prefiks, a następnie po prostu wyprowadzając resztę talii (minus powtarzający się prefiks), które mają ten sam prefiks, a następnie przejdź do następnego prefiksu i powtórz. Zakładając, że w ten sposób zaoszczędzę nawet 10 bitów na talię, powinienem pokonać 166 bitów na talię. Dzięki technice wyliczania podanej przez innych nie jestem pewien, czy prefiks będzie tak długi, jak w przypadku mojego algorytmu. Również szybkość pakowania i rozpakowywania przy użyciu mojego algorytmu jest zaskakująco dobra.

Jeśli chodzi o drugi poziom kompresji, w którym sortuję wyjściowe ciągi bitów mojego algorytmu, a następnie używam kodowania „różnicowego”: bardzo prostą metodą byłoby zakodowanie 61 278 unikalnych 16-bitowych prefiksów, które pojawiają się co najmniej dwa razy w danych wyjściowych (i maksimum z 89 razy zgłoszonych) po prostu jako wiodący bit 0 na wyjściu, aby wskazać dekompresorowi drugiego poziomu, że kodujemy prefiks (taki jak 0000111100001111), a następnie wszystkie upakowane talie z tym samym prefiksem będą poprzedzone 1 bitem wiodącym do wskazuje nieprzedrostkową część zapakowanego pokładu. Średnia liczba spakowanych talii z tym samym prefiksem wynosi około 49 dla każdego prefiksu, nie licząc kilku unikalnych (tylko 1 talia ma ten konkretny prefiks). Wygląda na to, że mogę zaoszczędzić około 15 bitów na talię, korzystając z tej prostej strategii (zapamiętywanie wspólnych prefiksów raz).

Po 2. poziomie kompresji przy użyciu kodowania różnicowego (przedrostka) posortowanego wyjścia łańcucha bitów pierwszego enkodera, teraz otrzymuję około 160 bitów na talię. Używam prefiksu o długości 18 i po prostu przechowuję go w nienaruszonym stanie. Ponieważ pojawiają się prawie wszystkie (245013 z 262144 = 93,5%) z tych możliwych 18-bitowych prefiksów, byłoby jeszcze lepiej zakodować prefiksy. Być może mogę użyć 2 bitów do zakodowania, jaki typ danych mam. 00 = zapisany prefiks 18 o regularnej długości, 01 = „1 prefiks w górę” (taki sam jak poprzedni prefiks z wyjątkiem 1 dodanego), 11 = kodowanie proste z pakowania pierwszego poziomu (średnio około 175 bitów). 10 = przyszłe rozszerzenie, gdy myślę o czymś innym do zakodowania, co pozwoli zaoszczędzić bity.

Czy ktoś jeszcze pobił 160 bitów na talię? Wydaje mi się, że mogę trochę obniżyć moje, eksperymentując i używając 2-bitowych deskryptorów, o których wspomniałem powyżej. Być może osiągnie dno przy 158ish. Moim celem jest uzyskanie go do 156 bitów (lub lepiej), ponieważ byłoby to 3 bity na kartę lub mniej. Bardzo imponujące. Dużo eksperymentów, aby sprowadzić go do tego poziomu, ponieważ jeśli zmienię kodowanie pierwszego poziomu, muszę ponownie przetestować, które jest najlepszym kodowaniem drugiego poziomu i jest wiele kombinacji do wypróbowania. Niektóre zmiany, które wprowadzam, mogą być dobre dla innych podobnych danych losowych, ale niektóre mogą być tendencyjne w stosunku do tego zestawu danych. Nie jestem do końca pewien, ale jeśli przyjdzie mi ochota, mogę wypróbować kolejny 3 milionowy zestaw danych pokładowych, aby zobaczyć, co się stanie, jeśli otrzymam podobne wyniki.

$10^{50}$

Czy ktoś ma jakieś pomysły, jak ulepszyć mój algorytm, jak inne przypadki, które powinienem zakodować, co zmniejszyłoby ilość pamięci dla każdej talii? Ktoś?

Jeszcze 2 rzeczy: 1) Jestem nieco rozczarowany, że więcej osób nie głosowało za moim rozwiązaniem, które choć nie jest optymalne w przestrzeni, jest przyzwoite i dość łatwe do wdrożenia (moje działa dobrze). 2) Przeprowadziłem analizę mojego pliku danych z 3 milionami talii i zauważyłem, że najczęściej występującą kartą, w której wypełnia się 1. stopień (np. 4444), jest karta 26. Zdarza się to około 6,711% czasu (dla 201322 z 3 milionów talii ). Miałem nadzieję, że wykorzystam te informacje do skompresowania większej ilości danych, takich jak start w trybie kodowania 12 symboli, ponieważ wiemy, że średnio nie zobaczymy każdej rangi aż do około połowy pokładu, ale ta metoda nie kompresowała żadnego, ponieważ narzut przekroczył oszczędności. Szukam kilku poprawek w moim algorytmie, które mogłyby faktycznie zaoszczędzić bity.

Czy ktoś ma jakieś pomysły, co powinienem spróbować, aby zaoszczędzić kilka bitów na talię za pomocą mojego algorytmu? Szukam wzoru, który zdarza się wystarczająco często, żebym mógł zmniejszyć liczbę bitów na talię, nawet po dodatkowym obciążeniu wynikającym z powiedzenia dekoderowi, jakiego wzoru się spodziewać. Myślałem coś z oczekiwanymi prawdopodobieństwami pozostałych niewidzialnych kart i wrzucałem wszystkie pozostałe pojedyncze karty do jednego wiadra. Pozwoli mi to szybciej przejść do niższego trybu kodowania i być może zaoszczędzę trochę bitów, ale wątpię w to.

Ponadto, FYI, wygenerowałem 10 milionów losowych przetasowań i zapisałem je w bazie danych w celu łatwej analizy. Tylko 488 z nich kończy się na quadzie (np. 5555). Jeśli spakuję tylko te, które używają mojego algorytmu, otrzymam średnio 165,71712 bitów z niskim 157 bitów i wysokim 173 bitów. Nieco nieco poniżej 166 bitów przy użyciu innej metody kodowania. Jestem nieco zaskoczony, jak rzadka jest ta sprawa (średnio około 1 na każde 20 492 przetasowań).