programer skripsi tesis tugas akhir
-

Contoh Program Source Code   /

Algoritma Huffman Dengan Java

Posted on 00.08
Join with us

Algoritma Huffman Dengan Java

Algoritma Huffman

Algoritma Huffman mrp algoritma yg dikembangkan oleh David A. Huffman yg dipakai unt menemukan prefix code yg optimal & dipublikasikan dlm sebuah paper “A Method for the Construction of Minimum-Redundancy Codes” pd tahun 1952.

Prinsip kerja algoritma Huffman adl mengkodekan setiap karakter ke dlm representasi bit. Representasi bit unt setiap karakter berbeda satu sama lain berdasarkan frekuensi kemunculan karakter. Semakin sering karakter tersebut muncul, maka semakin pendek panjang representasi bitnya. Sebaliknya jika semakin jarang frekuensi suatu karakter unt muncul, maka semakin panjang representasi bit unt karakter tersebut.

Dalam perkembangannya, pengimplementasinya dpt juga dipakai dlm bidang kriptografi / unt pengkompresi jenis data lainnya. Sebagian besar orang mengklasifikasikan algoritma ini menjadi 2 kategori, yaitu :

Huffman statis

Algoritma Huffman yg paling dasar adl algoritma Huffman statis. Yaitu algoritma yg hanya dpt dipakai unt kompresi data teks.

Huffman Dinamis 

merupakan pengembangan dari algoritma Huffman statis dg manambah / mengurangi suatu proses tertentu pd algoritma Huffman statis, hingga algoritma ini menjadi berbeda dg algoritma Huffman yg benar-benar dikembangkan oleh David A. Huffman.

Algoritma Huffman menggunakan prinsip pengkodean yg mirip dg kode Morse, yaitu tiap karakter (simbol) dikodekan hanya dg rangkaian beberapa bit, dimana karakter yg sering muncul dikodekan dg rangkaian bit yg pendek & karakter yg jarang muncul dikodekan dg rangkaian bit yg lebih panjang. Berdasarkan tipe peta kode yg dipakai unt mengubah pesan awal (isi data yg dimasukkan) menjadi sekumpulan code-word, algoritma Huffman termasuk ke dlm kelas algoritma yg menggunakan metode statik, yaitu metode yg selalu menggunakan peta kode yg sama. Metode ini membutuhkan dua fase (two-phase), yaitu fase pertama unt menghitung probabilitas kemunculan tiap simbol & menentukan peta kodenya, & fase kedua unt mengubah pesan menjadi kumpulan kode yg akan ditransmisikan.

Sedangkan berdasarkan teknik pengkodean simbol yg dipakai, algoritma Huffman menggunakan metode symbol-wise, yaitu metode yg menghitung kemunculan dari setiap simbol dlm satu waktu, dimana simbol yg sering muncul diberi kode lebih pendek dibandingkan dg simbol yg jarang muncul.

Dalam Huffman Coding, panjang blok dari keluaran sumber dipetakan dlm blok biner berdasarkan pajang variable. Cara spt ini disebut sebagai fixed to variable-length coding. Ide dasar dari cara Huffman ini adl memetakan mulai simbol yg paling banyak terdapat pd sebuah urutan sumber sampai dg yg jarring muncul menjadi urutan biner. dlm variable-length coding, sinkronisasi mrp suatu masalah. Ini berarti harus terdapat satu cara unt memecahkan urutan biner yg diterima kedalam suatu codeword.

Seperti yg disebutkan diatas, bahwa ide dari Huffman Coding adl memilih panjang codeword dari yg paling besar probabilitasnya sampai dg urutan codeword yg paling kecil probabilitasnya. Apabila kita dpt memetakan setiap keluaran sumber dari probabiltas pi ke sebuah codewortd dg panjang 1/pi & pd saat yg bersamaan dpt memastikan bahwa dpt didekodekan secara unik, kita dpt mecari rata-rata panjang kode H(x). Huffman Code dpt mendekodekan secara unik dg H(x) minimum, & optimum pd keunikan dari kode-kode tersebut.

Pembentukan Pohon Huffman

Kode Huffman pd dasarnya mrp kode prefiks (prefix code), yaitu himpunan yg berisi sekumpulan kode biner, dimana pd kode prefiks ini tidak ada kode biner yg menjadi awalan bagi kode biner yg lain. Kode prefiks biasanya direpresentasikan sebagai pohon biner yg diberikan nilai / label.

