Filter: 2013-09

Die Speicherung von Ganzzahlen kann, je nach Datentypgröße viel Platz auf dem Datenträger oder im Speicher in Anspruch nehmen. Werden aber hauptsächlich kleine Werte erwartet, zum Beispiel bei Deltaeinträgen, ist der Großteil des Wertes nicht belegt. Hier springt diese Art der Kodierung ein und versucht die Werte soweit es geht zu kürzen.

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

Beschreibung

Die Ganzzahl wird in Teile (meist) gleicher Größe aufgeteilt. Alle oberen Teile die keine Bits gesetzt haben werden nicht in die Ausgabe geschrieben. Alle Teile, bis auf den Letzten, bekommen einen Marker, dass der nachfolgende Teil nicht das Ende darstellt. Häufig werden die Zahlen in 7-Bit Teile gebrochen und mit übrigen Bit des Ausgabebytes markiert.

Es gibt hier allerdings viele Varianten, die häufigsten Unterscheidungen sind:

• Richtung
  • höherwertiger Teil zuerst
  • niederwertiger Teil zuerst
• Position des Markers im Ausgabebyte
• Vorzeichenbehandlu…

Die Huffman-Kodierung stellt neben der arithmetischen Kodierung bzw. der Bereichskodierung eine der häufigsten Formen der Entropiekodierung dar. Es wird und wurde vor allem, wegen der hohen Geschwindigkeit in älteren Kompressionsverfahren eingesetzt, von ZIP/Deflate über RAR bis hin zu JPEG. Allerdings gibt es auch einen kleinen Nachteil: Die Kodierung erreicht nicht immer die theoretische Entropie, da sie nur auf Bitbasis arbeitet.

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

Beschreibung

Diese Art der Kodierung, errechnet mit Hilfe der Symbolauftrittswahrscheinlichkeiten (oder auch Häufigkeiten), einen möglichst kurzen und eindeutigen Code. Kommt ein Symbol häufiger vor, wird es durch einen kürzeren binären Code ausgedrückt. Werden nicht alle Symbole des Alphabets benötigt, fließen diese nicht weiter in die Bearbeitung ein. Grundsätzlich kann unterschieden werden zwischen statischer, dynamischer und adaptiver Huffman-Kodierung. Die statische hat festgelegte Symbolhäufigkeiten, die…

Radixsort ist eine Sortierungsmethode, die Schrittweise anhand von Schlüsselwertteilen, über einen oder mehrere Sortieralgorithmen, das Eingangsfeld ordnet. Jeder Sortierungsschritt muss stabil sein, d.h. die Elementereihenfolge muss im sortierten Fall gleich bleiben. Am häufigsten wird hier Countingsort verwendet. Die Laufzeit hängt von der Anzahl der Sortierungsschritte und den gewählten Algorithmen ab.

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

Transformation

• Ganzzahlen

  Durch die Aufteilung des Schlüsselwertes, hat der darunterliegende Sortieralgorithmus keine Information, ob es sich um positive oder negative Zahlen handelt. Dies kann leicht durch hinzufügen eines Basiswertes geändert werden. Der Basiswert kann auch der kleinste Schlüsselwert sein und kann dann von allen Schlüsselwerten abgezogen werden.

• Fließkommazahlen

  Da Fließkommazahlen einen Exponenten und ein Vorzeichenbit haben, muss hier mit Vorsicht gearbeitet werden. Die Zahl selbst kann als entsprechend große…

Countingsort (Sortierung durch Zählung) ist eine Sortierungsmethode, die ohne Vergleiche funktioniert. Sie kann je nach zu sortierendem Typen und sehr viel schneller sein als Mergesort sein. Es ist aber in der normalem Implementation nötig ein Eingangs-, ein Ausgangsfeld sowie ein Hilfsfeld zu erstellen. Der Algorithmus ist besonders effektiv bei kleinen Wertebereichen der Eingangswerte, im Verhältnis zur Eingangsfeldgröße. Er funktioniert normalerweise nur mit Ganzzahlwerten, kann aber auch für andere Typen mit einer entsprechenden Transformation der Daten benutzt werden. Dieses wird näher beim Radixsort erläutert.

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

Häufigkeitsaufnahme

Zu Beginn wird ein Zählfeld erstellt, welches die Größe des erwarteten Wertebereiches besitzt. Die Zähler werden mit Null initialisiert. Nun wird der entsprechende Zähler, mit dem Index des Eingangswertes, im Zählfeld erhöht. Kurz gesagt, die Häufigkeitsverteilung wird aufgenommen.

Da dieses Zähl…

Ein recht interessanter, nicht direkt offensichtlicher Fehler, kam mir vor einiger Zeit unter die Finger. Hierzu ein Stück Code:

class CMyVariant
{
public:
    CMyVariant();
    virtual ~CMyVariant();
 
    // Getter & Setter
 
protected:
    union
    {
        int64_t nTime;
        float fValue;
    };
};
 
int main()
{
    CMyVariant v1;
    ...
    // Variant v1 setzt nTime
    ... 
    CMyVariant v2 = v1;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

Auswirkungen

Die Klasse soll einen Variant-Datentypen darstellen, der zum Transport von Werten über Netzwerke und innerhalb von Anwendung benutzt werden kann. Der Wert nTime hält eine Zeit in Millisekunden, dieser sollte die aktuelle Uhrzeit tragen, war jedoch ca. alle 24 Tage um 70 Minuten versetzt. Wie dass?

Analyse

Da es eine Regelmäßigkeit gibt, die scheinbar mit der Zeit zusammenhängt, lassen sich die Werte gut zurückrechnen (in Millisekunden):

• 70 Minuten = 4200000 Millisekunden = 0x00401640
• 24 Tage = 2073600000 Millisekunden…