| Sembol | Adet | Kod | Bit | Toplam bit |
|---|
Huffman kodu oluşturucu
Neden a gibi sık bir harf, j gibi nadir bir harf kadar bit kaplasın? Huffman kodlaması sık sembollere kısa, nadir sembollere uzun kodlar verir ve bunu mümkün olan en iyi şekilde yapar. Bir metin yazın ya da bir örnek seçin ve Huffman ağacını adım adım oluşturun: En hafif iki ağaç, tek bir ağaç kalana kadar tekrar tekrar yeni bir düğümün altında birleşir. Ardından tepeden inen her yol bir kodu oluşturur ve her sembolü kodlanmış bitler boyunca izleyebilirsiniz. Bir metin yazın ya da bir örnek seçin. Her sembol, adediyle birlikte bir yaprak olarak başlar. Oluşturmayı adım adım ilerletin: Her adım, en hafif iki ağacı toplamlarını taşıyan yeni bir düğümün altında birleştirir ve bu, tek bir ağaç kalana kadar sürer. Ardından tepeden bir yaprağa giden yol o yaprağın kodunu verir: Sol için 0, sağ için 1. Bir sembolü izlemek için bir yaprağa, bir satıra ya da bitlerden bir parçaya tıklayın ve toplamı sabit uzunluklu bir kodla ve entropiyle karşılaştırın.
Nasıl çalışır
- Bir metin yazın ya da yapıştırın veya ABRACADABRA ya da MISSISSIPPI RIVER gibi bir örnek seçin.
- Oluşturmayı “Sonraki adım” düğmesiyle ilerletin ya da “Oynat” düğmesine basın: Her adım, en hafif iki ağacı toplamlarını taşıyan bir düğümün altında birleştirir.
- Ağaç tamamlandığında bir sembolü izlemek için bir yaprağa, tablonun bir satırına ya da bitlerden bir parçaya tıklayın ve kutucuklardaki toplamları karşılaştırın.
Ağaç nasıl oluşturulur
Her sembolün kaç kez geçtiğini sayın ve her birini, adediyle ağırlıklandırılmış tek yapraklı bir ağaç yapın. Ardından basit bir adımı tekrarlayın: Ağırlığı en küçük iki ağacı alın ve ağırlığı ikisinin toplamı olan yeni bir düğümün altına asın. Her adım bir ağaç eksiltir; böylece n sembol için n − 1 adımdan sonra tek bir ağaç kalır. Nadir semboller ilk birleştirilenlerdir ve derinlerde yer alır; sık semboller geç birleştirilir ve tepeye yakın durur.
Kodları okumak
Tepeden aşağı inin: Sola atılan her adım bir 0, sağa atılan her adım bir 1 ekler. Bir yaprağa giden yol o sembolün kodudur. Semboller yalnızca yapraklarda bulunduğundan hiçbir kod başka bir kodun başlangıcı değildir; bu yüzden bir bit dizisi hiçbir ayırıcı olmadan çözülebilir: Bitleri izleyerek ağaçta aşağı inin, bir yaprağa ulaştığınızda sembolünü yazın ve yeniden tepeden başlayın. ABRACADABRA için Huffman 23 bite ihtiyaç duyar; harf başına 3 bitlik sabit uzunluklu bir kodla bu sayı 33'tür.
Sık sorulan sorular
Huffman kodu neden mümkün olan en iyi koddur?
Her sembole tam bitlerden oluşan kendi dizisini veren tüm kodlar arasında, verilen adetler için toplamı daha kısa olan hiçbiri yoktur. Kanıt, yapımı takip eder: Optimal bir kodda en nadir iki sembol her zaman en derin düzeyde kardeş yapılabilir ve bunları birleştirmek aynı türden daha küçük bir problem bırakır. Toplam bit sayısı, ağacın tüm iç düğümlerinin ağırlıklarının toplamına eşittir.
Önek kodu nedir?
Hiçbir kod sözcüğünün başka birinin başlangıcı olmadığı bir koddur; örneğin 0, 10, 110 ve 111. Bu özellik, bir kod çözücünün bir bit akışını ayırıcılar olmadan okumasını sağlar, çünkü bir kod sözcüğünün nerede bittiğini her zaman bilir. Her Huffman kodu bir önek kodudur: Semboller yalnızca ağacın yapraklarında bulunur.
Huffman ağacı tek midir?
Tam olarak değil: İki ağacın ağırlığı aynı olduğunda hangisinin önce alınacağı seçilebilir; sol ve sağ da yer değiştirebilir. Farklı seçimler farklı kodlar verir, ama toplam bit sayısı hep aynıdır. Oluşturucu eşitlikleri her zaman aynı şekilde bozar, bu yüzden bir metin her zaman aynı ağacı verir.
Huffman entropiye ne kadar yaklaşır?
Ortalama kod uzunluğu en az entropi kadardır ve entropinin bir bitten daha az üstündedir. Yarıya inen adetler örneğinde olduğu gibi her olasılık yarımın bir kuvveti olduğunda entropiye eşittir. Aritmetik kodlama ve modern aralık kodlayıcıları tam bit sınırından kaçınır ve daha da yaklaşır.
Metnim bir yere gönderiliyor mu?
Hayır. Ağaç ve kodlar tarayıcınızda hesaplanır ve metniniz bu tarayıcının yerel depolamasında kalır.
Denemeye hazır mısınız?
PictorX'i tarayıcınızda açın — kurulum gerekmez, başlamak için kredi kartı gerekmez.
Editöre Git