BAB 2 LANDASAN TEORI

BAB 2

LANDASAN TEORI

2.1 Pengertian File Teks

Teks adalah kumpulan dari karakter – karakter atau string yang menjadi satu kesatuan. Teks yang memuat banyak karakter didalamnya selalu menimbulkan masalah pada media penyimpanan dan kecepatan waktu pada saat transmisi data. File teks merupakan file yang berisi informasi-informasi dalam bentuk teks. Data yang berasal dari dokumen pengolah kata, angka yang digunakan dalam perhitungan, nama dan alamat dalam basis data merupakan contoh masukan data teks yang terdiri dari karakter, angka dan tanda baca.

Masukan dan keluaran data teks direpresentasikan sebagai set karakter atau sistem kode yang dikenal oleh sistem komputer. Ada tiga macam set karakter yang umum digunakan untuk masukan dan keluaran pada komputer, yaitu ASCII, Unicode, dan EBCDIC, ASCII (American Standard Code for Information Interchange) merupakan suatu standar internasional dalam kode huruf dan simbol seperti Hex, dan Unicode tetapi ASCII bersifat lebih universal. ASCII digunakan oleh komputer dan alat komunikasi lain untuk

menunjukkan teks. Kode ASCII memiliki komposisi

bilangan biner sebanyak 8 bit, dimulai dari 00000000 dan 11111111. Total kombinasi yang dihasilkan sebanyak 256, dimulai dari kode 0 hingga 255 dalam sistem bilangan desimal. Unicode adalah suatu standar industri yang dirancang untuk mengizinkan teks dan symbol dari semua sistem tulisan di dunia untuk ditampilkan dan dimanipulasi secara konsisten oleh komputer. EBCDIC (Extended Binary Code Decimal Interchange Code) merupakan set karakter yang diciptakan oleh komputer merk IBM. EBCDIC terdiri dari 256 karakter yang masing-masing berukuran 8 bit ( Sudewa, Ida Bagus Adi, 2003).

Universitas Sumatera Utara

2.1.1 Tipe Teks

Tipe teks merupakan tipe dasar yang sudah sangat dikenal dalam kehidupan seharihari. Tipe teks terdiri dari tipe karakter (char) dan tipe string. Tipe karakter (char) terdiri atas satu huruf, angka, tanda baca, atau karakter khusus seperti “c”,”1”,”#” dan sebagainya. Tipe string terdiri atas nol atau lebih karakter seperti “teks” dan “algoritma” dan sebagainya (Purnomo, Herry et al, 2005, hal: 99).

2.1.2 Format Teks

Secara umum, format data teks dibagi menjadi dua bagian, yaitu (Purnomo, Herry et al, 2005, hal: 410) :

1. Teks terformat (formatted text) Merupakan teks yang terformat dan mengandung styles. Format data dokumen Microsoft Word (*.doc) merupakan contoh format teks jenis ini yang paling popular.

2. Teks sederhana (plain text) Format data teks (*.txt) merupakan contoh format teks yang paling populer.

Contoh format data teks di atas beserta perangkat lunak yang biasa digunakan diantaranya adalah (Purnomo, Herry et al, 2005, hal: 410):

1. Rich Text Format (*.rtf) Format teks ini dikembangkan oleh Microsoft yang dapat dibaca oleh berbagai macam platform, seperti Windows, Linux, Mac OS, dan sebagainya.

2. Format data teks (*.txt) Format data teks merupakan format teks yang digunakan untuk menyimpan huruf, angka, karakter, kontrol (tabulasi, pindah baris, dan sebagainya) atau simbol-simbol lain yang biasa digunakan dalam tulisan seperti titik, koma, tanda petik, dan


sebagainya. Satu huruf, angka, karakter, kontrol atau simbol pada arsip teks memakan tempat satu byte. Berbeda dengan jenis teks terformat yang satu huruf saja dapat memakan tempat beberapa byte untuk menyimpan format dari huruf tersebut seperti font, ukuran, tebal atau tidak dan sebagainya. Kelebihan dari format data teks ini adalah ukuran datanya yang kecil karena tiadanya fitur untuk memformat tampilan teks. Saat ini perangkat lunak yang paling banyak digunakan untuk memanipulasi format data ini adalah Notepad.

