Zum Inhalt springen
L

Das Video kommt von YouTube: erst beim Abspielen verbindet sich die Seite mit YouTube (Google).

LZW Compression Explained | Step-by-Step Text Compression Tutorial

Baa Code Education3:33 7.226 Aufrufe veröffentlicht Auf YouTube

Das Wichtigste aus dem Video

Tipp auf eine Zeit – das Video springt genau dorthin.

Transkriptautomatisch erstellt · 20 Zeilen
Herunterladen
  1. Let me explain how to compress text using LZW compression and decompression. The basic idea of LZW compression is to turn repeated patterns into shorter
  2. codes. Let's start. I'll compress this text. Pikachu pinches Pirisu. We start by initializing a table. The
  3. first step is to fill the table with all the characters that appear in the original text and assign an index to each character. For now, keep the output
  4. column blank. We start from the beginning with P. P is already in the dictionary. So, we concatenate it with the next character, which is I. If the
  5. new pattern exists in the dictionary, that means it's already encoded. In this case, pi is not in the dictionary. So, we output the code for P, which is zero.
  6. This zero refers to the index of P in the dictionary. Now, we are at I. Just like before, I is in the dictionary. So we combine it with
  7. the next character K. I K doesn't exist in the dictionary. So we output the code for I which is one and add I K to the dictionary with a new
  8. index. Let's pause for a moment and talk about why we output zero for a pi and how this eventually leads to compression.
  9. Imagine we have the text ab. we combine it with B to form AB. Since AB isn't in the dictionary yet, we
  10. add AB to the dictionary with a new index and output the code for A, which is zero. At this point, we haven't actually compressed anything yet. We're
  11. just preparing for future repeats. Next, we see B. Same process here. Add BA to the dictionary and output the code for B, which is one. Now we encounter AB
  12. again. This time it's already in the dictionary. So instead of two separate codes for A and B, we output its new code three. We also add ABC to the
  13. dictionary for possible future repeats. So after compression, the text ab becomes 0132. That's where the real compression
  14. happens when repeated patterns get replaced by a single code. Now we at K we do same process. Combine K with A.
  15. K. A does not exist in dictionary. So we output end code for K. Continue this process with same rule.
  16. Here's where it gets interesting. We're at P and the next character is I. PI already exists in the dictionary. So instead of stopping we extend it by
  17. adding the next character which is n. Pin does not exist in the dictionary. So we output the code for pi which is 11 and then add pin to the dictionary with
  18. a new index. From here, we just repeat the same steps until the entire text is processed.
  19. Now the encoding is complete and our text is fully compressed. Elzw compression works even more efficiently when the text is longer and has more
  20. repeating patterns. In the next video, I'll explain the decoding process step by step. I'll put the link in the description. Thank you for watching.

Zum Nachlesen

Lempel-Ziv-Welch-AlgorithmusDer Lempel-Ziv-Welch-Algorithmus (kurz LZW-Algorithmus oder LZW genannt) ist ein häufig bei Grafikformaten zur Datenkompression, also zur Reduzierung der … DatenkompressionDatenkomprimierung [1] genannt – ist ein Vorgang, bei dem die Menge digitaler Daten reduziert wird. Dadurch sinkt der Speicherbedarf, Huffman-KodierungDie Huffman-Kodierung ist eine Form der Entropiekodierung, die 1952 von David A. Huffman entwickelt und in der Abhandlung A Method for the Construction of … LauflängenkodierungDie Lauflängenkodierung (englisch run-length encoding, kurz RLE), auch die Lauflängencodierung, ist ein einfacher verlustfreier Kompressionsalgorithmus.