TUGAS BESARSTRUKTUR DATA ANALISA ALGORITMA

“HUFFMAN CODE”

DUSUSUN OLEH:1. RIZKY KARTIKA PUTRI 12091000012. ROLAND TRI REINHARD DASE 12091000453. BIMA PRIHASTO 12091000534. REZKY BRIAN JONFRIS PURBA 1209100085

INSTITUT TEKNOLOGI SEPULUH NOPEMBER SURABAYAJURUSAN MATEMATIKA

2010-2011

1

DAFTAR ISI

Sampul…………………………………………………. 1Pendahuluan……………………………………………. 2Spesifikasi Sistem……………………………………… 6Desain………………………………………………….. 10Uji Coba………………………………………………… 16Penutup ………………………………………………… 17

2

I. PENDAHULUAN

Dalam ilmu komputer dan teori informasi, Huffman coding merupakan algoritma pengkodean yang digunakan dalam hal mengompres data. Istilah ini mengacu pada penggunaan tabel kode variable-length untuk pengkodean sumber simbol ( seperti karakter dalam sebuah data) dimana tabel kode variable-length telah diturunkan dengan cara tertentu berdasarkan perkiraan probabilitas dari kejadian untuk setiap kemungkinan dari sumber simbol. Hal ini dikembangkan oleh David A. Huffman saat dia masih mengambil gelar Ph.D. di MIT, dan diterbitkan di Koran tahun 1952 “A Method for the Construction of Minimum-Redundancy Codes” (sebuah metode untuk pembangunan minimum redundancy codes).

Huffman coding menggunakan metode tertentu dalam memilih perwakilan untuk setiap simbol, sehingga kode awalan (kadang-kadang disebut “awalan kode bebas(prefix-free codes)”, yaitu bit string yang mewakili beberapa simbol tertentu tidak pernah merupakan prefix dari bit string yang mewakili simbol yang lain) yang mengekspresikan sumber simbol yang paling umum menggunakan string yang lebih pendek dari bit daripada yang digunakan untuk sumber simbol yang lebih umum. Huffman mampu merancang metode kompresi yang paling efisien dari jenis ini: tidak ada pemetaan lainnya dari sumber simbol untuk string yang unik dari bit yang akan menghasilkan ukuran rata-rata output yang lebih kecil ketika frekuensi simbol yang sebenarnya cocok dengan cara yang berguna untuk membuat kode. Sebuah metode kemudian ditemukan untuk merancang kode Huffman dalamwaktu yang linier jika probabilitas dari input (juga dikenal sebagai bobot/weight) diurutkan.

Kita sering menggambarkan sekumpulan materi dalam sebuah program komputer dengan menempatkan sebuah kode unik kedalam setiap materi. Misalnya, pola standar kode ASCII memberikan sebuah nilai delapan bit yang unik ke setiap masing-masing karakter. Hal tersebut mengambil nomor minimum dari bits untuk memberikan kode-kode yang unik ke setiap masing-masing karakter. Misalnya, diambil [log 128] atau tujuh bits untuk memberikan 128 kode-kode unik yang dibutuhkan untuk mewakili 128 simbol dari kumpulan karakter ASCII.

Syarat [log n] bits untuk dapat menggambarkan n nilai kode-kode yang unik dengan mengasumsikan semua kode memiliki panjang yang sama, seperti kode ASCII. Hal ini disebut pola sandi fixed-length. Jika semua karakter digunakan dengan cara yang sama, maka pola kode fixed-length merupakan metode ruang yang paling efisien. Akan tetapi, kita mungkin sadar bahwa tidak semua karakter digunakan dengan cara yang sama di hamper semua aplikasi. Misalnya, bermacam-macam huruf dalam dokumen bahasa inggris mempunyai frekuensi kegunaan yang sangat berbeda.

3

Jika beberapa karakter digunakan lebih sering dari yang lain, dapatkah kita mengambil keuntungan dari kejadian ini dan bagaimana cara memberikan kode-kode yang lebih pendek? Akibatnya mungkin karakter-karakter yang lain memerlukan ruang yang lebih panjang. Konsep ini merupakan inti dari teknik kompresi data yang sering digunakan sehari-hari. Bagian selanjutnya akan menjelaskan mengenai kode variable-length, yang disebut Huffman coding. Tetapi Huffman coding jarang digunakan walaupun berbentuk sederhana dalam hal mengompresi data (ada cara lain yang lebih baik). Huffman coding memberi kesan yang menarik dalam pola persandian. Satu manfaat untuk mempelajarinya adalah karena Huffman coding memberik keuntungan pertama kita untuk melihat jenis dari struktur tree yang mengarah kepada search tree.

