Fundamentale Ideen der Informatik

Stefan Franke

Fundamentale Ideen der Informatik

Datenkompression

Übersicht

Verlustfreie Kompression
- Codes mit variabler Wortlänge
- Lauflängen-Codierung
- Differenzcodierung
- LZW-Algorithmus
Verlustbehaftete Kompression (Datenreduktion)

Datenkompression – warum?

Daten sollen möglichst effizient gespeichert und übertragen werden:
- Datenmenge möglichst gering halten
- Übermittlungszeit reduzieren
- Speicherplatz sparen
Beispiel: Tar o. Zip zur Kompression von Dateien

Allgemeiner Ablauf

Umgang mit komprimierten Daten

Beispielscript zum Entpacken in PHP


				<?php
				$file = 'homepage.zip';
				$path = pathinfo(realpath($file), PATHINFO_DIRNAME);
				$zip = new ZipArchive;
				$res = $zip->open($file);
				if ($res === TRUE) {
					$zip->extractTo($path);
					$zip->close();
					echo "Glueckwunsch! $file wurde erfolgreich nach $path exportiert.";
				} else {
					echo "Die Datei $file konnte nicht gefunden/geoeffnet werden.";
				}
				?>

Was macht das PHP-Script?

📁 Verzeichnis: /var/www/html
- entpacken.php (führt das Script aus)
- homepage.zip (die zu entpackende Datei)
📦 Aktion: homepage.zip wird geöffnet
📂 Entpackt nach: /var/www/html (aktuelles Verzeichnis)
✅ Erfolgreich: „Glückwunsch! ... wurde erfolgreich exportiert.“

❌ Fehler: „Die Datei ... konnte nicht geöffnet werden.“

Arten der Datenkompression

Verlustfreie Datenkompression

Dekodierte Daten unterscheiden sich nicht von den Originaldaten
Anwendung:
- Wenn der Verlust einzelner Bits die Qualität des Originals wahrnehmbar verändert
- Z. B. Texte, Tabellen

Verlustbehaftete Datenkompression

Ein Teil der Information geht bei der Kompression verloren
Dekodierte Daten unterscheiden sich von den Originaldaten
Anwendung:
- Qualitative Lücken in der menschlichen Wahrnehmung werden ausgenutzt: Bilder, Audio, Video
- Messdaten

VERLUSTFREIE KOMPRESSION

Verlustfreie Kompression

Forderungen:
- Alle Informationen müssen erhalten bleiben
- Informationen möglichst dicht packen
Analogie: Koffer packen

Merkmale:

Alle Gegenstände werden eingepackt
Möglichst wenig Zwischenraum lassen
Größe hängt davon ab, welche Arten von Gegenständen eingepackt werden

Ziel:
Koffer soll möglichst klein und kompakt gepackt werden

Generelles Ziel: Redundanz reduzieren

Redundanz:
- Informationen, die in einer Nachricht mehrfach vorkommen
- Informationen, die ohne Informationsverlust weggelassen werden können
Konkurrierende Ziele:

Komprimierung

Ziel: Redundanz in den Daten möglichst gering halten

↔

Fehlertoleranz

Redundante Daten unterstützen Fehlererkennung und Fehlerkorrektur

Redundanz am Beispiel von HTML-Code

index.html


				<html>
				<body>
				  <h1 style="font-family: Arial; font-size: 30px; color: red;">Wartungsseite</h1>
				  <p style="font-family: Arial; font-size: 16px; color: black;">Diese Homepage wird erstellt von Name</p>
				  <h2 style="font-family: Arial; font-size: 24px; color: orange;">Bitte habe noch etwas Geduld, die Homepage befindet sich noch in der Entstehung</h2>
				  <p style="font-family: Arial; font-size: 16px; color: black;"><a href="kontakt.html">Hier könnt ihr mich</a></p>
				</body>
				</html>

