6.2. Projekt

6.2.1. Implementierung von Beispiel-Algorithmen

6.2.1.1. Run-Length Encoding

Funktionsweise:

Zunächst werden alle Wiederholungen gesucht, also Sequenzen mit aufeinanderfolgenden, identischen Zeichen. Für jede Gruppe gleicher aufeinanderfolgender Zeichen wird die Anzahl der Wiederholungen gezählt. Anschließend wird statt jedes einzelnen Zeichens nur das Zeichen und die Anzahl an Wiederholungen notiert.

def rle_compress(data):
    """Compress the input data using Run-Length Encoding."""
    compressed_data = []
    i = 0

    while i < len(data):
        # Count occurrences of the same character
        count = 1
        while i + 1 < len(data) and data[i] == data[i + 1]:
            count += 1
            i += 1
        # Append the character and its count to the compressed data
        compressed_data.append((data[i], count))
        i += 1

    return compressed_data

Fazit:

Die LRE-Komprimierung bietet einige Vorteile, darunter ihre einfache Implementierung und ihr Verständnis. Sie ist besonders effektiv bei der Komprimierung von Daten mit vielen aufeinanderfolgenden gleichen Zeichen und erfordert daher einen geringen Speicherbedarf für diese Art von Daten. Die Dekomprimierung von LRE-kodierten Daten ist ebenfalls sehr einfach und schnell.

Allerdings hat die LRE-Komprimierung auch einige Nachteile. Sie ist bei Daten, die wenige Wiederholungen oder viele unterschiedliche Zeichen enthalten, ineffizient. Aufgrund ihrer Ineffizienz bei nicht-homogenen Daten eignet sich LRE nur für spezifische Anwendungsbereiche. Der Komprimierungsfaktor von LRE hängt stark von der Struktur der zu komprimierenden Daten ab, und sie ist kein Allzweck-Komprimierungsverfahren. Daher sollte LRE nur in Szenarien eingesetzt werden, in denen Daten mit vielen Wiederholungen vorkommen.

Die Anwendungsgebiete von LRE umfassen einfache Grafiken und Bilder, insbesondere Schwarz-Weiß-Bilder, sowie die Fax-Kommunikation. In diesen Kontexten kann LRE aufgrund seiner Effizienz bei der Komprimierung von wiederkehrenden Mustern und seiner einfachen Implementierung nützlich sein.

6.2.1.2. Huffman Encoding

Funktionsweise:

Daten sollen effizient komprimiert werden, indem häufig vorkommende Zeichen mit kurzen Binärcodes ersetzt werden und seltene Zeichen mit längeren Binärcodes codiert werden.

Zuerst wird die Häufigkeit der Zeichen bestimmt und anschließend ein Huffman- Baum erstellt. Dieser ist ein binärer Baum, bei dem jeder Knoten entweder ein Blattknoten ist, der ein Zeichen und seine Häufigkeit enthält, oder ein innerer Knoten, der die Summe der Häufigkeiten seiner beiden Kindknoten speichert. Die Zeichen mit den niedrigsten Häufigkeiten finden sich in den Blattknoten.

def build_huffman_tree(text):
    """Build the Huffman tree for the given text."""
    # Count frequency of occurrence for each character
    frequency = Counter(text)

    # Create a priority queue from frequencies
    heap = [Node(char, freq) for char, freq in frequency.items()]
    heapq.heapify(heap)

    while len(heap) > 1:
        # Remove two nodes with the smallest frequency
        left = heapq.heappop(heap)
        right = heapq.heappop(heap)

        # Create a new internal node with these two nodes as children
        merged = Node(freq=left.freq + right.freq)
        merged.left = left
        merged.right = right

        # Add the new node to the priority queue
        heapq.heappush(heap, merged)

    # The remaining node is the root of the Huffman tree
    return heap[0]

Jetzt müssen die Zeichen codiert werden, die codierung ergibt sich aus dem Pfad von der Wurzel zum entsprecenden Knoten des Zeichens.