Untuk cabang kiri pd pohon biner diberi label 0, sedangkan pd cabang kanan pd pohon biner diberi label 1. Rangkaian bit yg terbentuk pd setiap lintasan dari akar ke daun mrp kode prefiks unt karakter yg berpadanan. Pohon biner ini biasa disebut pohon Huffman.

Langkah-langkah pembentukan pohon Huffman adl sebagai berikut :

  1. Baca semua karakter di dlm teks unt menghitung frekuensi kemunculan setiap karakter. Setiap karakter penyusun teks dinyatakan sebagai pohon bersimpul tunggal. Setiap simpul di-assign dg frekuensi kemunculan karakter tersebut.
  2. Terapkan strategi algoritma sebagai berikut, gabungkan dua buah pohon yg mempunyai frekuensi terkecil pd sebuah akar. Setelah digabungkan, akar tersebut akan mempunyai frekuensi yg mrp jumlah dua buah pohon-pohon penyusunnya.
  3. Ulangi langkah 2 sampai hanya tersisa satu buah pohon Huffman. Agar pemilihan dua pohon yg akan digabungkan berlangsung cepat, maka semua pohon yg ada selalu terurut menaik berdasarkan frekuensi.

Sebagai contoh, dlm kode ASCII string 7 huruf “ABACCDA” membutuhkan representasi 7 x 8 bit = 56 bit (7 byte), dg rincian sebagai berikut:
A = 01000001
B = 01000010
A = 01000001
C = 01000011
C = 01000011
D = 01000100
A = 01000001
Pada string tersebut, frekuensi kemunculan A = 3, B = 1, C=2, & D = 1, hingga proses pembentukan pohon Huffman-nya adl spt yg ditampilkan pd gambar berikut:

Algoritma Huffman Dengan Java
Algoritma Huffman Dengan Java

Proses Encoding

Proses encoding unt satu karakter dimulai dg membuat pohon Huffman terlebih dahulu. Setelah itu, kode unt satu karakter dibuat dg menyusun nama string biner yg dibaca dari akar sampai ke daun pohon Huffman.

Langkah-langkah unt melakukan encoding pd suatu string biner adl sebagai berikut :
  1. Tentukan karakter yg akan di-encode.
  2. Mulai dari akar, baca setiap bit yg ada pd cabang yg bersesuaian sampai menemukan daun di mana karekter itu berada.
  3. Ulangi langkah 2 sampai seluruh karakter di-encode.
Proses Decoding

Decoding mrp kebalikan dari encoding. Decoding berarti menyusun kembali data yg tersandi menjadi data aslinya. Langkah-langkah decoding suatu data yg tersandi menggunakan pohon Huffman adl sebagai berikut :
  1. Baca sebuah bit dari string biner.
  2. Mulai dari akar.
  3. Untuk setiap bit pd langkah 1, lakukan penelusuran pd cabang yg bersesuaian.
  4. Ulangi langkah 1, 2, & 3 sampai bertemu daun. Kodekan rangkaian bit yg telah dibaca dg karakter di daun.
  5. Ulangi dari langkah 1 sampai semua bit di dlm string habis.
Gambar berikut menunjukan proses decoding string biner “111” yg menghasilkan karakter “D”.


Algoritma Huffman Dengan Java
Algoritma Huffman Dengan Java

Macam-macam Variasi Kode Huffman

A. Adaptive Huffman Coding

Metode Adaptive dipakai pd saat pembaharuan (update) model algoritma baru baik dari proses kompresi maupun dekompresi.

Konsep Dasar :

Encoder :
Initialize_model
Repeat for each character
{
Encode character
Update model
}
Decoder :
Initialize_model
Repeat for each character
{
Decode character
Update_model
}
Masalahnya adl bagaimana meng-update model algoritma yg terdiri dari menambah jumlah & mengupdate pohon Huffman. Caranya adl dg meng-update bagian pohon dimana terjadi proses pemampatan/nirmampat.

Pohon Huffman diinisialisasikan dg simpul single yg dikenal dg Not-Yet-Transmitted (NYT) Code yg dikirimkan setiap kali ditemukan karakter baru. Algoritma bekerja dg penomoran yg unik pd simpul dg jumlah daun yg berbeda.

