Huffman algorithmus

N

NonPlusUltra

Mitglied
Hallo Java Community,

ich versuch schon seit paar Stunden mein Glück an ein Java Programmier Projekt(Huffman),
meiner Meinung nach bin ich schon für meine Kenntnisse ziemlich weit gekommen😳

ich komm aber an einer Stelle einfach nicht weiter

und zwar habe ich ein ArrayList, die voller Knoten ist davon will ich die zwei kleinsten Knoten herausfinden (mit kleinsten knoten meine ich ,die zwei Knoten mit der kleinsten Häufigkeit der Zeichen)
also als Rückgabetyp brauch ich die zwei Knoten

hat einer ein Tipp für mich?


das sind Methoden die ich schon implementiert habe

getLeft(); -> linker Teilbaum
getRight(); -> Rechhter Teilbaum
getSymbol();-> ASCII zeichen
getWeight();-> gibt die Häufigkeit der Zeichen aus
 
Entweder die Liste nach der Häufigkeit sortieren und dann einfach die ersten zwei Indizes nehmen.
(s. Comparator, Collections.sort(...))
Oder die Liste in einer Schleife durchlaufen und sich die zwei kleinsten Indizes merken.
 
meinst du das so in etwa ?
aber das klappt ihrgend wiebei mir nicht^^

Java: 
int[] min = nodeArray[0].getWeight();
       for (int x = 0; x < noArray[x].getight().length; x++){
           if (nodesArray[x].getWeht() > min) {
               mi1 = ndeArray[x];    
           }
        }
 
Zuletzt bearbeitet:
Dachte es wird eine ArrayList verwendet?
NonPlusUltra hat gesagt.:
aber das klappt ihrgend wiebei mir nicht^^
Zum Vergrößern anklicken....
Soll vermutlich heißen: Lässt sich nicht kompilieren ;-)
Meinte es in etwa so:
Java: 
		int min1 = 0;
	    for (int x = 0; x < nodesArray[x].length; x++){
	    	if (nodesArray[x].getWeight() < nodesArray[min1].getWeight()) {
	    		min1 = x;    
	        }
	    }
Es ging ja auch darum den (Index des) Knoten zu bekommen und nicht nur den Wert.
 
Oki vielen dank^^

ich merk nur gerade das ich denn arrayList glaube ich falsch gemacht habe

beim Compelieren kommt immer alls fehler
cannot find symbol - variable nodeArray
Java: 
        int min = 0;
        for (int x = 0; x < nodeArray[x].length; x++){
            if (nodeArray[x].getWght() < nodArray[min].getWght()) {
                min = x;    
            }
        }
 
Zuletzt bearbeitet:
seh gerade auch im Ahang von mein ProProjekt steht da auch das mit int size();

muss ich es dann so schreiben nodes.get(x).size() ?

Edit:

glaub habs verstanden^^

so solls doch sein oder

int a = nodes.size();

dann in der schleife x< a
 
Zuletzt bearbeitet:
wieder zu meiner anfangs frage darf ich das so machen um min2 herauszufinden

Java: 
          int lenght = nodes.size();
        int min1 = 0;
        int min2 = 0;
        for (int x = 0; x < lenght; x++){
            if (nodes.get(x).getWeight() < nodes.get(min1).getWeight()) {
                min1 = x;
                if (nodes.get(x).getWeight()<= nodes.get(min2).getWeight()){
                    min2=x;
                }
            }
        }
 