def build_codes(node, prefix="", codebook={}):
    """Build the Huffman codebook for the given tree."""
    if node:
        if node.char is not None:
            codebook[node.char] = prefix  # Assign code to character
        build_codes(node.left, prefix + "0", codebook)
        build_codes(node.right, prefix + "1", codebook)
    return codebook

Anschließend werden die Zeichen durch die jeweilige Codierung ersetzt.

def huffman_encode(text, codebook):
    """Encode the text using the Huffman codebook."""
    return ''.join(codebook[char] for char in text)

Fazit:

Die Huffman-Codierung ist ein effizientes Komprimierungsverfahren, das eine hohe Komprimierungsrate erreichen kann, insbesondere wenn einige Zeichen in der zu komprimierenden Datei häufiger vorkommen als andere. Für eine gegebene Zeichenhäufigkeitsverteilung erzeugt die Huffman-Codierung ein optimal kodiertes Bitmuster, das die durchschnittliche Länge der Codes minimiert. Da die Huffman-Codierung verlustfrei ist, können die Originaldaten exakt wiederhergestellt werden. Diese Methode ist vielseitig einsetzbar und kann auf eine Vielzahl von Datentypen angewendet werden, einschließlich Text, Bilder und Audio.

Jedoch hat die Huffman-Codierung auch einige Nachteile. Die Erstellung des Huffman-Baums und der dazugehörigen Codes erfordert eine Vorverarbeitung der Daten, was zusätzliche Rechenzeit und Speicherplatz beansprucht. Da Huffman-Codes variable Längen haben, kann dies die Handhabung und Verarbeitung der kodierten Daten erschweren, insbesondere bei der Dekodierung. Zudem hängt die Effizienz der Huffman-Codierung stark von der Häufigkeitsverteilung der Zeichen ab. Bei sehr kleinen Datenmengen kann der Overhead der Huffman-Codierung die Vorteile der Komprimierung überwiegen.

Trotz dieser Nachteile wird die Huffman-Codierung häufig in verschiedenen Anwendungsgebieten verwendet. Ein prominentes Beispiel ist die Bildkomprimierung in JPEG. Ebenso wird sie in der Audiokomprimierung, beispielsweise im MP3-Format, genutzt, um die Daten effizient zu reduzieren.

6.2.1.3. Lempel-Ziv-Welch Algorithmus

Funktionsweise:

Im Gegensatz zum Huffman Encoding verwendet der LZW ganze Zeichenketten und encodiert diese.

Als erstes wird ein Wörterbuch initialisiert, dass die ersten 256 möglichen Zeichen/Bytekombinationen, die im Text vokommen könnten, enthält. Der Text wird dann Zeichen für Zeichen durchlaufen. Es wird eine Zeichenkette mit dem aktuellen Zeichen initialisiert. Wenn die aktuelle Kette im Buch gefunden wird, so wird sie um das nächste Zeichen erweitert, dies wird wiederholt, bis eine nicht vorhandene Kette gefunden wird. Diese Codierung, also die Stelle im Wörterbuch, die diese neue Kette hat, wird dann dem komprimierten Ausgabestream angefügt und zum Wörterbuch hinzugefügt.

Der LZW-Algorithmus aktualisiert das Wörterbuch, indem er die neu codierte Zeichenkette hinzufügt. Das nächste Zeichen wird als neue Anfangszeichenkette für die weitere Codierung verwendet.

def lzw_compress(uncompressed):
    """Compress a string to a list of output symbols."""
    
    # Build the dictionary with initial 65536 entries to support unicode chars used in kyrill text
    dict_size = 65536  # 2 Byte to support kyrill text
    dictionary = {chr(i): i for i in range(dict_size)}
    
    w = ""  # Initialize an empty string
    result = []  # List to store the compressed output
    for c in uncompressed:
        wc = w + c  # Concatenate the current string with the next character
        if wc in dictionary:
            w = wc  # If the concatenated string is in the dictionary, set w to wc
        else:
            result.append(dictionary[w])  # Add the dictionary code for w to the result
            # Add wc to the dictionary with a new code
            dictionary[wc] = dict_size
            dict_size += 1
            w = c  # Set w to the current character
    
    # Output the code for w if it's not empty
    if w:
        result.append(dictionary[w])
    return result

