Realisierung des Huffman-Algorithmus in Delphi

[Dannyboy]

Hallo Jungs,
ich habe vor einigen Wochen hier im Forum nach Algorithmen
zum Packen von Daten gefragt und bin auf den Huffman-Algorithmus
hingewiesen worden, welcher auf der Homepage der FH Flensburg sehr gut beschrieben ist.
Ich verstehe den Algorithmus und kann ihn in der Theorie auch problemlos
anwenden, allerdings hapert es an einem Konzept zur Umsetzung. :gruebel:

Konzept:
Die Knotenpunkte würde ich mit einzelnen Objekten realisieren. Ich habe früher mal einen Binären Baum in Pascal programmieren müssen und ich weiss, wie er mit ZEIGERN zu realisieren ist.
Es ergeben sich letzten Endes für mich lediglich 2 Fragen, die ich bisher
noch nicht beantworten konnte:

a) Wie realisiere ich denn einen binären Baum mit KNOTEN ALS OBJEKTEN, OHNE ZEIGER :gruebel:
b) Wie realisiere ich die Kantenmarkierungen ZWISCHEN den Knoten (also die zugewiesenen Einsen und Nullen) :gruebel:

Hinweis:
Ich möchte nicht auf bereits existierende, binäre Bäume zurückgreifen, sondern alles von Null programmieren :warn:
Thanx
DANNYBOY

[IngoD7]

Zitat:

Zitat von Dannyboy

a) Wie realisiere ich denn einen binären Baum mit KNOTEN ALS OBJEKTEN, OHNE ZEIGER :gruebel:

Indem jeder Knoten die dazugehörigen auch als Objekte aufnimmt. Es gibt ja genügend Delphi-Komponenten, die sowas ähnliches tun - als Beispiel TObjectList. Das ist eine Liste von Objekten. Die Technik, wie man mit ihnen umgeht, und den diesbzgl. Unterschied zwischen Object und Pointer sieht man so ungefähr in der Hilfe bei TList (Liste von Pointern) und TObjectList (Liste von Objekten - ist abgeleitet von TList).

Allerdings habe ich noch nicht verstanden, wieso es unbedingt ohne Zeiger gemacht werden soll. (Abgesehen davon, dass Objekte meistens auch als Referenzen (Zeiger) behandelt werden.)

[Dannyboy]

Zitat:

Zitat von IngoD7

Allerdings habe ich noch nicht verstanden, wieso es unbedingt ohne Zeiger gemacht werden soll. (Abgesehen davon, dass Objekte meistens auch als Referenzen (Zeiger) behandelt werden.)

Hallo IngoD7,
klar werden Objekte intern auch über Referenzen bahandelt. Früher musste
ich den binären Baum funktional (ohne OOP) und mit Zeigern lösen und
heutzutage würde ich das gern mit Objekten machen und mir Zeiger sparen.
Wichtig ist dabei, dass ich nicht auf vordefinierte Objektstrukturen
zurückgreife, sondern ich möchte dieses Problem "ohne Hilfsmittel" lösen.
Die Interaktion der Objekte stelle ich mir bisher so vor:

Delphi-Quellcode:

Type TKnoten = class
  private
    KindLinks  : TKnoten;
    KindRechts : TKnoten;
    Vorgaenger : TKnoten;
    ...

... aber im Huffman-Algorithmus gibt es auch Informationen, die an den Kanten liegen, also zwischen
den Knoten (Objekten), was mein Hauptproblem darstellt:

[neolithos]

Man könnte auch das Alphabet in einem Array ablegen

aAlpha : array [0..????] of record
c,
n : Byte;
end;

0..255 sind das Ansi-Alpha-Bet

alle weiteren sind Kompinationen.


a[0] = 0, -1; // a
a[1] = 1, -1; // b
a[2] = 2, -1; // c
a[3] = 3, -1; // d
a[4] = 3, 3; // dd
a[5] = 3, 0; // da
a[6] = 1, 5; // dab

so wird es z.B. bei Kombrimierungen gemacht. -> Was ja der sinn des Huffman ist!

Vorteil:
Man geht die Datei nur einmal durch.

Nachteil:
Es entsteht bei kleinen Datenmengen (vorrangig) kein optimaler Code

[Dannyboy]

Hallo neolithos,
das mit dem Array ist eine interessante Idee und ich werde diese
bei meiner Umsetzung berücksichtigen. Ich kann jedoch einige Dinge
nicht nachvollziehen:

Delphi-Quellcode:

aAlpha : array [0..????] of record 
c, 
n : Byte; 
end; 

0..255 sind das Ansi-Alpha-Bet 

alle weiteren sind Kompinationen. // Datentyp Byte kennt keine weiteren Kombinationen