Langkah-langkah peng-update-an model :
  1. Jika kode yg pertama kali ditemukan adl NYT, maka tambahkan dua simpul pd simpul NYT. Satu simpul sebagai simpul NYT & simpul yg lain sebagai daun. Tambahkan jumlah daun. Jika bukan NYT, langsung menuju daun.
  2. Jika pd blok tidak terdapat angka tertinggi, tukarkan dg angka tertinggi pd blok.
  3. Tambahkan jumlah dari simpul tersebut.
  4. Periksa apakah simpul tersebut mrp simpul akar. Jika bukan pergi ke simpul parent.

B. Length-Limited Huffman Coding

Variasi Huffman ini dipakai unt mendapatkan jarak kedalaman terkecil dari suatu simbol, dg batasan bahwa panjang masing-masing yg dimasukkan tidak kurang dari nilai konstanta yg diberikan. Metode ini biasanya dipakai pd GNU gzip.

Langkah-langkah dlm Metode Length-Limited

Huffman adl :
  1. Memilih dua / lebih simbol yg ingin dimampatkan
  2. Gabungkan simbol-simbol tersebut & gantikan dg pseudo-symbol beserta frekuensinya.
  3. Lakukan langkah di atas secara iteratif sampai semua simpul yg ada menjadi satu simpul akar.
  4. Jika simpul-simpul tersebut memiliki frekuensi yg sama, maka pilihlah simpul dg kedalaman terpendek.

C. n-ary Huffman Template Algorithm

Algoritma ini sebenarnya mirip dg algoritma Huffman biasa. Bedanya, pohon Huffman yg dipakai dlm algoritma ini memiliki lebih dari dua akar (0 & 1). Sementara dg Huffman template algorithm, memungkinkan unt menggunakan ukuran non-numerik (ukuran selain biaya & frekuensi).

D. Huffman With Unequal Letter Costs

Pada metode ini terdapat suatu permasalahan dimana suatu set kode yg terdiri dari beberapa huruf dg frekuensi kemunculan & biaya (cost) yg berbeda. Metode ini ditujukan unt mencari kode prefiks (prefix code) & menghitung biaya minimumnya (minimum cost). Prefix Code mrp sekumpulan kode yg prefix-free. Biaya (cost ) dari ini mrp jumlah biaya dari masing-masing huruf pd kode tersebut.

Contoh :

Terdapat dua buah kode di mana masing-masing kode memiliki biaya minimum unt frekuensi (f1,f2,f3,f4) = (2,2,1,1) tapi pd biaya huruf yg berbeda. Kode {00,01,10,11} memiliki biaya minimum unt kasus Huffman yg standar Σ = {0,1} dimana panjang tiap huruf adl 1. Kode {aaa, aab, ab, b} memiliki biaya minimum unt alphabet Σ = {a,b} dimana panjang a adl 1 & panjang b adl 3.

Biaya Kode Kiri = 2 · 2 + 2 · 2 + 1 · 2 + 1 · 2 = 12
Biaya Kode Kanan = 2 · 3 + 2 · 3 + 1 · 4 + 1 · 5 = 21.

Langkah-langkah umum metode Huffman Coding with Unequal Letter Cost :
  1. Mencari kode K-Prefix yg optimal.
  2. Mengubah kode K-Prefix menjadi kode prefix yg optimal.
  3. Setelah didapat kode hasil kemudian hitung biaya (cost)-nya.

Contoh Program Algoritma Huffman Dengan Java




public class Huffman {

    // Ukuran panjang alfabet ASCII
    private static final int R = 256;

    // pohon simpul Huffman 
    private static class Node implements Comparable<Node> {
        private final char ch;
        private final int freq;
        private final Node left, right;

        Node(char ch, int freq, Node left, Node right) {
            this.ch    = ch;
            this.freq  = freq;
            this.left  = left;
            this.right = right;
        }

        // Apakah node daun?
        private boolean isLeaf() {
            assert (left == null && right == null) || (left != null && right != null);
            return (left == null && right == null);
        }

        // membandingkan, berdasarkan frekuensi
        public int compareTo(Node that) {
            return this.freq - that.freq;
        }
    }