3. Hyper Text Markup Language (*.html atau *.htm) Merupakan format teks standard untuk tampilan dokumen web.

4. Format data dokumen (*.doc) Doc merupakan ekstensi arsip dokumen perangkat lunak Microsoft Word yang paling banyak digunakan dalam penulisan laporan, makalah dan sebagainya. Doc merupakan jenis teks terformat yang tidak hanya dapat mengatur tampilan teks seperti styles (font, ukuran huruf dan sebagainya), namun juga dapat menyisipkan gambar. Kekurangan format teks dokumen ini terletak pada ukuran datanya yang besar.

2.2 Pohon (Tree)

Secara sederhana tree dapat didefinisikan sebagai kumpulan elemen yang salah satu elemennya disebut root, dan sisa elemen yang lain (yang disebut node) terpecah menjadi sejumlah himpunan yang saling tidak berhubungan satu sama lain (disjoint), yang disebut dengan subtree. Node yang tidak mempunyai cabang disebut terminal node atau leaf, sedangkan node yang mempunyai cabang disebut branch node. Jumlah node pada sebuah tree merupakan bilangan terbatas (finite number) (Muthohar, Fiqri, 2004).

Sebuah pohon berakar adalah pohon di mana sebuah node tertentu dirancang seperti akar


v1 v2 v4

v3 v5

v6

v7

Gambar 2.1 Pohon Berakar dengan v1 Sebagai Akar Pohon secara luas digunakan dalam struktur data ilmu komputer seperti pohon biner, pohon perentang, tumpukan dan lain-lain.

2.3 Pohon Biner (Binary Tree)

Pohon biner merupakan kasus khusus pohon n-ary jika n = 2. Pohon biner adalah himpunan dengan jumlah terbatas yaitu m buah node (m ≥ 0), yang selain kosong (m = 0) hanya dapat berisi sebuah node root yang memiliki dua buah subtree yang masingmasing disebut sub binary tree kiri dan sub binary tree kanan. Jika m = 0 maka disebut empty binary tree (Muthohar, Fiqri, 2004).

Misalkan T adalah pohon biner dan vєV(T) adalah suatu titik cabang dalam T. Subpohon kiri v adalah pohon biner yang (Johnsonbaugh, Richard, 1998) :

1. Titik-titiknya adalah anak kiri v dan semua turunannya. 2. Garis-garisnya adalah garis-garis dalam E(T) yang menghubungkan titiktitik subpohon kiri v. 3. Anaknya adalah anak kiri v. v

w

x

Gambar 2.2. Pohon Biner


Gambar di atas merupakan pohon biner dengan dua subpohon, yaitu subpohon kiri v dengan w sebagai akar dan subpohon kanan v dengan x sebagai akar.

2.4 Pengertian Pemampatan Data

Pemampatan (kompresi) adalah proses pengubahan sekumpulan data menjadi bentuk kode dengan tujuan untuk menghemat kebutuhan tempat penyimpanan dan waktu untuk transmisi data (Linawaty et al,2004, hal:7). Pemampatan hanya mungkin untuk dilakukan apabila data yang direpresentasikan dalam bentuk normal mengandung informasi yang tidak dibutuhkan. Ketika data tersebut sudah ditampilkan dalam format yang seminimal mungkin, maka data tersebut sudah tidak akan bisa dimampatkan lagi. File yang demikian disebut random file.

Pemampatan merupakan salah satu dari teori informasi yang diperkenalkan oleh Shannon yang bertujuan untuk menghilangkan redundansi dari sumber. Pemampatan bermanfaat dalam membantu mengurangi konsumsi sumber daya yang mahal, seperti ruang hard disk atau perpindahan data melalui internet.

Pemampatan data memiliki beberapa aplikasi, diantaranya (Munir, Rinaldi, 2004, hal: 166):

1. Pengiriman data (data transmission) pada saluran komunikasi data Data yang telah dimampatkan membutuhkan waktu yang lebih singkat dibandingkan data yang tidak dimampatkan.

2. Penyimpanan data (data storing) di dalam media sekunder ( storage ) Data yang telah dimampatkan membutuhkan ruang pada media penyimpanan yang lebih sedikit dibandingkan dengan data yang tidak dimampatkan.


