Huffman algorithmus

[NonPlusUltra]

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

 

[Michael...]

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.

 

[NonPlusUltra]

meinst du das so in etwa ?
aber das klappt ihrgend wiebei mir nicht^^

int[] min = nodeArray[0].getWeight();
       for (int x = 0; x < noArray[x].getight().length; x++){
           if (nodesArray[x].getWeht() > min) {
               mi1 = ndeArray[x];    
           }
        }

 

[Michael...]

Dachte es wird eine ArrayList verwendet?

aber das klappt ihrgend wiebei mir nicht^^

Soll vermutlich heißen: Lässt sich nicht kompilieren ;-)
Meinte es in etwa so:

		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.

 

[NonPlusUltra]

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

        int min = 0;
        for (int x = 0; x < nodeArray[x].length; x++){
            if (nodeArray[x].getWght() < nodArray[min].getWght()) {
                min = x;    
            }
        }

 

[NonPlusUltra]

sry für denn Doppelpost hab ausversehen F5 gedruckt

 

[Michael...]

Es gibt keine Variable namens nodeArray. Muss nodes heißen und nodes.get(x)

 

[NonPlusUltra]

beim Compelieren kommt jetzt der fehler
cannot find symbol - variable length

hab für jedes nodeArray[x] das hier eingesetzt nodes.get(x)

 

[Michael...]

length ist ein Array spezifisches Attribut. Das kennt eine Liste nicht. List kennt z.B. die Methode size()
Weiteres zu Listen:
List (Java Platform SE 6)

 

[NonPlusUltra]

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

 

[NonPlusUltra]

wieder zu meiner anfangs frage darf ich das so machen um min2 herauszufinden

          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;
                }
            }
        }

 

[NonPlusUltra]

ist ihrgend wie druch einander gekommen habs jetzt wieder geändert

stimmt das so um Min 2 zu bekommen ?

 

[NonPlusUltra]

        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();

 

[Michael...]

Welche Fehler melder der Kompiler?
getWeight() liefert ja scheibar ein int Array, dann geht folgendes natürlich nicht

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.

 

[NonPlusUltra]

hmm hab mir was anderes einfallen lassen (das hat was zu bedeuten:lol

    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

 

[Michael...]

hmm hab mir was anderes einfallen lassen (das hat was zu bedeuten:lol

Interessant

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

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.

 

[NonPlusUltra]

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?

 

[NonPlusUltra]

  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

 

[NonPlusUltra]

komm mit denn Comarator einfach nicht weiter hast du vielleicht ein beispiel ?

oder wie hast du das noch mal gemeint

...
Oder die Liste in einer Schleife durchlaufen und sich die zwei kleinsten Indizes merken.

 

[Michael...]

Man muss noch den Typ Parameter <INode> am Konstruktor des Comparators mit angeben

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.

 

[NonPlusUltra]

die Methode getWeight() gibt ein normalen int wert züruck kein int []

 

[Michael...]

Ach so.
Den kann man dann einfach subtrahieren.
Entweder

return o2.getWeigth() -o1.getWeigth();

oder

return o1.getWeigth() -o2.getWeigth()

in der compare Methode zurückgeben. Je nachdem, ob absteigend oder aufsteigend sortiert werden soll.

Zum Kopieren:

Collections.sort(nodes, new Comparator<INode>() {
	public int compare(INode o1, INode o2) {
		return o1.getWeight() - o2.getWeight();
	}
});

 

[NonPlusUltra]

Danke schon mal dafür wäre niemals drauf gekommen^^

hab aber noch eine frage ist jetzt dadruch meine "ganze" liste sortiert?

 

[Michael...]

hab aber noch eine frage ist jetzt dadruch meine "ganze" liste sortiert?

Ja, das ist sie.

 

[NonPlusUltra]

darf ich das dann auch so schreiben ?

        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)));  
            }

 

[Michael...]

darf ich das dann auch so schreiben ?

        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
                
            }

Dürfen schon ;-)

Soll wohl

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.

 

[NonPlusUltra]

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

 

[Michael...]

Dann sollte das in etwa so lauten:

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.

 

[NonPlusUltra]

Danke für deine hilfe aber ich glaube meine merge methode ist ihrgend wie falsch

kannst du mal druber gucken

    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;

 

[thorstenthor]

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

 

[NonPlusUltra]

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

      *(9)
D(3)      *(6)
         A(3)  S(3)

der macht nur ein teilbaum und denn stehlt er auch nicht richtig da^^

 

[Michael...]

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??

other

ist übrigens auch nirgends deklariert und soll wohl o heißen

         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:

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);
}

 

[NonPlusUltra]

es klappt danke^^ :applaus:

 

[Legendary]

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." -.-

 

[6aEZSW]

kann mir jemand sagen wo hier der Fehler ist

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]

 

[lgvvsdkgnler]

hat sich erledigt hab das problem selbst gelößt