Beispiel: Texteingabe: BABBABABA

Wörterbuch

Wörterbuch

Schritt	Index	Zeichenkette
	0	A
	1	B
	2	BA
	3	AB
	4	BB
	5	BAB
	6	BABA

Schritt markiert, wann im Beispielablauf das Wörterbuch erweitert wurde, der Index ist die Codierung.

1. B -> im Wörterbuch (WB) an Stelle (1)

2. BA -> nicht im WB, also BA hinzufügen und (1) ausgeben

3. A -> im WB an Stelle (0)

4. AB -> nicht im WB, also AB hinzufügen und (0) ausgeben

5. B -> im WB an Stelle (1)

6. BB -> nicht im WB, also BB hinzufügen und (1) ausgeben

7. B -> im WB an Stelle (1)

8. BA -> im WB an Stelle (3)

9. BAB -> nicht im WB, also BAB hinzufügen und (3) ausgeben

10. B -> im Wörterbuch (B) an Stelle (1)

11. BA -> im Wörterbuch an Stelle (3)

12. BAB -> im Wörterbuch an Stelle (5)

13. BABA-> nicht im Wörterbuch -> hinzufüguen an Stelle (6) und (5) ausgeben

14. A -> kein weiterer Buchstabe mehr verfügbar, (0) ausgeben

Komprimierter Output: 1 0 1 3 5 0

Fazit:

LZW ist ein verlustfreies Komprimierungsverfahren, bei dem die Originaldaten exakt wiederhergestellt werden können. Diese Methode ist besonders effektiv bei Textdaten und bei Daten, die sich durch wiederkehrende Muster auszeichnen, wie zum Beispiel Quellcode oder strukturierte Daten. Ein wesentlicher Vorteil von LZW gegenüber der Huffman-Codierung ist, dass keine Vorverarbeitung zur Erstellung eines Kodierbaums erforderlich ist. Dies erleichtert die Implementierung und Anwendung in verschiedenen Kontexten. Zudem ist die Dekomprimierung von LZW-kodierten Daten relativ einfach und schnell, da das Wörterbuch während der Dekomprimierung gleichzeitig aufgebaut wird.

Allerdings hat LZW auch einige Nachteile. Während der Komprimierung wächst das verwendete Wörterbuch kontinuierlich, was bei sehr großen Dateien zu einem erheblichen Speicherbedarf führen kann. Außerdem kann die LZW-Komprimierung bei Daten, die keine oder nur wenige wiederkehrende Muster aufweisen, ineffizient sein. Die Implementierung des LZW-Algorithmus ist zudem komplexer als bei einfachen Komprimierungsverfahren wie der Lauf-Längen-Kodierung (RLE).

Trotz dieser Nachteile wird LZW häufig in bestimmten Anwendungsgebieten verwendet. Dazu gehören insbesondere Bildformate wie GIF und TIFF sowie PDF-Dokumente, wo die Vorteile der verlustfreien Komprimierung und der effizienten Dekomprimierung besonders zur Geltung kommen.

6.2.1.4. Der Performance-Vergleich

Um die Leistung der drei Komprimierungsverfahren zu testen, komprimieren wir drei verschiedene Texte mit allen drei Methoden und vergleichen anschließend die Größe der komprimierten Texte. Hierzu haben wir ein Python-Skript erstellt, das die Texte aus einer Datei einliest und nacheinander von allen Komprimierungsverfahren komprimieren lässt. Abschließend überprüfen wir, ob der nach der Dekomprimierung entstandene Text wieder dem Originaltext entspricht. Wir testen mit drei verschiedenen Texten: einem kurzen Text, einem langen Text und einem Text in kyrillischer Schrift.

short_text.txt (1833 bytes)

