Cómo funciona .zip: Árboles binarios

Compañeros buen día, inspirado en esta clase les comparto una app desarrollada por mi usando JavaScript, que simula un arbol binario y realiza la comprensión de un texto, tal como mostro Freddy en la clase.

Estoy atento a sus comentarios o sugerencias Ingresar a la aplicación

Me hubiera gustado que en 20 años de educación tradicional alguien se hubiera puesto a decirme "Están listos? Hagámoslo!"
Y luego se pone a hacerlo. Crei que en algún momento diría "bueno ya me dió hueva, ahí termínenlo ustedes."
Como básicamente todos mis profesores de todos los niveles que tuve.

Hazme un hijo tío Freddy.

Lo que mas me motivo fue la música. jajaja

Los árboles binarios también pueden ser usados como algoritmos de búsqueda:

Para mi es genial, por que de despúes de muchos años y en la edad que tengo (49) se ha despertado una curiosidad grande por la técnologia, por que siempre me pregunto " como lo hacen". Por ser muy nuevo en esto, es mucha información para procesar y entender. Quiero aprender cosas nuevas y prepararme para estos años que viene y que mi sirven mucho en la profesión como dibujante (autocad) que desempeño actualmente.

Realicé el experimento, en un archivo de texto coloqué Amo leer panama papers, en efecto hay 22 bytes

Al comprimir el archivo de texto el tamaño incremento a 136 bytes

Cómo funciona .zip: Árboles binarios

¿Cómo funciona la compresión de un archivo sin perder ningún valor de ese archivo?

Los árboles binarios nos permiten comprimir sin perder información. En este caso, vamos a comprimir “amo leer panama papers”.

1. Debemos ver cuantas veces se repite cada letra

• Una letra siempre tiene 8 bits(en UTF-16 puede ocupar 16bits), y esa es la clave sobre la que nosotros podemos comprimir. Siempre tener en cuenta ese numero para hacer la tablas de frecuencia y de esa manera determinar cual es la letra que más aparece.
• Con la frecuencia logramos que las letras que aparecen más frecuentemente solo ocupen un bit, esto lo logramos creando un árbol de dos ramas que dependiendo del numero realiza un movimiento: a la rama de la derecha es = 1 y a la rama de la izquierda es = 0 (Árboles Enearios).
• Luego buscamos la letra con mas frecuencia y la ubicamos en el primer 1 de nuestra rama:

• Ahora ya podemos comprimir nuestro texto. Recuerda: siempre que lleva una letra es 1 si me quiero mover en el árbol es 0… El 1 indica que represento una letra.

Ejemplo gráfico del algoritmo de compresión ZIP:

Me recordó a la serie Silicon Valley

    Me pregunto si habrá alguna forma matemática de demostrar que efectivamente, la cantidad de bits para representar un archivo luego de utilizar el algoritmo de compresión es, en todos los casos, menor a la cantidad de bits utilizados en el archivo original. 
    Quiero decir, que tal si tuviéramos 10 caracteres y sólo uno de ellos se repitiera. Originalmente ocuparíamos 80 bits para representarlos. Pero si usáramos el árbol binario ocuparíamos 72 bits para representar cada letra además de los bits utilizados para representar cada una de sus posiciones en el árbol binario, lo que resulta en una cantidad de bits incluso mayor que la usada en el texto original. 
    Creo que para que este algoritmo de compresión cumpla su objetivo deben cumplirse ciertas condiciones . Tal vez una relación como: número total de caracteres- número de caracteres repetidos; o algo por el estilo.

excelente clase tanto me gusto que decidi escribir el codigo para simular eso en JS , ahi lo deje en mi git por si lo quiere probar alguien, https://github.com/jjcmjavascript/CompressUncompress/blob/master/compress&uncompress.js , la funcion compress te devuelve un objeto, que le puedes pasar a la funcion uncompress para que lo revierta.

hay alguna herramienta para poder realizar un repaso del curso y estar listo para tomar el examen

