Veri sıkıştırma açıklandı

Yüklediğiniz her web sayfası, her ZIP dosyası ve her PNG görüntüsü sıkıştırılmıştır: Tek bir bit bile kaybetmeden küçültülmüş ve vardığı yerde yeniden açılmıştır. Arkasındaki yöntemler şaşırtıcı derecede basittir. Tekrar eden şeyleri ararlar ve onları yeniden söylemek yerine “öncekiyle aynı” derler. Bu fikrin ne kadar ileri gittiği ve nerede durduğu, bilgisayar biliminin en zarif hikâyelerinden biridir.

Tekrarlanan bölümlerin, ilk geçtikleri yeri gösteren geriye dönük oklarla değiştirildiği bir metin satırı ve yanında orijinal ile sıkıştırılmış boyutu gösteren çubuklar
Tekrarlanan bölümlerin, ilk geçtikleri yeri gösteren geriye dönük oklarla değiştirildiği bir metin satırı ve yanında orijinal ile sıkıştırılmış boyutu gösteren çubuklar

Kayıpsız ve kayıplı

Sıkıştırmanın iki türü vardır. Kayıpsız sıkıştırma orijinali tam olarak geri verir; bu, metin, program, elektronik tablo ve tek bir yanlış bitin önemli olduğu her şey için şarttır. Fotoğraf, müzik ve videoda kullanılan kayıplı sıkıştırma, insanların zar zor algıladığı ayrıntıları atar ve çok daha küçük boyutlara ulaşır, ama orijinal sonsuza dek kaybolur. Bu sayfa ve gösterici, fazlalığı, yani verinin tahmin edilebilecek kısımlarını bulup gidererek çalışan kayıpsız sıkıştırma hakkındadır.

Tekrar uzunluğu kodlaması

En basit yöntem, özdeş sembollerden oluşan bir seriyi bir sayaç ve sembolle değiştirir: On iki beyaz piksel 12W olur. Faks makineleri, ilk bitmap biçimleri ve PCX görüntü biçimi bunu kullandı, çünkü taranmış sayfalar ve basit çizimler uzun serilerle doludur. Sıradan metinde işe yaramaz, hatta zararlıdır: Seriler nadirdir ve her bir harf için bir sayaç yazmak boyutu iki katına çıkarır. Tekrar uzunluğu kodlaması yine de başka yöntemlerin içinde, ilk bir dönüşümden sonra kalan sıfır serileri için yaşamaya devam eder.

LZ77: Geriye işaret etmek

1977'de İsrail'deki Technion'da çalışan iki araştırmacı, Abraham Lempel ve Jacob Ziv, alanı değiştiren bir yöntem yayımladı. Kodlayıcı az önce işlediği metnin bir penceresini tutar. Sonraki karakterler pencerede zaten geçmişse bir çift yazar: Önceki kopyanın ne kadar geride başladığı ve ne kadar uzun olduğu. Aksi hâlde karakterin kendisini yazar. Kod çözücünün hiçbir sözlüğe ihtiyacı yoktur, yalnızca zaten yeniden oluşturduğu metne ihtiyaç duyar. Bir gönderme, ürettiği metinle örtüşebilir bile; böylece 100 özdeş harften oluşan bir seri, bir harf ve bir göndermeden ibarettir.

Abraham Lempel, 1977’de Technion’da Jacob Ziv ile birlikte bugün LZ77 denen pencere ve gönderim yöntemini yayımladı.
Abraham Lempel, 1977’de Technion’da Jacob Ziv ile birlikte bugün LZ77 denen pencere ve gönderim yöntemini yayımladı.

LZW: Bir sözlük öğrenmek

Lempel ve Ziv'in ikinci yöntemi LZ78, bir pencerede geriye bakmak yerine bir sözlük oluşturur. Terry Welch'in 1984'teki iyileştirmesi LZW, 256 bayt değerinin tümüyle başlar ve her adımda zaten bildiği en uzun dizinin numarasını gönderir, o diziyi bir sonraki karakterle birlikte yeni bir girdi olarak ekler. Kod çözücü aynı sözlüğü yalnızca numaralardan yeniden oluşturur. LZW hızlı ve basitti; Unix'in compress komutuna, GIF görüntü biçimine ve TIFF dosyalarına girdi, ta ki üzerindeki patentler 1990'larda uzun bir anlaşmazlığa yol açana kadar.

Deflate, ZIP ve ötesi