2.5 Metode Pemampatan

Metode pemampatan berdasarkan output ada 2 jenis, yaitu: 1.

Metode Lossless Pemampatan data yang menghasilkan file data hasil pemampatan yang dapat dikembalikan menjadi file data asli sebelum dimampatkan secara utuh tanpa perubahan apapun. Pemampatan data lossless bekerja dengan menemukan pola yang berulang di dalam pesan yang akan dimampatkan tersebut dan melakukan proses pengkodean pola tersebut secara efisien. Pemampatan ini juga dapat berarti proses untuk mengurangi redundancy. Pemampatan jenis ini ideal untuk pemampatan text. Algoritma yang termasuk dalam metode pemampatan lossless diantaranya adalah teknik dictionary coding dan Huffman coding (Fernando, Hary, 2004).

2.

Metode Lossy Pemampatan data yang menghasilkan file data hasil pemampatan yang tidak dapat dikembalikan menjadi file data sebelum dimampatkan secara utuh. Ketika data hasil pemampatan di-decode kembali, data hasil decoding tersebut tidak dapat dikembalikan menjadi sama dengan data asli tetapi ada bagian data yang hilang. Oleh karena itu, pemampatan jenis ini tidak baik untuk kompresi data yang kritis seperti data teks. Bentuk pemampatan ini sangat cocok untuk digunakan pada file-file gambar, suara, dan film. Contoh penggunaan pemampatan lossy adalah pada format file JPEG, MP3 dan MPEG . ( Nelson, Mark et al, 1996).

Efek pemampatan pada metode pemampatan losseless dapat diukur melalui sejumlah penyusutan suatu file asal dalam membandingkan ukuran dari jenis-jenis pemampatan, yaitu : 1.

Rasio pemampatan, merupakan perbandingan ukuran file setelah pemampatan dengan file semula yang ditunjukkan dalam persentase (ditulis dalam %):


x 100% 2.

(2.1)

Kecepatan proses pemampatan (ditulis dalam satuan Kbyte/s): Kecepatan Proses Pemampatan

(2.2)

Ada beberapa kriteria yang sering menjadi pertimbangan dalam memilih suatu metode pemampatan yang tepat diantaranya kecepatan pemampatan, sumber daya yang dibutuhkan, kualitas, ukuran file, kompleksitas algoritma dan lain-lain (Munir, Rinaldi, 2004, hal: 166). Kualitas pemampatan dengan kebutuhan memori biasanya berbanding terbalik. Kualitas pemampatan yang bagus umumnya dicapai pada proses pemampatan yang menghasilkan pengurangan memori yang tidak begitu besar dan begitu juga sebaliknya.

2.6 Algoritma Huffman

Algoritma Huffman, yang dibuat oleh seorang mahasiswa MIT bernama David Huffman pada tahun 1952, merupakan salah satu metode paling lama dan paling terkenal dalam pemampatan teks. Algoritma Huffman menggunakan prinsip pengkodean yang mirip dengan kode Morse, yaitu tiap karakter (simbol) dikodekan hanya dengan rangkaian beberapa bit, dimana karakter yang sering muncul dikodekan dengan rangkaian bit yang pendek dan karakter yang jarang muncul dikodekan.dengan rangkaian bit yang lebih panjang. Berdasarkan tipe peta kode yang digunakan untuk mengubah pesan awal (isi data yang diinputkan) menjadi sekumpulan codeword, algoritma Huffman termasuk kedalam kelas algoritma yang menggunakan metode statik (Ida, Mengyi Pu, 2006).

Metoda statik adalah metoda yang selalu menggunakan peta kode yang sama, metoda ini membutuhkan dua fase (two-pass): fase pertama untuk menghitung probabilitas kemunculan tiap simbol dan menentukan peta kodenya, dan fase kedua untuk mengubah pesan menjadi kumpulan kode yang akan di transmisikan. Sedangkan berdasarkan teknik pengkodean simbol yang digunakan, algoritma


Huffman menggunakan metode symbolwise. Metoda symbolwise adalah metode yang menghitung peluang kemunculan dari setiap simbol dalam satu waktu, dimana simbol yang lebih sering muncul diberi kode lebih pendek dibandingkan simbol yang jarang muncul. Dalam tugas akhir ini algoritma Huffman yang dibahas yaitu algoritma Huffman yang menggunakan metode statik ( Ida, Mengyi Pu, 2006).