kontakt.html


				<html>
				<body>
				  <h1 style="font-family: Arial; font-size: 30px; color: rgb(0, 21, 255);">Kontaktseite</h1>
				  <p style="font-family: Arial; font-size: 16px; color: black;">Feedback oder Verbesserungsvorschläge zu meine Homepage? Dann melde dich bei mir:</p>
				  <h2 style="font-family: Arial; font-size: 24px; color: orange;">dummy@email.de</h2>
				  <p style="font-family: Arial; font-size: 16px; color: black;">Danke für dein Feedback :)</p>
				</body>
				</html>

Beispiel HTML-Code / CSS

CSS:

Selektor { Eigenschaft : Wert ; }

‘stylesheet.css‘ für unser Beispiel:

p { font-family: Arial; font-size: 16px; color: black; }

‘stylesheet.css‘ formatiert:


					  p {

					    font-family: Arial;

					    font-size: 16px;

					    color: black;

					  }

Beispiel HTML-Code / CSS

HTML aufräumen:


							<html>

							<body>


							  <h1>Überschrift</h1>

							  <p>Erster Absatz</p>

							  <h2>Zweite Überschrift</h2>

							  <p>Zweiter Absatz</p>


							</body>

							</html>

Die „stylesheet.css“-Datei enthält diesen Code:


							p {

							  font-family: Arial;

							  font-size: 16px;

							  color: black;

							}



							h1 {

							  font-family: Arial;

							  font-size: 30px;

							  color: red;

							}



							h2 {

							  font-family: Arial;

							  font-size: 24px;

							  color: orange;

							}

Beispiel HTML-Code / CSS

externes Stylesheet laden:


						<html>

						  <head>

						    <link rel="stylesheet" href="stylesheet.css">

						  </head>

						  <body>


						    <h1>Überschrift</h1>

						    <p>Erster Absatz</p>

						    <h2>Zweite Überschrift</h2>

						    <p>Zweiter Absatz</p>


						  </body>

						</html>

Aufgabe 1: (im Anschluss)

Erstellen Sie die CSS-Datei.
„Räumen“ Sie die index.html und kontakt.html auf.
Verknüpfen Sie das externe Stylesheet in den HTML-Dateien.
Individualisieren und passen Sie die .html und .css Dateien leicht an.

Ansätze zur verlustfreien
Datenkompression

Codes mit variabel langen Codewörtern
- Morse-Code
- Huffman-Codierung
Lauflängen-Codierung
Differenzcodierung
Arithmetische Codierung
LZW-Algorithmus

Codes mit variabler Wortlänge

Codierungen mit einer festen Wortlänge werden als Block-Codes bezeichnet
- z. B. ASCII-Code: feste Wortlänge von 7 bzw. 8 Bit
Codes mit variabler Wortlänge basieren darauf, dass häufig auftretende Zeichen mit einer kürzeren Bitfolge dargestellt werden: statistische Datenkompression

Beispiel: Morse-Code

Im Morsealphabet werden die Zeichen durch kurze und lange Symbole dargestellt.
Pausen als drittes Symbol trennen die einzelnen Zeichen

Herold et al. (2017): Grundlagen der Informatik

Fano-Bedingung für die
Dekodierbarkeit eines Codes

Codes mit variabler Wortlänge müssen für die Dekodierbarkeit folgende Bedingung erfüllen:

Ein Code erfüllt die Fano-Bedingung, wenn kein Wort aus dem Code der Anfang eines anderen Wortes ist.

Codes, die die Fano-Bedingung erfüllen, nennt man präfixfreie Codes.

Welche Codes erfüllen die
Fano-Bedingung?

Welche Codes erfüllen die
Fano-Bedingung?

Huffman-Algorithmus

Wurde 1952 von dem amerikanischen Mathematiker A. Huffman entwickelt
Effektivste Methode, um die Redundanz in einem Code für Einzelzeichen zu minimieren
Grundidee:
- Die Zeichen eines Texts, die häufig auftreten, werden in kurzen Codewörtern codiert.
- Der Code ist präfixfrei (s. Fano-Bedingung)
- Der Code wird über einen Code-Baum erzeugt