4

II. SPESIFIKASI SISTEM

Pada huffman code yang dibuat kelompok kami, terdiri dari 8 class, yakni code.java, Dsutil.java, MinHeap.java, HuffBaseNode.java, HuffTree.java, HuffLeafNode.java, HuffinternalNode.java, dan Huffman.java.

Pada proses pertama yakni pembentukan array yang kemudian dengan konsep MinHeap dengan mengurutkan frekuensi terkecil ke terbesar, perintah MinHeap akan terus berulang sampai panjang length<1, dengan asumsi pembentukan MinHeap berdasarkan array list yang pertama.

Kemudian setelah melalui MinHeap note terkecil akan dijumlahkan dengan node terkecil kedua. Sampai pada akhirnya MinHeap tersebut mempunyai panjang length<1, pada note yang dijumlahkan otomatis akan mengalami pengelompokan yang didefinisikan di kelas HuffTree.java, HuffLeafNode.java dan HuffInternal.java. pengelompokan tersebut akan disimpan sebagai satu kesatuan yang mempunyai akar, yang kemudian tiap-tiap akar tersebut akan sebagai acuan penjumlahan berikutnya.

Input-OutputMisalkan kita memasukkan 5 frekuensi yang masing-masing: a=3, b=5, c=1, d=2, e=7.Maka karena masukkan tersebut tidak urut, maka masukkan tersebut didefinisikan sebagai array yang kemudian ditransformasikan pada MinHeap, sehingga didapatkan urutan :c=1,d=2,a=3,b=5,e=7

5

c

1

b

5

e

7

a

3

d

2

Kemudian node c dan node d diambil dan kemudian dijumlahkan lalu dilakukan proses MinHeap sehingga:

Kemudian node a dan node c&d diambil dan kemudian dijumlahkan lalu dilakuakan proses Minheap sehingga:

Kemudian node b dan node c&d&a diambil dan kemudian dijumlahkan lalu dilakukan proses MinHeap sehingga:

Kemudian node e dan node c&d&a&b diambil dan kemuadian dijumlahkan lalu dilakukan proses MinHeap sehingga:

Dan proses Min Heap berhenti karena length<1.

6

a

3c&d

3

e

7

b

5

e

7

b

5

c&d&a

6

c&d&a&b

11

e

7

e&c&d&a&b

18

Pada pengelompokan tersebut sebenarnya adalah sebuah tree yang disimpan sebagai kesatuan tersendiri, fungsi tersebut merupakan bagian dari kelas HuffLeafNode.java , HuffInternalNode.java, dan HuffTree.java. maka pengelompokan terseut dapat didefinisiakan sebagai:

7

3

c&d

3d

2

c

1

c&d&a

6

6

3a

3 c

1

d

2

11

c&d&a&b

11

a

3

d

2

c

1

3

b

5

6

18e&c&d&a&b

18

Hasil Akhir Huffman Code

Pada fungsi main terdapat pada kelas Huffman.java, pada kelas tersebut merupakan kelas inti karena fungsi penjumlahan dari masing kelopompok tree dan pengkodean yang terdiri dari encode dan decode terdapat pada kelas tersebut. Pada pengkodean encode didefinisikan bahwa anak kiri didefinisikan sebagai 0 dan anak kanan didefinisikan sebagai 1, sehingga didapat output dari tree tersebut: e = 0 ; b = 10 ; a = 110 ; c = 1110 ; d = 1111

Letter Frekuensi Bit Banyak bit*Frekuensie 7 0 1*7 = 7b 5 10 2*5 = 10a 3 110 3*3 = 9c 1 1110 4*1 = 4d 2 1111 4*2 = 8Jumlah 18 38

Yang didapat dari jumlah dari masing-masing hasil perkalian jumlah bit dikali freuensi, yang kemudian julah tersebut dibagi oleh frekuensi total.

8

1

1

1

1

0

0

0

0

e

7

6

a

3

d

2

c

1

3

11

b

5

18

e

7

6

a

3

d

2

c

1

3

11

b

5

rata-rata cost per karakternya = Jumlahbanyak bit∗frekuensi

jumlah frekuensi

¿ 3818