Pada awalnya David Huffman hanya menencoding karakter dengan hanya menggunakan pohon biner biasa, namun setelah itu David Huffman menemukan bahwa penggunaan algoritma greedy dapat membentuk kode prefiks yang optimal. Penggunaan algoritma greedy pada algoritma Huffman adalah pada saat pemilihan dua pohon dengan frekuensi terkecil dalam membuat pohon Huffman. Algoritma greedy ini digunakan pada pembentukan pohon Huffman agar meminimumkan total cost yang dibutuhkan. Cost yang digunakan untuk menggabungkan dua buah pohon pada akar setara dengan jumlah frekuensi dua buah pohon yang digabungkan, oleh karena itu total cost pembentukan pohon Huffman adalah jumlah total seluruh penggabungan. penggabungan dua buah pohon dilakukan setiap langkah dan algoritma Huffman selalu memilih dua buah pohon yang mempunyai frekuensi terkecil untuk meminimumkan total cost (Wardoyo, Irwan et al, 2003, hal:1).

2.6.1 Kode Prefix (Prefix Code)

Kode Huffman pada dasarnya merupakan kode prefiks (prefix code). Kode prefiks adalah himpunan yang berisi sekumpulan kode biner, dimana pada kode prefik ini tidak ada kode biner yang menjadi awal bagi kode biner yang lain. Kode prefiks biasanya direpresentasikan sebagai pohon biner yang diberikan nilai atau label. Untuk cabang kiri pada pohon biner diberi label 0, sedangkan pada cabang kanan pada pohon biner diberi label 1. Rangkaian bit yang terbentuk pada setiap lintasan dari akar ke daun merupakan kode prefiks untuk karakter yang berpadanan (Hanif, Irfan, 2004, hal: 3).


2.6.2 Kode Huffman

Huffman memberikan sebuah algoritma untuk memangun sebuah kode Huffman dengan masukan string teks S={s1,s2,…,sn} dan frekuensi kemunculan karakter F={f1,f2,…,fn}, dihasilkan keluaran berupa kode string biner C={c1,c2,…,cn} atau disebut kode Huffman (Liliana et al, 2003, hal:4).

Algoritma Pemampatan Huffman: 1. Baca file text yang akan dimampatkan (file asal). 2. Hitung frekuensi dari setiap karakter yang ada. Jenis karakter dan frekuensinya disimpan sebagai tree dalam sebuah list. 3. Selama list masih mempunyai node lebih dari satu maka a. Urutkan list berdasarkan frekuensinya, secara ascending. b. Buat tree baru, kaki kiri diisi dengan node pertama list dan kaki kanannya diisi dengan node kedua list. Karakter yang disimpan berupa “a“ dan frekuensinya merupakan jumlahan dari frekuensi kedua kakinya. 4. Sebelum hasil pemampatan disimpan dalam file hasil, maka simpan terlebih dahulu tree huffman nya. Pertama simpan jumlah karakter keseluruhan. Kemudian telusuri tree secara preorder, kaki kiri diberi kode “0“ dan kaki kanan diberi kode “1“. Setelah sampai pada leaf maka simpan karakter pada leaf tersebut baru kemudian simpan deretan kode yang dihasilkan. Setiap kode disimpan dengan dibatasi “a“. Setelah tree selesai disimpan, untuk membatasi penyimpanan tree dengan hasil kompresi, disisipkan “A“. 5. Telusuri tree secara preorder, kaki kiri diberi kode “0“ dan kaki kanan diberi kode “1“. Setelah sampai pada leaf maka deretan kode yang didapat digunakan untuk mengkodekan karakter pada leaf tersebut. Setelah penelusuran selesai maka akan didapat daftar karakter dan kode binernya. 6. Baca setiap karakter pada file asal. Ubah menjadi kode biner. Setelah semua dikodekan, setiap 8 kode dicari desimalnya (ASCII) kemudian simpan kembali sebagai karakter baru.


