Filter: 2013

Lauflängenkodierung

Bei vielen Kompressionsarten kommt, als Filter, die Lauflängenkodierung zum Einsatz. Sie ist sehr einfach, sehr schnell aber auch sehr spezialisiert, da bei ihr gleiche aufeinander folgende Symbole zusammengefasst werden. Diese Kodierung ist anzutreffen bei vielen Grafikformaten (inklusive JPEG).

Beispiel (Quellcode): rle.cpp
Download (Quellcode): rle.zip

Beschreibung

Lauflängenkodierung Schaubild Wie schon erwähnt, werden gleiche aufeinander folgende Symbole zusammengefasst. Dies geschieht oft durch einen Marker, ein Spezialsymbol oder durch eine andere Art von Metadaten innerhalb des Ausgabedatenstroms. Bei Kodierungsverfahren mit Codewörtern, lassen sich extra Codes verwenden. Die Länge der Symbolwiederholungen, die benötigt wird, um eine Datenkompression zu erreichen hängt vom Kodierungsverfahren ab. Bei einfachsten Implementationen, lohnt sich der Aufwand oft erst, wenn mindestens vier oder fünf gleiche aufeinander folgende Symbole möglich sind.

Wie bei eigentlich allen Kompressionsverfahren, kann auch bei RLE unter Umständen ü…

BCD-Konvertierung

Obwohl die binärkodierte Dezimalzahl in der Regel nicht mehr für Protokolle und Datenspeicherungen verwendet wird, sind ihre Auswirkungen heute spürbar. Alle paar Jahre tauchen, in den Nachrichten, Fälle von gestörten Systemen auf, die plötzlich ein falsches Datum haben oder Geldbeträge falsch lesen/schreiben. Hier ist direkt zu sehen, wo BCD noch immer (vor allem durch die Kompatibilität zu älteren Systemen) verwendet wird. Zum Beispiel Datumszähler im CMOS-RAM, Geburtsdaten, in Transferprotokollen zwischen Bezahlgeräten oder zur Speicherung von Zugangsberechtigungsnummern.

Leider ist immer wieder zu sehen, dass die Konvertierung in native Zahlenformate über Umwege (oder mehrere Konvertierungen) gemacht wird. Das muss natürlich nicht sein.

Beispiel (Quellcode): bcd.cpp
Download (Quellcode): bcd.zip

Beschreibung

BCD-Aufbau Bei BCD wird jede Dezimalziffer des Wertes für sich gespeichert und zwar binär von Null bis Neun. Da hierfür nur maximal 4 Bit benötigt werden, wird oft die gepackte Variante von BCD eingesetzt.…

Hashtabelle

Hashtabellen finden sehr oft ihren Weg in Anwendungen, bei denen es wichtig ist, bei einer relativ konstanten Laufzeit, Datensätze mit Hilfe eines Schlüssels zu finden.

Beispiel (Quellcode): hashtable.cpp
Download (Quellcode): hashtable.zip

Beschreibung

Hashtabellenübersetzung Die Funktion einer Hashtabelle ist sehr einfach. Die Schlüsselwerte werden mit einer Konvertierungsfunktion (Hashfunktion) in einen Wert gewandelt, der direkt als Index für ein Datenfeld benutzt wird. Durch die Verringerung des Schlüssels auf einen kleineren Wertebereich, kann es zu Kollisionen kommen. Das heißt auch, dass die Werte keine eindeutige Referenz für den Schlüssel sind. Somit muss, in der Designphase des Endproduktes, schon drauf geachtet werden, wie mit Kollisionen umgegangen werden soll. Da gibt es gleich einen ganzen Schwung an Möglichkeiten:

  1. Ignorieren. Je nach Bedarf der Anwendung, kann der neue Schlüssel wichtiger sein als ein Älterer, z.B. oft bei Kompressionssuchbäumen oder statistischen Daten.

  2. Datenfeld erweitern. Um die Kollisionen…

Fragmentiertes Datenfeld

Fragmentierte Datenfelder, also Datenfelder mit leeren Feldern, können je nach Aufgabengebiet auftreten. Wenn die Möglichkeit nicht besteht, das Feld durch verwerfen der leeren Zellen, zu verdichten, aber die leeren Felder wiederbenutzt werden soll, kann das hier beschriebene System helfen. Natürlich können leere Felder immer mit einer linearen Suche auf dem Datenfeld gefunden werden. Das lineare Verfahren hat aber seine Schwächen, spätestens bei großen Datenfeldern könnte die Suchzeit für sinnvollere Aufgaben verwendet werden.

Beispiel (Quellcode): fragmentedobjectallocator.cpp
Download (Quellcode): fragmentedobjectallocator.zip

Beschreibung

Wenn aus einem fragmentierten Datenfeld ein Feld gelöscht wird, kann dessen Index in eine Warteschlange oder einen Stapelspeicher geschrieben werden. Beim Anfordern eines neuen Feldes, wird nur der letzte Eintrag aus diesem Stapelspeicher zurückgegeben. Da beim Start noch kein Feld angefordert wurde und eine Ersterstellung des kompletten Stapels riesen Arbeit wäre, k…

Bereichskodierung / Rangecoder

Die Bereichskodierung ist, neben der Huffman-Kodierung, eine mittlerweile häufig anzutreffende Entropiekodierung. Sie ist einfach zu realisieren, kommt der theoretischen Entropie näher, ist aber etwas langsamer. Vor allem in Szenarien mit starken dynamischen oder extremen Symbolwahrscheinlichkeiten macht sich diese Kodierung bezahlt. Im Gegensatz zur Huffman-Kodierung ist die Untergrenze von einem Bit pro Symbol in der Ausgabe aufgehoben, so dass rein vom Betrachter aus, mehr als ein Symbol pro Bit gespeichert werden kann. Dieses Verfahren wird z.B. bei LZMA/7Zip, PPM, PAQ und bei sehr vielen aktuellen Audio-/Videokompressionen eingesetzt.

Beispiel (Quellcode): rangecoder.cpp
Download (Quellcode): rangecoder.zip

Beschreibung

Teil der Bereichskodierung ohne Ausgabe/Arithmetische Kodierung Eine Bereichskodierung ist eine Art der arithmetischen Kodierung, jedoch wird nur mit einem Ausschnitt des Ausgabewertes gerechnet. Die arithmetische Kodierung besitzt einen Ausgabewert und den Bereichswert. Der Ausgabewert ist mit Null initialisiert und der Wert, der später in die A…