Isi kandungan:
- Definisi - Apakah yang dimaksudkan dengan Burrows-Wheeler Transform (BWT)?
- Techopedia menerangkan Burrows-Wheeler Transform (BWT)
Definisi - Apakah yang dimaksudkan dengan Burrows-Wheeler Transform (BWT)?
The Burrows-Wheeler transform (BWT) adalah algoritma yang mengambil blok data, seperti rentetan, dan menyusun semula mereka ke dalam menjalankan aksara yang sama. Selepas transformasi, blok output mengandungi elemen data yang sama sebelum ia bermula, tetapi berbeza dalam pesanan. Sifat algoritma cenderung meletakkan watak-watak yang serupa di sebelah satu sama lain, menjadikan susunan data yang dihasilkan lebih mudah untuk dimampatkan. Oleh itu ia digunakan dalam banyak algoritma pemampatan.
Techopedia menerangkan Burrows-Wheeler Transform (BWT)
Algoritma transformasi Burrows-Wheeler adalah algoritma yang agak baru dicipta pada tahun 1994 oleh Michael Burrows dan David Wheeler dan berdasarkan transformasi yang tidak diterbitkan yang ditemui oleh Wheeler pada tahun 1983, yang diterbitkan dalam karya mereka "A Block-sorting Algorithm Mampatan Data Lossless."
Dalam yang paling asas, BWT mengambil blok data seperti rentetan, menambah watak EOF dan kemudian menyusun semua putaran rentetan itu ke dalam urutan leksikografik. Pseudocode atau langkah berikut menggambarkan algoritma:
- Buat jadual yang mengandungi baris yang mewakili semua kemungkinan satu putaran kenaikan rentetan.
- Isih semua baris mengikut abjad.
- Output lajur terakhir jadual.
Sebagai contoh: perkataan "pisang"; menambah aksara EOF menjadikannya "pisang $" maka kami menggunakan algoritma:
1. Buat jadual dengan baris yang mewakili semua putaran mungkin:
pisang $
anana $ b
nana $ ba
ana $ ban
na $ bana
a $ banan
$ pisang
2. Susun baris mengikut abjad / leksikografi berdasarkan lajur pertama:
$ pisang
a $ banan
ana $ ban
anana $ b
pisang $
nana $ ba
na $ bana
3.Balikkan lajur terakhir sebagai output BWT: annb $ aa
Rentetan yang terhasil lebih mudah untuk dimampatkan kerana aksara berulang dibentangkan bersebelahan antara satu sama lain. Tetapi perlu ada data tambahan yang disimpan dengan data yang berubah supaya transformasi terbalik dapat dilakukan. Walaupun data yang dihasilkan bervariasi lebih besar daripada bentuk asalnya tetapi ciri mampatannya bertambah banyak, pada dasarnya menjadikannya "bebas" kaedah meningkatkan kecekapan kaedah mampatan.