    // kompres byte dari input standar & menulis ke output standar
    public static void compress() {
        // baca masukan
        String s = BinaryStdIn.readString();
        char[] input = s.toCharArray();

        // tabulasi jumlah frekuensi
        int[] freq = new int[R];
        for (int i = 0; i < input.length; i++)
            freq[input[i]]++;

        // membangun pohon Huffman
        Node root = buildTrie(freq);

        // membangun tabel kode
        String[] st = new String[R];
        buildCode(st, root, "");

        // cetak unt decoder
        writeTrie(root);

        // Cetak jumlah byte dlm pesan terkompresi asli
        BinaryStdOut.write(input.length);

        // menggunakan kode Huffman unt mengkodekan masukan
        for (int i = 0; i < input.length; i++) {
            String code = st[input[i]];
            for (int j = 0; j < code.length(); j++) {
                if (code.charAt(j) == '0') {
                    BinaryStdOut.write(false);
                }
                else if (code.charAt(j) == '1') {
                    BinaryStdOut.write(true);
                }
                else throw new IllegalStateException("Illegal state");
            }
        }

        // Close output stream
        BinaryStdOut.close();
    }

    // membangun Huffman tree berdasarkan frekuensi
    private static Node buildTrie(int[] freq) {

        // antrian prioritas initialze dg pohon-pohon tunggal
        MinPQ<Node> pq = new MinPQ<Node>();
        for (char i = 0; i < R; i++)
            if (freq[i] > 0)
                pq.insert(new Node(i, freq[i], null, null));

        // kasus khusus dlm hal hanya ada satu karakter dg frekuensi nol
        if (pq.size() == 1) {
           if (freq['\0'] == 0) pq.insert(new Node('\0', 0, null, null));
           else                 pq.insert(new Node('\1', 0, null, null));
        }

        // menggabungkan dua pohon terkecil
        while (pq.size() > 1) {
            Node left  = pq.delMin();
            Node right = pq.delMin();
            Node parent = new Node('\0', left.freq + right.freq, left, right);
            pq.insert(parent);
        }
        return pq.delMin();
    }


    // menulis bitstring-dikodekan trie ke output standar
    private static void writeTrie(Node x) {
        if (x.isLeaf()) {
            BinaryStdOut.write(true);
            BinaryStdOut.write(x.ch, 8);
            return;
        }
        BinaryStdOut.write(false);
        writeTrie(x.left);
        writeTrie(x.right);
    }

    // membuat tabel dari simbol & pengkodean 
    private static void buildCode(String[] st, Node x, String s) {
        if (!x.isLeaf()) {
            buildCode(st, x.left,  s + '0');
            buildCode(st, x.right, s + '1');
        }
        else {
            st[x.ch] = s;
        }
    }


    // memperluas masukan Huffman-encode dari input standar & menulis ke output standar
    public static void expand() {

        // baca di Huffman trie dari input stream
        Node root = readTrie(); 

        // jumlah byte unt menulis
        int length = BinaryStdIn.readInt();

        // decode menggunakan Huffman
        for (int i = 0; i < length; i++) {
            Node x = root;
            while (!x.isLeaf()) {
                boolean bit = BinaryStdIn.readBoolean();
                if (bit) x = x.right;
                else     x = x.left;
            }
            BinaryStdOut.write(x.ch, 8);
        }
        BinaryStdOut.close();
    }


    private static Node readTrie() {
        boolean isLeaf = BinaryStdIn.readBoolean();
        if (isLeaf) {
            return new Node(BinaryStdIn.readChar(), -1, null, null);
        }
        else {
            return new Node('\0', -1, readTrie(), readTrie());
        }
    }


    public static void main(String[] args) {
        if      (args[0].equals("-")) compress();
        else if (args[0].equals("+")) expand();
        else throw new IllegalArgumentException("Illegal command line argument");
    }

}


Algoritma Huffman Dengan Java

Algoritma Huffman

Algoritma Huffman mrp algoritma yg dikembangkan oleh David A. Huffman yg dipakai unt menemukan prefix code yg optimal & dipublikasikan dlm sebuah paper “A Method for the Construction of Minimum-Redundancy Codes” pd tahun 1952.

Prinsip kerja algoritma Huffman adl mengkodekan setiap karakter ke dlm representasi bit. Representasi bit unt setiap karakter berbeda satu sama lain berdasarkan frekuensi kemunculan karakter. Semakin sering karakter tersebut muncul, maka semakin pendek panjang representasi bitnya. Sebaliknya jika semakin jarang frekuensi suatu karakter unt muncul, maka semakin panjang representasi bit unt karakter tersebut.

Dalam perkembangannya, pengimplementasinya dpt juga dipakai dlm bidang kriptografi / unt pengkompresi jenis data lainnya. Sebagian besar orang mengklasifikasikan algoritma ini menjadi 2 kategori, yaitu :

