Suponga que el peso de 1 es cuatro y el peso de 0 es uno, ¿cómo puedo transformar una secuencia de 0s y 1s en otra secuencia, posiblemente con diferentes longitudes, de modo que exista una forma de retroceder y la nueva secuencia tenga la menor? posible peso?

Answer 1

Supongamos primero que la secuencia inicial tiene una longitud fija [matemática] N [/ matemática]. Entonces queremos encontrar [matemática] f (x_ {0} x_ {1} x_ {2}… x_ {N-1}) [/ matemática] tal que [matemática] \ suma de peso (f (x)) [/ matemática] tiene el valor mínimo. Si suponemos que el rango también debe ser una longitud fija, para evitar codificaciones de palabras complicadas que eviten la ambigüedad, entonces podemos ver los tamaños N + 1, N + 2, … y ver cuál nos da un mapeo con el mínimo total peso.

El codominio debe tener entradas [matemáticas] 2 ^ N [/ matemáticas], por lo que podemos elegir que sean las entradas de menor peso de longitud [matemáticas] 2 ^ {N + k} [/ matemáticas]. Entonces, para cada longitud de salida, simplemente sume el peso agregado de los números de menor peso [matemática] 2 ^ N [/ matemática]:

* Todos los ceros: 1 entrada de peso [matemática] N + k [/ matemática]
* Uno: [matemáticas] N + k [/ matemáticas] entradas de peso [matemáticas] N + k-1 + 4 [/ matemáticas]
* Dos: [matemática] {N + k \ elegir 2} [/ matemática] entradas de peso [matemática] N + k-2 + 8 [/ matemática]

etc. Esto es bastante fácil de llevar a cabo en una hoja de cálculo. Si hacemos eso para secuencias de 32 bits obtenemos:

  N + k peso total de los elementos más ligeros 2 ^ 32
 33 324581322615
 34 317722362376
 35 313645269644
 36 310689339720
 37 310276537480
 38 309075705248
 39 310330609032
 40 310647293584  

 32 333466421615 [original]

Entonces, en este caso, elegir una longitud de salida de 38 bits nos da la codificación más ligera. En este caso, todas las secuencias de salida tienen entre 0 y 18 unidades. Ahora que tenemos un dominio y un codominio, simplemente elija cualquier asignación arbitraria entre los dos. (Esto puede tomar como máximo 19 GB para almacenar el ejemplo dado, incluso si elegimos el mapeo al azar).

Si queremos hacer esto para secuencias de longitud arbitraria, simplemente podríamos repetir una transformación de longitud fija varias veces. Probablemente obtendrá mejores resultados cuanto mayor sea la “longitud de código” que utilice, a costa de un mapeo más costoso, en el peor de los casos. (Tenga en cuenta que en general no obtuvimos muchos beneficios. Parte de esto se debe a que más de la mitad de las secuencias de entrada ya tienen menos de 18 bits establecidos).

Una función que asigna secuencias de longitud fija a secuencias de longitud variable es más difícil de analizar y es poco probable que proporcione un beneficio mucho mayor, a menos que la entrada venga equipada con una distribución de probabilidad no uniforme, en cuyo caso la codificación Huffman proporcionará un mejor resultado.

Por otro lado, si la entrada tiene una longitud fija pero la salida puede tener una longitud variable (y alguna forma inequívoca de delimitar la secuencia), puede simplemente tomar las palabras de salida de peso mínimo sobre todo N + 1, N + 2, … y construir la codificación de esa manera.

Answer 2

Se me ocurrió un algoritmo, pero no es lo que quieres … Es realmente lento y no se comprime si el peso de 1 es solo 4. Pero todavía lo estoy publicando, por si acaso ayuda.

1. Toma la cuerda.
2. Almacene el número de ceros a la izquierda.
3. Convertir a base 10.
4. Si es primo:

1. Consigue su posición. (11 es el quinto número primo)
2. Convierta la posición de nuevo a binario.
3. Y luego la salida es: los ceros + 1 + la posición en binario

Más:

1. Descomponerlo en un producto de sus factores primos
2. Y luego la salida es: los ceros + 1 + (número de “factor primo” de 0 + 1 + número de “su potencia” de 0 + 1) y luego elimina el último

Ejemplos:

1. 0001011:

1. 3 ceros
2. 11 en base 10
3. 5to número primo
4. 5 = 101 en binario
5. Salida: 0001101 (Sí, el resultado no tiene un peso menor, pero si el peso de 1 es 10, el algoritmo funciona para un número mayor)

00011000:

1. 3 ceros
2. 24 en base 10
3. 2 ^ 3 + 3 ^ 1
4. Salida: 0001001000100010

Usé Editar violín – JSFiddle para probarlo.

La descompresión es realmente simple: ves el primer número después del primer “1”. Si es 1, entonces es un número primo, de lo contrario, comienza a multiplicar el número, etc.

Answer 3

Si un 1 lleva cuatro veces el peso de un 0, puede minimizar el número de 1s haciendo que la secuencia sea lo más corta posible, es decir. comprimiéndolo usando un algoritmo de compresión de datos.

Después de comprimir los datos, puede codificar los datos para minimizar el número de 1s. Un código Huffman modificado (modificado para que sus palabras de código sean en su mayoría ceros, por ejemplo, 101 = 100, 110 = 1000 …) sería un buen lugar para comenzar. Por supuesto, ya no será la longitud mínima, pero el peso de la secuencia disminuirá.