¿2.1111111Proses EncodeEncode adalah cara menyusun string biner dari teks yang ada. Proses encode untuk satu karakter dimulai dengan membuat pohon huffman terlebih dahulu. Setelah itu, kode untuk satu karakter dibuat dengan menyusun nama string biner yang dibaca dari akar sampai ke daun pohon huffman. Langkah-langkah untuk men-encoding suatu string biner adalah sebagai berikut:1. Tentukan karakter yang akan di-encode2. Mulai dari akar, baca setiap bit yang ada pada cabang yang bersesuaian sampai ketemu

daun dimana karakter itu berada3. Ulangi langkah 2 sampai seluruh karakter si-encodeSehingga pada uji program pada saat encode dengan memasukkan kalimat “abac”, maka langkah pertama telah terpenuhi dengan mentukan karakter. Kemudian langkah kedua yakni melakukan penelusuran pada pohon biner, sehingga pada karakter pertama yakni huruf a dengan melakukan penelusuran pada pohon huffman didapat bahwa untuk menemukan huruf a pada daun maka setiap bit yang telah dilalui pada setiap cabang menghasilkan biner “110”, kemudian cara yang sama dilakuakan untuk mencari huruf b dan c sehinggan didapat bahwa b=10 dan c=1110. Sehingga hasil dari “abac” adalah “110101101110”

Proses DecodeDecode merupakan kebalikan dari encode. Decode berarti menyusun kembali data dari string biner menjadi sebuah karakter kembali. Docode dapat dilakukan dengan 2 cara, yang pertama menggunakan pohon huffman dan yang kedua menggunakan tabel kode Huffman. Langkah-langkah men-decode suatu string biner dengan menggunakan pohon huffman adalah sebgai berikut:1. Baca sebuah bit dari string biner2. Mulai dari akar3. Untuk setiap bit pada langkah 1, lakukan transversal pada cabang yang bersesuaian4. Ulagi langkah 1,2,dan 3 sampai bertemu daun. Kodekan rangkaian bit yang telah dibaca

dengan karakter di daun5. Ulangi dari langkah 1 sampai semua bit dalam string habis.Sehingga pada uji program pada saat decode dengan memasukkan string biner “100110”. Sehingga langkah awal adalah membaca string biner yang diinputkan, kemudian memulai penelusuran dari akar. Penelusuran dilakukan sesuai dengan urutan bit yang dimasukkan. Sehingga pada penelusuran uji program dimulai dengan “1” kemudian karena masih mempunyai anak sehingga dilanjutkan string biner berikutnya yakni “0”. Kemudian karena sudah tidak mempunyai anak lagi yang artinya posisi telah berada pada daun. Sehingga

9

proses selanjutnya adalah mengkodekan karakter yang terdapat pada daun yakni karakter “b”. Kemudian selanjutnya proses yang sama dari penelusuran urutan bit selanjutnya akan terus berulang. Sampai pada akhirnnya semua bit dalam string habis. Sehingga dapat disimpulkan bahwa bit selanjutnya adalah “0” yang menghasilkan karakter “e”, dan kemudian adalah “110” yang menghasilkan karakter a. Yang pada akhirnya bila disatukan akan membentuk kalimat “bea” .

DESAIN

10