Huffman statis

Algoritma Huffman yg paling dasar adl algoritma Huffman statis. Yaitu algoritma yg hanya dpt dipakai unt kompresi data teks.

Huffman Dinamis 

merupakan pengembangan dari algoritma Huffman statis dg manambah / mengurangi suatu proses tertentu pd algoritma Huffman statis, hingga algoritma ini menjadi berbeda dg algoritma Huffman yg benar-benar dikembangkan oleh David A. Huffman.

Algoritma Huffman menggunakan prinsip pengkodean yg mirip dg kode Morse, yaitu tiap karakter (simbol) dikodekan hanya dg rangkaian beberapa bit, dimana karakter yg sering muncul dikodekan dg rangkaian bit yg pendek & karakter yg jarang muncul dikodekan dg rangkaian bit yg lebih panjang. Berdasarkan tipe peta kode yg dipakai unt mengubah pesan awal (isi data yg dimasukkan) menjadi sekumpulan code-word, algoritma Huffman termasuk ke dlm kelas algoritma yg menggunakan metode statik, yaitu metode yg selalu menggunakan peta kode yg sama. Metode ini membutuhkan dua fase (two-phase), yaitu fase pertama unt menghitung probabilitas kemunculan tiap simbol & menentukan peta kodenya, & fase kedua unt mengubah pesan menjadi kumpulan kode yg akan ditransmisikan.

Sedangkan berdasarkan teknik pengkodean simbol yg dipakai, algoritma Huffman menggunakan metode symbol-wise, yaitu metode yg menghitung kemunculan dari setiap simbol dlm satu waktu, dimana simbol yg sering muncul diberi kode lebih pendek dibandingkan dg simbol yg jarang muncul.

Dalam Huffman Coding, panjang blok dari keluaran sumber dipetakan dlm blok biner berdasarkan pajang variable. Cara spt ini disebut sebagai fixed to variable-length coding. Ide dasar dari cara Huffman ini adl memetakan mulai simbol yg paling banyak terdapat pd sebuah urutan sumber sampai dg yg jarring muncul menjadi urutan biner. dlm variable-length coding, sinkronisasi mrp suatu masalah. Ini berarti harus terdapat satu cara unt memecahkan urutan biner yg diterima kedalam suatu codeword.

Seperti yg disebutkan diatas, bahwa ide dari Huffman Coding adl memilih panjang codeword dari yg paling besar probabilitasnya sampai dg urutan codeword yg paling kecil probabilitasnya. Apabila kita dpt memetakan setiap keluaran sumber dari probabiltas pi ke sebuah codewortd dg panjang 1/pi & pd saat yg bersamaan dpt memastikan bahwa dpt didekodekan secara unik, kita dpt mecari rata-rata panjang kode H(x). Huffman Code dpt mendekodekan secara unik dg H(x) minimum, & optimum pd keunikan dari kode-kode tersebut.

Pembentukan Pohon Huffman

Kode Huffman pd dasarnya mrp kode prefiks (prefix code), yaitu himpunan yg berisi sekumpulan kode biner, dimana pd kode prefiks ini tidak ada kode biner yg menjadi awalan bagi kode biner yg lain. Kode prefiks biasanya direpresentasikan sebagai pohon biner yg diberikan nilai / label.

Untuk cabang kiri pd pohon biner diberi label 0, sedangkan pd cabang kanan pd pohon biner diberi label 1. Rangkaian bit yg terbentuk pd setiap lintasan dari akar ke daun mrp kode prefiks unt karakter yg berpadanan. Pohon biner ini biasa disebut pohon Huffman.

Langkah-langkah pembentukan pohon Huffman adl sebagai berikut :

  1. Baca semua karakter di dlm teks unt menghitung frekuensi kemunculan setiap karakter. Setiap karakter penyusun teks dinyatakan sebagai pohon bersimpul tunggal. Setiap simpul di-assign dg frekuensi kemunculan karakter tersebut.
  2. Terapkan strategi algoritma sebagai berikut, gabungkan dua buah pohon yg mempunyai frekuensi terkecil pd sebuah akar. Setelah digabungkan, akar tersebut akan mempunyai frekuensi yg mrp jumlah dua buah pohon-pohon penyusunnya.
  3. Ulangi langkah 2 sampai hanya tersisa satu buah pohon Huffman. Agar pemilihan dua pohon yg akan digabungkan berlangsung cepat, maka semua pohon yg ada selalu terurut menaik berdasarkan frekuensi.

