Huffman Coding

Kode Huffman

Kode Huffman pada dasarnya merupakan kode Initialize model prefiks (prefix code) yang merupakan himpunan yang berisi sekumpulan kode biner. Kode prefiks direpresentasikan sebagai pohon biner berlabel dimana setiap sisi diberi label 0 (cabang kiri) atau 1 (cabang kanan).
Rangkaian bit yang terbentuk pada setiap lintasan dari akar ke daun merupakan kode prefiks untuk karakter yang berpadanan.
Kode ini pun memiliki berbagai macam variasi antara lain :

1. Adaptive kode Huffman
2. Length-Limited kode Huffman
3. N-Ary Huffman Template Algoritma
4. Huffman With Unequal Letter Costs

1. Macam-macam Variasi Kode Huffman

A. Adaptive kode Huffman
Metode Adaptive digunakan pada 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 adalah bagaimana meng-update model algoritma yang terdiri dari menambah jumlah dan mengupdate pohon Huffman. Caranya adalah dengan meng-update bagian pohon di mana terjadi proses pemampatan/nirmampat.

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

Langkah-langkah peng-update-an model
1. Jika kode yang pertama kali ditemukan adalah NYT, maka tambahkan dua simpul pada simpul NYT. Satu simpul sebagai simpul NYT dan simpul yang lain sebagai daun. Tambahkan jumlah daun. Jika bukan NYT, langsung menuju daun.

2. Jika pada blok tidak terdapat angka tertinggi, tukarkan dengan angka tertinggi pada blok.

3. Tambahkan jumlah dari simpul tersebut.

4. Periksa apakah simpul tersebut merupakan simpul akar. Jika bukan pergi ke simpul parent.

B. Length-Limited Huffman Coding

Variasi Huffman ini digunakan untuk mendapatkan jarak kedalaman terkecil dari suatu simbol, dengan batasan bahwa panjang masing-masing yang dimasukkan tidak kurang dari nilai konstanta yang diberikan. Metode ini biasanya digunakan pada GNU gzip.
Langkah-langkah dalam Metode Length-Limited Huffman adalah :

1. Memilih dua atau lebih simbol yang ingin dimampatkan

2. Gabungkan simbol-simbol tersebut dan gantikan dengan pseudo-symbol beserta frekuensinya.

3. Lakukan langkah di atas secara Literatif sampai semua simpul yang ada menjadi satu simpul akar.

4. Jika simpul-simpul tersebut memiliki frekuensi yang sama, maka pilihlah simpul dengan kedalaman terpendek.

Read more »

TUGAS STRUKTUR DATA 07/05/2012

TUGAS STRUKTUR DATA
Versi Bahasa Pemrograman Borland Delphi 7
  Berikut ini adalah Scriptnya:

unit fortodo;

interface

uses

  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

  Dialogs, StdCtrls;

type

  TForm1 = class(TForm)

    fortodo: TButton;

    fordowntodo: TButton;

    whiledo: TButton;

    repeatuntil: TButton;

    Button5: TButton;

    Label1: TLabel;

    Label2: TLabel;

    Label3: TLabel;

    Label4: TLabel;

    Label5: TLabel;

    Label6: TLabel;

    Edit1: TEdit;

    Edit2: TEdit;

    Label7: TLabel;

    Edit3: TEdit;

    bt_keluar: TButton;

    Label8: TLabel;

    Label9: TLabel;

    Label10: TLabel;

    procedure fortodoClick(Sender: TObject);

    procedure fordowntodoClick(Sender: TObject);

    procedure whiledoClick(Sender: TObject);

    procedure repeatuntilClick(Sender: TObject);

    procedure bt_keluarClick(Sender: TObject);

    procedure Button5Click(Sender: TObject);

  private

    { Private declarations }

  public

    { Public declarations }

  end;

var

  Form1: TForm1;

implementation

{$R *.dfm}

procedure TForm1.fortodoClick(Sender: TObject);

var

  i,j:integer; b:string;

begin

  b:=''; j:=2;

  for i:=1 to 10 do

  begin

    b:=b+inttostr(j)+'';

    j:=j+2;

  end;

  label1.Caption:=b;

end;

procedure TForm1.fordowntodoClick(Sender: TObject);

var

  i,j:integer; b:string;

begin

  b:=''; j:=2;

  for i:=10 downto 1 do

  begin

    b:=b+inttostr(i)+'';

    j:=j+2;

  end;

  label2.Caption:=b;

end;

procedure TForm1.whiledoClick(Sender: TObject);

var

  i,j:integer; b:string;

