İçindekiler:
- Tanımı - Burrows-Wheeler Dönüşümü (BWT) ne anlama geliyor?
- Techopedia, Burrows-Wheeler Dönüşümü'nü (BWT) açıklıyor
Tanımı - Burrows-Wheeler Dönüşümü (BWT) ne anlama geliyor?
Burrows-Wheeler dönüşümü (BWT), dizeler gibi veri bloklarını alan ve bunları benzer karakterlerin çalışmalarına yeniden düzenleyen bir algoritmadır. Dönüşümden sonra, çıkış bloğu başlamadan önce aynı veri elemanlarını içerir, ancak sıralamada farklılık gösterir. Algoritmanın doğası, benzer karakterleri yan yana koyma eğilimindedir ve elde edilen veri sırasının sıkıştırılmasını kolaylaştırır. Bu nedenle birçok sıkıştırma algoritmasında kullanılır.
Techopedia, Burrows-Wheeler Dönüşümü'nü (BWT) açıklıyor
Burrows-Wheeler dönüşüm algoritması, 1994 yılında Michael Burrows ve David Wheeler tarafından icat edilen ve 1983'te Wheeler tarafından keşfedilen ve “Blok Sıralama Kayıpsız Veri Sıkıştırma Algoritması” başlıklı makalesinde yayınlanan nispeten yeni bir algoritmadır.
En temelde, BWT dize gibi bir veri bloğu alır, bir EOF karakteri ekler ve sonra o dizenin tüm rotasyonlarını sözlükbilimsel sıraya göre sıralar. Aşağıdaki sahte kod veya adımlar algoritmayı gösterir:
- Dizenin tüm olası bir artışlı dönüşlerini temsil eden satırları içeren bir tablo oluşturun.
- Tüm satırları alfabetik olarak sıralayın.
- Tablonun son sütununu çıktılar.
Örneğin: “muz” kelimesi; bir EOF karakteri eklemek “banana $” a dönüştürür ve algoritmayı uygularız:
1. Olası tüm rotasyonları temsil eden satırları içeren bir tablo oluşturun:
muz $
anana $ b
nana $ ba
ana $ yasağı
na $ bana
Bir $ banan
$ muz
2. İlk sütuna göre satırları alfabetik / sözlükbilimsel olarak sıralayın:
$ muz
Bir $ banan
ana $ yasağı
anana $ b
muz $
nana $ ba
na $ bana
Son sütunu BWT çıktısı olarak döndürün: annb $ aa
Sonuç dizesinin sıkıştırılması daha kolaydır çünkü tekrarlanan karakterler yan yana toplanmıştır. Ancak, ters dönüştürmenin yapılabilmesi için dönüştürülmüş verilerle birlikte ek verilerin depolanması gerekir. Sonuçta elde edilen dönüştürülmüş veriler orijinal formundan daha büyük olmasına rağmen, sıkıştırılabilirlik karakteristiği çok katlanır, bu da onu sıkıştırma yöntemlerinin verimliliğini arttırmak için “serbest” bir yöntem haline getirir.