Sebagai contoh, dlm kode ASCII string 7 huruf “ABACCDA” membutuhkan representasi 7 x 8 bit = 56 bit (7 byte), dg rincian sebagai berikut:
A = 01000001
B = 01000010
A = 01000001
C = 01000011
C = 01000011
D = 01000100
A = 01000001
Pada string tersebut, frekuensi kemunculan A = 3, B = 1, C=2, & D = 1, hingga proses pembentukan pohon Huffman-nya adl spt yg ditampilkan pd gambar berikut:

Algoritma Huffman Dengan Java
Algoritma Huffman Dengan Java

Proses Encoding

Proses encoding unt satu karakter dimulai dg membuat pohon Huffman terlebih dahulu. Setelah itu, kode unt satu karakter dibuat dg menyusun nama string biner yg dibaca dari akar sampai ke daun pohon Huffman.

Langkah-langkah unt melakukan encoding pd suatu string biner adl sebagai berikut :
  1. Tentukan karakter yg akan di-encode.
  2. Mulai dari akar, baca setiap bit yg ada pd cabang yg bersesuaian sampai menemukan daun di mana karekter itu berada.
  3. Ulangi langkah 2 sampai seluruh karakter di-encode.
Proses Decoding

Decoding mrp kebalikan dari encoding. Decoding berarti menyusun kembali data yg tersandi menjadi data aslinya. Langkah-langkah decoding suatu data yg tersandi menggunakan pohon Huffman adl sebagai berikut :
  1. Baca sebuah bit dari string biner.
  2. Mulai dari akar.
  3. Untuk setiap bit pd langkah 1, lakukan penelusuran pd cabang yg bersesuaian.
  4. Ulangi langkah 1, 2, & 3 sampai bertemu daun. Kodekan rangkaian bit yg telah dibaca dg karakter di daun.
  5. Ulangi dari langkah 1 sampai semua bit di dlm string habis.
Gambar berikut menunjukan proses decoding string biner “111” yg menghasilkan karakter “D”.


Algoritma Huffman Dengan Java
Algoritma Huffman Dengan Java

Macam-macam Variasi Kode Huffman

A. Adaptive Huffman Coding

Metode Adaptive dipakai pd saat pembaharuan (update) model algoritma baru baik dari proses kompresi maupun dekompresi.

Konsep Dasar :

Encoder :
Initialize_model
Repeat for each character
{
Encode character
Update model
}
Decoder :
Initialize_model
Repeat for each character
{
Decode character
Update_model
}
Masalahnya adl bagaimana meng-update model algoritma yg terdiri dari menambah jumlah & mengupdate pohon Huffman. Caranya adl dg meng-update bagian pohon dimana terjadi proses pemampatan/nirmampat.

Pohon Huffman diinisialisasikan dg simpul single yg dikenal dg Not-Yet-Transmitted (NYT) Code yg dikirimkan setiap kali ditemukan karakter baru. Algoritma bekerja dg penomoran yg unik pd simpul dg jumlah daun yg berbeda.

Langkah-langkah peng-update-an model :
  1. Jika kode yg pertama kali ditemukan adl NYT, maka tambahkan dua simpul pd simpul NYT. Satu simpul sebagai simpul NYT & simpul yg lain sebagai daun. Tambahkan jumlah daun. Jika bukan NYT, langsung menuju daun.
  2. Jika pd blok tidak terdapat angka tertinggi, tukarkan dg angka tertinggi pd blok.
  3. Tambahkan jumlah dari simpul tersebut.
  4. Periksa apakah simpul tersebut mrp simpul akar. Jika bukan pergi ke simpul parent.

B. Length-Limited Huffman Coding

Variasi Huffman ini dipakai unt mendapatkan jarak kedalaman terkecil dari suatu simbol, dg batasan bahwa panjang masing-masing yg dimasukkan tidak kurang dari nilai konstanta yg diberikan. Metode ini biasanya dipakai pd GNU gzip.

Langkah-langkah dlm Metode Length-Limited

Huffman adl :
  1. Memilih dua / lebih simbol yg ingin dimampatkan
  2. Gabungkan simbol-simbol tersebut & gantikan dg pseudo-symbol beserta frekuensinya.
  3. Lakukan langkah di atas secara iteratif sampai semua simpul yg ada menjadi satu simpul akar.
  4. Jika simpul-simpul tersebut memiliki frekuensi yg sama, maka pilihlah simpul dg kedalaman terpendek.

