Her gün internette dolaşan 9 milyar gigabayttan fazla bilgiyle, araştırmacılar sürekli olarak verileri daha küçük paketlere sıkıştırmanın yeni yollarını arıyorlar. Son teknoloji teknikler, bir iletimden bilgileri kasıtlı olarak "kaybederek" sıkıştırmayı sağlayan kayıplı yaklaşımlara odaklanır. Örneğin Google, kısa bir süre önce, gönderen bilgisayarın bir görüntüden ayrıntıları çıkardığı ve alıcı bilgisayarın eksik parçaları tahmin etmek için yapay zeka kullandığı kayıplı bir stratejiyi açıkladı. Netflix bile, şirket bir kullanıcının düşük çözünürlüklü bir cihazda izlediğini tespit ettiğinde video kalitesini düşürerek kayıplı bir yaklaşım kullanıyor.

Buna karşılık, iletimlerin daha küçük hale getirildiği ancak hiçbir maddenin feda edilmediği kayıpsız stratejiler üzerine şu anda çok az araştırma yürütülmektedir. Nedeni? Kayıpsız yaklaşımlar zaten oldukça verimli. JPEG görüntü standardından her yerde bulunan yazılım yardımcı programı PKZip'e kadar her şeye güç sağlarlar. Ve hepsi, zorlu bir final sınavından çıkış yolu arayan bir yüksek lisans öğrencisi yüzünden.

Yetmiş yıl önce, Massachusetts Teknoloji Enstitüsü profesörü Robert Fano, bilgi teorisi dersinde öğrencilere bir seçenek sundu: Geleneksel bir final sınavına girin veya veri sıkıştırma için önde gelen bir algoritma geliştirin. Fano, öğrencilerine bu mevcut algoritmanın yazarı olduğunu veya yıllardır bir iyileştirme peşinde olduğunu söylemiş olabilir veya olmayabilir. Bildiğimiz şey, Fano'nun öğrencilerine aşağıdaki meydan okumayı teklif ettiğidir.

Harflerden, rakamlardan ve noktalama işaretlerinden oluşan bir mesaj düşünün. Böyle bir mesajı kodlamanın basit bir yolu, her karaktere benzersiz bir ikili sayı atamak olacaktır. Örneğin, bir bilgisayar A harfini 01000001 ve ünlem işaretini 00100001 olarak gösterebilir. Bu, ayrıştırılması kolay kodlarla sonuçlanır - her sekiz basamak veya bit, benzersiz bir karaktere karşılık gelir - ancak korkunç derecede verimsizdir, çünkü aynı sayı İkili basamak sayısı, hem yaygın hem de yaygın olmayan girişler için kullanılır. Daha iyi bir yaklaşım, sık kullanılan E harfinin yalnızca tek bir nokta ile temsil edildiği Mors kodu gibi bir şey olabilir, oysa daha az yaygın olan Q daha uzun ve daha zahmetli çizgi-çizgi-nokta-çizgi gerektirir.

Yine de Mors kodu da verimsizdir. Elbette, bazı kodlar kısa, diğerleri uzun. Ancak kod uzunlukları değiştiği için, Mors alfabesindeki mesajlar, her karakter iletimi arasında kısa sessizlik süreleri içermedikçe anlaşılamaz. Aslında, bu maliyetli duraklamalar olmadan, alıcıların Mors mesajını çizgi nokta-çizgi-nokta nokta-nokta çizgi nokta ("basmakalıp") ile çizgi nokta-çizgi-nokta nokta-nokta-çizgi nokta ("doğru") arasında ayırt etmelerinin hiçbir yolu yoktur. ).

Fano sorunun bu kısmını çözmüştü. Aynı rakam düzenini hem tam bir kod hem de başka bir kodun başlangıcı olarak kullanmadığı sürece, değişen uzunluklardaki kodları maliyetli boşluklara ihtiyaç duymadan kullanabileceğini fark etti. Örneğin, belirli bir mesajda S harfi o kadar yaygınsa, Fano ona son derece kısa olan 01 kodunu atadıysa, o mesajdaki başka hiçbir harf 01 ile başlayan herhangi bir harfle kodlanmayacaktır; 010, 011 veya 0101 gibi kodların tümü yasak olacaktır. Sonuç olarak, kodlanmış mesaj herhangi bir belirsizlik olmadan soldan sağa okunabilir. Örneğin, S harfine 01, A harfine 000, M harfine 001 ve L harfine 1 atandığında, L bir ile temsil edilse bile 0100100011 mesajı aniden "küçük" kelimesine çevrilebilir. basamak, S iki basamaklı ve diğer harfler üçerli.

