Komprimieren mit Huffman

Lege darin die Datei huffman.rb an:

# Huffman-Codes: häufige Bytes bekommen kurze Codes, seltene lange.
#
# Ein Baum ist entweder ein Blatt, das Byte selbst (eine Zahl), oder ein
# Knoten, ein Array [links, rechts]. Links steht für 0, rechts für 1.

# Wie oft jedes Byte vorkommt: {65 => 5, 66 => 2, ...}
def frequencies(data)
end

# Immer die beiden leichtesten Bäume zusammenfassen, bis einer übrig ist.
def build_tree(counts)
end

# Der Code jedes Bytes als String aus 0 und 1: {65 => '0', 66 => '10', ...}
def code_table(tree)
end

# Der ganze Text als String aus 0 und 1
def encode(data, table)
end

# Aus den Bits und dem Baum wieder die Bytes
def decode(bits, tree)
end

p frequencies('ABRACADABRA')

Lege darin die Datei huffman.py an:

# Huffman-Codes: häufige Bytes bekommen kurze Codes, seltene lange.
#
# Ein Baum ist entweder ein Blatt, das Byte selbst (eine Zahl), oder ein
# Knoten, ein Tupel (links, rechts). Links steht für 0, rechts für 1.


def frequencies(data):
    """Wie oft jedes Byte vorkommt: {65: 5, 66: 2, ...}"""


def build_tree(counts):
    """Immer die beiden leichtesten Bäume zusammenfassen, bis einer übrig ist."""


def code_table(tree):
    """Der Code jedes Bytes als String aus 0 und 1: {65: '0', 66: '10', ...}"""


def encode(data, table):
    """Der ganze Text als String aus 0 und 1"""


def decode(bits, tree):
    """Aus den Bits und dem Baum wieder die Bytes"""


print(frequencies(b'ABRACADABRA'))

b'ABRACADABRA' sind Bytes, keine Zeichen; alle Methoden bekommen und liefern Bytes.

Schreib frequencies. Es gibt einen Hash zurück, der für jedes Byte des Texts sagt, wie oft es vorkommt.

Schreib frequencies. Es gibt ein dict zurück, das für jedes Byte des Texts sagt, wie oft es vorkommt.

• data.each_byte { |byte| … } geht die Bytes durch, als Zahlen.
• Hash.new(0) ist ein Hash, der für jeden Schlüssel, den es noch nicht gibt, 0 liefert. Damit kannst du gleich counts[byte] += 1 schreiben.

• for byte in data: geht die Bytes durch, als Zahlen.
• counts.get(byte, 0) liefert 0, wenn es das Byte noch nicht gibt. Damit kannst du gleich counts[byte] = counts.get(byte, 0) + 1 schreiben.

Schreib build_tree nach den drei Schritten von oben. Ein Blatt ist das Byte selbst, eine Zahl; ein Knoten ist ein Array aus seinen beiden Kindern. Für »ABRACADABRA« könnte der Baum so aussehen: [65, [[67, 68], [66, 82]]].

Schreib build_tree nach den drei Schritten von oben. Ein Blatt ist das Byte selbst, eine Zahl; ein Knoten ist ein Tupel aus seinen beiden Kindern. Für »ABRACADABRA« könnte der Baum so aussehen: (65, ((67, 68), (66, 82))).

• Beim Bauen brauchst du zu jedem Baum sein Gewicht. Halte deshalb eine Liste von Paaren [weight, tree], am Anfang eines für jedes Byte.
• sort_by! { |weight, _| weight } sortiert die Liste nach dem Gewicht, shift nimmt das erste Element heraus. Zweimal shift nach dem Sortieren gibt dir die beiden leichtesten.
• Am Ende ist ein einziges Paar übrig, und sein Baum ist das Ergebnis.

• Beim Bauen brauchst du zu jedem Baum sein Gewicht. Halte deshalb eine Liste von Paaren (weight, tree), am Anfang eines für jedes Byte.
• trees.sort(key=lambda pair: pair[0]) sortiert die Liste nach dem Gewicht, trees.pop(0) nimmt das erste Element heraus. Zweimal pop(0) nach dem Sortieren gibt dir die beiden leichtesten.
• Am Ende ist ein einziges Paar übrig, und sein Baum ist das Ergebnis.