C. n-ary Huffman Template Algorithm

Algoritma ini sebenarnya mirip dg algoritma Huffman biasa. Bedanya, pohon Huffman yg dipakai dlm algoritma ini memiliki lebih dari dua akar (0 & 1). Sementara dg Huffman template algorithm, memungkinkan unt menggunakan ukuran non-numerik (ukuran selain biaya & frekuensi).

D. Huffman With Unequal Letter Costs

Pada metode ini terdapat suatu permasalahan dimana suatu set kode yg terdiri dari beberapa huruf dg frekuensi kemunculan & biaya (cost) yg berbeda. Metode ini ditujukan unt mencari kode prefiks (prefix code) & menghitung biaya minimumnya (minimum cost). Prefix Code mrp sekumpulan kode yg prefix-free. Biaya (cost ) dari ini mrp jumlah biaya dari masing-masing huruf pd kode tersebut.

Contoh :

Terdapat dua buah kode di mana masing-masing kode memiliki biaya minimum unt frekuensi (f1,f2,f3,f4) = (2,2,1,1) tapi pd biaya huruf yg berbeda. Kode {00,01,10,11} memiliki biaya minimum unt kasus Huffman yg standar Σ = {0,1} dimana panjang tiap huruf adl 1. Kode {aaa, aab, ab, b} memiliki biaya minimum unt alphabet Σ = {a,b} dimana panjang a adl 1 & panjang b adl 3.

Biaya Kode Kiri = 2 · 2 + 2 · 2 + 1 · 2 + 1 · 2 = 12
Biaya Kode Kanan = 2 · 3 + 2 · 3 + 1 · 4 + 1 · 5 = 21.

Langkah-langkah umum metode Huffman Coding with Unequal Letter Cost :
  1. Mencari kode K-Prefix yg optimal.
  2. Mengubah kode K-Prefix menjadi kode prefix yg optimal.
  3. Setelah didapat kode hasil kemudian hitung biaya (cost)-nya.

Contoh Program Algoritma Huffman Dengan Java




public class Huffman {

    // Ukuran panjang alfabet ASCII
    private static final int R = 256;

    // pohon simpul Huffman 
    private static class Node implements Comparable<Node> {
        private final char ch;
        private final int freq;
        private final Node left, right;

        Node(char ch, int freq, Node left, Node right) {
            this.ch    = ch;
            this.freq  = freq;
            this.left  = left;
            this.right = right;
        }

        // Apakah node daun?
        private boolean isLeaf() {
            assert (left == null && right == null) || (left != null && right != null);
            return (left == null && right == null);
        }

        // membandingkan, berdasarkan frekuensi
        public int compareTo(Node that) {
            return this.freq - that.freq;
        }
    }


    // kompres byte dari input standar & menulis ke output standar
    public static void compress() {
        // baca masukan
        String s = BinaryStdIn.readString();
        char[] input = s.toCharArray();

        // tabulasi jumlah frekuensi
        int[] freq = new int[R];
        for (int i = 0; i < input.length; i++)
            freq[input[i]]++;

        // membangun pohon Huffman
        Node root = buildTrie(freq);

        // membangun tabel kode
        String[] st = new String[R];
        buildCode(st, root, "");

        // cetak unt decoder
        writeTrie(root);

        // Cetak jumlah byte dlm pesan terkompresi asli
        BinaryStdOut.write(input.length);

        // menggunakan kode Huffman unt mengkodekan masukan
        for (int i = 0; i < input.length; i++) {
            String code = st[input[i]];
            for (int j = 0; j < code.length(); j++) {
                if (code.charAt(j) == '0') {
                    BinaryStdOut.write(false);
                }
                else if (code.charAt(j) == '1') {
                    BinaryStdOut.write(true);
                }
                else throw new IllegalStateException("Illegal state");
            }
        }

        // Close output stream
        BinaryStdOut.close();
    }