a[0] = 0, -1; // a -> -1 mit Byte nicht möglich
a[1] = 1, -1; // b -> -1 mit Byte nicht möglich
a[2] = 2, -1; // c -> -1 mit Byte nicht möglich
a[3] = 3, -1; // d -> -1 mit Byte nicht möglich
a[4] = 3, 3; // dd 
a[5] = 3, 0; // da 
a[6] = 1, 5; // dab -> bda ?

Nachtrag:
Man kann auch den Datentyp Byte nicht einfach durch Integer ersetzen, da dieser die 4-fache Menge an Speicherplatz verwendet, was der Kompression
nicht gerade dient.

[dizzy]

Erstelle doch einfach eine Knotenklasse wie du sie vorschlugst, mit ein paar Feldern mehr. Z.B:

Delphi-Quellcode:

type
  TKnoten = class
  public
    subKnoten: array[0..1] of TKnoten;
    superKnoten: TKnoten;
    kantenInfo: array[0..1] of // irgendwas was deinem Zweck dient
  end;

So stehen die Daten an den Kanten auf dem selben Index wie der zugehörige subKnoten - das erleichtert das Handling etwas. Die Begriffe "Kanten" und "Knoten" uns so sind finde ich zur bildhaften Darstellung gut geeignet, aber sie sagen einem so überhaupt nicht, wie man es implementieren könnte. Es gibt ja de facto gar keine "Kanten" im eigentlichen Sinne... Aber so wie oben würd ich das mal versuchen.


gruss,
dizzy

[neolithos]

Ich Versuch es mal anders zu erklären

Algorithmus:

1. Also du brauchst ein Grund-Alphabet, welches alle Zeichen enthält (z.B. 8 Bit breit)
2. Die Liest das erste Zeichen und schreibst es in den Dest-Strom
3. Liest ein nächstes Byte
4. Prüfe ob die Kombination existiert
NEIN -> 5. a) Füge an die Liste an, als neuen Buchstaben
5. b) Erhöhe gegebenfalls die Bitbreite des Alphabets
5. c) Zerstöre Kombinationssammlung
6. Schreib Bits in Dest-Strom
7. Not EOF dann gehe 3.

Übrigens habe vor ca. 6 Jahren versucht diesen Kombrimierungsalgorithmus umzusetzen. Hat leider damals nicht sollen sein. Berichte wenn du damit Erfolg haben solltest. Theoretisch sollte es funktionieren.

[IngoD7]

Zitat:

Zitat von dizzy

Erstelle doch einfach eine Knotenklasse wie du sie vorschlugst, mit ein paar Feldern mehr. Z.B:

Delphi-Quellcode:

type
  TKnoten = class
  public
    subKnoten: array[0..1] of TKnoten;
    superKnoten: TKnoten;
    kantenInfo: array[0..1] of // irgendwas was deinem Zweck dient
  end;

Seid ihr sicher, dass eine Klasse in sich selber vorkommen darf?

[dizzy]

Ja, hab ich selber erst kürzlich benutzt. Man könnte es auch einfach ausprobieren ;)

Und wenns net tut, dann eben mit einer Forwarddeklaration (Evtl. gibts da ja Unterschiede zwischen den Delphi-Versionen)

Delphi-Quellcode:

type
  TKnoten = class;
  .
  .
  .
  TKnoten = class
  private
    subKnoten: array[0..1] of TKnoten;
    .
    .
  end;

Das sollte aber IMHO nicht nötig sein. Eine Forwarddeklaration wird erst dann zwingend, wenn sich zwei Klassen gegenseitig benutzen. Eine Klasse kennt immer nur die bereits, die im QT VOR ihr deklariert wurden.

Delphi-Quellcode:

type
  TKlasse2 = class;

  TKlasse1 = class
  public
    objekt: TKlasse2;
  end;

  TKlasse2 = class
  public
    objekt: TKlasse1;
  end;

TKlasse1 kennt TKlasse2 eigentlich noch nicht, da sie noch nicht definiert wurde. Jetzt sagt man dem Compiler durch die Deklaration am Anfang, dass es definitiv eine solche Klasse geben wird. (Er meckert auch, wenn NUR die Forwarddeklaration dort steht.)
TKlasse2 kennt TKlasse1 bereits, da vorher beschrieben. Daher hier keine FD nötig.


grusss,
dizzy

[atreju2oo0]

Wenn Du Dir den Huffmann-Code nochmal ansiehst wirst Du erkennen, das die Infos mit 0 und 1 redundant sind!
Nach links ist IMMER 0 und nach RECHTS immer 1...
Also brauchst Du diese Werte nicht zu speichern sondern kannst sie einfach voraussetzen.
Und mehr brauchst Du ja eigentlich nicht...

P.S.: Falls ich jetzt was falsch gesagt habe bitte um Nachsicht... ist noch früh!
:-D