aritmetik kodlamanın ne olduğunu öğrenmeden önce
huffman kodlamasına bir göz atalım.
muhtemelen en çok bilinen kodlama yöntemi huffman kodlamasıdır. 1952 yılında d.a. huffman tarafından, olasılıkları verilen sembollerin kod tablolarını oluşturan bir yöntem olarak duyurulmuştur. bu kodlama sistemi, sabit uzunluklu kodlar kullanıldığı zaman mümkün olan en kısa (optimum) bit sayısına ulaşılmasını sağlamaktadır. huffman kodlaması benzeri bir diğer kodlama sistemi olan
shannon-fano kodlamasının ise optimum çıktıyı vermediği huffman tarafından kanıtlanmıştır.
huffman kodlaması, sembollerin olasılıklarına bağlık olmak üzere her sembol için bir çıkış kodu atar. bu kodlar 1 bit de olabilir, sembolün değerinden daha fazla da olabilir. her sembol için kullanılan optimum bit sayısı, p sembolün olasılığı olmak üzere 2’lik tabanda log (1/p) formülü
* ile hesaplanır. şöyle ki; eğer bir karakterin olasılığı 1/256 ise, karakter başına kullanılan optimum bit sayısı 8 olur. eğer olasılık 1/2 ise, karakter başına kullanılan bit sayısı 1’e kadar iner.
ancak bu yöntemin zayıf tarafı şudur; olasılıklar her zaman 1/2'nin katları şeklinde gitmeyebilir. bu yüzden optimum bit sayısı tam sayı olmayabilir. örneğin, olasılığı 1/3 olan bir sembolün optimum karakter sayısı 1.6 civarındadır. huffman kodlama şeması bu sembole ya 1, ya da 2
bit atamak zorunda kalır, her iki durumda da çıkış kodu (sıkıştırılmış mesaj) optimumdan daha uzun olur.
bu optimumdan uzaklaşma eğilimi, olasılığı çok yüksek olan sembollerde gittikçe artar. 9/10 olasılıklı bir sembolün optimum bit sayısı 0.15’tir. huffman kodlamasında ise 1 bit kullanılmak zorundadır. (gerekenin 6 katı)
şimdi aritmetik kodlamaya, en civcivli kısma gelelim. aritmetik kodlama, huffman kodlamasının sembollere atadığı kodları devre dışı bırakıyor. yerine, giriş sembollerini bir blok halinde tek bir kayar noktalı sayıya (floating point) çeviriyor.giriş mesajı uzadıkça ve dolayısıyla daha fazla karmaşıklaştıkça, çıktıdaki bit ihtiyacı da artıyor.
biraz daha açıklayalım bu yöntemi. aritmetik kodlamanın çıkışı 0 ile 1 arasında reel bir sayıdır. bu çıktının değerini oluşturmak için, kodlanacak sembollerin olasılıklarını (görülme sıklıklarını) bilmek yeterli. örneğin, “bill gates” mesajının karakter - olasılık dağılımını verelim önce (* karakteri aradaki boşluğu temsil etsin):
kar. – olas.
----- -----
*- 1/10
a - 1/10
b - 1/10
e - 1/10
g - 1/10
i - 1/10
l - 2/10
s - 1/10
t - 1/10
karakter olasılıkları bilindiğinde, her bir sembolün aralığı olasılık çizgisi boyunca (0 ile 1 arasında) sıralanır. görselleştirelim:
kar. – olas. - aralık
----- -----
*- 1/10 – (0.00-0.10)
a - 1/10 – (0.10-0.20)
b - 1/10 – (0.20-0.30)
e - 1/10 – (0.30-0.40)
g - 1/10 – (0.40-0.50)
i - 1/10 – (0.50-0.60)
l - 2/10 – (0.60-0.80)
s - 1/10 – (0.80-0.90)
t - 1/10 – (0.90-1.00)
karakterler aralık değerlerinden yüksek olanına kadar olan aralık içinde her hangi bir değer alabilir. (t harfi aslında 0.90 ile 0.9999… aralığı içinde yeralır, 1 değerini hiçbir zaman almaz)
aritmetik olarak kodlanmış olan mesaj, ilk karakterinin aralığına bağlıdır. “bill gates” mesajını kodlarken ilk harf “b”dir. ilk karakterin düzgün olarak dekode edilmesi için, oluşturulan kodun b harfinin aralığı olan 0.20-0.30 aralığında olması gerekir. ilk karakteri böylece kodladıktan sonra yeni alt ve üst değerlerimiz ilk karakterin olasılık aralığı. (0-1 aralığı ile işimiz kalmadı artık, üst sınırımız 0.30, alt sınırımız 0.20)
kodlama işleminin kalan kısmında, ikinci karakter olan i harfinin 0.20-0.30 içerisinde hangi olasılıkla yer aldığını bulmamız gerek. i hafinin aralığı 0.50-0.60 aralığı. bu aralığım 0.20-0.30 aralığı içinde denk geldiği aralık ise 0.25-0.26 aralığı.
bu işlemi üçüncü ve diğer karakterler için devam ettirirsek sonuca ulaşmış oluruz. bu prosedürü,
algoritma olarak yazarsak:
------------------
alt_sınır 0.0 olsun
üst_sınır 1.0 olsun
giriş sembolü olduğu müddetçe
………giriş sembolünü al
………kod_aralığı=üst_sınır-alt_sınır
………üst_sınır=alt_sınır+aralık*üst_sınır(sembol)
………alt_sınır=alt_sınır+aralık*alt_sınır(sembol)
yap
alt_sınır çıktı olarak verilsin
--------------
bu algoritmayı takip ederek elde ettiğimiz tablo karakter – alt değer – üst değer tablosu aşağıdaki gibidir:
yeni karakter – alt değer – üst değer
0.0 - 1.0
b - 0.2 - 0.3
i - 0.25 - 0.26
l - 0.256 - 0.258
l - 0.2572 - 0.2576
* - 0.25720 - 0.25724
g - 0.257216 - 0.257220
a - 0.2572164 - 0.2572168
t - 0.25721676 - 0.2572168
e - 0.257216772 - 0.257216776
s - 0.2572167752 - 0.2572167756
son olarak elde ettiğimiz alt değer 0.2572167752 “bill gates” mesajının kodlanmış halidir. kodlama prosedürü bu kadar.
kodu çözme prosedürü ise şu şekilde gerçekleşiyor:
mesajın kodlanmış hali olan 0.2572167752 sayısı 0.2 ve 0.3 aralığına denk geliyor. daha önce bütün harflerin olasılık aralıklarını bildiğimiz için 0.2 ve 0.3 aralığının “b” harfini temsil ettiğini biliyoruz. ilk harfi çözdük, sıra ikinci harfte. 0.2572167752 sayısınından b harfinin alt sınırı olan 0.2 sayısını çıkardığımızda elde edilen sayıyı (0.0572167752) b harfinin aralığına (0.1) bölüyoruz. sonuçta elde edilen sayı 0.572167752 oluyor. bu sayı 0.5-0.6 aralığında olduğundan ve bu aralığa denk gelen harf i harfi olduğundan ikinci harfi de rahatlıkla bulabiliyoruz. bu prosedürü sürekli tekrar ederek “bill gates” mesajını bire bir elde ediyoruz.
algoritma olarak yazmak gerekirse:
---------
kodlanmış sayıyı al
yap
……kodlanmış sayının dahil olduğu aralığın hangi harfe ait olduğunu bul
……sembolü yaz
……aralık=sembolün alt değeri – sembolün üst değeri
……sembolün alt değerini kodlanmış sayıdan çıkar
……kodlanmış sayıyı aralık’a böl
sembol kalmayana kadar
--------
işte bu kadar.
aritmetik kodlama buraya kadar ilginç ve zekice bir teknik olarak görünse de, henüz neden huffman’dan daha iyi olduğunu söylemedik. şimdi bunu anlatmak için bir örnek verelim: “aaaaaaa” mesajını kodlayalım. a’nın olasılığı 0.90. kodlama algoritmasını kullanarak elde edeceğimiz sayı ise 0.4782969 olarak bulunuyor. kodlanmış metni çözmek için elimizde sadece 0.45 sayısının olması yeterli. 0.45 sayısı 7 bitten daha az bir alan kaplıyor. huffman ile elde edilecek olan “optimum” kod ise 9 bitlik alan kaplayacaktı.
daha büyük bir örnek ise, 100000 adet 0’dan oluşan bir metin. aritmetik kodlama ile bu metin yalnızca 3 byte uzunluğunda olurken, hufmann ile 12501 byte uzunluğunda! uç bir örnek olsa da, aritmetik kodlamanın gücünü ortaya koyuyor sanırım.
(büyük oranda
mark nelson’ın
http://www.dogma.net/... adresinde bulunan makalesinden çevirilmiştir)
