Zeigerproblem im Binären Baum



  • Hi,
    für die Huffman-Kompression erzeugt folgener Code einen binären Baum, der seltene Zeichen weiter unten im Baum und häufe weiter oben (nahe der Wurzel) anordnet.
    Zuerst befinden sich alle Symbole in einer Liste (List), dann werden sie nach und nach in den Binären Baum (bintree) übertragen, bis die Liste leer ist und alle Symbole im Baum sind.

    Eigentlich sollte es so sein, dass alle Parent (Eltern) Zeiger der Nodes (Knoten) auf eine andere gültige Node im Baum zeigen. Jedoch haben zeigen einige von ihnen auf ungültige Nodes in der Liste. Ich dachte im Code wäre sichergestellt, dass am Ende keine Node mehr zur Liste zeigt. Aber wenn ich die Symbole der Parents überprüfe sind sie bei den ungültigen -1, was einen gelöschen Listeintrag symbolisiert. Ich hoffe jemand erkennt im Code einen grundlegenden Zeiger-Fehler:

    while ( 1 ) {
    
            // Zwei seltensten Elemente suchen
            minc1 = 102400;
            minc2 = 102400;
            for (long i=0 ; i<256 ; ++i) {
                if (list[i].symbol != -1 && list[i].count< minc1 ) { 
                    min1 = i; minc1 = list[i].count; }
                if (list[i].symbol != -1 && list[i].count< minc2 && min1!=i ) {
                    min2 = i; minc2 = list[i].count; }
            }
    
            // Noch ein Element auf Liste-> Zu Baum kopieren & Loop verlassen
            if (minc2 == 102400) {
                list[min1].symbol = -1;
                bintree[nodecount] = list[min1];
                bintree[nodecount].symbol = 257;
                bintree[nodecount].bit0->parent = &bintree[nodecount];
                bintree[nodecount].bit1->parent = &bintree[nodecount];
                bintree[nodecount].parent = NULL;
                break;
            }
    
            // Elemente von Liste zu Baum kopieren & aus Liste löschen
            bintree[nodecount]  = list[min1];
            bintree[nodecount+1]= list[min2];    
            bintree[nodecount].value   = "0";
            bintree[nodecount+1].value = "1";
            list[min2].symbol = -1;  
    
            // Evtl. neue Position vorheriger Parentnode anpassen
            if (list[min1].bit0 != NULL) {
                list[min1].bit0->parent = &bintree[nodecount];
                list[min1].bit1->parent = &bintree[nodecount];
            } else if (list[min2].bit0 != NULL) {
                list[min2].bit0->parent = &bintree[nodecount+1];
                list[min2].bit1->parent = &bintree[nodecount+1];
            }
    
            // Aus Elementen neue Node erstellen & in Liste ablegen
            list[min1].symbol = 256;
            list[min1].count = bintree[nodecount].count + bintree[nodecount+1].count;
            list[min1].bit0  = &bintree[nodecount];
            list[min1].bit1  = &bintree[nodecount+1];
            bintree[nodecount].parent   = &list[min1];
            bintree[nodecount+1].parent = &list[min1];
    
            nodecount += 2;
        }
    

    Man beachte den Code unter dem Kommentar "Position vorheriger Parentnode anpassen". Damit wollte ich dieses Problem eigentlich verhindern.
    Ich weiß übrigens, dass mein Code 1. nicht optimal ist und 2. nicht dem allgemeinen Huffmanverfahren entspricht. Für Optimierungsvorschläge bin ich sehr dankbar, das grundlegende Verfahren würde ich jedoch gerne so belassen.

    Riesen Dank im Voraus 🙂
    Neo



  • Ich habe zumindest dieses Problem gelöst:

    // Evtl. neue Position vorheriger Parentnode anpassen
            if (list[min1].bit0 != NULL) {
                list[min1].bit0->parent = &bintree[nodecount];
                list[min1].bit1->parent = &bintree[nodecount];
            } else if (list[min2].bit0 != NULL) { // Hier muss das Else weg!
                list[min2].bit0->parent = &bintree[nodecount+1];
                list[min2].bit1->parent = &bintree[nodecount+1];
            }
    

    Hier sollte sichergestellt werden, dass die Kinderelemente einer Node, die gerade von der Liste zum Baum verschoben wurde, nicht mehr auf das Listen- sondern auf das neue, gültige Baumelement zeigen sollten.
    Es war aber schlicht logisch falsch, ein "else if" zu verwenden, da *beide* Child-Nodes überprüft werden müssen, und nicht nur eine.

    Noch eine weitere Frage: Wie findet man heraus, ob ein Huffman-Algo wirklich die optimalen (kürzesten) Codes für die einzelnen Zeichen liefert?

    Danke,
    Neo



  • ...hab mich wohl zu früh gefreut: Der Code funktioniert nur punktuell, ab und zu gibt es trotzdem noch Zeiger die auf eine ungültige Parentnode (Elternknoten) zeigen. Zumeist (vlt. auch immer?) sind es die Knoten direkt vor der Wurzel, die halt nicht mehr auf die Wurzel zeigen. Ich bin völlig ratlos.

    Zudem scheint der ganze Algo bei genau drei Zeichen die genau die gleiche Verteilung haben (z.B. aabbcc) nicht zu funktionieren, was aber nicht soo schlimm ist, da das in der Praxis wohl selten vorkommen wird.

    Es wäre wirklich schön, wenn jemand der damit Erfahrung hat den obigen Code nochmal nach Logikfehler untersucht. Währenddessen versuche ich ebenfalls den Fehler ausfindig zu machen.

    Gruß,
    Neo


Log in to reply