Dann code_table: Es geht den Baum von oben durch und merkt sich den Weg. Am einfachsten ist das mit einer Methode, die sich selbst aufruft, für das linke Kind mit einer 0 mehr im Weg, für das rechte mit einer 1. Kommt sie an ein Blatt, also an eine Zahl (tree.is_a?(Integer)), ist der Weg bis dorthin der Code dieses Bytes. Eine Methode darf dafür weitere Parameter mit Standardwerten haben, etwa def code_table(tree, prefix = '', table = {}).

Dann code_table: Es geht den Baum von oben durch und merkt sich den Weg. Am einfachsten ist das mit einer Funktion, die sich selbst aufruft, für das linke Kind mit einer 0 mehr im Weg, für das rechte mit einer 1. Kommt sie an ein Blatt, also an eine Zahl (isinstance(tree, int)), ist der Weg bis dorthin der Code dieses Bytes. Eine Funktion darf dafür weitere Parameter mit Standardwerten haben, etwa def code_table(tree, prefix=''); table.update(…) nimmt die Einträge eines anderen dict dazu.

encode ist kurz: Für jedes Byte der Code aus der Tabelle, alle hintereinander. join hängt eine Liste von Strings aneinander.

encode ist kurz: Für jedes Byte der Code aus der Tabelle, alle hintereinander. ''.join(…) hängt Strings aneinander.

decode liest die Bits einzeln und geht dabei im Baum nach unten, bei 0 nach links (node[0]), bei 1 nach rechts (node[1]). Kommt es an ein Blatt, hat es ein Byte gefunden, merkt es sich und beginnt wieder oben. Wie bei LZW macht pack('C*') am Schluss aus den Zahlen einen String. Denk auch hier an den Baum, der nur ein Blatt ist.

decode liest die Bits einzeln und geht dabei im Baum nach unten, bei 0 nach links (node[0]), bei 1 nach rechts (node[1]). Kommt es an ein Blatt, hat es ein Byte gefunden, merkt es sich und beginnt wieder oben. Wie bei LZW macht bytes(…) am Schluss aus den Zahlen Bytes. Denk auch hier an den Baum, der nur ein Blatt ist.

File.binread('spec-gif89a.txt') liest sie Byte für Byte. Lass dein Programm ausgeben, wie viele Bits encode daraus macht, und probier gleich, ob decode die Datei wieder genau herausgibt.

open('spec-gif89a.txt', 'rb').read() liest sie als Bytes; das b in 'rb' ist wichtig. Lass dein Programm ausgeben, wie viele Bits encode daraus macht, und probier gleich, ob decode die Datei wieder genau herausgibt.

Schreib canonical(lengths): Es bekommt einen Hash mit der Länge jedes Bytes und gibt einen Hash mit den kanonischen Codes zurück, als Strings aus 0 und 1. code.to_s(2) schreibt eine Zahl als Binärzahl, rjust(length, '0') füllt vorn mit Nullen auf, und << schiebt eine Zahl nach links, hängt also hinten Nullen an: 0b10 << 1 ist 0b100.

Schreib canonical(lengths): Es bekommt ein dict mit der Länge jedes Bytes und gibt ein dict mit den kanonischen Codes zurück, als Strings aus 0 und 1. format(code, 'b') schreibt eine Zahl als Binärzahl, rjust(length, '0') füllt vorn mit Nullen auf, und << schiebt eine Zahl nach links, hängt also hinten Nullen an: 0b10 << 1 ist 0b100. sorted(lengths.items(), key=lambda item: (item[1], item[0])) sortiert nach Länge und dann nach Byte.

• Bits packen: Schreib encode so um, dass es echte Bytes liefert, mit [bits].pack('B*'), und decode passend dazu. Wie erkennt decode, wo die Bits zu Ende sind, wenn das letzte Byte nicht voll ist?

• Bits packen: Schreib encode so um, dass es echte Bytes liefert, mit int(bits[i:i + 8].ljust(8, '0'), 2) für je 8 Bits, und decode passend dazu. Wie erkennt decode, wo die Bits zu Ende sind, wenn das letzte Byte nicht voll ist?