Los árboles binarios tienen algoritmos en donde se nos permite recorrerlos en diferente orden. También hay momentos en donde necesitamos eliminar elementos y tienen infinita cantidad de usos.

Acá hay algunos algoritmos que se puede llegar a usar para los árboles binarios

La mejor explicación de algoritmos de compresión que he visto. Ojalá Freddy hubiese sido mi profesor en la universidad.

Aqui un poco de teoria mas compleja respecto al Arbol Binario para aquellos interesados.
https://es.wikipedia.org/wiki/Árbol_binario
Y un poco de teoria de grafos si desean profundizar.
https://es.wikipedia.org/wiki/Teoría_de_grafos

Por si alguien al igual que yo tenía la duda de cual era el código de cada letra acá se los dejo:
A: 01000001 a: 01100001
B: 01000010 b: 01100010
C: 01000011 c: 01100011
D: 01000100 d: 01100100
E: 01000101 e: 01100101
F: 01000110 f: 01100110
G: 01000111 g: 01100111
H: 01001000 h: 01101000
I: 01001001 i: 01101001
J: 01001010 j: 01101010
K: 01001011 k: 01101011
L: 01001100 l: 01101100
M: 01001101 m: 01101101
N: 01001110 n: 01101110
O: 01001111 o: 01101111
P: 01010000 p: 01110000
Q: 01010001 q: 01110001
R: 01010010 r: 01110010
S: 01010011 s: 01110011
T: 01010100 t: 01110100
U: 01010101 u: 01110101
V: 01010110 v: 01110110
W: 01010111 w: 01110111
X: 01011000 x: 01111000
Y: 01011001 y: 01111001
Z: 01011010 z: 01111010

Si definimos caracteres frecuentes = a aquellos que en el árbol binario llegan hasta la octava rama.

Los caracteres menos frecuentes pesan más que 8 bits (pudiendo llegar a pesar 256 bits), o sea que el archivo zipeado puede llegar a ser más grande que el original. (entiendo que es muy improbable)

La matemática es clara pero para probarlo podemos crear un bloc de notas con el abecedario, lo guardamos, zipeamos, y comparamos sus tamaños.

ME ENCANTA ESO DE " YA VERÁN COMO TODO ENCAJA DE MANERA MÁGICA REPENTINAMENTE"

Esta clase es genial y no se ve complicado en la practica!!

Wow, me acaba de estallar la mete.
La forma que me enseñaron en la escuela (secundaria) es que solo se comprimen los caracteres que se repiten y yo le dije a la profa que eso no tenia mucho sentido y la profa me bajó un punto.

Esta clase me gustó, fue estimulante ver en primer lugar el comentario de Freddy en el panel donde dice que lo hizo con amor. Esto me hizo sentir cómoda, y crear un vinculo con él. Lo segundo que me gustó, es ver el ejercicio de conversión del mensaje completo a comprimido fue perfecto. Lo tercero y lo mejor fue que si le entendí.
pd: La musiquita que ponen cuando va en cámara rápida es genial.

En realidad el estandar UTF-8 soporta caractéres de 1 a 4 bytes, es decir un único símbolo puede tener 4 bytes, mientras que UTF-16 es un sistema que permite caractéres de dos palabras de 16 bits, es decir grupos de 2 o 4 bytes.

Muy buen curso freddy sin duda uno de los mejores. Ahora una duda, entiendo bien como funciona el algoritmo de compresión .zip . Pero a la hora de descomprimir ese archivo como sabe en que posición va cada letra?

Hice una prueba comprimiendo en zip un fichero de texto que tenía 19B y pasó a tener 183B. 😲

Gracias a esta clase puedo entender por qué para este caso de un fichero tan pequeño tiene más bytes al comprimirlo, al tener que almacenar también su árbol binario. 👏

Con ficheros más grandes sí se aprovecha mejor el algoritmo, ya que puede encontrar más bytes repetidos y es cuando este árbol cobra mayor sentido. 👍

