Clarificación de codificación de bytes variables

Question

Soy muy nuevo en el mundo de la codificación de bytes, así que discúlpeme (y por supuesto, corrígeme) si estoy utilizando/expresando conceptos simples de la manera incorrecta.

Estoy tratando de comprender la codificación de bytes variables. He leído el artículo de Wikipedia (http://en.wikipedia.org/wiki/Variable-width_encoding), así como un book chapter de un libro de texto de recuperación de información. Creo que entiendo cómo codificar un entero decimal. Por ejemplo, si quería dar bytes codificación variable para el número entero 60, tendría el siguiente resultado:

1 0 1 1 1 1 0 0 

(por favor, hágamelo saber si lo anterior es incorrecta). Si entiendo el esquema, entonces no estoy completamente seguro de cómo se comprime la información. ¿Es porque normalmente usaríamos 32 bits para representar un número entero, de modo que representar 60 daría como resultado 1 1 1 1 0 0 precedido por 26 ceros, desperdiciando ese espacio en lugar de representarlo con solo 8 bits?

Gracias de antemano por las aclaraciones.

Answer 1

La forma de hacerlo es reservando uno de los bits para indicar "No he terminado con el valor". Por lo general, ese es el bit más significativo.

Cuando lee un byte, procesa los 7 bits más bajos. Si el bit más significativo es 1, entonces sabes que hay un byte más para leer, y repites el proceso, agregando los 7 bits siguientes a los 7 bits actuales.

El formato MIDI utiliza esa codificación exacta para representar longitudes de eventos MIDI, de la siguiente manera:

1. ExpectedValue = 0
2. byte = ReadFromFile
3. ExpectedValue = ExpectedValue + (byte Y 0x7f)
4. si byte> 127 entonces
   1. ExpectedValue = ExpectedValue SHL 7
   2. Goto 2
5. Hecho

Por ejemplo, el valor 0x80 se representaría mediante el bytes 0x81 0x00. Puede intentar ejecutar el algoritmo en esos dos bytes, y verá que obtendrá el valor correcto.

UTF-8 funciona de manera similar, pero utiliza un esquema un poco más complejo para decirle cuántos bytes debe esperar. Esto permite algunas correcciones de errores, ya que puedes decir fácilmente si los bytes que estás obteniendo coinciden con la longitud reclamada. Wikipedia describes their structure bastante bien.

Answer 2

Golpeas el clavo en la cabeza.

Existen muchos esquemas de codificación, como gamma y delta, que son casos especiales de codificación de elias. Estos son códigos de nivel de bit, a diferencia del código de nivel de byte que usaste, y son útiles cuando tienes un fuerte sesgo hacia números pequeños (que a menudo se puede lograr codificando deltas en lugar de valores absolutos). Los esquemas de codificación a nivel de bit son mucho más difíciles de implementar que los esquemas de byte y la carga adicional de CPU puede superar el tiempo ahorrado al tener menos datos para leer, aunque la mayoría de las CPU modernas tienen "bit más alto" y "más bajo". instrucciones "de bits" que mejoran drásticamente el rendimiento de los códecs de nivel de bit. A medida que las velocidades de la CPU continúan superando las velocidades de la RAM, los esquemas a nivel de bits se volverán más atractivos, aunque la simplicidad de los códecs de nivel de byte también es un factor importante.

Answer 3

Sí, tienes razón, ahorras espacio codificando usando un byte en lugar de 4. Generalmente, guardarás la memoria si los valores que estás codificando son mucho menores que el valor máximo que cabría en tu original. ancho de codificacion