Huffman kodları: örnekler, uygulama

Şu anda, birkaç kişi düşünüyordosya sıkıştırma nasıl çalışır? Geçmişe kıyasla, kişisel bir bilgisayar kullanmak çok daha kolay hale geldi. Dosya sistemi ile çalışan hemen hemen her kişi arşiv kullanır. Ancak çok az insan nasıl çalıştıklarını ve dosya sıkıştırma ilkesinin ne olduğunu düşünür. Bu sürecin ilk sürümü Huffman kodlarıydı ve çeşitli popüler arşivlerde bu güne alışkınlar. Birçok kullanıcı, dosyanın ne kadar kolay sıkıştırıldığını ve hangi programa göre çalıştığını bile düşünmez. Bu makalede, sıkıştırma işleminin nasıl gerçekleştiğine, hangi nüansların kodlama sürecini hızlandırıp basitleştirdiğine ve ayrıca bir kodlama ağacı oluşturma ilkesinin ne olduğunu göreceğiz.

Algoritma tarihi

Etkili olan ilk algoritmaElektronik bilgiyi kodlamak, Huffman tarafından yirminci yüzyılın ortalarında, yani 1952'de önerilen kod haline geldi. Halen, bilgiyi sıkıştırmak için tasarlanmış çoğu programın ana temel unsuru. Şu anda, bu kodu kullanan en popüler kaynakların bazıları ZIP, ARJ, RAR ve diğer birçok arşivdir.

Ayrıca, bu Huffman algoritmasıJPEG görüntülerinin ve diğer grafik nesnelerinin sıkıştırılması. Tüm modern fakslar, 1952'de icat edilen kodlamayı da kullanır. Kodun oluşturulduğu zamandan bu yana çok zaman geçmesine rağmen, hala en yeni mermilerde ve eski ve modern tipteki ekipmanlarda kullanılmaktadır.

Verimli kodlama ilkesi

Huffman algoritması şemaya dayanmaktadır,en olası, en yaygın karakterleri ikili sistem kodlarıyla değiştirmenize olanak tanır. Ve daha az yaygın olanlar daha uzun kodlarla değiştirilir. Uzun Huffman kodlarına geçiş, ancak sistem tüm minimum değerleri kullandıktan sonra gerçekleşir. Bu teknik, bir bütün olarak orijinal mesajın her karakteri için kodun uzunluğunu en aza indirmenize izin verir.

Önemli olan nokta, başlangıçtaHarflerin oluşma olasılığının kodlama önceden bilinmesi gerekir. Onlardan nihai mesaj oluşturulacak. Bu verilere dayanarak, arşivdeki harfleri kodlama işleminin gerçekleştirileceği bir Huffman kod ağacı oluşturulur.

Huffman kod örneği

Algoritmayı göstermek için,bir kod ağacı oluşturmanın grafik versiyonu. Bu yöntemin kullanımının etkili olabilmesi için bu yöntem kavramı için gerekli olan bazı değerlerin tanımının açıklığa kavuşturulmasında fayda vardır. Düğümden düğüme yönlendirilen bir dizi yay ve düğüm kümesine grafik denir. Ağacın kendisi, belirli özelliklere sahip bir grafiktir:

• her düğüm birden fazla yay içerebilir;
• düğümlerden biri ağacın kökü olmalı, yani yaylar ona hiç girmemelidir;
• Kökten yaylar boyunca hareket etmeye başlarsanız, bu işlem kesinlikle herhangi bir düğüme ulaşmanıza izin vermelidir.

Kodlarda da böyle bir kavram var.Huffman ağaçtaki yaprak gibidir. Hiçbir yayın dışarı çıkmaması gereken bir düğümü temsil eder. İki düğüm bir yay ile bağlıysa, yayın hangi düğümden çıktığına ve hangi düğüme girdiğine bağlı olarak bunlardan biri ebeveyn, diğeri çocuktur. İki düğüm aynı ana düğüme sahipse, bunlar genellikle kardeş düğümler olarak adlandırılır. Yapraklara ek olarak, düğümlerin birkaç yayı varsa, bu ağaca ikili denir. Huffman ağacı tam olarak budur. Bu yapının düğümlerinin bir özelliği, her ebeveynin ağırlığının, tüm düğüm çocuklarının ağırlıklarının toplamına eşit olmasıdır.

