Fano-Algorithmus

Computer: Software & Programmierung Programmierung allgemein
#1

Schönen Guten Tag!

Ich bin grad am tüffteln, wie man den Fano-Algorithmus, der zur Redundanzminimierung dient, in C übersetzen kann. Im Moment scheitere ich aber entweder an zu langen if-Schleifen bzw. an zu komplexen switch-Strukturen.
Falls mir irgendjeman einen Tipp geben könnte, wo ich einen Quelltext oder einen PAP finde, wäre mir doch sehr geholfen. Die Programmiersprache ist mir eigentlich egal, da ich wirklich nur den Algorithmus brauche.

Ich wäre euch echt verbunden.

Bis denn, ein verwirrterr Reisender in der Welt von Bits&Bytes

#2

Moien

Ich bin grad am tüffteln, wie man den Fano-Algorithmus, der
zur Redundanzminimierung dient, in C übersetzen kann.

… du könntest auch Huffman implementieren, der ist einfacher was die Bestimmung der Kodierung angeht. Und für den findet google auch jede Menge Zeug.

cu

#3

Hallo Fragewurm,

Ich bin grad am tüffteln, wie man den Fano-Algorithmus, der
zur Redundanzminimierung dient, in C übersetzen kann. Im
Moment scheitere ich aber entweder an zu langen if-Schleifen
bzw. an zu komplexen switch-Strukturen.
Falls mir irgendjeman einen Tipp geben könnte, wo ich einen
Quelltext oder einen PAP finde, wäre mir doch sehr geholfen.
Die Programmiersprache ist mir eigentlich egal, da ich
wirklich nur den Algorithmus brauche.

Du machst wohl den Denkfehler das ganze linear programmieren zu wollen.
Da bei bekommst du verschachtelte IFs, bis zur maximalen Baumgrösse.

Einfacher wird es, wenn man sich, wie Tarzan, in einer SChleife von Knoten zu Knoten hangelt.
In der Schlaufe nimmst du eine Varaibele, welche du bei jeder Verzweigung nachlinks verschiebst und das niederwertigste Bit entsprechend auf 0 oder 1 setzt. Zusammen mit der Anzahl Durchgängen (Schleifenzähler) hast du dann die fertige Codierung.

Was willst du eigentlich alles machen?
Codieren oder decodieren oder beides ??

MfG Peter(TOO)

#4

Moinsen

Der gute alte Huffmann kommt auch noch, aber erstma das schwierige und dann das leichte. Ne hab eigentlich noch gar nicht über die Implementierung von Huffmann nachgedacht, aber wenn das einfacher ist, mach ich den Onkel erstmal.

Bis denne.

#5

Moinsen.

Kannst du mir das vllt noch ma genauer erklären, ich häng gerade sowas von aufm Schlauch. Und dazu kommt, das ich gerade Mikrokontroller programmiere, was mehr auf bits und weniger auf Bytes setzt. und Außerdem habe ich da ZUstandsbits/-flags, die einem das Programmmieren dann doch extrem vereinfachen.

Also würd mich freuen, wenn ich dir die Zeit stehlen dürfte, wenn du es nochmal ein wenig genauer beschreibst.

Bis denn. Danke Schon mal

#6

Hallo Fragewurm,

Kannst du mir das vllt noch ma genauer erklären, ich häng
gerade sowas von aufm Schlauch. Und dazu kommt, das ich gerade
Mikrokontroller programmiere, was mehr auf bits und weniger
auf Bytes setzt. und Außerdem habe ich da ZUstandsbits/-flags,
die einem das Programmmieren dann doch extrem vereinfachen.

Also würd mich freuen, wenn ich dir die Zeit stehlen dürfte,
wenn du es nochmal ein wenig genauer beschreibst.

Zuerst benötigst du ein Array um die Hüffigkeit zu bestimmem. Wenn wir mal 8-Bit für die Zeichen annehmen:

typedef struct -sKNOTEN
{
 unsigned in zaeler;
} sKNOTEN;

sKNOTEN knoten[256];

jetzt kannst du mit

unsigned char c; // hier ist das zeichen drin
knoten[c].zaeler++;

mal die Zählerei erledigen.

Danach bildest du eine Zeite Liste und sortierst diese entsprechend dem Algothmus.

Nun müssen wir das ganze noch etwas erweitern:

typedef struct \_sKNOTEN
{
 struct \_sKNOTEN \*links;
 struct \_sKNOTEN \*rechts;
 unsigned in zaeler;
} sKNOTEN;

sKNOTEN knoten[256];

jetzt benötigst du noch eine Variable welche den Anfang des Baums enthält, welchen du aus der Verteilung bekommst.
Von diesem Knoten aus, kannst du nun den Baum mit „links“ und „rechts“ aufbauen.
Bei jedem Blatt musst du entspreched NULL in „links“ oder „rechts“ eintagen um zu erkennen wo der Zweig endet.

Decodieren kannst du nun in einer Schlaufe:

unsigned char decode( unsigned int code, unsigned char bit\_anzahl)
{
 unsigned int maske;
 sKNOTEN \*ptr1;
 sKNOTEN \*ptr2 = &knoten[start];

 temp = 1 rechts;
 else ptr2 = ptr1-\>links;
 maske \>\>= 1;
 }
 return ptr1 - &knoten[0];
}

OK, ich habe das ganze jetzt nicht getestet.

MfG Peter(TOO)