Interesante conocer como funciona el formato zip.
A modo de aporte, los árboles binarios de búsqueda son una de las estructura de datos más eficientes.

Años estudiando informatica, y primera vez que veo un lugar donde se consigue tanta informacion interesante que no sabia.

Wow la manera en que comprime es genial. Es lo fácil de entender el método. Entre más raro sea la aparición de una letra, más información lleva. Las letras que se repiten mucho llevan poca información y por eso se hace la compresión.

Si uso letras en mayúscula, ¿se guarda como otra letra?

Uno de las clases que más me han gustado!!! Aaah!!!

Me hizo recordar mucho al curso de Matemática Discreta. Por cierto en Platzi también hay un curso acerca de ello, para poder entender mejor los árboles binarios.

La música del min 1:50 lo es todo xddd I love Platzi!!!

increibleeee aprendí mas en este curso que en la universidad.
Mis respetos…

Desde 1:45 a 2:08 escuchar en 1.5x jajaja

Muy lindo el curso, pero los arboles crecen para arriba jaja salu2

El formato ZIP fue diseñado originalmente por Phil Katz, fundador de PKWARE. Katz liberó al público la documentación técnica del formato ZIP, y lanzó al mismo tiempo la primera versión de PKZIP en enero de 1989.
https://es.wikipedia.org/wiki/Phil_Katz
https://es.wikipedia.org/wiki/Formato_de_compresión_ZIP#:~:text=ZIP es un formato de fichero bastante simple%2C que comprime,lo que aumenta el rendimiento.

Los árboles binarios se emplean a menudo para la representación de expresiones aritméticas, dado que una operación con dos operandos la podemos representar como un árbol cuya raíz sea el operador, y sus subárboles sean los operandos.

Ahora con “Amo leer Pandora Papers”

jajajajaja ya de por si esa musiquita es graciosa pero como yo veo los videos en 1.5x suena aun mas divertido.

Hoy estaba aprendiendo por mí mismo a cifrar mensajes y me encuentro con esto. Que genial!!

Ya entendí cómo funciona la compresión de archivos

¿Cómo se llama la cancioncita que se escucha cuando el profesor hace las cuentas rapidas? Es para una tarea 😃

Vean el siguiente video: https://www.youtube.com/watch?v=wolbjbIhfbQ

de lujo el soundtrack

Che ta buena la música de avance rápido :v

se puede decir que cuando pone la música esta comprimiendo el ejercicio?

que interesante… ironico pero gracioso que archivos pequeños pesen más comprimidos 😄

Quien mas esta cumpliendo el reto de azure? 😄 Buena suerta

Me quede sorprendido con el arbol binario para poder comprender el .zip y es increible que es muy efectivo en archivos muy grandes como lo son los proyectos de android o de visual studio.

Puro ingeniero , y yo apenas comprando mi primer laptop

Clase 27 – Cómo funciona .zip: Arboles binarios

¿El compresor .zip funciona igual que formato .png y .flac?

• Si.

¿Qué usa el compresor .zip para funcionar?

• La teoría de árbol binario.

¿Cuáles son los pasos que usamos en la teoría de árbol binario para comprimir archivos?

• Identificar de cuantos Bytes se compone el archivo
• Encontrar cuáles son las letras que se repiten con mayor frecuencia.
• Crear un árbol n-ario.
• En dicho árbol organizamos las letras de mayor a menor frecuencia.
• Recorremos raíz por raíz del árbol n-ario para lograr identificar el número de veces que se pasa por una raíz 0 hasta encontrar el byte que estamos comprimiendo.
• Escribimos en una sola línea los 0 y 1 que nos resultaron luego de recorrer todo el árbol n-ario para crear un x número de bytes.

¿Cómo funcionan las raíces del árbol n-ario?