Huffman ağaç oluşturma algoritması

Huffman kodu oluşturmak harflerden yapılırgiriş alfabesi. Gelecekteki kod ağacında serbest olan düğümlerin bir listesi oluşturulur. Bu listedeki her bir düğümün ağırlığı, o düğüme karşılık gelen mesaj harfinin ortaya çıkma olasılığı ile aynı olmalıdır. Bu durumda, gelecek ağacın birkaç serbest düğümü arasından en az ağırlığa sahip olanı seçilir. Ayrıca, birkaç düğümde minimum göstergeler gözlenirse, çiftlerden herhangi birini özgürce seçebilirsiniz.

Daha sonra ebeveyn oluşturulur.bu düğüm çiftinin ağırlığı kadar ağır olması gereken düğüm. Bundan sonra, ebeveyn ücretsiz düğümleri olan listeye gönderilir ve çocuklar kaldırılır. Bu durumda, yaylar ilgili göstergeleri, birleri ve sıfırları alır. Bu işlem sadece bir düğüm kalacak şekilde tam olarak gerektiği kadar tekrarlanır. Daha sonra ikili sayılar yukarıdan aşağıya yazılır.

Sıkıştırma verimliliğini artırma

Sıkıştırma verimliliğini artırmak için şunları yapmanız gerekir:kod ağacını oluştururken, ağaca eklenmiş belirli bir dosyada harflerin görünme olasılığına ilişkin tüm verileri kullanın ve çok sayıda metin belgesine dağılmalarına izin vermeyin. İlk önce bu dosyayı gözden geçirirseniz, sıkıştırılacak nesneden gelen harflerin ne sıklıkta bulunduğuna ilişkin istatistikleri hemen hesaplayabilirsiniz.

Sıkıştırma işlemini hızlandırın

Algoritmayı hızlandırmak için harfleri tanımlamabelirli bir mektubun ortaya çıkma olasılığının göstergelerine göre değil, oluşma sıklığına göre yapılması gerekir. Bu, algoritmayı daha basit ve çalışmak için çok daha hızlı hale getirir. Ayrıca kayan nokta ve bölme işlemlerini de önler.

Ayrıca, bu modda çalışırken dinamikHuffman kodu veya daha doğrusu algoritmanın kendisi herhangi bir değişikliğe tabi değildir. Bunun temel nedeni, olasılıkların frekanslarla doğru orantılı olmasıdır. Dosyanın veya sözde kök düğümün nihai ağırlığının, işlenecek nesnedeki harf sayısının toplamına eşit olacağı gerçeğine özellikle dikkat etmeye değer.

Sonuç

Huffman kodları - basit ve köklühala birçok tanınmış program ve şirket tarafından kullanılan bir algoritma. Sadeliği ve netliği, her boyuttaki dosyaların sıkıştırılmasında etkili sonuçlar elde etmenize ve depolama disk alanını önemli ölçüde azaltmanıza olanak tanır. Başka bir deyişle, Huffman algoritması, alaka düzeyi bugüne kadar azalmayan, uzun süredir çalışılmış ve iyi geliştirilmiş bir şemadır.

Dosya boyutunu küçültme özelliği sayesinde,ağ üzerinden veya başka yollarla iletimleri daha kolay, daha hızlı ve daha uygun hale gelir. Algoritma ile çalışarak, yapısına ve kalitesine zarar vermeden, ancak dosya ağırlığını azaltmanın maksimum etkisi ile kesinlikle herhangi bir bilgiyi sıkıştırabilirsiniz. Başka bir deyişle, Huffman kodlaması dosya boyutunu sıkıştırmak için en popüler ve güncel yöntem olmuştur ve olmaya devam etmektedir.