Usando la base 80 para comprimir archivos

8

Quiero comprimir el tamaño del archivo haciendo mi propio sistema de numeración, que es un número basado en 80, ¿realmente quiero saber si esto es posible? Aprendí que el hexadecimal usa símbolos como A, B, C, D, E, F para representar 10,11,12,13,14,15, y eso es lo que quiero hacer con mi propio sistema de numeración, pero a mayor escala . Por favor corrígeme si me falta algo.

Es posible ?

Kinani
fuente
2
Ver también aquí .
Raphael
55
La respuesta de Frank explica por qué esto no funciona. Pero aquí hay algo que podría haberse preguntado antes de comenzar: ¿qué propiedad especial del número 80 cree que está usando? A menos que haya algo especial sobre 80, si su idea funcionó para 80, ¿no funcionaría mejor para 81? O 801?
David Richerby
3
@DavidRicherby: No puedo pensar en mucho valor para la base 80, pero en realidad hay un valor real al usar la base-85: puede convertir grupos de cuatro octetos en cinco caracteres imprimibles. Si bien la eficiencia del almacenamiento no es una gran mejora con respecto a la base 64 (veinte caracteres representarán quince octetos en la base 64 y dieciséis en la base 85), el hecho de que el "fragmento" de datos básicos es de 32 bits en lugar de 24 puede a veces Se muy útil.
supercat
Quiero decir, ¿qué pasaría si pudiera encontrar algunos patrones y representarlos en símbolos?
Kinani
2
Si encuentra patrones y los representa en símbolos, ha creado un algoritmo de compresión funcional (siempre que la representación sea más corta que el patrón original). Así es como funcionan todos los algoritmos de compresión.
Tanner Swett

Respuestas:

30

Si bien necesitará menos números basados ​​en 80 que números basados ​​en 2 (bits) para codificar el mismo archivo, la única forma de almacenar estos números basados ​​en 80 en una computadora es codificarlos como bits. Entonces no ganas nada.

De hecho, realmente pierde espacio, ya que 80 no es una potencia de 2: necesitará 7 bits para cada número basado en 80, pero en estos 7 bits podría codificar 128 estados diferentes, si los utilizó directamente.

FrankW
fuente
10

Hay varias formas de interpretar la pregunta. Lo que creo que podrías estar preguntando es que tienes una secuencia denorte letras en un alfabeto Σ dónde El |ΣEl |=80. Desea almacenar esto en el menor número posible de bits. Asumiremos que las letras del alfabeto están distribuidas uniformemente.

La cantidad de espacio teórica de información requerida para almacenar esto es norteIniciar sesión2El |ΣEl |bits Usando la codificación aritmética, puede hacer esto en tiempo lineal, usandoO(Iniciar sesiónnorte)pedazos de espacio intermedio. (¡Recuerde, ese es el logaritmo del número de símbolos, en bits! Si el tamaño de la secuencia se ajusta a una palabra de máquina, el almacenamiento intermedio requerido es un número constante de palabras de máquina como máximo).

Eso es bastante bueno. Pero, ¿qué pasa si queremos acceso aleatorio?

Resulta que se puede hacer. La primera técnica para hacerlo solo se descubrió hace unos cuatro años. Podemos almacenar la secuencia ennorteIniciar sesión2El |ΣEl |bits, de modo que leer o escribir cualquier entrada tomaO(1)hora. Si lo piensa, este es un resultado notable, porque significa que una computadora que funciona con cualquier raíz es, en cierto sentido, equivalente a una binaria.

Aquí está el documento: Yevgeniy Dodis, Mihai Pătraşcu y Mikkel Thorup, Una alternativa a la codificación aritmética con decodificación local , STOC 2010.

Por cierto, recuerda el nombre Mihai Pătraşcu. Él era y es lo más parecido que tenemos a un Évariste Galois moderno. Murió muy joven, de un tumor cerebral a la edad de 29 años. Pero en su corta carrera como científico de la computación, su trabajo revolucionó el campo de análisis de algoritmos de una manera que llevará décadas comprenderlo completamente.