begin

  i:=1;

  b:='';

  while i<10 do

  begin

    b:=b+inttostr(i)+'';

    i:=i+2;

  end;

  label3.Caption:=b;

end;

procedure TForm1.repeatuntilClick(Sender: TObject);

var

  i,j:integer; b:string;

begin

  i:=1;

  b:='';

  repeat

    b:=b+inttostr(i)+'';

    i:=i+1;

  until i>10;

  label4.Caption:=b;

end;

procedure TForm1.bt_keluarClick(Sender: TObject);

begin

close;

end;

procedure TForm1.Button5Click(Sender: TObject);

var

  bil,hasil,pangkat,a:integer;

begin

  bil:=strtoint(edit1.Text);

  hasil:=bil;

  pangkat:=strtoint(edit2.Text);

  if edit2.Text='0' then edit3.Text:='1' else

  if edit2.Text='1' then edit3.Text:=edit1.Text else

  begin

    for a:=2 to pangkat do

    hasil:=hasil*bil;

  edit3.Text:=inttostr(hasil);

  end;

end;

end.

Setelah Scriptnya telah jadi kita langsung Runing, lalu masukkan inputnya

Berikut ini adalah Tampilan gambar dari script diatas: 

Read more »

Banyaknya kombinasi dapat dihitung dari rumus :

C pangkat n dan r = n! per ( n-r)! dikalikan r!

Keterangan :

N = banyaknya data yang belum dikombinasikan

R = banyaknya kombinasi

C = jumlah kombinasi yang terjadi

Misal : n= 4

R= 4

= 4! per (4-4)! dikali 4!=4!per 4!=1.2.3.4 per 1.2.3.4= 24 per 24= 1

nah untuk menghitung dalam Turbo Pascal juga ada langkah – langkahnya, simak berikut :

program Kombinasi;

uses

WinCrt;

Procedure Fak(Var F,Hasil:integer);

Var

I:integer;

begin

Hasil:=1;

For I:=2 to F do Hasil:=Hasil*I;

end;

Var

R,N,NR,F1,F2,F3:integer;

C:real;

Begin

Write('Masukkan nilai yang akan dikombinasikan = ');Readln(N);

Write('Jumlah Kombinasi = ');Readln(R);

NR:=N-R;

Fak(N,F1);

Fak(NR,F2);

Fak(R,F3);

C:=F1/(F2*F3);

Writeln;

writeln ('------------------------------');

Writeln('Kombinasi : ',c:7:0);

end.

inilah Tanpilan outputnya....

Read more »

Tugas ke 2

TUGAS 2

Hai.... bertemu lagi di Tugas ke 2 (o_0)

Pusing tapi tetap semangat Guys...

Ok guys biasanya saat kita berbelanja di mart kita akan membayar barang yang sudah kita beli, tentu jika dalam membayar kita akan mendapat uang kembalian atau permen (hahahaha) nah di situ mesin kasir akan menghitung jumlah nilai pembayaran yang kita beli, namun disini dalam Turbo Pascal kita bahas bukan jumlah uang yang harus kita bayar tapi lembar-lembar atau koin kembalian yang kita terima. Namun sebelum kita ke scrip disini saya akan menggunakan uang nilai bayarnya yang dibawah 50.000 guys...! Berikut scrip nya......

program kembalian_uang_belanja;

uses wincrt;

var

a,b:longint;

j,c,d,e,f,g,h,i,k:longint;

begin

writeln('Kasir Bintang Kasih 1');

writeln ('=-=-=-=-=-=-=-=-=-=-=-=-');

writeln('Masukkan Nilai Uang=');readln(a);

writeln('=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-');

writeln('Masukkan Nilai Harga Barang=');readln(b);

writeln('=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=--=');

j:=a-b;

writeln('kembalian=',j);

writeln('Rincian uang kembalian anda');

c:=j div 50000;

d:=(j mod 50000)div 10000;

e:=(j mod 10000)div 5000;

f:=(j mod 5000)div 2000;

g:=(j mod 2000)div 1000;

h:=(j mod 1000)div 500;

i:=(j mod 500)div 200;

k:=(j mod 200)div 100;

writeln('',c,'.LEMBAR=50000');

writeln('',d,'.LEMBAR=10000');

writeln('',e,'.LEMBAR=5000');

writeln('',f,'.LEMBAR=2000');

writeln('',g,'.LEMBAR=1000');

writeln('',h,'.LEMBAR=500');

writeln('',i,'.LEMBAR=200');

writeln('',k,'.LEMBAR=100');

writeln;

writeln('Terima Kasih Sudah Berbelanja Ditoko Kami');

end.

Beginilah tampilan output nya...

Read more »