Algoritmo LZW - Compresión
ฝัง
- เผยแพร่เมื่อ 16 ต.ค. 2024
- Compresión de datos con el algoritmo LZW. El algoritmo es el siguiente:
Inicializar diccionario con cadenas de longitud 1
w=NULL
MIENTRAS (!EOF)
...LEER K
...SI (wK está en el diccionario) ENTONCES
......w=wK
...SINO
......Imprimir el código de w
......Agregar wK al diccionario
......w=K
...FIN_SI
FIN_MIENTRAS
Imprimir el código de w
Gracias por el vídeo... Crack, maquina, tigre, fiera, jefe, torbellino, tifón, número 1!
Me alegro de que el material ta haya sido útil! Saludos!
Después de pensar un poc en como sería la mejor forma de comprimir algo, me di cuenta de que eso sería con un diccionario, y vaya sorpresa que me doy al saber que alguien ya lo hizo, y lo agradezco; me siento como cuando Rick le regala a Rick la pistola de portales y se dice: no has hecho esto, tu lo hiciste en otro universo te has ayudado y ahora construiras algo más genial :)
Está perfecta tu explicación, desarrollé una app para android y partiendo desde tu explicación. mil gracias!!!!!
Me alegro de que el contenido te haya sido útil. Saludos!
Estaba buscando un canal referente al mk ultra y acabé aquí xd
Igual excelente vídeo, a pesar de que no sabía casi nada del tema le entendí bastante bien
De verdad gracias por explicarlo tan detalladamente, me ha servido mucho, en verdad que esto si es un contenido de muy alta calidad.
Muchas gracias! Me alegro de que el material te haya sido de utilidad.
Hola Juan,
En primer lugar déjame felicitarte por compartir tus conocimientos de manera tan didáctica e interesante como lo vienes haciendo por este medio, ya me he descargado todos tus videos (menos lo musicales jaja). Tengo las siguientes consultas y espero me puedas apoyar, realmente las necesito, aquí te las dejo:
1) En qué carrera se estudia todo esto a lo que corresponde en teoría de la información, pero con ese enfoque matemático? Es en una maestría? En un carrera de pregrado se aprende todo eso (lo dudo)? o eso ya se ve en estudios de postgrado? Te comento esto, pues mi formación universitaria es básicamente matemática (mi carrera se llama Computación Científica), pero tengo muchos estudios de networking (LINUX, CCNA, Seguridad en Sistemas de la Información, Sistemas de Fibra Optica). Me fascina el campo de las telecomunicaciones y trabajo en ella actualmente.
2) Quisiera especializarme en el Sector de las Telecomunicaciones. Por el momento vengo trabajando en empresas privadas por necesidad (y por estudiar más cursos); sin embargo, me fascina y me gustaría saber todo lo que enseñas, ese enfoque teórico y matemático, pero siempre aplicado a las telecomunicaciones, explicando los fenómenos, realmente me fascina eso!!! Después de lo dicho, qué me recomiendas?
3) Si tienes más videos, estaría muy agradecido que los puedas compartir, realmente apoyas enormemente a las personas que quieren aprender de raíz estas materias.
Un gran abrazo desde Lima Perú.
Emmanuel Aldo Valerio Suarez Hola Emmanuel,Me alegro de que el material te haya sido de utilidad! Paso a resolver tus preguntas:
1) Toda esta temática de teoría de la información la vemos en nuestra carrera de Ingeniería Telemática, que es de pregrado. Todo esto se ve en el curso de Comunicaciones Digitales.
2) Si quieres especializarte en esta parte de Teoría de la Información, puedes comenzar con este libro: Fundamentals of Information Theory and Coding Design, de Roberto Togneri y Christopher J.S. deSilva (Chapman & Hall). Tiene el suficiente rigor matemático que tú buscas (por tu formación), y a la vez, muestra las aplicaciones. Puedes también consultar el libro Digital Communications, de Sklar. Tiene algunos años, pero es prácticamente la "biblia" de las comunicaciones digitales.
3) Ya vi que te apuntaste a mi canal :) En la medida en que vaya grabando más videos, quedarán disponibles. Quisiera grabar muchos más, pero a ratos el tiempo no me alcanza...
Un fuerte abrazo desde Cali, Colombia!!
Juan, muchas gracias por explicar este algoritmo. Estaba intentando encontrar una explicación más clara y gracias a ti ya la tengo. Saludos!!!!
Con mucho gusto, Leonardo! :)
Hola, muchas gracias por tan detallada explicación. Saludos desde México.
Con mucho gusto! Me alegra que el material ta haya sido útil. Saludos desde Colombia!
Muchas gracias profesor, me ayudó mucho en mi exposición de metodos criptograficos :) saludos desde perú
Con mucho gusto! Me alegro de que el material te haya servido.
Muy buena explicacion, muchisimas gracias por ese excelente video
Me alegra que te haya sido útil. Saludos!
wow, esto realmente que es interesante, gracias por explicarlo tan detalladamente ! :)
Que grande!! Gracias por compartir este video.
Un saludo
Al toque mi rey gran video 10/10
Muchas gracias! Me alegra que el material te haya sido útil... saludos!
¡Excelente explicación! Me ayudó muchísimo, gracias.
Lucy Chaves Con mucho gusto! Me alegro de que el material te haya sido útil.
muy buen video me sirvio para la universidad
Me alegro de que te haya servido el material. Saludos!
Gracias por el video Juan. Al final como se codifica? No entiendo, porque en la salida hay valores que se repiten
Es normal que se presenten valores repetidos en la salida, al menos hasta que ingresen los patrones de uso común al diccionario. La codificación, en este ejemplo, queda como dice en la columna "Salida" del tablero. Existe ganancia en dos aspectos: Menos códigos de salida que caracteres de entrada (al introducir los patrones de uso común). Y cada código se puede representar con menos bits que los caracteres del alfabeto inicial.
Gracias,Excelente explicación, saludos desde medellin UdeA.
+Juan José Gallego Con mucho gusto Juan José, me alegro de que te haya sido útil. Saludos desde Cali!
sencillamente increible
Excelente explicación, muchas gracias
Excelente! muy bien explicado!
le quería preguntar si tal vez tiene alguno así de Huffman (Entropía y redundancia) y como saber si un código es óptimo o no? muchas gracias
Hola Andrés Felipe, me alegro de que el vídeo te haya sido útil. Para codificación de Huffman y eficiencia, revisa en este mismo canal el video del Módulo 3, clase 2.
Buenas noches, gracias por compartir el vídeo. Este algoritmo aplica para comprimir textos, imágenes... Tendiendo en cuenta que los vídeos son secuencias de imágenes, ¿este protocolo aplica para compresión de vídeo?
Hola Alejandro! Este algoritmo no aplica para compresión de video, por la complejidad que tienen los flujos de datos de este tipo. En los videos se puede lograr una mejor compresión empleando técnicas de redundancia temporal (es decir, ver qué cambia entre un cuadro y otro del video, y codificar solamente los cambios entre cuadros). Saludos!
Gracias por la respuesta!
Muchísimas gracias!!!
Me alegro que el material te haya sido de utilidad. Saludos!
BRILLANTE
No lo tengo tan claro, si necesitas guardar el diccionario y la combinación de caracteres además de la información de cuántos bits utilizas no veo la compresión. diccionario: (9 letras * 8 bits = 72) + composición: (18 números * 5 bits = 90) = 162 + cuantos bits usas para el diccionario, cuantos bits usas para la combinación de números + que parte es diccionario y que parte son datos...
Muy buen punto, Miguel! Este es, de hecho, un ejercicio de pensamiento que le pongo a mis estudiantes. El problema, en este caso, es que el texto a comprimir es muy corto. Si emisor y receptor no se han puesto de acuerdo en el diccionario inicial, transmitir el diccionario y el código comprimido pesa más que transmitir la frase original en ASCII. Con textos a comprimir más largos sí se ve el ahorro.
Sí, yo también lo he pensado. Además, aun olvidándonos del diccionario, el mayor ahorro está en los pocos caracteres diferentes que tiene la frase frente al total de códigos ASCII posibles, más que en la eficacia del propio algoritmo. Por supuesto entiendo que se trata de un ejemplo didáctico, pero creo que es necesario explicar la importancia del peso del diccionario pues, de otro modo, podría no comprenderse el sentido del algoritmo. Si el tamaño del diccionario no importara, podría pensar el alumno en un algoritmo mucho más eficaz: asignamos el código 0 a "COMPADRE NO COMO COCO". Nuestro archivo solo ocuparía 1 bit, y todavía nos sobraría un código para cualquier otra cosa; así que podemos asignar el código 1 a "En un lugar de la Mancha, de cuyo nombre no quiero acordarme..."
No quisiera que se me malinterpretara; el video me ha hecho comprender el algoritmo y por ello le estoy sumamente agradecido.
@@CivitateDei Al contrario, gracias a ti por mencionar estas cosas que son importantes, y que sirven para una nueva versión del video, o inclusive, para un pequeño video aclaratorio. Me alegro de que el material te haya servido como está, y como te digo, emplearé estas reflexiones para generar más material. GRACIAS!!
muy bueno algún libro
por favor que me recomiende
+luis yanque Para profundizar en el tema, puedes consultar "Digital Communications" de Bernard Sklar, o "Multimedia Comunications" de Fred Halsall.
GRACIAS! muy buen video. pero lo que necesito el el codigo en c++
Gracias!
Y el peso del diccionario? Se puede saber desde que punto es eficiente el algoritmo? Por ejemplo a partir de 1000 palabras el archivo comprimido pesa menos que el original
Depende mucho del tipo de datos y cantidad de datos que estés comprimiendo. Con un ejemplo tan corto como el que se ve en el video, la eficiencia del algoritmo no se ve. Con un texto de una página puedes comenzar a ver el efecto de la compresión. Para lenguaje natural, la relación de compresión es aproximadamente 1.8:1. Para textos en los que se repiten muchas palabras (tales como archivos de bitácora -log- o texto de programas) la relación puede subir a 2.5:1. En el caso de gráficos con áreas grandes de color sólido, la relación es aún mayor. El formato GIF, que emplea el algoritmo LZW, es sumamente eficiente para comprimir imágenes con una paleta limitada de colores.
gracias por tan buena explicación
Con mucho gusto! :)
¿por qué cuando wk no está en el diccionario se imprime sólo el código de w y luego se añade wk al diccionario? ¿No sería mejor imprimir directamente el nuevo código de wk?
Pienso probar esto en python mas tarde... :)
Jorge: El algoritmo LZW siempre va un paso por detrás en cuanto a usar los nuevos códigos que se ingresan al diccionario. Esto se hace así porque no hay garantía de que el código recién ingresado se vaya a emplear otra vez.
Creo que esa es la razón por la que los mortales tendríamos grandes dificultades para inventar un algoritmo de compresión, salvo idea feliz de inspiración divina. Yo también pensé eso, y creo que es lo que ofrece mayor resistencia para comprender el algoritmo. Si intentas hacerlo verás que conduce a un callejón sin salida porque conduciría a solapamientos en la impresión y códigos superfluos, y dejaría de haber un punto donde poner freno al crecimiento del código; la solución a esto sería fijar arbitrariamente el número de caracteres del código. O sea, tendríamos un algoritmo muy pobre que en realidad no comprimiría nada, sino que solo lo encriptaría, también pobremente.
Juan Manuel, hay algo que no logro comprender, por que "COMPADRE_NO_COMPRO_COCO" ocupa 184 bytes, mientras que "COMPADRE_NCOOMHPPAADDRREE__NNOO__CCOMMPRROO_CCOC" solo ocupa 5 bytes..
+Oscar Gonzalez En efecto, todo el diccionario no se puede representar con tan solo 5 bytes. Cada uno de los códigos de la tabla se representa con 5 bytes. La columna "Salida" contiene los códigos que realmente se transmiten. Haciendo el cálculo, se transmiten 18 códigos de 5 bytes cada uno, es decir, 90 bytes en total.
+Juan Manuel Madrid Muchas gracias, casi lo tengo... volveré a revisar ambos videos hasta comprender el 100%
Me puedo contactar con usted?
Seguro. Mi dirección de correo está en la info del canal.
Muchas gracias! :3
Muchas Gracias :)
Gracias por el video
Jin Chen Con mucho gusto! :)
excelente
can you speak in english ? and please upload a LZ77 and LZ78 techniques in english