Zuletzt bearbeitet:
Java: 
        for (int x = 0; x < lenght-1; x++){
            for (int y = x; y < lenght; y++){
                            if (nodes.get(x).getWeight() > nodes.get(y).getWeight()) {
                //... Exchange elements
                int temp = nodes.get(x).getWeight();
                nodes.get(x).getWeight() = nodes.get(y).getWeight();
                nodes.get(y).getWeight() = temp;
            }

dann ist doch nodes.get(0) mein min 1 und nodes.get(1) mein min2

aber was ist wenn min1 = min2 ist wie kann ich das mit selectionsort berücksichtigen

aber hab da noch fehler der Compiler spuckt hier ein fehler raus
nodes.get(x).getWeight() = nodes.get(y).getWeight();
 
Welche Fehler melder der Kompiler?
getWeight() liefert ja scheibar ein int Array, dann geht folgendes natürlich nicht
Code: 
int temp = nodes.get(x).getWeight();
Willst Du die Liste damit sortieren? Dann musst Du die Positionen der Knoten tauschen. Du manipulierst hier aber nur die in den Knoten gespeicherten Häufigkeiten.
 
hmm hab mir was anderes einfallen lassen (das hat was zu bedeuten:lol🙂

Java: 
    public INode createTree(String text) {

        ArrayList<INode> nodes = new ArrayList<INode>();
        int [] Counter = getFrequencies(text);

   
}

dan ist ja INode Min2 und INode Min1 die die ich suche oder?

der compiler merkt zwar kein fehler , aber ich trau mir selbst nicht ^^

EDIT: der compiler spinnt bei der variante nur wenn ich die beiden Knoten verbinden will dann steht beim Compiler das er die Variable Min2 nicht finden kann
 
Zuletzt bearbeitet:
NonPlusUltra hat gesagt.:
hmm hab mir was anderes einfallen lassen (das hat was zu bedeuten:lol🙂
Zum Vergrößern anklicken....
Interessant
NonPlusUltra hat gesagt.:
der compiler merkt zwar kein fehler , aber ich trau mir selbst nicht ^^
Zum Vergrößern anklicken....
Und das zu Recht ;-) Da sind mehrere Denkfehler drin.

Min1 und Min2 nur innerhalb Ihrer Schleifen gültig, es wird immer gegeben nodes.get(0) verglichen...

und selbst wenn das behoben wäre, würde das mit den zwei Schleifen so nicht korrekt funktionieren.

Zum Suche reicht eine Schleife.

Ich würde die Liste (mittels Comparator) sortieren. Und dann einfach Index 0 und 1 als die zwei Minima abgreifen.
 
ich schau mir mal an wie das mit den Comperator funktioniert dann versuch ich es mal^^


kann man den Comerator auch in die Methode einfach rein schreiben ohne eine Neue zu machen?
 
Java: 
  Collections.sort(nodes, new Comparator(){
 
            public int compare(INode o1, INode o2) {
               return o1.getWeight().compareTo(o2.getWeight());
            }
        }
);

sortiert er jetzt die list nach Häufigkeit?

beim Compiler kommt auch noch diese fehler Meldung das die klasse Huffman nicht Abstract sei
 
Man muss noch den Typ Parameter <INode> am Konstruktor des Comparators mit angeben
Java: 
Collections.sort(nodes, new Comparator<INode>() {...
Beim return muss wenn das erste Objekt vor dem zweiten Objekt einsortiert werden soll eine negative und umgekehrt eine positive Zahl zurückgeben.
Wie jetzt Deine getWeight() Werte verglichen werden müssen müsstest Du sagen, da diese ja - glaube ich ein int[] zurückgeben. compareTo kann nur Objekte vergleichen, die Comparable implementieren.
 
Ach so.
Den kann man dann einfach subtrahieren.
Entweder
Code: 
return o2.getWeigth() -o1.getWeigth();
oder
Code: 
return o1.getWeigth() -o2.getWeigth()
in der compare Methode zurückgeben. Je nachdem, ob absteigend oder aufsteigend sortiert werden soll.

Zum Kopieren:
Java: 
Collections.sort(nodes, new Comparator<INode>() {
	public int compare(INode o1, INode o2) {
		return o1.getWeight() - o2.getWeight();
	}
});
 
darf ich das dann auch so schreiben ?

Java: 
        int lenght = nodes.size();
        
        while( lenght == 1 ){

            Collections.sort(noes, new Coarator<INode>() {
                    public int comre(INode o1, INode o2) {
                        return o1.getWeight() - o2.getWeight();
                    }
                } );
                
             nodes.get(0).mee(nodes.get(1)); //
             nods.remove(noes.get(0));    //
             nodes.ad(nodes.et(0).merge(odes.et(1)));  
            }
 
Zuletzt bearbeitet:
NonPlusUltra hat gesagt.:
darf ich das dann auch so schreiben ?

Java: 
        int lenght = nodes.size();
        
        while( lenght == 1 ){

            Collections.sort(nodes, new Comparator<INode>() {
                    public int compare(INode o1, INode o2) {
                        return o1.getWeight() - o2.getWeight();
                    }
                } );
                
             nodes.get(0).merge(nodes.get(1)); //verbinde die Knoten
             nodes.remove(nodes.get(0));    // lösche denn Knoten 1
             nodes.remove(nodes.get(1));    // lisch den knoten 2
             nodes.add(nodes.get(0).merge(nodes.get(1)));  //trage denn verbindeten Knotten in die liste
                
            }
Zum Vergrößern anklicken....
Dürfen schon ;-)

Soll wohl
Code: 
while( lenght > 1)
heißen (und vermutlich auch length)
Beim Löschen könntest Du aber durchaus auf ernsthaftere Probleme stossen.

Gibt die merge - Methode ein neues Knoten Objekt zurück oder verändert sie den Knoten an dem sie aufgerufen wird?
Du rufst get(0) und get(1) auf nach dem diese zuvor aus der List gelöscht wurden und greifst damit auf Index 2 und 3 der ursprünglichen Liste zu - ist vermutlich auch nicht gewollt.
 
so hab ich die merge methode Implementiert

sie soll zwei knoten addieren und die beiden knotten sollen vom neuen knotten die kinder sein

also so in etwas

AB => Eltern knoten
A B => Kinder Knoten
 
Zuletzt bearbeitet:
Dann sollte das in etwa so lauten:
Java: 
while(nodes.size() > 1 ){
            Collections.sort(nodes, new Comparator<INode>() {
                    public int compare(INode o1, INode o2) {
                        return o1.getWeight() - o2.getWeight();
                    }
            });
            nodes.add(nodes.get(0).merge(nodes.get(1)));  
            nodes.remove(nodes.get(0));    // lösche denn Knoten 1
            nodes.remove(nodes.get(1));    // lisch den knoten 2
}

Wobei man den Comparator dann eher ausserhalb der Schleifer erzeugen sollte und nicht bei jedem Schleifendurchlauf neu.
 
Danke für deine hilfe aber ich glaube meine merge methode ist ihrgend wie falsch

kannst du mal druber gucken

Java: 
    public INode merge(INode o){
        int A = o.getWeight();
        int B = this.getWeight();
        int Sum = A + B;
 
         if ( A <= B ) { 
            left = other.get0();
            right = this.get1();
        }
        else if ( A >= B) { 
            right = other.get1();
            left = this.get0();
        }
 
        INode Neu = new Node ( '*', Sum, right, left);
 
        return Neu;
 
Um die kleinsten x Elemente zu finden, genügt doch ein maxHeap mit x Elementen, dessen Wurzel man immer dann austauscht, wenn ein Element kleiner ist. Oder eine abfallende priority queue, wo man nur einfügt, wenn vorderstes Element größer ist.

das wäre schneller als Sortieren, nur ist die Frage, ob man diese x Elemente auch noch in sortierter Reihenfolge benötigt
 
also das mit denn sortieren klappt ja schon

aber ich glaube meine merge methode klappt nicht so richtig

wenn ich zb die text eingebe : DDDAAASSS

dann kommt nur
*(6)

anstatt
Code: 
      *(9)
D(3)      *(6)
         A(3)  S(3)

der macht nur ein teilbaum und denn stehlt er auch nicht richtig da^^
 
k.Ahnung wo und wie left und right deklariert sind. Ich hoffe mal Du überschreibst hier nicht die Instanzvariablen des Knotens. Und das getX (was auch immer das ist) ist hier auch Fehl am Platz. Du willst Doch die beiden Knoten als Kindknoten des neuen Knotens setzen??
Code: 
other
ist übrigens auch nirgends deklariert und soll wohl o heißen
Java: 
         if ( A <= B ) { 
            left = other;
            right = this;
        }
        else if ( A >= B) { 
            right = other;
            left = this;
        }
Falls meine Befürchtung zutrifft, das ganze geht auch kürzer:
Java: 
public INode merge(INode o){
        int a = o.getWeight();
        int b = this.getWeight();
        if (a <= b)
                return new INode('*', a +b, this, o);
        return new INode('*', a +b, o, this);
}
 
Was gibst du als return an?

Ich beschäfftige mich mit ähnlichem (😉) und ich ich weiß einfach nicht, was ich returnen soll... das Programm will ja einen return des Datentypes INode... Wenn man die Liste returnen will kommt "Ne, geht nicht weil is'n Array." -.-
 
kann mir jemand sagen wo hier der Fehler ist
Java: 
while( g > 1 ){
              Node min1;
              Node min2;
           min1 = (Node) node.remove(0);
            for(int i = 1; i < g; i++) {
        
                Node temp = (Node) node.get(i);
               
                if (temp.getWeight() < min1.getWeight()) {
                    node.remove(i);
                    node.add(min1);
                    temp= min1; 
                }
            }
            min2 = (Node) node.remove(0);
          
            for(int i = 0; i < g ; i++) {
               Node temp = (Node) node.get(i);
             
                if (temp.getWeight() < min2.getWeight()) {
                   node.remove(i);
                   node.add(min2);
                   temp= min2;
                } 
            }
            node.add((Node) min1.merge(min2));
         }
         return node.get(0);
        }
[code=Java]
 

Aktuelle Jobs

Neue Themen

Ähnliche Themen

komprimierung mittels Huffman-Algorithmus, bit-shifting.
Antworten: 2
[Aufgabe] Huffman Bäume
Antworten: 10
Huffman Codierung
Antworten: 5
Huffman Codierung
Antworten: 4
Huffman Kodierung
Antworten: 5

Zurück
Oben