Autor Tema: ¿Por qué hay un límite a la compresión de datos de una fuente aleatoria?

0 Usuarios y 1 Visitante están viendo este tema.

16 Noviembre, 2015, 11:05 am
Leído 993 veces

Raúl Aparicio Bustillo

  • Matemático
  • Mensajes: 3,105
  • Karma: +0/-3
  • Sexo: Masculino
La información que lleva un dato en bits es \(  -log_2 p_i \) donde p es la probabilidad de que aparezca dicho dato. El promedio es la entropía de Shannon. Si el número de datos es lo suficientemente grande se entiende que la cantidad de información que lleva el dato en promedio es esa. Pero ¿por qué en una muestra finita pequeña no puede dar la casualidad de que datos muy probables aparezcan mucho y se pueda reducir por debajo de ese límite?

17 Noviembre, 2015, 08:27 am
Respuesta #1

Raúl Aparicio Bustillo

  • Matemático
  • Mensajes: 3,105
  • Karma: +0/-3
  • Sexo: Masculino
Aprovechando mis vacaciones forzosas, tengo tiempo para pensar, así que me respondo la pregunta. Supongamos que hay una secuencia finita que rebasa el límite de compresión de Shannon. LA compresión de una cadena finita no puede bajar ese limite ideal porque si unimos 2 secuencias la capacidad de comprimir, en el peor de los casos será la suma de ambas. Si usamos el mismo compresor, añadiendole una intrucción de que si sale la compresión de las 2 secuencias por separado mayor las junte, es obvio que nos acercamos al límite ideal por arriba.

La definición frecuentista se puede aplicar a secuencias aleatorias finitas. Es verdad que no es computable, pero se puede acotar usando cualquier lenguaje de programación. No sé en qué grado se puede acotar para decir que es útil. Hay que ir probando programas de ordenador, si alguien se apunta... (si casi nadie se molesta en responder, hay excepciones pero no voy a dar nombres por cortesía)
 es un juego interesante.