> bwt | dönüştür | sıkıştır <
// Burrows-Wheeler Transform - sıkıştırmayı iyileştirmek için geri döndürülebilir metin dönüşümü
>> özellikler
Tamamen geri döndürülebilir
Orijinal metni eksiksiz geri getirebilen kayıpsız bir dönüşümdür.
Karakter kümelenmesi
Benzer karakterleri bir araya getirerek sonraki kodlayıcıların daha verimli sıkıştırma yapmasını sağlar.
bzip2 çekirdeği
bzip2 ailesindeki pek çok sıkıştırma algoritmasının temelini oluşturur.
>> teknik bilgiler
BWT nasıl çalışır?
Burrows-Wheeler dönüşümü, giriş dizgesinin tüm döngüsel döndürmelerini üretir, bunları sözlük sırasına göre sıralar ve sıralanmış matrisin son sütununu orijinal dizgenin indeks değeriyle birlikte döndürür. Böylece benzer karakterler yan yana toplanır ve çıktı, RLE, Move-to-Front ve diğer entropi kodlayıcılarıyla çok iyi sıkıştırılabilir hale gelir.
BWT örneği
Input: "banana$" Rotations: 0: banana$ 1: anana$b 2: nana$ba 3: ana$ban 4: na$bana 5: a$banan 6: $banana Sorted: 0: $banana 1: a$banan 2: ana$ban 3: anana$b 4: banana$ 5: na$bana 6: nana$ba Last column: annb$aa Original index: 4 Output: annb$aa|4
Neden BWT kullanmalı?
- Metin verilerinin sıkıştırılabilirliğini artırır
- Tamamen geri döndürülebilir ve kayıpsızdır
- Benzer bağlamları kümeler halinde toplar
- bzip2 sıkıştırma algoritmasının temel bileşenidir
- Diğer kodlama adımlarından önce etkili bir ön işlem sağlar
>> sık sorulan sorular
Burrows-Wheeler Dönüşümü nedir?
Burrows-Wheeler Dönüşümü (BWT), karakter dizisini yeniden düzenleyerek aynı sembollerin uzun ardışık koşular oluşturmasını sağlayan geri döndürülebilir bir algoritmadır. 1994 yılında Michael Burrows ve David Wheeler tarafından önerilmiş olup, bzip2 gibi sıkıştırıcılarda daha iyi sıkıştırma oranları elde etmek için ön işleme adımı olarak kullanılır.
BWT neden sıkıştırmayı geliştirir?
BWT, benzer bağlamlarda görünen karakterleri gruplayarak çıktıda aynı sembollerin yan yana gelmesini sağlar. Bu tür diziler, koşu uzunluğu kodlama (RLE), Move-to-Front ve Huffman gibi entropi kodlayıcılarıyla çok verimli biçimde sıkıştırılabilir.
EOF işareti nedir?
EOF (End Of File) işareti genellikle '$' veya başka benzersiz bir karakterdir ve tüm döndürmelerin birbirinden ayırt edilebilir olmasını sağlar; ayrıca orijinal dizgenin konumunu belirlemeye yardımcı olur. Bu işaret olmadan bazı dizgelerin tekil bir gösterimi olmazdı. Ters dönüşüm sırasında EOF işareti kaldırılır.
BWT başlı başına bir sıkıştırma algoritması mıdır?
Hayır. BWT tek başına veri sıkıştırmaz, veriyi sıkıştırmaya daha uygun bir forma dönüştürür. Gerçek sıkıştırma için genellikle Move-to-Front, RLE ve Huffman kodlama ile birleştirilerek bzip2 benzeri şemalarda kullanılır.