Lorem ipsum dolor sit amet, consectetur adipiscing elit. Sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur. Excepteur sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id est laborum.
Lorem ipsum dolor sit amet, consectetur adipiscing elit. Sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur. Excepteur sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id est laborum.
Lorem ipsum dolor sit amet, consectetur adipiscing elit. Sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur. Excepteur sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id est laborum.
Lorem ipsum dolor sit amet, consectetur adipiscing elit. Sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur. Excepteur sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id est laborum.

Ausschnitt aus long_text.txt (9798374 bytes)

Buch#Kapitel#Vers (nach Luther 1984, maschinenlesbar)ßLuther 1912
1. Mose#1#1ß1. Am Anfang schuf Gott Himmel und Erde. - Apostelgeschichte 17,24; Offenbarung 4,11; Hebr‰er 11,3; Johannes 1,1ñ3.
1. Mose#1#2ß2. Und die Erde war w¸st und leer, und es war finster auf der Tiefe; und der Geist Gottes schwebte auf dem Wasser.
1. Mose#1#3ß3. Und Gott sprach: Es werde Licht! und es ward Licht. - Psalm 33,9; 2. Korinther 4,6.
1. Mose#1#4ß4. Und Gott sah, dafl das Licht gut war. Da schied Gott das Licht von der Finsternis

Ausschnitt aus kyrill_text.txt (6899560 bytes)

1Авраам поднялся оттуда к югу и поселился между Кадесом и между Суром; и был на время в Гераре. 2И сказал Авраам о Сарре, жене своей: она сестра моя. И послал Авимелех, царь Герарский, и взял Сарру. 3И пришел Бог к Авимелеху ночью во сне и сказал ему: вот, ты умрешь за женщину, которую ты взял, ибо она имеет мужа. 4Авимелех же не прикасался к ней и сказал: Владыка! неужели ты погубишь и невинный народ? 5Не сам ли он сказал мне: она сестра моя? И она сама сказала: он брат мой. Я сделал это в простоте сердца моего и в чистоте рук моих. 6И сказал ему Бог во сне: и Я знаю, что ты сделал сие в простоте сердца твоего, и удержал тебя от греха предо Мною, потому и не допустил тебя прикоснуться к ней; 7теперь же возврати жену мужу, ибо он пророк и помолится о тебе, и ты будешь жив; а если не возвратишь, то знай, что непременно умрешь ты и все твои. 8И встал Авимелех утром рано, и призвал всех рабов своих, и пересказал все слова сии в уши их; и люди сии весьма испугались. 9И призвал Авимелех Авраама и сказал ему: что ты с нами сделал? чем согрешил я против тебя, что ты навел было на меня и на царство мое великий грех? Ты сделал со мною дела, каких не делают. 10И сказал Авимелех Аврааму: что ты имел в виду, когда делал это дело? 11Авраам сказал: я подумал, что нет на месте сем страха Божия, и убьют меня за жену мою; 12да она и подлинно сестра мне: она дочь отца моего, только не дочь матери моей; и сделалась моею женою; 13когда Бог повел меня странствовать из дома отца моего, то я сказал ей: сделай со мною сию милость, в какое ни придем мы место, везде говори обо мне: это брат мой. 14И взял Авимелех мелкого и крупного скота, и рабов и рабынь, и дал Аврааму; и возвратил ему Сарру, жену его. 15И сказал Авимелех: вот, земля моя пред тобою; живи, где тебе угодно. 16И Сарре сказал: вот, я дал брату твоему тысячу [сиклей] серебра; вот, это тебе покрывало для очей пред всеми, которые с тобою, и пред всеми ты оправдана. 17И помолился Авраам Богу, и исцелил Бог Авимелеха, и жену его, и рабынь его, и они стали рождать; 18ибо заключил Господь всякое чрево в доме Авимелеха за Сарру, жену Авраамову.