• Este árbol tiene únicamente dos ramas. La rama de la derecha representa un 1 y la de la izquierda un 0.
• En la rama de la derecha siempre colocaremos la letra que estamos organizando y en la rama de la izquierda crearemos la siguiente rama este proceso se debe hacer hasta que se terminen de organizar todas las letras.

¿Cómo recorremos el árbol n-ario?

• Una vez organizados todos los bytes de mayor a menor frecuencia empezamos desde la primera raíz recorriendo cada raíz de la izquierda (0) hasta llegar al byte que esta en la raíz de la derecha, para que seamos capaces de comprimir el peso del byte.

¿Cómo organizamos varias letras que se repitan el mismo número de veces?

• Los podemos hacer en el orden que queramos.

¿el espacio se considera como carácter?

• Si.

¿La compresión con .zip funciona mejor en archivos de gran tamaño?

• Si.

¿Podemos usar .zip para varios formatos de archivo?

• Si.

¿.zip solo funciona con lenguajes que puedan hacer corrimiento de bits?

• Si.

¿Qué es el corrimiento de bits?

• Es cuando somos capaces de meternos en lo bytes y leer bit por bit el contenido del byte.

En resumen
La compresion de un archivo funciona creando un arbol binario que crea un index con las palabras mas repetidas Iniciando por la palabra que mas se repite y asi poder crear un mismo archivo que pese menos que el original
Esto es algo increible que sin este curso, probablemente nunca hubiera aprendido, y siempre tuve esa duda

Fabiola dónde estás! Extraño tus apuntes jajaja

lo mejor que me ha podido pasar invertir en platzi gracias amigo fredy

También existen codec para compresión de video, muy usados en los sitemas de cctv y televisión digital.
H.264
H.265.

Compresión de archivos:

1. Tabla de frecuencia --> carácter con peso especifico en archivo.
2. Caracteres idénticos —> 1 Byte.
3. Identificar carácter con mayor frecuencia. Los árboles binarios nos permiten comprimir sin perder información.

Clase 27
¿Que puedo aprender de esta clase?
¿Como puedo utilizarlo a nivel personal y a nivel profesional?
¿Para que me sirve este conocimiento?
¿Como funciona las compresiones que no pierden NADA de informaciòn?
¿Como puedo ayudar a otras personas a traves de este conocimiento?
¿Como puedo usar esta informacion para tomar mejores decisiones?

Puntos claves:
PNG, FLAG, ZIP, no pierde nada de informaciòn , Why?
Arbol Binario
Caso
Primero detectan cuanta informaciòn tiene
“amo leer panama papers”
a=5
m=2
0=1
“ ”=3
l=1
e=3
r=2
p=3
n=1
s=1
3-1-4-1-6-1-6 = 22B (178b)
¿Cuales son las letras que tiene la mayor frecuencia?
La forma màs fàcil no es a ojo, pensemos como piensa un computador
Una letra es un Byte, un codigo binario (en utf 16 es 2 bits)

d
A 100001000000101000000010010010000001010001100000000011000011010001100010010000001000000001

AMO LEER PANAMA PAPERS
22 B = 176 bits; | 88 bits = 11 bits
cualquiera puede programar un arboil binario
Esto aplica a imagenes, sonidos, video, todo
arbol binario 😮
Corrimiento de bits
matematicas binaria

Aprendi lo fascinante que es convertir la informaciòn
La informaciòn es medible y comprimible

Excelente explicación de codificación con árboles binarios. Sin embargo, cabe acotar que .zip utiliza el algoritmo de compresión lempel ziv (en conjunto con otros). También es un algoritmo de compresión sin pérdidas y el contexto de compresión es similar al de árboles binarios, pero es mucho más eficiente y de igual forma fácil de entender.

Los invito a leer un poco más sobre ese algoritmo.

Saludos 😃

Oigan winrar no sirve o que sucede?
porque cuando comprimo el archivo amo leer panama papers si pesa 22 bytes pero a comprimirlo en rar
ó .zip me da 190 bytes

Siento que esta clase en algún momento me resultara muy provechosa

