Daftar Isi:
- Definisi - Apa yang dimaksud Burrow-Wheeler Transform (BWT)?
- Techopedia menjelaskan Burrows-Wheeler Transform (BWT)
Definisi - Apa yang dimaksud Burrow-Wheeler Transform (BWT)?
Transformasi Burrows-Wheeler (BWT) adalah algoritma yang mengambil blok data, seperti string, dan menyusunnya kembali menjadi karakter-karakter yang mirip. Setelah transformasi, blok output berisi elemen data yang persis sama sebelum dimulai, tetapi berbeda dalam urutannya. Sifat algoritme cenderung menempatkan karakter yang mirip di samping satu sama lain, membuat urutan data yang dihasilkan lebih mudah dikompresi. Oleh karena itu digunakan dalam banyak algoritma kompresi.
Techopedia menjelaskan Burrows-Wheeler Transform (BWT)
Algoritma transformasi Burrows-Wheeler adalah algoritma yang relatif baru ditemukan pada tahun 1994 oleh Michael Burrows dan David Wheeler dan didasarkan pada transformasi yang tidak dipublikasikan yang ditemukan oleh Wheeler pada tahun 1983, yang diterbitkan dalam makalah mereka "Algoritma Kompresi Data Lossless Sortir Blok-sorting."
Pada dasarnya, BWT mengambil blok data seperti string, menambahkan karakter EOF dan kemudian menyortir semua rotasi string ke dalam urutan leksikografis. Pseudocode atau langkah-langkah berikut menggambarkan algoritma:
- Buat tabel yang berisi baris yang mewakili semua kemungkinan rotasi satu-string.
- Sortir semua baris berdasarkan abjad.
- Keluarkan kolom terakhir dari tabel.
Misalnya: kata "pisang"; menambahkan karakter EOF mengubahnya menjadi "pisang $" maka kami menerapkan algoritme:
1. Buat tabel dengan baris yang mewakili semua kemungkinan rotasi:
pisang $
anana $ b
nana $ ba
dan $ larangan
na $ bana
a $ banan
$ pisang
2. Urutkan baris secara abjad / leksikografis berdasarkan pada kolom pertama:
$ pisang
a $ banan
dan $ larangan
anana $ b
pisang $
nana $ ba
na $ bana
3.Kembalikan kolom terakhir sebagai output BWT: annb $ aa
String yang dihasilkan lebih mudah untuk dikompres karena karakter yang berulang-ulang dikelompokkan di samping satu sama lain. Tetapi perlu ada data tambahan yang disimpan dengan data yang ditransformasi sehingga transformasi terbalik dapat dilakukan. Meskipun data yang ditransformasikan yang dihasilkan lebih besar dari bentuk aslinya tetapi karakteristik kompresibilitasnya meningkat banyak kali lipat, pada dasarnya menjadikannya metode “bebas” untuk meningkatkan efisiensi metode kompresi.
