Hallo Leute!


Also, folgende Herausforderung:

Ich soll eine GFS (so was wie ein Referat, nur größer) im Wahlkurs Informatik zum Thema Textkompression halten. Theorie ist überhaupt kein Problem, die einzelnen Algorithmen (Huffman, Shannon-Fano, RLE, LZ77/78 ) lassen sich mit Flash-Präsentationen und Javaapplets recht gut veranschaulichen. Nun sollen meine Kameraden aber auch noch etwas zu tun bekommen - selbst ein kleines Textkompressionsprogramm in Delphi 6 schreiben.
Da wir schon für ein einfaches Sortierprogramm mit Quicksort/Bubblesort aufgrund des schwierigen Algorithmus (o_O) etwa 5 Doppelstunden benötigten, sollte der Algorithmus so einfach wie nur möglich zu verstehen und zu implementieren sein. Das spricht eigentlich für RLE, aber da würde sich die Kompression sehr stark in Grenzen halten, und ich glaube, es käme wesentlich besser an, wenn man auch tatsächlich etwas von der Kompression sehen könnte (ok, ich könnte einen Text "haaaaaaaaaaalloooooooo!!!!!!" zum Komprimieren nehmen...).
Ich habe dann an den LZ78-Algorithmus gedacht, von dem man mir mehrfach sagte, er sei leicht zu verstehen und zu implementieren. Verstanden habe ich ihn, aber keine Ahnung, wie ich das in Delphi umsetzen soll. Entweder habe ich schlecht/falsch gesucht, oder es gibt im weltweiten Netz echt nicht viele Leute, die in Delphi diesen Algorithmus verwendet haben... alles, was ich gefunden habe, war ein Codeschnipsel eines Lempel-Ziv-Huffman-Algorithmus, aber Huffman ist zu schwer zu verwenden, zumindest in einem Informatikkurs wie dem unseren.
Ich brauche also einen Quelltext, in dem kurz und bündig das Wesentliche eines LZ78-Kompressionsprogrammes enthalten ist: Datei einlesen, komprimieren/dekomprimieren, Datei ausgeben, und dabei soll das Kompressionsverfahren ganz ohne den Zugriff auf eine andere Unit, wie so oft beim Huffman-Algorithmus, auskommen.

Kann mir da bitte irgend jemand helfen? Das ganze sollte noch bis zum 9. Juni fertig sein, um noch genug Zeit zu haben, Wichtiges (Dateien einlesen/ausgeben) im Unterricht durchzunehmen. Mit dem Algorithmus in Delphi an sich ist mir auch schon sehr gedient, den Rest bekomme ich mit Sicherheit auch selbst noch raus, nur wenn einer schon ein fertiges Programm oder so rumliegen hätte, wär das echt toll!


Grüße,

Daniel

www.efg2.com/Lab/Lib...lgorithms/index.html

Auch wenn ich relativ wenig Ahnung habe sagt mir der Algo garnichts...

Schon bei Wikipedia geschaut? Da wird das ganz gut erklärt.

de.wikipedia.org/wiki/LZ78

LZ78 ist zwar simpel, aber imho wesentlich schwieriger zu implementieren als RLE. RLE kommt mit ca. 10-20 Zeilen aus, LZ78 benötigt dagegen im Vergleich zu RLE "wahnsinnig komplexe" Datenstrukturen (Listen!, Zeiger!, Autsch!).

RLE sollte auch für jeden Informatik-Laien verständlich und unmittelbar umsetzbar sein, LZ77/78 dagegen nicht.

Danke für eure Antworten!

Ich habe mich jetzt, nachdem ich an LZ(77/78/W) verzweifelt bin, dazu entschieden, RLE zu verwenden. Von der Schwierigkeit für den Kurs eigentlich genau richtig, man muss halt die Kompressionsrate mit verschiedenen Test-Dateien prüfen, damit der große Nachteil von RLE sichtbar wird.

Frage somit beantwortet, und das Programm für euch mal mit angehängt, der nächste Informatik-Schüler freut sich vielleicht drüber Nichts Weltenbewegendes, aber soll ja auch ohne viel Schnickschnack auskommen und nur aufs Wesentliche beschränkt sein.

Grüßle,

Daniel