# Huffman algorithmus



## NonPlusUltra (14. Jun 2011)

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... (14. Jun 2011)

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 (14. Jun 2011)

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... (14. Jun 2011)

Dachte es wird eine ArrayList verwendet?


NonPlusUltra hat gesagt.:


> 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 (14. Jun 2011)

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 (14. Jun 2011)

sry für denn Doppelpost hab ausversehen F5 gedruckt


----------



## Michael... (14. Jun 2011)

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


----------



## NonPlusUltra (14. Jun 2011)

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

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


----------



## Michael... (14. Jun 2011)

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 (14. Jun 2011)

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 (14. Jun 2011)

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 (14. Jun 2011)

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

stimmt das so um Min 2 zu bekommen ?


----------



## NonPlusUltra (14. Jun 2011)

```
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... (14. Jun 2011)

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 (15. Jun 2011)

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... (15. Jun 2011)

NonPlusUltra hat gesagt.:


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


Interessant


NonPlusUltra hat gesagt.:


> 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 (15. Jun 2011)

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 (15. Jun 2011)

```
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 (15. Jun 2011)

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

oder wie hast du das noch mal gemeint


Michael... hat gesagt.:


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


----------



## Michael... (15. Jun 2011)

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 (15. Jun 2011)

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


----------



## Michael... (15. Jun 2011)

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 (15. Jun 2011)

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

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


----------



## Michael... (15. Jun 2011)

NonPlusUltra hat gesagt.:


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


 Ja, das ist sie.


----------



## NonPlusUltra (15. Jun 2011)

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... (15. Jun 2011)

NonPlusUltra hat gesagt.:


> darf ich das dann auch so schreiben ?
> 
> 
> ```
> ...


Dürfen schon ;-)

Soll wohl 
	
	
	
	





```
while( lenght > 1)
```
 heißen (und vermutlich auch leng*th*)
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 (15. Jun 2011)

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... (15. Jun 2011)

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 (15. Jun 2011)

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 (15. Jun 2011)

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 (15. Jun 2011)

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... (15. Jun 2011)

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 (15. Jun 2011)

es klappt danke^^ :applaus:


----------



## Legendary (17. Jun 2011)

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 (23. Jun 2011)

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 (23. Jun 2011)

hat sich erledigt hab das problem selbst gelößt


----------