Me recordó a fourier en vez de leer cada dato, mejor se toman las frecuencias dominantes y así se reconstruye la señal.

Me encantó el mensaje final, mucha energía freddy

Por si se preguntan cómo se comprimen las imágenes

Excelente curso: resumen

• Primero vemos cuantos Bytes tiene el texto a comprimir
• Luego identificamos cuantas veces las letras se repiten
• Empezamos con el árbol binario, 0 izquierda, 1 derecha, comienza con la letra que más se repite
• Para representar la “M” contamos los ceros hasta llegar al 1 de la “M” en este caso la “M” en vez de tener 8 bits tiene 5

Ahora entiendo muchas cosas, es por esta razón que cuando uno lee un archivo comprimido, sale ese tren de caracteres, por que el block de notas toma la codificación ASCII de los bytes nuevos que creó el compresor.

Que buen ejemplo lo voy a poner en práctica con mis alumnos de S.O.

¿La letra M no seria 00001? Lo representaste de una manera pero lo escribiste de otra xD, corríjanme porfavor

Que ingeniosa manerade comprimir archivos. Todo a partir de como funcionan los bits y los bytes

Lo que no entendi, es como el algoritmo sabe el orden en que deben ir la letras? Porque Freddy va viendo el orden en pantalla

Los Arboles binarios el principio mas básico de como funciona un compresor de archivos !

En ciencias de la computación, un árbol binario es una estructura de datos en la cual cada nodo puede tener un hijo izquierdo y un hijo derecho. No pueden tener más de dos hijos (de ahí el nombre “binario”).

basicamente los arboles binarios son una forma de decirle al sistema que ahora este es el nuevo orden y significado de el sistema binario y se usa para acortar el texto o la cantidad de bytes que ocupa al final

jajajaja me encanto la musica del speed fast! 😂🤣, muy buena produccion jajaj super dinámico, me hizo concentrarme cuando ya estaba cansado! jajaja

Siempre me había preguntado como carajos se comprime un archivo

Para el algoritmo de compresión podrían usar un diccionario en lugar de un árbol, dado que la estructura del mismo es regular. Habría que hacer el ordenamiento por cantidad de ocurrencias que hace Freddy al principio. Luego, cada llave sería la letra en sí, y el valor al que apunta, la cantidad de 0’s necesarias para llegar a la letra, recorriendo el ordenamiento resultante de la primera fase, sumado al ‘1’ final. De ese modo, luego se recorre el mensaje, y se va traduciendo cada letra, a la cantidad de bits correspondiente.

oh! valla, no imagine que de esta manera seria la técnica de comprimir archivos, genial. Gracias!

Lo que mas me gusta de estos cursos dirigidos por Freddy es la aptitud y actitud que tiene y le pone a cada uno de los videos educativos a su cargo, para envolver al estudiante en un mundo de conocimiento divertido que convierte este conocimiento en algo de fácil recordación.

4 años después recién tomando el curso. está genial.

me encantó la música qué le ponán al freddy en cámara rápida jaja

Esto ha sido el mejor curso que he hecho en mi vida… this is the best thing on internet.

de verdad es excelente ver este tipo de explicaciones

Es como la serie Silicon Valley.

¿Con matemática binaria te refieres al álgebra de Boole o es otra cosa?

Video sobre tablas de frecuencia

Y pensar que después de tantos años trabajando en tecnología nunca me había cuestionado esto.
Gracias por compartir como funciona zip Team Platzi.

Recuerdo haber visto esto en un cruso de la universidad, pero nunca me explicaron cual era el objetivo de hacer este procedimiento, ahora me quedo super claro.

que divertidas las clases 😄

me encanto la canción de los 50s, es una buena manera de esperar cuando freddy hace algo largo

Un excelente curso, es otro mundo, muchas gracias. 😃

