Vorwort
Ich denke, Freunde, die Datenstrukturen gelernt haben, müssen Huffman kennen. Dieser große Gott hat den berühmten "optimalen binären Baum" erfunden. Um ihn zu erinnern, nennen wir es den "Huffman Tree". Der Huffman -Baum kann für die Huffman -Codierung verwendet werden, und das Wissen über die Codierung ist sehr großartig, wie zum Beispiel für Komprimierung, Kryptographie usw.
Konzept
Natürlich ist eine der Routinen, dass wir einige grundlegende Konzepte verstehen müssen.
1. Pfadlänge: Der Pfad, der die beiden Knoten von einem Knoten im Baum zu einem anderen Knoten bildet. Die Anzahl der Zweige auf dem Pfad wird als Pfadlänge bezeichnet.
2. Baumpfadlänge: Die Summe der Pfadlängen von der Baumwurzel bis zu jedem Knoten. Was wir einen vollständigen binären Baum nennen, ist die kürzeste Länge dieser Art.
3.. Die gewichtete Pfadlänge des Baumes: Wenn jedem Blattknoten des Baumes ein gewichteter Wert zugeordnet wird, ist die gewichtete Pfadlänge des Baumes gleich der Summe des Produkts der Pfadlänge vom Wurzelknoten zu allen Blattknoten und dem Gewicht des Blattknotens.
Wie bestimmen wir also, ob ein Baum ein optimaler binärer Baum ist? Schauen wir uns die folgenden Bäume an:
Ihre Stromlängen sind:
WPL1: 7*2+5*2+2*2+4*2 = 36
WPL2: 7*3+5*3+2*1+4*2 = 46
WPL3: 7*1+5*2+2*3+4*3 = 35
Es ist offensichtlich, dass der dritte Baum den kürzesten Gewichtspfad hat (Sie glauben nicht, Sie können es versuchen. Wenn Sie einen kürzeren finden, werden Sie wahrscheinlich den Turing Award gewinnen). Dies nennen wir den "optimalen Binärbaum (Hafman Tree)". Seine Konstruktionsmethode ist sehr einfach. Sie wählen den Knoten mit dem kleinsten Gewicht aus und platzieren ihn am Boden des Baumes und legen die beiden kleinsten Verbindungen in einen neuen Knoten. Es ist zu beachten, dass das Gewicht des gebildeten neuen Knotens gleich der Summe der Gewichte dieser beiden Knoten sein sollte. Setzen Sie diesen neuen Knoten dann wieder in den Knoten, wo wir den Baum bilden müssen, um weiter zu sortieren. Auf diese Weise befinden sich alle im Hafman -Baum gespeicherten Knoten mit Informationen auf den Blattknoten.
Nachdem ich das Konzept beendet habe, kann ich ein bisschen "unklar" sein.
Lassen Sie uns ein Beispiel geben, um es klar zu bauen.
Es gibt eine Schnur: aaaaaaaaAbbbaaaACCCCCCCCCCCDDDDDDFFF
Im ersten Schritt zählen wir zunächst die Häufigkeit, mit der jedes Zeichen erscheint, und nennen es das Gewicht des Charakters. A 15, B 5, C 8, D 6, F 3.
Der zweite Schritt besteht darin, die beiden Zeichen mit dem kleinsten Gewicht B5 und F3 zu finden und den Knoten zu bauen.
Entfernen Sie dann F3 und B5, jetzt A15, C8, D6, FB8.
Schritt 3, wiederholen Sie den zweiten Schritt, bis nur ein Knoten übrig ist.
Es ist jetzt DFB14, A15, C8.
endlich,
OK, also ist unser Huffman -Baum gebaut.
Schritte zu bauen
Nach der obigen Logik, um es zusammenzufassen, gibt es einige Schritte:
1. Statistik Die Anzahl der Zeichen und Zeichen, die in einer Zeichenfolge erscheinen;
2. Erstellen Sie Knoten gemäß der Struktur des ersten Schritts;
3.. Sortieren Sie die aufsteigenden Knotengewichte;
4. Nehmen Sie die beiden Knoten mit dem geringsten Gewicht heraus und erzeugen Sie einen neuen übergeordneten Knoten.
5. Löschen Sie die beiden Knoten mit dem geringsten Gewicht und speichern Sie den übergeordneten Knoten in der Liste.
6. Wiederholen Sie Schritt 4 oder 5, bis ein Knoten übrig ist;
7. Weisen Sie dem Stammknoten den letzten Knoten zu.
Java -Code
Das Prinzip ist abgeschlossen und der nächste Schritt besteht darin, den Code zu implementieren.
Erstens gibt es eine Knotenklasse, um Daten zu speichern.
Paket Huffman;/** * Knotenklasse * @author yuxiu * */public class Node {public String Code; // Hafman codierung des Knotens public int codessize; // Länge des Knotens Huffman, der öffentliche String -Daten codiert; // Knotendaten öffentliche Int; // Node Gewicht öffentliche Knoten lchild; öffentlicher Knoten Rchild; public node () {} public node (String data, int count) {this.data = data; this.count = count; } public node (int count, node lchild, node rchild) {this.count = count; this.lchild = lchild; this.rchild = rchild; } public node (Stringdaten, int count, knoten lchild, node rchild) {this.data = data; this.count = count; this.lchild = lchild; this.rchild = rchild; }}Dann gibt es den Implementierungsprozess.
Paket Huffman; Java.io importieren. Zeichen ist das gleiche Zeichen in derselben Position private ArrayList <node> nodelist; // Die Warteschlange zum Speichern von Knoten 15 16/ ** * Erstellen Sie den Huffman -Baum * * @param str */ public void creathfMtree (String str) {this.str = str; charList = new ArrayList <string> (); Nodelist = new ArrayList <node> (); // 1. Statistik Die Anzahl der Zeichen und Zeichen, die in einer Zeichenfolge erscheinen. // Die Zeichenflagge = true herausnehmen; für (int j = 0; j <charlist.size (); j ++) {if (charlist.get (j) .Charat (0) == CH) {// Wenn das gleiche Zeichen für Zeichenfolge s = charlist.get (j)+ch; charList.set (j, s); Flag = Falsch; brechen; }} if (flag) {charlist.add (charList.size (), ch + ""); }} // 2. Erstellen Sie einen Knoten gemäß der Struktur des ersten Schritts für (int i = 0; i <charlist.size (); i ++) {String data = charlist.get (i) .charat (0)+""; // Erhalten Sie das erste Zeichen jeder Zeichenfolge in charList int count = charlist.get (i) .Length (); // Die Länge der Zeichenfolge in der Liste ist der entsprechende Gewichtknotenknoten = neuer Knoten (Daten, Anzahl); // Knotenobjekt nodelist.add (i, node) erstellen; // Machen Sie mit der Knotenwarteschlange} // 3. sort (nodelist); while (nodelist.size ()> 1) {// Wenn die Anzahl der Knoten größer als eins ist // 4. Nehmen Sie die beiden Knoten mit dem kleinsten Gewicht heraus und generieren Sie einen neuen übergeordneten Knoten // 5. Löschen Sie die beiden Knoten mit dem kleinsten Gewicht und speichern Sie den Elternknoten im Listenknoten links = NodeList.Remove (0); Node right = nodelist.remove (0); int parentWeight = links.count + rechts.count; // Das Gewicht des übergeordneten Knotens entspricht der Summe der Gewichte des untergeordneten Knotenknotens parent = neuer Knoten (Elterngewicht, links, rechts); Nodelist.add (0, Eltern); // den übergeordneten Knoten an der ersten Position einlegen} // 6. Wiederholen Sie die vierten und fünften Schritte, um die while -Loop // 7 zu sein. Weisen Sie den letzten Knoten dem Root Knoter Root = nodelist.get (0) zu; } / ** * Aufstieg order * * @param nodelist * / public void sort (arrayList <node> nodelist) {for (int i = 0; i <nodelist.size () - 1; i ++) {für (int j = i+1; j <node.size (); j ++) {node temp; if (nodelist.get (i) .count> nodelist.get (j) .count) {temp = nodelist.get (i); nodelist.set (i, nodelist.get (j)); nodelist.set (j, temp); }}}} / ** * traversal * * @param node * node * / public void output (Knotenknoten) {if (node.lchild! = Null) {output (node.lchild); } System.out.print (node.count + ""); // In-Ordnung-Traversal if (node.rchild! = Null) {output (node.rchild); }} public void output () {output (root); }/** * Hauptmethode * * @param args */public static void main (string [] args) {huffman huff = new Huffman (); // Erstellen Sie das Havalman -Objekt huff.creathfmtree ("sdfassvvdfgsfdfsdfs").Zusammenfassen
Bei der oben genannten Umsetzung des Huffman -Baumes basierend auf Java. Ich hoffe, dieser Artikel wird für alle hilfreich sein, um zu lernen, wie man Java benutzt. Wenn Sie Fragen haben, überlassen Sie bitte eine Nachricht, um zu diskutieren.