Tabel karakter-karakter yang diurutkan berdasarkan frekuensi kemunculan karakter tersebut berhubungan dengan distribusi probabilitas atau distribusi peluang. Distribusi probabilitas ini berhubungan pada kemungkinan penempatan akar atau subpohon baru yang telah terbentuk. Probabilitas untuk masing-masing karakter adalah frekuensi karakter tersebut dibagi jumlah frekuensi keseluruhan.

Untuk proses penirmampatan (decompression) merupakan kebalikan dari proses pemampatan (compression), Decompression berarti menyusun kembali data dari string biner menjadi sebuah karakter kembali. Decompression dapat dilakukan dengan dua cara, yang pertama dengan menggunakan tabel dan yang kedua dengan menggunakan algoritma penirmampatan (decompression).

Algoritma penirmampatan

1. Baca sebuah bit dari string biner. 2. Mulai dari akar 3. Untuk setiap bit pada langkah 1, lakukan traversal pada cabang yang bersesuaian. 4. Ulangi langkah 1, 2 dan 3 sampai bertemu daun. Kodekan rangkaian bit yang telah dibaca dengan karakter di daun. 5. Ulangi dari langkah 1 sampai semua bit di dalam string habis.

Contoh 2.1 Diberikan string “piagam penghargaan” sebagai masukan pada pemampatan file teks. Masukan ini terdiri dari karakter-karakter abjad S={p, i, a, g, m, e, n, h, r, spasi} dengan frekuensi kemunculan karakter F={2, 1, 5, 3, 1, 1, 2, 1, 1, 1}. Apabila string tersebut menggunakan koe ASCII untuk mengkodekan setiap karakter, maka representasi 18 karakter membutuhkan 18 x 8 = 144 bit atau 18 bytes. Untuk meminimumkan jumlah bit yang dibutuhkan, panjang kode untuk setiap karakter sedapat mungkin diperpendek, terutama untuk setiap karakter yang frekuensi kemunculannya besar. Jadi, bagaimana memperoleh jumlah minimum bit apabila digunakan algoritma Huffman untuk menghasilkan kode yang merepresentasikan setiap karakter.


Dengan menggunakan algoritma Huffman untuk mengkodekan setiap karakter dapat diperoleh kode Huffman sebagai berikut : Masukan : 18 karakter yang telah diurutkan dan table frekuensi Keluaran : Kode Huffman

1. Pengurutan karakter berdasarkan frekuensi kemunculannya. Karakter pada data diurutkan di dalam tabel secara menaik (ascending order).

Tabel 2.1 Frekuensi Kemunculan Karakter yang Telah Diurutkan Karakter

Frekuensi

spasi

1

r

1

h

1

e

1

m

1

i

1

p

2

n

2

g

3

a

5

Jumlah

18

2. Pembentukan pohon Huffman Setiap karakter digambarkan sebagai daun. Gabungkan dua daun yang mempunyai frekuensi kemunculan karakter paling kecil untuk membentuk sebuah akar kemudian akar diurutkan kembali. Akar merupakan jumlah frekuensi dua daun atau subpohon penyusunnya. Iterasi ini dilakukan hingga terbentuk satu buah pohon biner. Beri label 0 dan 1 pada setiap sisi pohon biner. Sisi kiri diberi label 0 dan sisi kanan diberi label 1.


Pengurutan kembali akar yang baru terbentuk berhubungan dengan distribusi probabilitas. Pada contoh ini, ada lebih dari satu kemungkinan tempat yang tersedia pada penggabungan karakter “spasi” dan “r” dengan frekuensi 2. Untuk mencegah penggabungan akar baru terlalu cepat maka akar ditempatkan pada posisi terendah. Jadi, akar baru “spasi” dan “r” ditempatkan sesudah karakter “a”. Pembentukan pohon biner dari string “piagam penghargaan” adalah :

1.

h=1

e=1

m=1

2

a=5

g=3

n=2

p=2

i=1

r=1

spasi=1 2.

2

a=5

g=3

n=2

p=2

i=1

m=1

2

3.

n=2

p=2

2

a=5

g=3

4.

2

a=5

g=3

2

5.

2 i=1

m=1

h=1

spasi=1

2

i=1

m=1

8 n=2

p=2

spasi=1

n=2

p=2

h=1

g=3

4 2

e=1

spasi=1

g=3

a=5

8

4 2

a=5

r=1 8

i=1