Chapter 21
1И призрел Господь на Сарру, как сказал; и сделал Господь Сарре, как говорил. 2Сарра зачала и родила Аврааму сына в старости его во время, о котором говорил ему Бог; 3и нарек Авраам имя сыну своему, родившемуся у него, которого родила ему Сарра, Исаак; 4и обрезал Авраам Исаака, сына своего, в восьмой день, как заповедал ему Бог. 5Авраам был ста лет, когда родился у него Исаак, сын его. 6И сказала Сарра: смех сделал мне Бог; кто ни услышит обо мне, рассмеется. 7И сказала: кто сказал бы Аврааму: Сарра будет кормить детей грудью? ибо в старости его я родила сына. 8Дитя выросло и отнято от груди; и Авраам сделал большой пир в тот день, когда Исаак отнят был от груди. 9И увидела Сарра, что сын Агари Египтянки, которого она родила Аврааму, насмехается, 10и сказала Аврааму: выгони эту рабыню и сына ее, ибо не наследует сын рабыни сей с сыном моим Исааком. 11И показалось это Аврааму весьма неприятным ради сына его. 12Но Бог сказал Аврааму: не огорчайся ради отрока и рабыни твоей; во всем, что скажет тебе Сарра, слушайся голоса ее, ибо в Исааке наречется тебе семя; 13и от сына рабыни Я произведу народ, потому что он семя твое. 14Авраам встал рано утром, и взял хлеба и мех воды, и дал Агари, положив ей на плечи, и отрока, и отпустил ее. Она пошла, и заблудилась в пустыне Вирсавии; 15и не стало воды в мехе, и она оставила отрока под одним кустом 16и пошла, села вдали, в расстоянии на [один] выстрел из лука. Ибо она сказала: не [хочу] видеть смерти отрока. И она села против, и подняла вопль, и плакала; 17и услышал Бог голос отрока; и Ангел Божий с неба воззвал к Агари и сказал ей: что с тобою, Агарь? не бойся; Бог услышал голос отрока оттуда, где он находится; 18встань, подними отрока и возьми его за руку, ибо Я произведу от него великий народ. 19И Бог открыл глаза ее, и она увидела колодезь с водою, и пошла, наполнила мех водою и напоила отрока. 20И Бог был с отроком; и он вырос, и стал жить в пустыне, и сделался стрелком из лука. 21Он жил в пустыне Фаран; и мать его взяла ему жену из земли Египетской. 22И было в то время, Авимелех с Фихолом, военачальником своим, сказал Аврааму: с тобою Бог во всем, что ты ни делаешь; 23и теперь поклянись мне здесь Богом, что ты не обидишь ни меня, ни сына моего, ни внука моего; и как я хорошо поступал с тобою, так и ты будешь поступать со мною и землею, в которой ты гостишь. 24И сказал Авраам: я клянусь. 25И Авраам упрекал Авимелеха за колодезь с водою, который отняли рабы Авимелеховы. 26Авимелех же сказал: не знаю, кто это сделал, и ты не сказал мне; я даже и не слыхал [о том] доныне. 27И взял Авраам мелкого и крупного скота и дал Авимелеху, и они оба заключили союз. 28И поставил Авраам семь агниц из [стада] мелкого скота особо. 29Авимелех же сказал Аврааму: на что здесь сии семь агниц, которых ты поставил особо? 30[он] сказал: семь агниц сих возьми от руки моей, чтобы они были мне свидетельством, что я выкопал этот колодезь. 31Потому и назвал он сие место: Вирсавия, ибо тут оба они клялись 32и заключили союз в Вирсавии. И встал Авимелех, и Фихол, военачальник его, и возвратились в землю Филистимскую. 33И насадил [Авраам] при Вирсавии рощу и призвал там имя Господа, Бога вечного. 34И жил Авраам в земле Филистимской, как странник, дни многие.

Das Python-Skript für den Performance-Test sieht wie folgt aus:

import sys
import time
import rle
import lzw 
import huffman
texts = ["short_text.txt", "long_text.txt", "kyrill_text.txt"]