Kodları fiilen belirlemek için Fano, gerekli her harfi görsel bir dalın sonuna yerleştirerek ikili ağaçlar oluşturdu. Her harfin kodu daha sonra yukarıdan aşağıya doğru yolla tanımlandı. Yol sola dallandıysa, Fano bir 0 ekledi; sağ dallar 1 aldı. Ağaç yapısı, Fano'nun bu istenmeyen çakışmalardan kaçınmasını kolaylaştırdı: Fano ağaca bir harf yerleştirdiğinde, o dal sona ererdi, yani gelecekteki hiçbir kod aynı şekilde başlayamazdı.

Fano, hangi harflerin nereye gideceğine karar vermek için mümkün olan her modeli maksimum verimlilik için kapsamlı bir şekilde test edebilirdi, ancak bu pratik olmazdı. Bunun yerine bir tahmin geliştirdi: Her mesaj için, ilgili harfleri frekansa göre organize edecek ve ardından harfleri dallara atayacak, böylece herhangi bir dal çiftinde soldaki harfler mesajda kabaca aynı sayıda kullanılmış olacaktı. sağdaki harfler. Bu şekilde, sık kullanılan karakterler daha kısa, daha az yoğun dallarda son bulur. Az sayıda yüksek frekanslı harf her zaman daha fazla sayıda düşük frekanslı harfleri dengeleyecektir.

Sonuç, oldukça etkili bir sıkıştırma oldu. Ancak bu yalnızca bir tahmindi; daha iyi bir sıkıştırma stratejisi mevcut olmalıydı. Bu yüzden Fano öğrencilerine onu bulmaları için meydan okudu.

Fano, çift dallar arasında mümkün olduğu kadar çok simetriyi koruyarak ağaçlarını yukarıdan aşağıya inşa etmişti. Öğrencisi David Huffman, aynı ağaç türlerini aşağıdan yukarıya inşa ederek süreci tersine çevirdi. Huffman'ın anlayışı, başka ne olursa olsun, verimli bir kodda en az ortak olan iki karakterin en uzun iki koda sahip olması gerektiğiydi. Böylece Huffman en az yaygın olan iki karakteri belirledi, onları dallanan bir çift olarak gruplandırdı ve ardından işlemi tekrarladı, bu sefer kalan karakterler ve az önce oluşturduğu çift arasından en az ortak olan iki girişi aradı.

Fano yaklaşımının duraksadığı bir mesajı düşünün. "Okul odasında" O dört kez ve S/C/H/L/R/M her biri birer kez görünür. Fano'nun dengeleyici yaklaşımı, O harfini ve diğer bir harfi sol dala atayarak başlar ve bu harflerin toplam beş kullanımı, kalan harflerin beş görünüşünü dengeler. Ortaya çıkan mesaj 27 bit gerektirir.

Buna karşın Huffman, alışılmadık iki harfle başlar - diyelim ki R ve M - ve çifti tek bir harf gibi ele alarak onları gruplandırır.

Güncellenmiş frekans çizelgesi ona dört seçenek sunar: dört kez görünen O, işlevsel olarak iki kez kullanılan yeni birleştirilmiş RM düğümü ve tek harfler S, C, H ve L. Huffman yine en az yaygın olan iki seçeneği seçer, eşleşen (diyelim) H ile L.

Grafik tekrar güncellenir: O hala 4 ağırlığa sahiptir, RM ve HL artık her birinin ağırlığı 2'dir ve S ve C harfleri tek başınadır. Huffman oradan devam eder, her adımda en az kullanılan iki seçeneği gruplandırır ve ardından hem ağacı hem de sıklık tablosunu günceller.

Nihayetinde, "okul odası" 11101111110000110110000101 olur ve Fano yukarıdan aşağıya yaklaşımından bir parça uzaklaşır.

Bir bit çok gibi gelmeyebilir, ancak küçük tasarruflar bile milyarlarca gigabayta ölçeklendiğinde muazzam bir şekilde büyür.

Gerçekten de, Huffman'ın yaklaşımı o kadar güçlü çıktı ki, bugün neredeyse her kayıpsız sıkıştırma stratejisi, Huffman içgörüsünü tamamen veya kısmen kullanıyor. Bir Word belgesini sıkıştırmak için PKZip'e mi ihtiyacınız var? İlk adım, yinelemeyi belirlemek ve böylece mesaj boyutunu sıkıştırmak için başka bir akıllı strateji içerir, ancak ikinci adım, ortaya çıkan sıkıştırılmış mesajı alıp Huffman sürecinden geçirmektir. Bir görüntüyü JPEG olarak sakla? Bilgisayarınız önce görüntüyü metin tabanlı bir temsile çevirir ve ardından, bu metni sıkıştırmak için yine Huffman kodlamasını kullanır.

Başlangıçta bir yüksek lisans öğrencisinin final sınavını geçme arzusuyla motive edilen bir proje için fena değil.