La verdad a sido una experiencia muy grata, vengo de estudiar una carrera en hoteleria y turismo (la cual desafortunadamente me lleve un sin sabor), y comenzando a estudiar el tema de programación y fundamentos de ingenieria de software, uno como persona se replantea, y empieza a generar amor por esta maravillosa carrera. Freddy , mil felicitaciones.

wow nice pense que comprimir un archivo o un texto seria mas complicado de entender, realmente esta muy bien explicado

que cantidad de informacion, muy bueno he estado repasando cada clase y profundizandollo

hasta ahora el curso, mas o menos conocía todo… pero esta class de como comprimir… si es nueva para mi y la verdad super interesante…

Como es posible que pueda representar un archivo en menos espacio?

No tiene mucho sentido, pero gracias a las matemáticas binarias podemos lograrlo. La respuesta para ZIP son los arboles binarios

Veamos un ejercicio práctico de como funciona

• Normalmente una letra ocupa 8 0 16 bits, pero si analizamos un archivo byte a byte hay algunos caracteres que se repiten por ejemplo veamos esta frase, vemos como la A se repite 5 veces, representando la a un número en código binario

• Ahora dentro de un arbol representemos cada una de estas letras por frecuencia, en orden de primero las que más se repiten y así descendentemente.

Ahora de esta forma podría representar la A como un único bit o la m con 4 bits, estoy creando una forma más pequeña de representar los caracteres.

• Representemos ahora toda la frase

Ahora como vemos pudimos reducir muchísimo el tamaño en bits de mi frase, sin embargo aparte del arbol ya transformado tengo que también guardar mi arbol creado para poder interpretar ese valor de nuevo a su original.

Dios mío, nunca pensé que la compresión de un ZIP funcionara así 🤯
Ojalá hubiese visto este ejemplo cuando vi árboles binarios en la universidad.

La compresión de archivos es una parte increíblemente importante del espacio de trabajo digital. Podemos enviar más datos a mayores velocidades que nunca antes, por lo cual los archivos ZIP son una herramienta tan popular para los negocios en todo el mundo. Pero ¿un archivo ZIP?

Los archivos ZIP codifican información en menos bits y, por lo tanto, reducen el tamaño del archivo o de los archivos, al quitar datos redundantes. Esto es lo que se denomina “compresión de datos sin pérdidas”, que asegura que todos los datos originales se mantengan intactos. Veamos un ejemplo rápido para explicar cómo funciona.

Imagina un archivo que contiene las siguientes oraciones:

La mejor solución de almacenamiento y uso compartido de archivos para tu empresa
Tu solución empresarial para el mejor intercambio y almacenamiento
Cada palabra de este archivo aparece dos veces. Ahora, si cada carácter y espacio en el archivo equivalen a una unidad de memoria, el tamaño total del archivo sería de 110 unidades. Sin embargo, si creas un código numerado para el archivo, los datos pueden expresarse de una manera diferente:

1 - La
2 - mejor
3 - solución
4 - de
5 - intercambio
6 - y
7 - almacenamiento
8 - para
9 - empresas
O, para expresarlo de una forma diferente, la oración ahora se leería así: 123456789896712345. Esto significa que el tamaño inicial del archivo de 110 unidades puede reducirse a solo 18 unidades, lo cual representa un ahorro increíble. El formato de archivo ZIP usa algoritmos de compresión sin pérdidas para hacer exactamente eso y permitirte expresar la misma información de una manera más eficaz, simplemente al quitar los datos redundantes del archivo.

https://experience.dropbox.com/es-la/resources/what-is-a-zip-file

https://experience.dropbox.com/es-la/resources/what-is-a-zip-file

😎😎😎😎😎😎

Like si te gustó la música de fondo mientras Freddy contaba las letras

Me gustó mucho la explicación. Pero la música de fondo no tiene precio!

Un árbol binario puede definirse como un árbol que en cada nodo puede tener como mucho grado 2,es decir,a lo más 2 hijos. Los hijos suelen denominarse hijo a la izquierda e hijo a la derecha,estableciéndose de esta forma un orden en el posicionamiento de los mismos.