def main():

    for text_name in texts: 
        text=""
        with open(text_name, "r") as f:
            text = f.read()
        print(f"\nTesting {text_name}")
        text_size = sys.getsizeof(text)



        # RLE
        start = time.time()
        rle_compressed = rle.rle_compress(text)
        rle_time_comp = time.time() - start

        start = time.time()
        rle_decompressed = rle.rle_decompress(rle_compressed)
        rle_time_decomp = time.time() - start

        assert text == rle_decompressed

        # LZW 
        start = time.time()
        lzw_compressed = lzw.lzw_compress(text)
        lzw_time_comp = time.time() - start

        start = time.time()
        lzw_decompressed = lzw.lzw_decompress(lzw_compressed)
        lzw_time_decomp = time.time() - start
        assert text == lzw_decompressed

        # Huffman
        start = time.time()
        huffman_tree = huffman.build_huffman_tree(text)
        huffman_codebook = huffman.build_codes(huffman_tree)
        huffman_encoded_text = huffman.huffman_encode(text, huffman_codebook)
        huffman_time_comp = time.time() - start

        start = time.time()
        huffman_decompressed = huffman.huffman_decode(huffman_encoded_text, huffman_tree)
        huffman_time = time.time() - start
        assert text == huffman_decompressed

        print(f"Original text size: {text_size}")
        print(f"RLE compressed text size: {rle.rle_compressed_size(rle_compressed)}\n with time: {round(rle_time_comp *1000)}ms compression and {round(rle_time_decomp*1000)}ms decompression")
        print(f"LZW compressed text size: {lzw.calculate_lzw_compressed_size(lzw_compressed)}\n with time: {round(lzw_time_comp*1000)}ms compression and {round(lzw_time_decomp*1000)}ms decompression")
        print(f"Huffman compressed text size: {huffman.calculate_huffman_compressed_size(huffman_encoded_text)}\n with time: {round(huffman_time_comp*1000)}ms compression and {round(huffman_time*1000)}ms decompression")

if __name__ == "__main__":
    main()

6.2.1.5. Ergebnisse

Die Ergebnisse unseres Tests sind wie folgt:

short_text.txt (1833 bytes)

Metric	RLE	LZW	Huffman
Compressed Size (bytes)	3504	1552	931
Compression Time (ms)	1	8	0
Decompression Time (ms)	0	6	1
Compression Ratio	1.91	0.85	0.51

long_text.txt (9798374 bytes)

Metric	RLE	LZW	Huffman
Compressed Size (bytes)	9756399	1375006	2975492
Compression Time (ms)	1148	792	330
Decompression Time (ms)	284	252	1529
Compression Ratio	0.996	0.14	0.30

kyrill_text.txt (6899560 bytes)

Metric	RLE	LZW	Huffman
Compressed Size (bytes)	9487980	1176078	2082318
Compression Time (ms)	1010	623	408
Decompression Time (ms)	241	243	1085
Compression Ratio	1.38	0.17	0.30

Der Originaltext „short_text.txt“ hat eine Größe von 1833 Bytes. Nach der Komprimierung mit RLE beträgt die Dateigröße 3504 Bytes, was bedeutet, dass die Datei nach der Komprimierung größer ist als vorher. Dieses Ergebnis ist nicht unerwartet, da RLE besonders effektiv bei Texten mit vielen Wiederholungen ist, was in diesem kurzen Text nicht der Fall war. Die LZW-Komprimierung hat den Text auf 1552 Bytes reduziert, was einer Reduzierung der Dateigröße um etwa 15 % entspricht. Am effektivsten war die Huffman-Codierung, die den Originaltext auf 931 Bytes komprimieren konnte, was einer Einsparung von fast 50 % entspricht.

Der Originaltext „long_text.txt“ hat eine Größe von 9798374 Bytes. Die RLE-Komprimierung reduzierte die Dateigröße nur minimal auf 9756399 Bytes, was einer Kompressionsrate von 0.996 entspricht. Dies zeigt, dass RLE für diesen langen Text ebenfalls ineffektiv ist. Die LZW-Komprimierung reduzierte die Größe auf 1375006 Bytes, was einer erheblichen Einsparung von etwa 86 % entspricht. Die Huffman-Komprimierung reduzierte die Dateigröße auf 2975492 Bytes, was einer Einsparung von etwa 70 % entspricht, jedoch bei einer deutlich längeren Dekompressionszeit im Vergleich zu den anderen Methoden.

