Kata pengantar
Saya pikir teman yang telah belajar struktur data harus mengenal Huffman. Dewa yang hebat ini menemukan "pohon biner optimal" yang terkenal. Untuk memperingati dia, kami menyebutnya "pohon Huffman". Pohon Huffman dapat digunakan untuk pengkodean Huffman, dan pengetahuan pengkodean sangat hebat, seperti untuk kompresi, kriptografi, dll. Mari kita lihat seperti apa pohon Huffman hari ini.
konsep
Tentu saja, salah satu rutinitasnya adalah kita perlu memahami beberapa konsep dasar.
1. Panjang jalur: Jalur yang membentuk dua node dari satu node di pohon ke node lain. Jumlah cabang di jalur disebut panjang jalur.
2. Panjang jalur pohon: Jumlah panjang jalur dari akar pohon ke setiap node. Apa yang kita sebut pohon biner lengkap adalah panjang jalur terpendek dari jenis ini.
3. Panjang jalur tertimbang pohon: Jika nilai tertimbang ditetapkan untuk setiap simpul daun pohon, panjang jalur tertimbang pohon sama dengan jumlah produk dari panjang jalur dari simpul akar ke semua node daun dan berat simpul daun.
Jadi bagaimana kita menentukan apakah pohon adalah pohon biner yang optimal? Mari kita lihat pohon -pohon berikut:
Panjang kekuatan mereka adalah:
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
Jelas bahwa pohon ketiga memiliki jalur berat terpendek (Anda tidak percaya, Anda dapat mencobanya. Jika Anda dapat menemukan yang lebih pendek, Anda mungkin akan memenangkan Turing Award). Inilah yang kita sebut "pohon biner optimal (pohon hafman)". Metode konstruksinya sangat sederhana. Anda memilih simpul dengan berat terkecil dan meletakkannya di bagian bawah pohon, dan menempatkan dua koneksi terkecil ke dalam simpul baru. Perlu dicatat bahwa berat simpul baru yang terbentuk harus sama dengan jumlah bobot dari kedua node ini. Kemudian masukkan simpul baru ini ke dalam simpul di mana kita perlu membentuk pohon untuk terus menyortir. Dengan cara ini, semua node dengan informasi yang disimpan di pohon hafman ada di node daun.
Setelah menyelesaikan konsep, saya mungkin sedikit "tidak jelas".
Mari kita berikan contoh untuk membangunnya dengan jelas.
Ada string: aaaaaaaabbbbaaaacccccccddddddfff
Pada langkah pertama, pertama -tama kita menghitung berapa kali setiap karakter muncul dan menyebutnya berat karakter. A 15, B 5, C 8, D 6, F 3.
Langkah kedua adalah menemukan dua karakter dengan bobot terkecil, B5 dan F3, dan membangun simpul.
Kemudian lepaskan F3 dan B5, sekarang A15, C8, D6, FB8.
Langkah 3, ulangi langkah kedua sampai hanya satu node yang tersisa dibangun.
Sekarang DFB14, A15, C8.
akhirnya,
Oke, jadi pohon Huffman kami dibangun.
Langkah untuk membangun
Menurut logika di atas, untuk meringkasnya, ada beberapa langkah:
1. Statistik Jumlah karakter dan karakter yang muncul dalam string;
2. Buat node sesuai dengan struktur langkah pertama;
3. Urutkan Node Bobot Menurut urutan naik;
4. Keluarkan kedua node dengan berat terkecil dan hasilkan node induk baru;
5. Hapus kedua node dengan berat terkecil dan simpan node induk dalam daftar;
6. Ulangi langkah 4 atau 5 sampai ada simpul yang tersisa;
7. Tetapkan simpul terakhir ke node root.
Kode Java
Prinsipnya selesai, dan langkah selanjutnya adalah mengimplementasikan kode.
Pertama, ada kelas simpul untuk menyimpan data.
Paket huffman;/** * kelas simpul * @Author yuxiu * */kelas publik node {kode string publik; // pengkodean hafman dari node public int codesize; // panjang node huffman encoding data string publik; // node data int int node public; // node bobot node node lchild; node publik rchild; node publik () {} public node (data string, jumlah int) {this.data = data; this.count = count; } node publik (jumlah int, node lchild, node rchild) {this.count = count; this.lChild = lChild; this.rchild = rchild; } node publik (data string, jumlah int, node lchild, node rchild) {this.data = data; this.count = count; this.lChild = lChild; this.rchild = rchild; }}Lalu ada proses implementasi.
paket huffman; import java.io.*; import java.util.*; kelas publik huffman {string pribadi stred; // awalnya digunakan untuk kompresi pribadi string newstr = ""; // string yang dihubungkan oleh huffman yang mengkodekan node private root; Karakter adalah karakter yang sama dalam posisi yang sama dengan arraylist pribadi <node> nodelist; // antrian untuk menyimpan node 15 16/ ** * Bangun pohon huffman * * @param str */ public void Creathfmtree (string str) {this.str = str = str; charlist = ArrayList baru <String> (); NodeList = ArrayList baru <Node> (); // 1. Statistik Jumlah karakter dan karakter yang muncul dalam string // Ide dasarnya adalah untuk memasukkan string yang tidak berurutan seperti ababccdebed ke dalam charlist, yaitu aa, bbb, cc, dd, ee // dan panjang string dalam daftar adalah bobot yang sesuai untuk (int i = 0; i <str.length (); // Keluarkan bendera karakter = true; untuk (int j = 0; j <charlist.size (); j ++) {if (charlist.get (j) .charat (0) == ch) {// Jika karakter yang sama ditemukan string s = charlist.get (j)+ch; charlist.set (j, s); bendera = false; merusak; }} if (flag) {charlist.add (charlist.size (), ch + ""); }} // 2. Buat node sesuai dengan struktur langkah pertama untuk (int i = 0; i <charlist.size (); i ++) {string data = charlist.get (i) .charat (0)+""; // Dapatkan karakter pertama dari setiap string dalam charlist int count = charlist.get (i) .length (); // Panjang string dalam daftar adalah simpul berat simpul yang sesuai = simpul baru (data, hitungan); // buat objek node nodelist.add (i, node); // Bergabunglah dengan antrian simpul} // 3. Sort (nodelist); while (nodeList.size ()> 1) {// Ketika jumlah node lebih besar dari satu // 4. Keluarkan dua node dengan berat terkecil dan hasilkan node induk baru // 5. Hapus dua node dengan berat terkecil dan simpan node induk di node daftar kiri = nodelist.remove (0); Node kanan = nodelist.remove (0); int parentweight = left.count + right.count; // Berat simpul induk sama dengan jumlah bobot node node anak Parent = node baru (parentweight, kiri, kanan); Nodelist.add (0, induk); // Letakkan simpul induk pada posisi pertama} // 6. Ulangi langkah keempat dan kelima menjadi loop while // 7. Tetapkan simpul terakhir ke node root root = nodelist.get (0); } / ** * Urutan naik * * @param nodelist * / public void sort (arraylist <node> nodelist) {for (int i = 0; i <nodelist.size () - 1; i ++) {for (int j = i+1; j <nodelist.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 * / output public void (node node) {if (node.lChild! = Null) {output (node.lChild); } System.out.print (node.count + ""); // in-order traversal if (node.rchild! = Null) {output (node.rchild); }} public void output () {output (root); }/** * Metode utama * * @param args */public static void main (string [] args) {huffman huff = new huffman (); // buat objek havalman huff.cheathfmtree ("sdfassvvvdfgsfdfsdfs"); // buat pohon}}Meringkaskan
Di atas adalah semua tentang mengimplementasikan pohon Huffman berdasarkan Java. Saya harap artikel ini akan membantu semua orang untuk belajar cara menggunakan Java. Jika Anda memiliki pertanyaan, silakan tinggalkan pesan untuk didiskusikan.