Huffman'ın algoritması, verileri sıkıştırmak veya kodlamak için kullanılır. Normalde, bir metin dosyasındaki her karakter, ASCII adı verilen bir kodlama kullanılarak o karakterle eşleşen sekiz bit (rakam, 0 veya 1) olarak saklanır. Bir Huffman kodlu dosya, katı 8 bitlik yapıyı bozar, böylece en yaygın kullanılan karakterler yalnızca birkaç bitte saklanır ('a', "01100001" olan ASCII yerine "10" veya "1000" olabilir)). O halde en az yaygın karakterler genellikle 8 bitten çok daha fazlasını kaplar ('z', "00100011010" olabilir), ancak çok nadiren meydana geldikleri için, Huffman kodlaması, genel olarak, orijinalden çok daha küçük bir dosya oluşturur.
adımlar
Bölüm 1 / 2: Kodlama
Adım 1. Kodlanacak dosyadaki her karakterin sıklığını sayın
Dosyanın sonunu işaretlemek için boş bir karakter ekleyin - bu daha sonra önemli olacaktır. Şimdilik, EOF (dosya sonu) olarak adlandırın ve frekansı 1 olarak işaretleyin.
Örneğin, "ab ab cab" yazan bir metin dosyasını kodlamak istiyorsanız, 'a' 3 frekanslı, 'b' 3 frekanslı, ' ' (boşluk) 2 frekanslı, 'c' 1 frekanslı olacaktır., ve frekans 1 ile EOF
Adım 2. Karakterleri ağaç düğümleri olarak saklayın ve bir öncelik sırasına koyun
Her karakterin yaprak olduğu büyük bir ikili ağaç oluşturacaksınız, bu nedenle karakterleri ağacın düğümleri haline gelebilecekleri bir biçimde saklamanız gerekir. Bu düğümleri, her karakterin frekansı düğümünün önceliği olacak şekilde bir öncelik sırasına yerleştirin.
- İkili ağaç, her veri parçasının bir ebeveyne ve iki çocuğa sahip olabilen bir düğüm olduğu bir veri formatıdır. Genellikle dallanan bir ağaç olarak çizilir, bu nedenle adı.
- Kuyruk, kuyruğa giren ilk şeyin aynı zamanda ilk çıkan şey olduğu (sırada beklemek gibi) uygun şekilde adlandırılmış bir veri koleksiyonudur. Bir öncelik kuyruğunda, veriler öncelik sırasına göre depolanır, böylece ilk ortaya çıkan şey en acil şeydir, sıraya alınan ilk şey yerine en küçük önceliğe sahip şeydir.
- "ab ab cab" örneğinde, öncelik sıranız şöyle görünür: {'c':1, EOF:1, ' ':2, 'a':3, 'b':3}
Adım 3. Ağacınızı oluşturmaya başlayın
Öncelik kuyruğundan en acil iki şeyi kaldırın (veya kuyruğunu kaldırın). Bu iki düğümün ebeveyni olacak yeni bir ağaç düğümü oluşturun, ilk düğümü sol çocuğu ve ikincisini sağ çocuğu olarak depolayın. Yeni düğümün önceliği, onun çocuğunun önceliklerinin toplamı olmalıdır. Ardından bu yeni düğümü öncelik kuyruğunda sıraya alın.
Öncelik sırası şimdi şöyle görünür: {' ':2, new node:2, 'a':3, 'b':3}
Adım 4. Ağacınızı oluşturmayı bitirin:
kuyrukta yalnızca bir düğüm kalana kadar yukarıdaki adımı tekrarlayın. Karakterler ve frekansları için oluşturduğunuz düğümlere ek olarak, sırayı boşaltacağınızı, ağaçlara dönüşeceğinizi ve zaten kendileri ağaç olan düğümleri yeniden kuyruğa alacağınızı unutmayın.
- İşiniz bittiğinde, kuyruktaki son düğüm, diğer tüm düğümlerin ondan ayrıldığı kodlama ağacının kökü olacaktır.
- En sık kullanılan karakterler ağacın tepesine en yakın olan yapraklar olurken, nadiren kullanılan karakterler ağacın alt kısmında, kökten daha uzakta konumlandırılacaktır.
Adım 5. Bir kodlama haritası oluşturun. Her karaktere ulaşmak için ağacın içinden geçin. Bir düğümün sol çocuğunu her ziyaret ettiğinizde, bu bir '0'dır. Bir düğümün sağ çocuğunu her ziyaret ettiğinizde, bu bir '1'dir. Bir karaktere ulaştığınızda, karakteri oraya ulaşmak için gereken 0'lar ve 1'ler dizisiyle kaydedin. Bu sıra, karakterin sıkıştırılmış dosyadaki gibi kodlanacağı şeydir. Karakterleri ve dizilerini bir haritada saklayın.
- Örneğin, kökten başlayın. Kökün sol çocuğunu ziyaret edin ve ardından o düğümün sol çocuğunu ziyaret edin. Şu anda bulunduğunuz düğümün çocuğu olmadığı için bir karaktere ulaştınız. Bu ' '. Buraya gelmek için iki kez sola yürüdüğünüz için ' ' nin kodlaması "00" dır.
- Bu ağaç için harita şöyle görünecektir: {' ':"00", 'a':"10", 'b':"11", 'c':"010", EOF:"011"}.
Adım 6. Çıktı dosyasında, kodlama haritasını başlık olarak ekleyin
Bu, dosyanın kodunun çözülmesine izin verecektir.
Adım 7. Dosyayı kodlayın
Dosyadaki kodlanacak her karakter için, haritaya kaydettiğiniz ikili diziyi yazın. Dosyayı kodlamayı bitirdikten sonra, sonuna EOF'yi eklediğinizden emin olun.
- "ab ab cab" dosyası için kodlanmış dosya şöyle görünecektir: "1011001011000101011011".
- Dosyalar bayt (8 bit veya 8 ikili basamak) olarak saklanır. Huffman Encoding algoritması 8 bit biçimini kullanmadığından, kodlanmış dosyaların uzunlukları genellikle 8'in katları olmaz. Kalan basamaklar 0'larla doldurulur. Bu durumda, dosyanın sonuna başka bir boşluk gibi görünen iki 0 eklenir. Bu bir sorun olabilir: Kod çözücü okumayı ne zaman durduracağını nasıl bilebilir? Ancak, bir dosya sonu karakteri eklediğimiz için, kod çözücü buna ulaşacak ve daha sonra eklenen her şeyi yok sayarak duracaktır.
Bölüm 2/2: Kod Çözme
Adım 1. Huffman kodlu bir dosyada okuyun
İlk önce, kodlama haritası olması gereken başlığı okuyun. Bunu, dosyayı kodlamak için kullandığınız ağacı oluşturduğunuz şekilde bir kod çözme ağacı oluşturmak için kullanın. İki ağaç aynı olmalıdır.
Adım 2. Bir seferde ikili bir rakamı okuyun
Okurken ağacı çaprazlayın: '0' okursanız, bulunduğunuz düğümün sol çocuğuna gidin ve '1' okursanız sağ çocuğa gidin. Bir yaprağa (çocuksuz bir düğüm) ulaştığınızda, bir karaktere ulaştınız. Karakteri kodu çözülen dosyaya yazın.
Karakterlerin ağaçta saklanma şekli nedeniyle, her karakterin kodlarının bir önek özelliği vardır, böylece hiçbir karakterin ikili kodlaması başka bir karakterin kodlamasının başlangıcında gerçekleşemez. Her karakterin kodlaması tamamen benzersizdir. Bu, kod çözmeyi çok daha kolay hale getirir
Adım 3. EOF'ye ulaşana kadar tekrarlayın
Tebrikler! Dosyanın kodunu çözdünüz.