Der Originaltext „kyrill_text.txt“ hat eine Größe von 6899560 Bytes. Auch hier führte die RLE-Komprimierung zu einer Vergrößerung der Datei auf 9487980 Bytes, was eine Kompressionsrate von 1.38 zeigt. Die LZW-Komprimierung reduzierte die Dateigröße auf 1176078 Bytes, was einer Einsparung von etwa 83 % entspricht. Die Huffman-Komprimierung reduzierte die Dateigröße auf 2082318 Bytes, was einer Einsparung von etwa 70 % entspricht. Hier war die Dekompressionszeit bei der Huffman-Komprimierung ebenfalls deutlich länger als bei den anderen Methoden.

Insgesamt zeigt sich, dass die RLE-Komprimierung für diese Textdateien ineffektiv war und oft zu einer Vergrößerung der Dateigröße führte. Die LZW-Komprimierung erwies sich als sehr effektiv, insbesondere bei großen Textdateien, und konnte die Dateigröße erheblich reduzieren. Die Huffman-Komprimierung war ebenfalls effektiv, wobei sie besonders bei kleinen Texten herausragende Ergebnisse lieferte, jedoch mit einer längeren Dekompressionszeit bei großen Textdateien verbunden war.

6.2.2. Vergleich von Bildkomprimierungsverfahren

Die folgende Tabelle und die dazugehörigen Bilder vergleichen die drei populären Bildformate: PNG, JPEG und GIF. Diese Formate unterscheiden sich in Komprimierungsart, Bildqualität, Farbhandhabung und Transparenz. Als Grundbild wurde ein ARW (oder RAW) Bild mit der Dateigröße 11.142.144 Bytes (ca.11,1 MB) verwendet.

Vergleich von Bildkomprimierungsformaten

Eigenschaft	PNG	JPEG	GIF
Dateigröße	4,139,048 Bytes (ca. 4,14 MB)	893,250 Bytes (ca. 893 KB)	2,270,466 Bytes (ca. 2,27 MB)
Bildqualität	Verlustfreie Komprimierung, keine sichtbaren Artefakte, ideal für Detailtreue	Verlustbehaftete Komprimierung, kann zu Artefakten führen, geeignet für moderate Kompression, Dateigröße auf Kosten der Bildqualität reduziert	Verlustfreie Komprimierung, aber begrenzt auf 256 Farben, kann zu Banding führen
Farbhandhabung	Unterstützt bis zu 48-Bit Farbtiefe, exzellent für Farbverläufe	Unterstützt bis zu 24-Bit Farbe, ausreichend für die meisten fotografischen Zwecke	Begrenzt auf 256 Farben, ungeeignet für farbreiche Bilder
Transparenz	Volle Alpha-Kanal-Transparenz, ideal für komplexe Bilder	Keine Transparenz unterstützt	Einfache binäre Transparenz, kann zu harten Rändern führen

6.2.2.1. Bildvergleich

Im Folgenden sind die Bilder in den drei Formaten zu sehen, die oben besprochen wurden. Beachten Sie die Unterschiede in der Darstellung von Farben und Details.

PNG-Format:

JPEG-Format:

GIF-Format:

6.2.2.2. Zusammenfassung

Wann welches Format wählen?: Für hochwertige, bearbeitbare Bilder oder Grafiken mit Transparenz ist PNG die beste Wahl. Für Fotografien und Bilder, die online geteilt werden sollen, wo Dateigröße ein wichtiger Faktor ist, ist JPEG ideal. GIF sollte für einfache Grafiken oder kleine Animationen verwendet werden, besonders wenn eine niedrige Farbtiefe ausreichend ist.