g=3 8

4

2 m=1

r=1

n=2

p=2

4

2 e=1

h=1 7.

r=1

spasi=1

4

2

6.

4

2 e=1

r=1

spasi=1

e=1

2 e=1

h=1

2

h=1

2 i=1

m=1

2 i=1

m=1

r=1

spasi=1

e=1

h=1

p=2

a=5

n=2

r=1


16

2

8. m=1

i=1

8

8 4

2

p=2

2 e=1

h=1

g=3

4

spasi=1

9.

a=5

n=2

r=1

18 16

2 m=1

i=1

8

8 4

2

0

m=1

e=1

spasi=1

18

0

8

0 0

2

1

h=1

e=1

4

1 0

n=2

r=1

16

0

i=1

a=5

1

1

0

p=2

2

2 h=1

g=3

4

1

0 0

2

spasi=1

1

1

4

p=2

1

8

g=3

1

a=5

n=2

r=1

Gambar 2.3 Pembentukan Pohon Huffman

Keterangan gambar : : akar yang dibentuk dari dua daun atau subpohon penyusunnya : daun yang terdiri dari karakter dan frekuensinya


3. Kode Huffman yang diperoleh dari pohon Huffman yang telah terbentuk adalah :

Tabel 2.2 Tabel Kode Huffman untuk Masing-Masing Karakter Karakter

Frekuensi

Kode Huffman

(f)

Panjang Kode

Total Panjang

( shf )

( f x shf )

Spasi

1

10110

5

5

r

1

10111

5

5

h

1

10100

5

5

e

1

10101

5

5

m

1

00

2

2

i

1

01

2

2

p

2

1000

4

8

n

2

1001

4

8

g

3

110

3

9

a

5

111

3

15

Total

18

34

64

Dengan demikian, jumlah bilangan bit yang dibutuhkan oleh algoritma Huffman untuk merepresentasikan string “piagam penghargaan” adalah 64 bit. String tersebut dimampatkan dengan rasio sebesar : x 100% x 100% = 44,4% Dengan demikian string “piagam penghargaan” dimampatkan menjadi rangkaian bit : 1000011111101110010110100010101100111010100111101111101111111001

Untuk proses penirmampatan (decompression) atau menyusun kembali data dari kode biner menjadi sebuah string asli dapat digunakan tabel kode Huffman yang


telah terbentuk atau

menggunakan algoritma penirmampatan. Pada proses

penirmampatan, rangkaian bit biner 1000011111101110010110100010101100111010100111101111101111111001 Dimulai dengan membaca bit pertama yaitu “1”, tidak terdapat bit “1” pada tabel kode Huffman. Lalu baca bit berikutnya, sehingga menjadi “10”, tidak terdapat juga bit “10”, kemudian baca lagi bit berikutnya, sehingga menjadi “100”, tidak terdapat juga bit “100”, kemudian baca lagi bit berikutnya, sehingga menjadi “1000”. Rangkaian bit “1000” ini ditemukan pada tabel kode Huffman yaitu bit yang merepresentasikan karakter “p”. Proses ini terus dilakukan hingga tidak terdapat lagi bit biner.

2.7 Algoritma LZW (Lempel Ziv Welch)

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 ( Cormen et al, 2001).

Algoritma ini melakukan kompresi dengan menggunakan dictionary, di mana fragmen-fragmen teks digantikan dengan indeks yang diperoleh dari sebuah “kamus”. Prinsip sejenis juga digunakan dalam kode Braille, di mana kode-kode khusus digunakan untuk merepresentasikan kata-kata yang ada. Pendekatan ini bersifat adaptif dan efektif karena banyak karakter dapat dikodekan dengan mengacu pada string yang telah muncul sebelumnya dalam teks. Prinsip kompresi tercapai jika referensi dalam bentuk pointer dapat disimpan dalam jumlah bit yang lebih sedikit dibandingkan string aslinya (Dobb, 1989).

2.7.1 Kode LZW ( Lempel-Ziv-Welch )

Berikut yang akan dibahas pada subbab ini adalah algoritma pemampatan LZW . Algoritma pemampatan LZW :


