Home > PHP > Algoritma Kompresi Lempel-Ziv-Welch (LZW) di PHP

Algoritma Kompresi Lempel-Ziv-Welch (LZW) di PHP

Terdapat berbagai macam teknik-teknik kompresi yang diantaranya akan dijelaskan berikut ini:

1. Dictionary Based Coding Algoritma

Lempel-Ziv-Welch (LZW) menggunakan teknik adaptif dan berbasiskan “kamus” Pendahulu LZW adalah LZ77 dan LZ78 yang dikembangkan oleh Jacob Ziv dan Abraham Lempel pada tahun 1977 dan 1978. Terry Welch mengembangkan teknik tersebut pada tahun 1984. LZW banyak dipergunakan pada UNIX, GIF, V.42 untuk modem.

Algoritma Kompresi :

BEGIN
S = next input character;
While not EOF
{
C = next input character;
If s + c exists in the diactionary
S = s + c
Else
{
Output the code for s;
Add string s + c to the dictionary with a new code
S = c;
}
}
END

Implementasi kompresi LZW dengan PHP


<?php

 $kata = "ABABBABCABABABABBABBBBg";//string inputan
 $len = strlen($kata);//hitung panjang inputan
 $huruf = str_split($kata);//pecah inputan menjadi perhuruf dan jadikan array
 //ambil huruf unik(jika jumlah huruf sama lebih dari satu ambil satu saja)
 //simpan di kamus->$dic[]
 $dic = array_unique($huruf);
 sort($dic);//urutkan Asceding
 //tampilkan input $kata
 echo "<b>INPUT: $kata<b>";
 echo "<p></p>";
 echo "<b>KAMUS:<b><br>";
 echo "<table border=1>
 <tr><th>code</th><th>String</th></tr>";
 //tampilkan kamus
 $m=0;
 foreach($dic as $k){
 $m++;
 echo "<tr><td>$m</td><td>$k</td></tr>";
 }
 echo "</table>";
 echo "<p></p>";
 //simpan hasil kompresi di $result
 echo "<b>HASIL: <b>";
 $result ="";
 $s = $huruf[0];
 $j = count($dic);//hitung jumlah kata yang ada di kamus
 echo "<table border=1>
 <tr><th>s</th><th>c</th><th>output</th><th>code</th><th>string</th></tr>";
 //proses kompresi
 for($i=0;$i<$len;$i++){

 $c = $huruf[$i+1];
 $new = $s.$c;
 //jika $new ada di dalam kamus
 if (in_array($new, $dic)){
 if($c==NULL){//jika huruf terakhir
 $nilai = array_keys($dic, $s);//ambil code huruf di dlam kamus
 $output = $nilai[0]+1;
 $result .= $output;
 echo "<tr><td>$s</td><td>EOF</td><td>$output</td><td>-</td><td>-</td></tr>";
 }else{
 echo "<tr><td>$s</td><td>$c</td><td>-</td><td>-</td><td>-</td></tr>";
 $s=$new;
 }
 }else{//jika $new belum ada di kamus

 $j++;
 $nilai = array_keys($dic, $s);
 $output = $nilai[0]+1;
 $result .= $output;
 $code = $j;
 $string = array($new);
 $dic = array_merge($dic, $string);//masukkan $new ke dalam kamus $dic dan berikan kode= $code
 echo "<tr><td>$s</td><td>$c</td><td>$output</td><td>$code</td><td>$new</td></tr>";

 $s=$c;
 }
 }
 echo "</table>";
 echo "<p></p>";
 //tampilkan output =$result
 echo "Ouput = ".$result."<br>";
?>

Algoritma Dekompresi :

BEGIN
S = NULL;
While not EOF
{
K = NEXT INPUT CODE;
Entry = dictionary entry for K;
Ouput entry;
If (s != NULL)
add string s + entry[0] to dictionary with new code
S = Entry;
}
END

source kompresi bisa di download disini

Sumber : http://blog.unila.ac.id/muh47ir/2008/12/26/teori-informasi/

Categories: PHP Tags: , , , ,
  1. 4 January 2011 at 16:59

    Thank for visit guys

  2. 21 February 2011 at 22:10

    THANKS

  3. 21 February 2011 at 22:10

    THANKS 4 VISIT

  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: