Huffman Coding Algoritması ile Veri Sıkıştırma
Merhabalar, bu makalede sizlerle birlikte veri sıkıştırmanın ilkelerini ve Huffman coding algoritmasının ayrıntılarını inceleyeceğiz. Veri sıkıştırma, verinin boyutunu azaltmayı amaçlayan temel bir bilgisayar bilimi kavramıdır, bu da veriyi depolamayı ve iletmeyi daha verimli hale getirir. Robert Sedgewick ve Kevin Wayne tarafından yazılan “Algorithms, Fourth Edition” kitabı, çeşitli veri sıkıştırma tekniklerine dair kapsamlı bir genel bakış sunar ve bu tekniklerin algoritmalarına ve uygulamalarına odaklanır. Bu teknikler arasında, Huffman sıkıştırma en verimli ve yaygın olarak kullanılan yöntemlerden biri olarak öne çıkar.
Veri Sıkıştırmaya Giriş
Veri sıkıştırma, bilgiyi orijinal temsilinden daha az bit kullanarak kodlamayı içerir. Bu süreç, dosya depolama, veri iletimi ve multimedya işleme gibi çeşitli uygulamalar için önemlidir. Veri sıkıştırmanın temel hedefleri, fazlalığı azaltmak, depolama gereksinimlerini en aza indirmek ve iletim süresini kısaltmaktır.
Başlıca iki tür veri sıkıştırma vardır:
- Kayıpsız Sıkıştırma: Bu tür sıkıştırma, orijinal verinin sıkıştırılmış veriden mükemmel bir şekilde yeniden oluşturulabilmesini sağlar. Metin, çalıştırılabilir dosyalar ve veri bütünlüğünün önemli olduğu diğer uygulamalar için yaygın olarak kullanılır.
- Kayıplı Sıkıştırma: Bu tür, daha yüksek sıkıştırma oranları karşılığında bazı veri kayıplarına izin verir. Genellikle görüntüler, ses ve video gibi multimedya dosyaları için kullanılır, burada mükemmel bir yeniden yapılandırma gerekli değildir.
Huffman Sıkıştırma
Huffman sıkıştırma, MIT’de doktora öğrencisi olan David A. Huffman tarafından geliştirilen popüler bir kayıpsız veri sıkıştırma algoritmasıdır. Özellikle, farklı karakterlerin farklı frekanslarda bulunduğu verileri sıkıştırmada etkilidir. Huffman sıkıştırmanın arkasındaki temel fikir, daha sık karakterler için daha kısa kodlar ve daha az sık karakterler için daha uzun kodlar kullanarak kodlanan verinin toplam uzunluğunu en aza indirmektir.
Huffman Sıkıştırma Nasıl Çalışır?
Huffman sıkıştırma algoritması birkaç adımdan oluşur:
- Frekans Analizi: Girdi verisindeki her karakterin frekansını hesaplayın.
- Huffman Ağacının Oluşturulması: Karakter frekanslarına dayalı olarak bir ikili ağaç, yani Huffman ağacı oluşturun.
- Huffman Kodlarının Üretilmesi: Huffman ağacındaki konumlarına dayalı olarak her karaktere ikili kodlar atayın.
- Verinin Kodlanması: Orijinal verideki her karakteri karşılık gelen Huffman kodu ile değiştirin.
- Verinin Kodunun Çözülmesi: Sıkıştırılmış veriyi, Huffman ağacını kullanarak orijinal formuna geri dönüştürün.
ABRACADABRA! metni 12 karakter ve karakter başına 8 bit olacak şekilde hafızada 96 bit yer işgal ediyor. Bunu huffman coding ile 28 bit‘e düşürebiliyoruz ve bu şekilde hafızada daha az yer kaplamış oluyor.
Python ile kodlama çalışmaları
Frekans Analizi
Huffman sıkıştırmanın ilk adımı, girdi verisindeki her karakterin frekansını analiz etmektir. Bu, her karakteri ve karşılık gelen frekansını listeleyen bir frekans tablosu oluşturarak yapılabilir.
data = "this is an example for huffman encoding"
frequency = {}
for char in data:
if char in frequency:
frequency[char] += 1
else:
frequency[char] = 1
print(frequency)Huffman Ağacının Oluşturulması
Frekans tablosu oluşturulduktan sonra, bir sonraki adım Huffman ağacını inşa etmektir. Bu, her yaprak düğümünün bir karakter ve frekansını temsil ettiği bir ikili ağaçtır. Ağaç, en düşük frekanslara sahip iki düğümün tekrar tekrar birleştirilmesiyle oluşturulur, bu işlem sadece bir düğüm kalana kadar devam eder.
import heapq
heap = [[weight, [char, ""]] for char, weight in frequency.items()]
heapq.heapify(heap)
while len(heap) > 1:
lo = heapq.heappop(heap)
hi = heapq.heappop(heap)
for pair in lo[1:]:
pair[1] = '0' + pair[1]
for pair in hi[1:]:
pair[1] = '1' + pair[1]
heapq.heappush(heap, [lo[0] + hi[0]] + lo[1:] + hi[1:])
huffman_tree = heapq.heappop(heap)[1:]
print(huffman_tree)Huffman Kodlarının Üretilmesi
Huffman ağacını kullanarak, her karakter için Huffman kodlarını üretebiliriz. Bu kodlar, ağaçtaki her karaktere ulaşmak için izlenen yollardan türetilir; sol dallar 0 ve sağ dallar 1 ile temsil edilir.
huffman_codes = {}
for pair in huffman_tree:
huffman_codes[pair[0]] = pair[1]
print(huffman_codes)Verinin Kodlanması
Huffman kodları üretildikten sonra, girdi verisini her karakteri karşılık gelen Huffman kodu ile değiştirerek kodlayabiliriz.
encoded_data = "".join(huffman_codes[char] for char in data)
print(encoded_data)Verinin Kodunun Çözülmesi
Sıkıştırılmış veriyi çözmek için, Huffman ağacını kullanarak kodlanan verideki ikili rakamlar doğrultusunda ilerleyerek onları orijinal karakterlere dönüştürürüz.
decoded_data = []
current_code = ""
for bit in encoded_data:
current_code += bit
for char in huffman_codes:
if huffman_codes[char] == current_code:
decoded_data.append(char)
current_code = ""
break
decoded_data = "".join(decoded_data)
print(decoded_data)Huffman Sıkıştırmanın Avantajları
- Optimumluk: Huffman kodlama, belirli bir karakter frekans seti için ortalama kod uzunluğunu en kısa hale getirir.
- Basitlik: Algoritma, uygulanması ve anlaşılması açısından basittir.
- Verimlilik: Huffman kodlama, özellikle karakter frekanslarında büyük farklılıklar olduğunda veri boyutunu önemli ölçüde azaltabilir.
Huffman Sıkıştırmanın Dezavantajları
- Değişken Uzunluklu Kodlar: Huffman kodları değişken uzunluktadır, bu da depolama ve iletimi karmaşık hale getirebilir.
- Statik Doğa: Geleneksel Huffman kodlaması, tüm veri setinin önceden analiz edilmesini gerektirir, bu da akış verileri veya çok büyük veri setleri için pratik olmayabilir.
- Fazlalık: Karakter frekansları nispeten uniform ise, Huffman kodlaması iyi performans göstermeyebilir.
Sonuç
Huffman sıkıştırma, kayıpsız veri sıkıştırma için güçlü ve etkili bir tekniktir ve dosya sıkıştırma, multimedya kodlama ve veri iletimi gibi çeşitli uygulamalarda yaygın olarak kullanılır. “Algorithms, Fourth Edition” kitabında anlatılan Huffman sıkıştırmanın prensiplerini ve uygulanmasını anlamak, daha gelişmiş veri sıkıştırma yöntemlerini keşfetmek için önemli bir temel sağlar.
“Her gün 2,5 kentilyon bayt veri yaratıyoruz; o kadar ki, bugün dünyadaki verilerin %90'ı yalnızca son iki yılda oluşturuldu.”