1. Dictionary diinisialisasi dengan semua karakter dasar yang ada : {‘A’..’Z’,’a’..’z’,’0’..’9’}. 2. P = karakter pertama dalam stream karakter. 3. C = karakter berikutnya dalam stream karakter. 4. Apakah string (P + C) terdapat dalam dictionary ? • Jika ya, maka P = P + C (gabungkan P dan C menjadi string baru). • Jika tidak, maka : i. Output sebuah kode untuk menggantikan string P. ii. Tambahkan string (P + C) ke dalam dictionary dan berikan nomor/kode berikutnya yang belum digunakan dalam dictionary untuk string tersebut. iii. P = C. 5. Apakah masih ada karakter berikutnya dalam stream karakter ? • Jika ya, maka kembali ke langkah 2. • Jika tidak, maka output kode yang menggantikan string P, lalu terminasi proses (stop).

Isi dictionary pada awal proses diset dengan tiga karakter dasar yang ada. Kolom posisi menyatakan posisi sekarang dari stream karakter dan kolom karakter menyatakan karakter yang terdapat pada posisi tersebut. Kolom dictionary menyatakan string baru yang sudah ditambahkan ke dalam dictionary dan nomor indeks untuk string tersebut ditulis dalam kurung siku. Kolom output menyatakan kode output yang dihasilkan oleh langkah kompresi (Linawati et al, 2004, hal: 10).

Algoritma penirmampatan LZW :

1. Dictionary diinisialisasi dengan semua karakter dasar yang ada : {‘A’..’Z’,’a’..’z’,’0’..’9’}. 2. CW = kode pertama dari stream kode (menunjuk ke salah satu karakter dasar). 3. Lihat dictionary dan output string dari kode tersebut (string.CW) ke stream karakter. 4. PW = CW; CW = kode berikutnya dari stream kode. 5. Apakah string.CW terdapat dalam dictionary ? 󲐀 Jika

ada, maka :

i. output string.CW ke stream karakter ii. P = string.PW


iii. C = karakter pertama dari string.CW iv. tambahkan string (P+C) ke dalam dictionary 󲐀 Jika

tidak, maka :

i. P = string.PW ii. C = karakter pertama dari string.PW iii. output string (P+C) ke stream karakter dan tambahkan string tersebut ke dalam dictionary (sekarang berkorespondensi dengan CW); 6. Apakah terdapat kode lagi di stream kode ? 󲐀 Jika

ya, maka kembali ke langkah 4.

󲐀 Jika

tidak, maka terminasi proses (stop).

Contoh 2.2 String “ABBABABAC” akan dikompresi dengan LZW. Isi dictionary pada awal proses diset dengan tiga karakter dasar yang ada: “A”, “B”, dan “C”. Tahapan proses kompresi ditunjukkan pada Tabel di bawah ini.

Tabel 2.3 Proses Pemampatan LZW Langkah

Posisi

Karakter

1

1

A

[4] A B

[1]

2

2

B

[5] B B

[2]

3

3

B

[6] B A

[2]

4

4

A

[7] A B A

[4]

5

6

A

[8] A B A C

[7]

6

9

C

Steam karakter : a

Kode output

b

: [1] [2]

Frasa baru yang 4 ditambahkan ke = dictionary ab

5 = bb

Dictionary

---

b

ab

aba

c

[2]

[4]

[7]

[3]

6 = ba

7 = aba

Output

[3]

8 = abac


Proses penirmampatan pada LZW dilakukan dengan prinsip yang sama seperti proses kompresi. Pada awalnya, dictionary diinisialisasi dengan semua karakter dasar yang ada. Lalu pada setiap langkah, kode dibaca satu per satu dari stream kode, dikeluarkan string dari dictionary yang berkorespondensi dengan kode tersebut, dan ditambahkan string baru ke dalam dictionary. Tahapan proses dekompresi ini ditunjukkan pada Tabel di bawah ini (Linawati et al, 2004, hal: 11).

Tabel 2.4 Proses Penirmampatan LZW Langkah

Kode

Output

Dictionary

1

[1]

A

---

2

[2]

B

[4] A B

3

[2]

B

[5] B B

4

[4]

AB

[6] B A

5

[7]

ABA

6

[3]

C

[7] A B A [8] A B A C

Hasil Penirmampatan: ABBABABAC


BAB 2 LANDASAN TEORI

Recommend Documents