public class Code { // class code yang di simpan di code table private char data; private String code;

public Code(char d, String c) // konstruktor { data = d; code = c; }

public char data() { return data; } // return data public String code() { return code; } } // return code

// interface implementasi pada class HuffInternaNode dan HuffLeafNodepublic interface HuffBaseNode<E> { public boolean isLeaf(); public int weight(); }

class HuffInternalNode<E> implements HuffBaseNode<E> { private int weight; // variable weight ( jumlah frekuensi dari anak ) private HuffBaseNode<E> left; // pointer ke anak kiri private HuffBaseNode<E> right; // pointer ke anak kanan public HuffInternalNode(HuffBaseNode<E> l, HuffBaseNode<E> r, int wt) // konstruktor { left = l; right = r; weight = wt; } public HuffBaseNode<E> left() { return left; } // return anak kiri public HuffBaseNode<E> right() { return right; } // return anak kanan

public int weight() { return weight; } // return weight public boolean isLeaf() { return false; } } // return false

class HuffLeafNode<E> implements HuffBaseNode<E> { private E element; // Element for this node private int weight; // Weight for this node public HuffLeafNode(E el, int wt) // konstruktor { element = el; weight = wt; } public E element() { return element; } // return nilai elemen public int weight() { return weight; } // return weight public boolean isLeaf() { return true; } } // return true

class DSutil<E> { // DSutil class buat Huffman Code

11

public static <E> void swap(E[] A, int p1, int p2) { E temp = A[p1];

A[p1] = A[p2];A[p2] = temp; }

static void permute(int[] A) { for (int i = A.length; i > 0; i--) swap(A, i-1, DSutil.random(i)); } public static void swap(int[] A, int p1, int p2) { int temp = A[p1];

A[p1] = A[p2];A[p2] = temp;

}static <E> void permute(E[] A) { for (int i = A.length; i > 0; i--) swap(A, i-1, DSutil.random(i)); } static private Random value = new Random();static int random(int n) { return Math.abs(value.nextInt()) % n;}}}

public class MinHeap<E extends Comparable<? super E>> { // class MinHeap private E[] Heap; private int size; private int n;

public MinHeap(E[] h, int num, int max){ Heap = h; n = num; size = max; buildheap(); }

public int heapsize() { return n; }public boolean isLeaf(int pos){ return (pos >= n/2) && (pos < n); }public int leftchild(int pos) { assert pos < n/2 : "Position has no left child"; return 2*pos + 1; }

public int rightchild(int pos) { assert pos < (n-1)/2 : "Position has no right child"; return 2*pos + 2; }

public int parent(int pos) {

12

assert pos > 0 : "Position has no parent"; return (pos-1)/2; }

public void buildheap() { for (int i=n/2-1; i>=0; i--) siftdown(i); }

public void insert(E val) { assert n < size : "Heap is full"; int curr = n++; Heap[curr] = val; while ((curr != 0) && (Heap[curr].compareTo(Heap[parent(curr)]) < 0)) { DSutil.swap(Heap, curr, parent(curr)); curr = parent(curr); } }

private void siftdown(int pos) { assert (pos >= 0) && (pos < n) : "Illegal heap position"; while (!isLeaf(pos)) { int j = leftchild(pos); if ((j<(n-1)) && (Heap[j].compareTo(Heap[j+1]) > 0)) j++; if (Heap[pos].compareTo(Heap[j]) <= 0) return; DSutil.swap(Heap, pos, j); pos = j; } }

public E removemin() { assert n > 0 : "Removing from empty heap"; DSutil.swap(Heap, 0, --n); if (n != 0) siftdown(0); return Heap[n]; }

public E remove(int pos) { assert (pos >= 0) && (pos < n) : "Illegal heap position"; if (pos == (n-1)) n--; else { DSutil.swap(Heap, pos, --n while ((pos > 0) && (Heap[pos].compareTo(Heap[parent(pos)]) < 0)) { DSutil.swap(Heap, pos, parent(pos)); pos = parent(pos); } if (n != 0) siftdown(pos); } return Heap[n]; } }

13

class HuffTree<E> implements Comparable<HuffTree<E>>{ private HuffBaseNode<E> root; // root dari tree

public HuffTree(E el, int wt) // konstruktor { root = new HuffLeafNode<E>(el, wt); } public HuffTree(HuffBaseNode<E> l, HuffBaseNode<E> r, int wt) { root = new HuffInternalNode<E>(l, r, wt); }

public HuffBaseNode<E> root() { return root; } public int weight() // weight dari tree sama dengan weight root { return root.weight(); } public int compareTo(HuffTree<E> that) { if (root.weight() < that.weight()) return -1; else if (root.weight() == that.weight()) return 0; else return 1; } }

public class HuffmanCoding {

private static Vector<Code> codeTable = new Vector<Code>(); // The code lookup tableprivate static int total = 0; // jumlah weight dari codeprivate static MinHeap<HuffTree<Character>> Hheap;private static HuffTree<Character>[] TreeArray;

// membaca string dan membuat list dari node Huffman coding@SuppressWarnings("unchecked") static void readFreqs(BufferedReader d) throws IOException { String line; char letter; int freq; line = d.readLine(); int count = 0;

if (line != null) count = Integer.parseInt(line); elseSystem.out.println("bad input file"); TreeArray = (HuffTree<Character>[])new HuffTree[count]; for (int i=0; i<count; i++) { // memproses input dan membuat HuffTree baru line = d.readLine();

if (line != null&&line.length()>2&&Character.isDigit(line.charAt(2))){letter = line.charAt(0);

freq = Integer.parseInt(line.substring(2));TreeArray[i] = new HuffTree<Character>(letter,freq);}

14

elseSystem.out.println(“not enough character”);

}Hheap = new MinHeap<HuffTree<Character>>(TreeArray, count, count);}

// membuat Huffman tree dari list huffliststatic HuffTree<Character> buildTree() { HuffTree tmp1, tmp2, tmp3 = null;

while (Hheap.heapsize() > 1) { // ketika sisa 2 item tmp1 = Hheap.removemin(); tmp2 = Hheap.removemin(); tmp3 = new HuffTree<Character>(tmp1.root(), tmp2.root(), tmp1.weight() + tmp2.weight()); Hheap.insert(tmp3); // return tree baru ke heap } return tmp3; // return tree }

// menemukan index pada codetable untuk dimasukkan codewordstatic int getindex(char codeword) { int i; for (i=0; i<codeTable.size(); i++) if (codeword == codeTable.elementAt(i).data()) return i; return i; // tidak ketemu }

// menampikan code dan menambahkannya ke codetablestatic void outputTree(HuffBaseNode<Character> node, String prefix) { assert node != null : "Bad input tree"; if (node.isLeaf()) { System.out.println(((HuffLeafNode<Character>)node).element() + "\t" + prefix); char temp = ((HuffLeafNode<Character>)node).element(); codeTable.addElement(new Code(temp, prefix)); total += prefix.length() * node.weight(); } else { outputTree(((HuffInternalNode)node).left(), prefix + "0"); outputTree(((HuffInternalNode)node).right(), prefix + "1"); } } // proses Encode dan Decodestatic void doCommands(BufferedReader d, HuffTree<Character> tree) throws IOException { HuffBaseNode<Character> temp; String line; int i;

while ((line = d.readLine()) != null) { if (line.substring(0, 6).equals("decode")) {

15

for (i=0; line.charAt(i) != '"'; i++); System.out.print("Decode " + line.charAt(i++)); temp = tree.root(); for (; line.charAt(i) != '"'; i++) { // traverse tree if (line.charAt(i) == '0') temp = ((HuffInternalNode)temp).left(); else if (line.charAt(i) == '1') temp = ((HuffInternalNode)temp).right(); else assert false : "Bad input: " + line; if (temp.isLeaf()) { System.out.print(((HuffLeafNode)temp).element()); temp = tree.root(); // reset root } } System.out.println(line.charAt(i)); } else if (line.substring(0, 6).equals("encode")) { for (i=0; line.charAt(i) != '"'; i++); System.out.print("Encode " + line.charAt(i++)); for (; line.charAt(i) != '"'; i++) { // anggap codenya berupa characters int index = getindex(line.charAt(i)); assert index < codeTable.size() : "Tried to find code of bad character|" + line.charAt(i) + "|"; System.out.print(codeTable.elementAt(index).code()); } System.out.println(line.charAt(i)); } else assert false : "Bad command line: " + line; } // while }

public static void main(String argv[]) throws FileNotFoundException, IOException { BufferedReader f;

if (argv.length == 0) // membaca input f = new BufferedReader(new InputStreamReader(System.in)); else // data file dimasukkan sebagai parameter f = new BufferedReader(new InputStreamReader(new FileInputStream(argv[0]))); System.out.println("Read frequencies"); readFreqs(f); System.out.println("Build the tree"); HuffTree<Character> codes = buildTree(); System.out.println("Output the tree"); outputTree(codes.root(), ""); System.out.println("Average code length is " + (double)total/(double)codes.weight()); doCommands(f, codes); System.in.read(); } }III.

16

IV. UJI COBA

17

V. PENUTUP

Huffman coding merupakan algoritma pengkodean yang digunakan dalam hal mengompres data. Dengan huffman code kita dapat memperkecil jumlah bit dalam suatu teks, sehingga bila dibandingkan dengan kode ASCII maka akan terlihat persentase bit yang signifikan. Hal tersebut disebabkan karena huffman code hanya menggunakan huruf yang diperlukan saja semisal dalam bahasa jawa tidak mengenal huruf z sehingga huruf z dapat dihilangkan, hal tersebut tentu berbeda dengan bahasa inggris yang memerlukan huruf z. Sehingga pada intinya huffman code hanya menggunakan huruf yang diperlukan saja sehingga jumlah bit menjadi lebih kecil.

Pada tugas besar dari kelompok kami, yakni pada program kami harus ditentukan jumlah karakter dan perkiraan frekuensi karakter terlebih dahulu. Sehingga dapat menghasilkan pengkompresan data yang efisien pada saat proses encode dan decode.

18