Redundanz (Informationstheorie)
Der Begriff der Redundanz in der Informationstheorie gibt an, wie viel Information im Mittel pro Zeichen in einer Informationsquelle mehrfach vorhanden ist. Eine Informationseinheit ist dann redundant, wenn sie ohne Informationsverlust weggelassen werden kann. Das Identifizieren und Entfernen solcher Redundanzen heißt Deduplizierung.
Inhaltsverzeichnis |
Nachrichten- und Informationsübertragung
Redundant ist der Teil einer Nachricht, der keine weitere Information enthält, weil diese implizit oder explizit schon vorher in der Nachricht gegeben wurde. Die redundante Information ist jedoch eine Funktion der nichtredundanten Information. Beide bilden zusammen die Nachricht.
In der informationstechnischen und nachrichtentechnischen Anwendung wird Redundanz genutzt, um Defekte in einer Übertragung ausgleichen zu können. Daher ist Redundanz allenfalls in einem ungestörten Informationskanal überflüssig.
Fehlertoleranz
Eine Kommunikation lässt sich durch redundante Informationen fehlertolerant über einen Informationskanal durchführen, da unter Umständen verloren gegangene oder verfälschte Teilinformationen von dem Empfänger aus ihrem Kontext rekonstruiert werden können. Ein Maß für die Fehlertoleranz ist die Hamming-Distanz.
- Sei Alphabet Z, wobei z ∈ Z
- C(z) bezeichnet das zu z gehörende Codewort
- l(z) bezeichnet die Länge von C(z)
Die mittlere Codewortlänge L(C) eines Quell-Codes C(z) mit der Wahrscheinlichkeitsverteilung p(z) ist gegeben durch:
Redundanz eines Codes
Die Redundanz des Codes ist die Differenz zwischen mittlerer Codewortlänge L(C) und Entropie H(X). (Bsp.: Huffman-Kodierung für optimales(=minimales) L(C)).
Die Redundanz der Quelle ist die Differenz zwischen maximaler Entropie Hmax(X) = log2|Z| und der Entropie H(X) der Nachrichtenquelle.
Da die Codewortlänge nicht kleiner als die Entropie sein kann, ist die Redundanz nie negativ.
Codierung
In der Codierungstheorie werden zwei Erscheinungsformen der Redundanz unterschieden:
- Die Verteilungsredundanz liegt in dem unterschiedlich wahrscheinlichen Auftreten der einzelnen Zeichen des Alphabets.
- Die Bindungsredundanz liegt darin, dass nach bestimmten Zeichen das Auftreten eines bestimmten anderen Zeichens besonders wahrscheinlich ist. Beispielsweise folgt in einem deutschen Text auf ein q fast immer ein u.
Datenbanken und Datenstrukturen
In der Datenbankentwicklung sowie in Datenstrukturen von Programmen gilt es, Redundanzen möglichst vollständig zu vermeiden, da diese zu einem höheren Speicherplatzbedarf und zu Inkonsistenzen führen können. Redundanzen werden daher zu den Anomalien gezählt. Redundanzfreiheit gilt als Grundprinzip in Datenbanken.
Durch Normalisierung des Datenbankschemas können Redundanzen weitgehend vermieden werden. Es gibt auch Redundanzen, die unvermeidbar sind z. B. Schlüsselredundanzen und daher als notwendiges Übel in Kauf genommen werden. Es gibt auch Redundanzen, die in Kauf genommen werden, weil deren Vermeidung ein zu hoher Aufwand im Verhältnis zu ihrer Problematik darstellen würde, wie zum Beispiel das mehrfache Auftreten eines Attributwertes oder die doppelte Speicherung des Namens Müller für Herrn Müller und für Frau Müller.
Nachteile
In Datenstrukturen von Programmen und Datenbanken können Redundanzen zu Programmfehlern führen. Der Programmierer muss darauf achten, dass er bei allen Änderungen auch die redundanten Daten konsistent hält. Dies erfordert einen hohen Synchronisationsaufwand. Je größer das Projekt ist und je länger an dem Projekt entwickelt wird, desto schwieriger gestaltet sich dies. Wenn mehrere Programmierer unwissenderweise unabhängig voneinander an redundanten Daten arbeiten, so ist es fast unmöglich, die Änderungen konsistent zu halten.
Vorteile
Es gibt einige Fälle, in denen Datenredundanz die Rechenzeit der Software reduziert. Da aber die Nachteile schwer wiegen, soll der Entwickler Datenredundanz nur sehr selektiv und bei offensichtlichem Bedarf einsetzen. Zudem muss der Entwickler genau prüfen, ob das Programm häufiger Schreib- oder Lesezugriffe auf die redundanten Daten durchführt. Sollten häufiger Schreibzugriffe auf die Daten stattfinden, erhöht sich durch Datenredundanz die Rechenzeit.
Why are we here?
All text is available under the terms of the GNU Free Documentation License
This page is cache of Wikipedia. History