APLIKASI HUFFMAN pada MATLAB

                    Salah satu teori yang dapat digunakan untuk mengompresi data adalah dengan kode Huffman.  Kode ini dikemukakan oleh David A. Huffman,  seorang doktor teori informasi  (information  theory) lulusan MIT (Massachusets Institute of Technology) pada tahun 1952.

David A. Huffman (1925 - 1999)

           Dalam kompresi data, kode Huffman adalah kode-kode biner yang mengodekan suatu simbol  tertentu pada suatu data. Kode-kode tersebut dibentuk dengan memperhatikan frekuensi kemunculan simbol  tertentu pada data tersebut. Kode Huffman tidak  bersifat unik, kode untuk setiap simbol berbeda pada  setiap data berbeda yang dikompres. Dalam pembentukannya, Kode Huffman  menerapkan konsep kode awalan (prefix code), yang merupakan himpunan kode biner, sedemikian sehingga tidak ada anggota  himpunan yang merupakan  awalan dari anggota yang lain, supaya pada proses dekoding, tidak ada keambiguan antara satu simbol dengan simbol yang lain.  Kode awalan yang merepresentasikan  simbol  yang lebih sering muncul menggunakan rangkaian biner yang lebih pendek daripada kode yang digunakan untuk merepresentasikan  simbol  yang lebih jarang muncul. Dengan demikian jumlah bit yang digunakan untuk menyimpan informasi pada suatu data bisa lebih pendek. Urutan algoritma untuk membentuk kode Huffman adalah sebagai berikut:

1. Mula-mula dihitung terlebih dahulu frekuensi kemunculan tiap simbol di dalam data
2. Pembentukan kode Huffman dilakukan dengan membangun pohon biner dengan panjang lintasan berbobot minimum, (yang dinamakan pohon huffman) ;
   
   • Pertama-tama dipilih dua simbol dengan peluang kemunculan paling kecil (terdapat  dengan jumlah paling sedikit di dalam data).
   • Kedua simbol tadi digabungkan membentuk simpul orang tua dari kedua simbol itu sendiri, dengan peluang kemunculan sebesar jumlah dari peluang  kemunculan kedua simbol itu.
   • Simbol baru ini diperlakukan sebagai simpul baru dan diperhitungkan dalam mencari symbol selanjutnya yang memiliki peluang kemunculan terkecil.
   • Kemudian, dipilih dua simbol lainnya yang juga memiliki peluang kemunculan paling kecil (termasuk simbol yang baru dibuat).
   • Prosedur yang sama dilakukan pada dua simbol berikutnya yang mempunyai peluang kemunculan terkecil.
   • Langkah nomor 2 diluangi terus sampai semua simbol habis dibuat pohon biner.
    
3. Daun pada pohon Huffman menyatakan simbol yang terdapat di dalam data yang dikompres.
4. Setiap simbol dikodekan dengan memberi label 0 pada setiap cabang kiri pohon biner dan label 1 untuk setiap cabang kanannya.
5. Dibuat lintasan dari akar ke daun, sambil membaca label 0 atau 1 yang terdapat pada setiap cabang.
6. Kode Huffman untuk simbol pada suatu daun adalah rangkaian biner yang dibaca dari akar hingga daun yang bersangkutan.

berikut adalah koding yang digunakan pada Matlab :

function huff()

clc;

fid=fopen('Budianto.txt','r');

seq=fread(fid,'*char');

fclose(fid);

seq=reshape(seq,1,length(seq));

[alpha prob]=probmodel(seq);

if ~isempty(alpha)

[huf entropy avglength redundancy]=huffman(alpha,prob);

if ~isempty(huf)

    lp=length(prob);

   for i=1:lp

     str=huf(i).sym;

     str=strcat(str,' :');

     str=strcat(str,num2str(huf(i).prob));

     str=strcat(str,' :');

     str=strcat(str,huf(i).code);

     disp(str);

   end

   disp(strcat('Entropy = ',num2str(entropy)));

   disp(strcat('Average length = ',num2str(avglength)));

   disp(strcat('Redundancy = ',num2str(redundancy)));

   encseq=huffencode(huf,seq);

   disp('Sequence :');

   disp(seq);

   disp('Encoded Sequence :');

   disp(encseq);

   decseq=huffdecode(huf,encseq);

   disp('Decoded Sequence :');

   disp(decseq);

end

else

    display('Empty Sequence....');

end

end

Outputnya :

    'B :0.125 :111'

    'u :0.125 :110'

    'd :0.125 :101'

    'i :0.125 :100'

    'a :0.125 :011'

    'n :0.125 :010'

    't :0.125 :001'

    'o :0.125 :000'

Entropy =3

Average length =3

Redundancy =0

Sequence :

Budianto

Encoded Sequence :

111110101100011010001000

Decoded Sequence :

Budianto

Terima Kasih

Salam

Budianto