Huffman kodlama ağacı, bilgisayar biliminde kayıpsız veri sıkıştırma ve entropi kodlaması için kullanılan temel bir veri yapısıdır. ZIP, MP3, PNG gibi popüler formatlarda sıkıştırma amacıyla genellikle başka algoritmalarla birlikte kullanılır. Bu makalede, Huffman ağaçlarının temel prensiplerini, entropi kavramını ve Python ile bir sıkıştırma aracının nasıl oluşturulacağını adım adım inceleyeceğiz.
Entropi, verinin rastgelelik derecesini ifade eder. Örneğin, 'roooar' kelimesi 6 karakterden oluşur ve sadece 3 farklı karakter içerir. Tekrarlayan karakterler düşük entropi anlamına gelir, yani belirsizlik azdır. Buna karşılık, '123456' kelimesinde 6 farklı karakter vardır, bu da yüksek entropi ve daha fazla belirsizlik demektir. Entropi kodlaması, düşük entropili veriyi daha verimli sıkıştırmayı hedefler.
Huffman kodlaması, her karaktere değişken uzunlukta bit dizileri atayarak çalışır. Örneğin, 'roooar' için r=100, o=0, a=101 atandığında, kelime 12 bit ile temsil edilebilir (100000101100). Bu sayede 6 baytlık veri 2 bayta sıkıştırılmış olur. Ancak, bit dizilerinin bayt sınırlarına hizalanması için padding eklenmesi gerekebilir.
Sistem Güvenliği
Bir Huffman sıkıştırma aracı oluşturmanın ilk adımı, frekans haritasını çıkarmaktır. Kaynak dosyadaki her baytın kaç kez geçtiğini sayarak, daha sık tekrarlanan karakterleri belirleriz. Python'da bu, dosyadaki baytlar üzerinde döngü yaparak ve bir sözlük kullanarak kolayca gerçekleştirilebilir. Frekans haritası, Huffman ağacının yapımında temel teşkil eder.
Teknik Analiz
Huffman ağacı, yaprak düğümler (leaf nodes) ve iç düğümlerden (internal nodes) oluşur. Her karakter için bir yaprak düğüm oluşturulur ve ağırlık olarak frekans değeri atanır. Ardından, en düşük ağırlığa sahip iki düğüm seçilir ve bunların ağırlıkları toplanarak yeni bir iç düğüm oluşturulur. Bu işlem, tek bir kök düğüm kalana kadar tekrarlanır. Verimli bir şekilde minimum elemanı bulmak için min-heap (öncelik kuyruğu) kullanılabilir.
Python uygulamasında, BaseTreeNode soyut sınıfı, LeafNode ve InternalNode sınıfları türetilerek ağaç yapısı modellenir. LeafNode, bir bayt değeri ve ağırlığını içerir; InternalNode ise sol ve sağ alt düğümleri birleştirir. from_frequency_map statik metodu, frekans haritasını alır ve düğümleri heap'e ekleyerek ağacı oluşturur. Bu yaklaşım, Huffman ağacının inşasını hem anlaşılır hem de etkili kılar.
Huffman ağaçları, sıkıştırma oranını artırmak için diğer algoritmalarla birleştirilebilir. Örneğin, ZIP'te LZ77 ve Huffman kodlaması birlikte kullanılır. Kendi sıkıştırma aracınızı geliştirirken, frekans haritası çıkarma, ağaç inşası ve kod atama adımlarını doğru uygulamak önemlidir. Bu sayede, özellikle tekrarlayan desenler içeren metin dosyalarında yüksek sıkıştırma oranları elde edilebilir.
Kaynak: dev.to