    // membangun Huffman tree berdasarkan frekuensi
    private static Node buildTrie(int[] freq) {

        // antrian prioritas initialze dg pohon-pohon tunggal
        MinPQ<Node> pq = new MinPQ<Node>();
        for (char i = 0; i < R; i++)
            if (freq[i] > 0)
                pq.insert(new Node(i, freq[i], null, null));

        // kasus khusus dlm hal hanya ada satu karakter dg frekuensi nol
        if (pq.size() == 1) {
           if (freq['\0'] == 0) pq.insert(new Node('\0', 0, null, null));
           else                 pq.insert(new Node('\1', 0, null, null));
        }

        // menggabungkan dua pohon terkecil
        while (pq.size() > 1) {
            Node left  = pq.delMin();
            Node right = pq.delMin();
            Node parent = new Node('\0', left.freq + right.freq, left, right);
            pq.insert(parent);
        }
        return pq.delMin();
    }


    // menulis bitstring-dikodekan trie ke output standar
    private static void writeTrie(Node x) {
        if (x.isLeaf()) {
            BinaryStdOut.write(true);
            BinaryStdOut.write(x.ch, 8);
            return;
        }
        BinaryStdOut.write(false);
        writeTrie(x.left);
        writeTrie(x.right);
    }

    // membuat tabel dari simbol & pengkodean 
    private static void buildCode(String[] st, Node x, String s) {
        if (!x.isLeaf()) {
            buildCode(st, x.left,  s + '0');
            buildCode(st, x.right, s + '1');
        }
        else {
            st[x.ch] = s;
        }
    }


    // memperluas masukan Huffman-encode dari input standar & menulis ke output standar
    public static void expand() {

        // baca di Huffman trie dari input stream
        Node root = readTrie(); 

        // jumlah byte unt menulis
        int length = BinaryStdIn.readInt();

        // decode menggunakan Huffman
        for (int i = 0; i < length; i++) {
            Node x = root;
            while (!x.isLeaf()) {
                boolean bit = BinaryStdIn.readBoolean();
                if (bit) x = x.right;
                else     x = x.left;
            }
            BinaryStdOut.write(x.ch, 8);
        }
        BinaryStdOut.close();
    }


    private static Node readTrie() {
        boolean isLeaf = BinaryStdIn.readBoolean();
        if (isLeaf) {
            return new Node(BinaryStdIn.readChar(), -1, null, null);
        }
        else {
            return new Node('\0', -1, readTrie(), readTrie());
        }
    }


    public static void main(String[] args) {
        if      (args[0].equals("-")) compress();
        else if (args[0].equals("+")) expand();
        else throw new IllegalArgumentException("Illegal command line argument");
    }

}

Contoh Program Algoritma Huffman Dengan Java

Source Code Algoritma Huffman Dengan Java

Source Code Tutorial belajar Gratis download Flow Chart PDF ZIP RAR DOC Java C# Visual Basic VB PHP Matlab C++ Penerapan implementasi metode algoritma pemrograman

Tutorial belajar Algoritma Huffman Dengan Java

VB PHP Matlab C++ Penerapan implementasi metode algoritma pemrograman Source Code Tutorial belajar Gratis download Flow Chart PDF ZIP RAR DOC Java C# Visual Basic

Gratis download Algoritma Huffman Dengan Java

Chart PDF ZIP RAR DOC Java C# Visual Basic VB PHP Matlab C++ Penerapan implementasi metode algoritma pemrograman Source Code Tutorial belajar Gratis download Flow

Penerapan implementasi Algoritma Huffman Dengan Java Algoritma Huffman Dengan Java

Posted by: Project-G Contoh Program Algoritma Huffman Dengan Java Updated at : 00.08
Jika Anda perlu source code terkait dengan artikel di atas atau ada yang ingin di tanyakan anda bisa melakukan konsultasi gratis kepada kami, melalui form di bawah. Hasil konsultasi akan di kirimkan ke email Anda. Kami mohon supportnya dengan mengklik beberapa tombol berikut :


Contoh Program Algoritma Huffman Dengan Java

perhatian

Informasi Penting Untuk Mahasiswa !

Kami menawarkan layanan jasa konsultan bimbingan pembuatan program untuk Tesis Skripsi dan Tugas Akhir Informatika, Komputer, Elektro dan Teknik lainnya yang bidang minatnya mengarah ke teknologi informasi. BASED PROJECT :Mobile Development (Java, Adobe, AS3, Android, BB, iOS, WPhone dll), Web & Desktop Development (.Net, C#, MATLAB, PHP, Delphi, Visual Basic dll). BONUS : Di bimbing untuk penguasaan materi dan coding dan revisi.
detail
Label: ,
Konsultasi gratis