Pendahuluan Pengkodean Huffman
Pengkodean Huffman berkaitan dengan masalah pemasangan pengkodean karakter dan biner yang sesuai dengan karakter, yang dibagi menjadi pengkodean dan decoding, dengan tujuan mengompresi panjang data biner yang sesuai dengan karakter. Kita tahu bahwa ketika karakter disimpan dan ditransfer, mereka adalah biner (hanya komputer yang tahu 0/1), jadi ada hubungan pemetaan antara karakter dan biner. Karakter milik set karakter (charset). Karakter perlu disimpan dan ditransmisikan dalam biner melalui Encode. Saat ditampilkan, mereka perlu diterjemahkan kembali ke karakter. Metode set karakter dan pengkodean adalah hubungan satu-ke-banyak (Unicode dapat dikodekan dengan UTF-8, UTF-16, dll.). Setelah memahami set karakter, pengkodean dan decoding, masalah kode kacau terbang di seluruh langit dapat dengan mudah diselesaikan. Mengambil huruf kecil dari huruf bahasa Inggris sebagai contoh, dalam pengkodean ASCII, desimal adalah 97 dan biner adalah 01100001. Setiap karakter dalam ASCII dikodekan dengan 8 bit (1byte). Jika ada 1000 karakter yang akan ditransmisikan, maka 8000 bit harus ditransmisikan. Masalahnya adalah bahwa frekuensi menggunakan huruf E dalam bahasa Inggris adalah 12,702%, sedangkan z adalah 0,074%. Yang pertama lebih dari 100 kali lipat dari yang terakhir, tetapi menggunakan biner dengan angka yang sama. Ini dapat dilakukan dengan lebih baik, metode ini adalah pengkodean panjang variabel. Prinsip panduannya adalah mengkodekan frekuensi yang lebih tinggi dengan angka yang lebih pendek, dan yang dengan frekuensi rendah dengan angka yang lebih panjang. Algoritma pengkodean Huffman berkaitan dengan masalah seperti itu.
Implementasi Java yang menyandikan Huffman
Struktur data yang terutama digunakan oleh algoritma pengkodean Huffman adalah pohon biner penuh dan antrian prioritas. Yang terakhir menggunakan java.util.priorityqueue, dan yang pertama mengimplementasikan itu sendiri (semua adalah kelas internal). Kodenya adalah sebagai berikut:
pohon kelas statis {private node root; node publik getroot () {return root; } public void setRoot (node root) {this.root = root; }} Node kelas statis mengimplementasikan yang sebanding <node> {private string chars = ""; frekuensi int pribadi = 0; orang tua simpul pribadi; Node Private LeftNode; Node Private RightNode; @Override public int compareto (node n) {return frekuensi - n.frequency; } public boolean isleaf () {return chars.length () == 1; } public boolean isroot () {return parent == null; } public boolean isleftchild () {return parent! = null && this == parent.leftnode; } public int getFrequence () {frekuensi pengembalian; } public void setFrequence (frekuensi int) {this.frequency = frekuensi; } public string getChars () {return chars; } public void setChars (string chars) {this.chars = chars; } node publik getParent () {return parent; } public void setParent (node induk) {this.parent = parent; } node publik getLeftNode () {return leftNode; } public void setleftNode (node leftNode) {this.leftnode = leftNode; } node publik getRightNode () {return rightNode; } public void setRightNode (node rightNode) {this.rightNode = rightNode; }} Statistik
Karena tabel pengkodean perlu diatur sesuai dengan frekuensi, maka tentu saja, Anda harus mendapatkan informasi statistik dari frekuensi. Saya menerapkan metode untuk menangani masalah seperti itu. Jika sudah ada statistik, maka konversi ke peta <karakter, integer>. Jika informasi yang Anda dapatkan adalah persentase, kalikan dengan 100 atau 1000, atau 10000. Itu selalu dapat dikonversi menjadi bilangan bulat. Misalnya, 12,702% dikalikan dengan 1000 adalah 12702, dan pengkodean Huffman hanya peduli tentang masalah ukuran. Metode statistik diimplementasikan sebagai berikut:
peta statis publik <karakter, integer> statistik (char [] chararray) {peta <karakter, integer> peta = hashmap baru <karakter, integer> (); untuk (charc c: chararray) {karakter karakter = karakter baru (c); if (map.containskey (karakter)) {map.put (karakter, map.get (karakter) + 1); } else {map.put (karakter, 1); }} return peta; } Membangun pohon
Membangun pohon adalah langkah inti dalam algoritma pengkodean Huffman. Idenya adalah untuk menggantung semua karakter pada simpul daun pohon biner yang benar-benar, dan frekuensi simpul kiri simpul anak non-halaman tidak muncul lebih dari simpul kanan. Algoritma mengubah statistik menjadi node dan menyimpannya dalam antrian prioritas. Setiap kali dua node dengan frekuensi minimum muncul dari antrian, simpul induk baru (node non-daun) dibangun. Jumlah dari dua node yang konten karakternya baru saja muncul, dan frekuensinya juga jumlahnya. Pop-up pertama digunakan sebagai simpul anak kiri, dan yang berikutnya digunakan sebagai simpul anak yang tepat, dan simpul induk yang baru dibangun ditempatkan dalam antrian. Ulangi tindakan di atas N-1 kali, n adalah jumlah karakter yang berbeda (angka dalam antrian dikurangi 1 setiap kali). Akhiri langkah -langkah di atas, ada simpul yang tersisa di antrian, dan simpul akar pohon muncul. Kodenya adalah sebagai berikut:
private static tree buildtree (peta <character, integer> statistik, daftar <node> daun) {karakter [] keys = statistics.keyset (). toarray (karakter baru [0]); PriityQueue <Node> prioritasqueueE = prioritas baru <node> (); untuk (karakter karakter: tombol) {node node = new node (); node.chars = karakter.toString (); node.frequency = statistics.get (karakter); prioritasqueue.add (node); leaves.add (node); } int size = prioritasqueue.size (); untuk (int i = 1; i <= ukuran - 1; i ++) {node node1 = prioritasqueue.poll (); Node node2 = prioritasqueue.poll (); Node sumnode = node new (); sumnode.chars = node1.chars + node2.chars; sumnode.frequency = node1.fraquence + node2.fraquence; sumnode.leftnode = node1; sumnode.rightnode = node2; node1.parent = sumnode; node2.parent = sumnode; prioritasqueue.add (sumnode); } Pohon pohon = pohon baru (); tree.root = prioritasqueue.poll (); pohon kembali; } pengkodean
Pengkodean karakter yang sesuai adalah mencari dari simpul daun di mana karakter berada. Jika simpul karakter adalah simpul kiri dari node induk, tambahkan 0 sebelum karakter yang dikodekan, jika tidak jika itu adalah simpul kanan, tambahkan 1 sampai simpul root. Selama hubungan pemetaan antara karakter dan kode biner diperoleh, pengkodeannya sangat sederhana. Kodenya adalah sebagai berikut:
Public Static String Encode (String Originalstr, Map <Character, Integer> Statistics) {if (originalstr == null || Originalstr.equals ("")) {return ""; } char [] chararray = originalstr.tochararray (); Daftar <Node> Leafnodes = ArrayList baru <Node> (); Buildtree (Statistik, Leafnodes); Peta <karakter, string> encodinfo = buildeCodingInfo (Leafnodes); StringBuffer buffer = stringBuffer baru (); untuk (char c: chararray) {karakter karakter = karakter baru (c); buffer.append (encodinfo.get (karakter)); } return buffer.toString (); } peta statis privat <karakter, string> buildEncodingInfo (daftar <node> leafnodes) {peta <karakter, string> codewords = hashmap baru <karakter, string> (); untuk (node leafnodes: leafnodes) {karakter karakter = karakter baru (leafnode.getchars (). charaat (0)); String codeword = ""; Node currentNode = Leafnode; do {if (currentNode.isleftChild ()) {codeword = "0" + codeword; } else {codeword = "1" + codeword; } currentNode = currentNode.parent; } while (currentNode.parent! = null); codewords.put (karakter, codeword); } return codewords; } decoding
Karena algoritma pengkodean Huffman dapat memastikan bahwa kode biner apa pun tidak akan menjadi awalan kode lain, decoding sangat sederhana. Keluarkan setiap bit biner secara berurutan, cari dari akar pohon, 1 ke kanan, 0 ke kiri, mencapai simpul daun (Hit), dan kembali ke simpul akar dan terus mengulangi tindakan di atas. Kodenya adalah sebagai berikut:
decode string statis public (string BinerSTRST, peta <karakter, integer> statistik) {if (binerstr == null || binarystr.equals ("")) {return ""; } char [] BinaryCharArray = BinaryStr.tochararray (); LinkedList <Character> BinaryList = new LinkedList <CHARCTER> (); ukuran int = BinaryCharArray.length; untuk (int i = 0; i <size; i ++) {BinaryList.AddLast (karakter baru (BinaryCharArray [i])); } Daftar <Node> Leafnodes = ArrayList baru <Node> (); Pohon pohon = Buildtree (Statistik, Leafnodes); StringBuffer buffer = stringBuffer baru (); while (BinaryList.size ()> 0) {node node = tree.root; do {karakter c = BinaryList.removefirst (); if (c.charvalue () == '0') {node = node.LeftNode; } else {node = node.RightNode; }} while (! node.isleaf ()); buffer.append (node.chars); } return buffer.toString (); } Tes dan perbandingan
Tes berikut tentang kebenaran pengkodean Huffman (dikodekan terlebih dahulu, kemudian diterjemahkan, termasuk Cina), dan perbandingan pengkodean Huffman dengan pengkodean karakter yang umum. Kodenya adalah sebagai berikut:
public static void main (string [] args) {string oristr = "Huffman Code Compress Data dengan sangat efektif: penghematan 20% hingga 90% khas," + "tergantung pada karakteristik data yang dikompresi. Kenaikan Cina"; Peta <karakter, integer> statistik = statistik (oristr.tochararray ()); String encodedBinArtr = encode (oristr, statistik); String decodedstr = decode (encodedBinaristr, statistics); System.out.println ("String Asli:" + oristr); System.out.println ("Huffman Encoed Binary String:" + EncodedBinaristr); System.out.println ("String Decoded dari Binariy String:" + DecodedStr); System.out.println ("String Biner dari UTF-8:" + GetTringOfByte (oristr, charset.forname ("UTF-8"))); System.out.println ("String biner UTF-16:" + getstringofbyte (oristr, charset.forname ("UTF-16")))); System.out.println ("String biner US-ASCII:" + getstringofbyte (oristr, charset.forname ("us-ascii"))); System.out.println ("String biner GB2312:" + getStringOfByte (oristr, charset.forname ("GB2312"))); } public static String getStringOfByte (string str, charset charset) {if (str == null || str.equals ("")) {return ""; } byte [] bytearray = str.getbytes (charset); int size = bytearray.length; StringBuffer buffer = stringBuffer baru (); untuk (int i = 0; i <size; i ++) {byte temp = byteArray [i]; buffer.append (getStringOfByte (temp)); } return buffer.toString (); } public static String getStringOfByte (byte b) {stringBuffer buffer = new stringBuffer (); untuk (int i = 7; i> = 0; i--) {byte temp = (byte) ((b >> i) & 0x1); buffer.append (string.valueof (temp)); } return buffer.toString (); }Di atas adalah semua konten artikel ini. Saya berharap ini akan membantu untuk pembelajaran semua orang dan saya harap semua orang akan lebih mendukung wulin.com.