Stundenprotokoll
In der letzten Stunde haben wir viele Komprimierungsprogramme (wie z.B GIF) kennengerlernt. Als „Hausübung“ sollten wir auf die RLE Komprimierung und die LZW Komprimierung näher eingehen.
RLE – Komprimierung:
(Run Length Encoding) ist eine Lauflängenkodierung die zur verlustfreien Datenkomprimierung verwendet wird. Meist wird sie zum Komprimieren von Rastergrafiken verwendet wie zum Beispiel bei Bitmaps.
Meist zu komprimieren von Rastergrafiken
Ist eine Lauflängenkodierung
Reversibel–> verlustfrei
Diese Komprimierung verläuft folgendermaßen:
Die RLE Komprimierung fast alle gleichen Zeichen (des Klartextes) zusammen womit es zur Verkleinerung der Datei kommt. Es wird nur die Anzahl der folgenden Glieder abgespeichert.
.Zum Beispiel: AAAAAABBBCCDDDDDDDDDD –> 6A3B2C9D
LZW – Komprimierung:
=(Lempel-Ziv Welch-Algorithmus)
Algorithmus 1978 von Abraham Lempel und Jacob Ziv entwickelt und veröffentlicht.
LZW ist der bekannteste Vertreter der “LZ-Familie
verlustfreies Komprimierungsverfahren und kann bei fast allen Grafikformaten verwendet werden (z.B bei Gif`s)
Diese Komprimierung verläuft folgendermaßen:
Mittels Wörterbücher werden die häufigsten Zeichen zusammengefasst. Der Decoder hat keine Probleme die vollständige Datei wieder herzustellen. Die in das Wörterbuch eingetragenen Zeichen (das jedoch selbst keinen Speicherplatz benötigt) werden über einen 12 bit langen Index gemacht, womit maximal 212( = 4096) Einträge möglich sind.
Weitere Einträge werden generiert indem der gefundene Eintrag plus dem nächsten Zeichen gespeichert wird.
Aus der nachstehenden Tabelle kann man dann eine Zahlenfolge erkennen, die beim Entschlüsseln wieder den gegebenen Text komplett widerherstellen kann. Somit ist dieser Vorgang reversibel und der Klartext verlustfrei wieder zu bekommen.
Da die Aufgabenstellung so gewählt wurde, dass man die beispiele selbst lösen sollte habe ich es (jedoch anhand des Beispiels im Wiki )selber versucht.
Das kam dabei raus:
|
Zeichenkette |
gefundener Eintrag |
Ausgabe |
|
|
SEESPEF12DWYRALFB2 |
S |
S |
SE <256> |
|
EESPEF12DWYRALFB2 |
E |
E |
ED <257> |
|
DSPF12DWYRALFB2 |
D |
D |
DS <258> |
|
SPEF12DWYRALFB2 |
S |
S |
SR <259> |
|
REF12DWYRALFB2 |
RQ <257> |
<257> |
RF<260> |
|
F12DWYRALFB2 |
F |
F |
F1 <261> |
|
12DWYRALFB2 |
12 <261> |
<261> |
12P <262> |
|
PWYRALFB2 |
P |
P |
PW <263> |
|
WYRALFB2 |
WY <259> |
<259 |
WYA <264> |
|
ALFB2 |
A |
A |
AC <265> |
|
CVFB2 |
C |
C |
CV <266> |
|
VFB2 |
V |
V |
VB <267> |
|
BB2 |
B |
B |
- |
Bisher keine Kommentare
Hinterlasse eine Antwort
