Codificar el fin de jugar a las cartas (compresión de datos)

Question

Supongamos que tenemos una baraja de cartas se barajan en un azar de configuración. Nos gustaría encontrar una $k$-bits de código en la que se explica el actual orden de las cartas. Esto sería fácil de hacer para $k=51 \cdot 6=306$, ya que podría codificar nuestra cubierta de la tarjeta por tarjeta, el uso de $2$ bits para la coloración y el $4$ bits para el número de cada tarjeta.

Nos gustaría optimizar este código. Existen $52!$ formas de organizar nuestro mazo, y por lo $k$ tendrá que ser al menos de: $\lceil\log(52!)\rceil=226$. Me piden que encuentre un código para un $k$-valor a mitad de camino entre el$306$$226$.

Entiendo que mi código no puede funcionar la tarjeta por tarjeta, ya que existen $52$ tarjetas diferentes y $\lceil \log(52)\rceil=6$. Por lo tanto, cualquier tarjeta por tarjeta de codation llevará a $k\geq306$.

Por lo tanto llegué a la conclusión de que mi estrategia debe codificar bloques de tarjetas, otra idea que yo tenía era para codificar la coloración de la primera y los números de la segunda.

Podría alguien darme una pista sobre dónde ir desde aquí?

Answer 1

El fin de las permutaciones de $\{1,2,\dots, 52\}$ en lexicográfica del orden.

Codificar el $r^{th}$ permutación en esa lista como $r$ (no requiere más de $226$ bits).

Encontrar un camino para ir y volver de la permutación, dado $r$.

Answer 2

Enumerar todas las cartas en la baraja, decir, por su valor y satisfacer de una manera sencilla, por ejemplo, dejar que los diamantes ser numeradas del 1 al 13, del as al rey, luego los clubes de 14 a 26, entonces los corazones de 27 a 39 y, por último, las espadas de la 40 a la 52.

Como codificar tarjetas una por una, disminuir el valor de cada tarjeta por encima de ella. Así que la secuencia $1,2,3,4$ significa que el as, tres, cinco y siete de diamantes, mientras que la secuencia $15,15,14, 15$ significa que la dos, la tres, la ace y, a continuación, cinco de los clubes.

En el principio, el uso de seis bits para cada número. Después de 20 tarjetas, el uso de cinco bits por tarjeta (ya que ahora el valor más alto entre el de las tarjetas es de 32). Dieciséis tarjetas más tarde, usted puede comenzar a utilizar de cuatro bits por tarjeta. Y así sucesivamente.

En total, se utiliza $$20\cdot6+16\cdot5+8\cdot4+4\cdot3+2\cdot2+1=249$$ bits, que es un poco mejor que lo que había pedido (pero por supuesto no óptima)

Answer 3

Según Hoffman, la óptima y sin pérdida de codificación de las necesidades, al menos, $H(s)$ bits en promedio para cada código, donde $h(s)$ es la entropía de la fuente $s$.

En su caso no hay redundancia en los números que desea codificar. Son simly números a partir del $1$$52!$. Yo podría sugerir el uso de la longitud de la variable codificación. Uno tiene que ser cuidadoso acerca del código de la construcción ya que se necesita para ser descifrable y no todos los códigos son descifrables. Está explicado en el artículo de wiki cómo hacerlo.

Answer 4

Para ampliar sobre Arthur solución:

Hay una buena cantidad de espacio que se va no utilizados entre los más altos de la tarjeta disponible y el final del campo de bits. Una forma bastante sencilla para recuperar un poco de esto es codificar dos tarjetas a la vez. Utilizando su mismo sistema básico llego 240 bits necesarios, a sólo 14 bits por encima del mínimo teórico.