Phil Katz'ın 1993'te PKZIP 2 ile tanıttığı deflate yöntemi, LZ77'yi Huffman kodlamasıyla birleştirir: Tekrarları bulduktan sonra en sık literallere, uzunluklara ve mesafelere en kısa bit kodlarını verir. Deflate; ZIP, gzip, PNG görüntüleri ve web sayfalarının sıkıştırılmasında kullanılır ve göstericinin tarayıcının kendi sıkıştırıcısıyla ölçtüğü yöntem de odur. Zstandard, Brotli ve xz gibi daha yeni yöntemler daha büyük pencereler, daha akıllı eşleştirme ve daha hassas entropi kodlaması kullanır ve tipik dosyaları %10 ila %30 daha küçültür.

Neden her şey küçülemez

Hiçbir yöntem her dosyayı küçültemez. n bitlik 2ⁿ dosya vardır, ama bundan kısa yalnızca 2ⁿ − 1 dosya vardır; bu yüzden bir yöntem hepsini küçültseydi, ikisi aynı sonuca varır ve ikisi birden geri getirilemezdi: Bu, güvercin yuvası ilkesidir. Bu nedenle her sıkıştırıcı bazı girdileri büyütür; bunlar genellikle şifrelenmiş dosyalar, zaten sıkıştırılmış dosyalar ve gürültü gibi rastgele görünen verilerdir. Bu aynı zamanda bir rastgelelik testidir: Hiçbir sıkıştırıcının küçültemediği veriler rastgele görünür.

Entropi sınırı

Claude Shannon 1948'de bir kaynağın entropisinin, herhangi bir kayıpsız kod için sembol başına mümkün olan en küçük ortalama bit sayısı olduğunu gösterdi. Harf harf sayıldığında İngilizce metnin entropisi harf başına yaklaşık 4 bittir; bu, saklandığı 8 bitin yarısıdır. LZ77 gibi bağlamı kullanan yöntemler, tekrarlı metinlerde bu tek harflik değerin altına iner, çünkü bir gönderme bütün bir parçayı tek seferde temsil eder. Her harfi kendisinden önceki her şeyden tahmin eden en iyi modern sıkıştırıcılar, İngilizceyi harf başına 2 bitin altına indirir.

Claude Shannon, 1948’de Bell Labs’te bir iletinin ne kadar bilgi içerdiğini kesinleştirip bunu bit cinsinden ölçtü.
Claude Shannon, 1948’de Bell Labs’te bir iletinin ne kadar bilgi içerdiğini kesinleştirip bunu bit cinsinden ölçtü.

Keşfedin

LZ77, LZW ve tekrar uzunluğu kodlamasını bir paragraf, nakaratlı bir şarkı, bir piksel satırı, bir veri tablosu, rastgele harfler ya da DNA veya kendi metniniz üzerinde çalıştırmak için sıkıştırma göstericisini açın. Neyi kopyaladığını görmek için herhangi bir LZ77 göndermesine tıklayın, LZW sözlüğünün büyüyüşünü izleyin ve tüm yöntemleri ZIP ve entropi sınırıyla karşılaştırın.

Sık sorulan sorular

3 : 1 sıkıştırma oranı ne anlama gelir?

Orijinalin sıkıştırılmış hâlinden üç kat büyük olduğu, yani sıkıştırılmış dosyanın yerin üçte birini kaplayıp üçte ikisinden tasarruf ettiği anlamına gelir. Metin ZIP ile tipik olarak 2 : 1 ile 4 : 1 arasına ulaşır; günlük (log) dosyaları gibi çok tekrar içeren veriler ise çoğu zaman çok daha fazlasına.

Bir ZIP dosyasını yeniden sıkıştırmak neden işe yaramaz?

İlk geçiş tekrarları zaten gidermiştir ve çıktısı neredeyse rastgele görünür. İkinci geçiş geri gönderme yapacak hiçbir şey bulamaz ve yalnızca kendi ek yükünü ekler; bu yüzden dosya aynı boyutta kalır ya da biraz büyür.

Daha büyük bir LZ77 penceresi neden daha iyidir?

Daha büyük bir pencere, kodlayıcının daha geride kalan tekrarları, örneğin birkaç kıtadan sonra geri dönen bir nakaratı bulmasını sağlar. Bedeli, her mesafeyi yazmanın daha fazla bit gerektirmesi ve aramanın daha uzun sürmesidir; deflate'in 32 KB ile sınırlı kalmasının, daha yeni yöntemlerinse megabaytlara izin vermesinin nedeni budur.

Sıkıştırma, şifrelemeyle aynı şey mi?

Hayır. Sıkıştırma veriyi küçültür ve herkes onu geri alabilir; şifreleme ise veriyi anahtar olmadan okunamaz hâle getirir. İkisi sık sık birlikte kullanılır ve bu durumda veri önce sıkıştırılmalıdır: Şifrelenmiş veri rastgele görünür ve artık sıkıştırılamaz.

Denemeye hazır mısınız?

PictorX'i tarayıcınızda açın — kurulum gerekmez, başlamak için kredi kartı gerekmez.

Sıkıştırma göstericisini aç