Seudónimo
fuente
3

Si usted tiene un número (por ejemplo. 123456789⏨) en forma de texto se puede escribir en una base diferente (como 21i3v9 en base 36), por lo que comprimir se escribe como texto (de 9 caracteres a 6).

Si va más allá, terminará almacenándolo en binario (4 bytes¹).

Ahora, esto funciona porque comenzaste con un conjunto reducido [0-9] y te moviste a uno más grande [0-9a-z] y muchos bits de datos no fueron utilizados en la representación inicial.

Del mismo modo, si sabemos que un archivo solo contiene letras, podemos comprimirlo fácilmente cambiando la base. Sin embargo, si tuviera que comprimir contenido arbitrario, eso no (siempre) funcionará. Puede comprimir (obtener salidas más pequeñas) para algunos archivos, pero otros se harán más grandes como cualquier método de compresión sin pérdida , esto es inevitable.

Sin embargo, aún puede ser útil, por ejemplo, un método que comprime bien los textos en inglés pero hace que los textos en chino sean más grandes puede ser lo suficientemente bueno si escribe mucho más inglés que chino.

¹ En realidad, solo necesita 2²⁷ bits, aunque hoy en día el almacenamiento de la computadora utiliza múltiplos de 8 bits (¿pero tal vez quería almacenar una serie de números de 2²⁷ bits? ☺).

Ángel
fuente
2

Base 80 ?? ¿Por qué 80? No tiene sentido, sin embargo, la base 85 sí. Es bastante conveniente ya que puede representar 4 bytes con 5 caracteres (porque 85 ^ 5 = 4,437,053,125, que es un poco más de 2 ^ 32 = 4,294,967,296)

Aquí está mi código para escribir un solo 32 bits word:

for (i=0; i<5; i++)
{
    c = (word % 85) + 37;
    word /= 85;
    fwrite(&c, sizeof(uint8_t), 1, file);
}

y aquí para leerlo de nuevo:

    word = 0;
    for (i=4; i>=0; i--)
        fread(&c[i], sizeof(uint8_t), 1, file);

    for (i=0; i<5; i++)
        word = word*85 + c[i]-37;

Si realmente desea usar la base 80, puede usar el mismo enfoque y reemplazar las instancias de 85 con 80 y necesitará 6 caracteres por cada 4 bytes en lugar de 5.

Sin embargo, ¿cómo va a comprimir algo? Te das cuenta de que los archivos están escritos en la base 256, ¿verdad? Dicho esto, si comprime un archivo escrito en base 85, tendrá aproximadamente el mismo tamaño que el archivo base 256 original comprimido, lo que hace que la base 85 (o la base 64) sea una buena opción si desea representar datos binarios con caracteres imprimibles.

Michel Rouzic
fuente
tools.ietf.org/html/rfc1924 ;-)
Digital Trauma
0

Se utilizan diferentes bases para diferentes propósitos, aunque como explican las otras respuestas, no obtendrá nada en términos de compresión.

Ver wikipedia para una explicación de la codificación base64 . Base 64 se usa a menudo, no para la compresión, sino para codificar datos binarios que normalmente darían como resultado caracteres no imprimibles y códigos de control en un espacio de caracteres ASCII imprimible. Esto dará como resultado un tamaño de archivo más grande, pero es útil para transferir datos binarios que se pueden incrustar en otros archivos ASCII, por ejemplo, dentro de XML, correos electrónicos, CSS, páginas web, etc.

Luke Mills
fuente
Lo que dices es cierto pero no responde la pregunta.
David Richerby
@DavidRicherby No estoy de acuerdo. Responde a la pregunta desde el punto de que es posible usar bases de números diferentes a las que el OP está familiarizado, y que tienen un propósito, pero ese propósito no es la compresión.
Luke Mills el
La pregunta es, ¿es posible comprimir archivos escribiéndolos en base-80? La respuesta a eso es "no", como mencionas en tu primera oración y como todas las otras respuestas ya cubren. Su segundo párrafo es un comentario sobre la pregunta. Los comentarios van en comentarios.
David Richerby