Huffman Sıkıştırma Algoritması

İyi günler.

Bu yazımda sizlere [Huffman Sıkıştırma Algoritması](http://tr.wikipedia.org/wiki/Huffman_kodu)ndan bahsedeceğim.

İlk olarak Huffman algoritmasından bahsetmek istiyorum. Huffman algoritması temel olarak bir metinde yer alan karakterlerin frekanslarını bularak belli bir düzende Huffman ağacına yerleştirilmesine ve buradan erişilmesine dayanıyor. Biraz daha açıklayıcı konuşalım. Bilgisayarda karakterler 8bit(1 byte) olarak saklanır. Huffman algoritmasındaki asıl amaç karakterlerin kapladığı alanı azaltarak sıkıştırma yapmak.

Mesela bir örnek vermek gerekirse diyelim “AAAABBBCC” diye bir metnimiz var. Normalde bu metin herbir karakter 8bit kaplayacak şekilde yani toplamda 8*9 bitte saklanır. Huffman algoritmasına göre ise şu şekilde saklıyoruz:

**1-**Öncelikle karakterlerin metinde bulunma sıklığı(frekans) larını buluyoruz.
A karakteri metinde 4 kere geçmiş yani frekansı 4
A:  4   ,   B:  3   , C:   2
**2-**Bundan sonra yapılacak işlem en düşük frekansa sahip iki elemanı seçerek onlardan ağaç oluşturma işlemi

[![](http://www.onurbaysan.com/blog/wp-content/uploads/2010/09/tree1.jpg “tree1”)](http://www.onurbaysan.com/blog/wp-content/uploads/2010/09/tree1.jpg)

[![](http://www.onurbaysan.com/blog/wp-content/uploads/2010/09/tree2.jpg “tree2”)](http://www.onurbaysan.com/blog/wp-content/uploads/2010/09/tree2.jpg)

**3-** Şimdide bu karakterlerin yeni hallerinin ne olacağına. Ağaçta kökten itibaren eğer karakterimiz sol alt ağaçta bulunuyorsa koda 0 ekliyoruz , eğer karakter sağ alt ağaçta ise 1 ekliyoruz. Buna göre:

A: 0 oluyor
B: 11
C: 10

**Sonuç:** Normalde “AAAABBBCC” metinini 8*9 bit ile saklıyorduk. Şimdi ise bu metni şu şekilde saklıyoruz.

AAAA  = 0000
BBB = 111111
CC = 1010

“AAAABBBCC” = 00001111111010 yani 14 bit.

Sıkıştırma oranı ((72- 14) / 72) * 100 = %80 oranında sıkıştırdık.

283 Words

Java’da Comparable Arayüzü

İyi akşamlar.

Diyelim ki Java’da Integer tipinde değişken tutan bir kolleksiyonum var. Aşağıdaki gibi yazmışım kodunu da

ArrayList test = new ArrayList(); test.add(9); test.add(4); test.add(1); test.add(30); test.add(25); test.add(100); for(Integer i : test) System.out.print(i + ” “);

Yukarıdaki kodu; yazmış olduğumuz sınıfta ilgili methodun içinde kullanınca , çıktı olarak *ArrayList *e eklenme sırasına göre bir çıktı görürüz. *ArrayList *i belli bir sıraya sokmak istediğimizde *Collections.sort()* methodunu kullanırız. Örneğin yukarıdaki kodda 9. satırdan sonra aşağıdaki kodu yazdığımız varsayalım.

Collections.sort(test);

Kodu tekrar çalıştırdığımızda çıktının sıralı olacağını göreceğiz. *Collections.sort() *methodu birden çok overload u bulunan (String , Integer , …) bir methodtur. Ve Java’da kolaksiyonlar içindeki verileri sıralamada kullanılır.

Şimdi gelelim bizim asıl senaryomuza. Senaryomuz şöyle diyelim benim Insan diye bir sınıfım var. Ve bu sınıfın içinde *ad* ve *yas* diye iki değişkenim olsun. Ben bu niteliklerle oluşturduğum Insan nesnelerini *ArrayList*‘te tutmak istiyorum ve yine rasgele sırada bir dağılım olduğunu düşünelim. Ben bu listemi Insan tipi nesnelerin yas bilgisini kullanarak nasıl sıralarım? İşte senaryom bu.

Bunun için *Comparable* arayüzünü Insan sınıfıma implement ederek *Comparable *arayüzünün içinde bulunan *compareTo* methodunu override edeceğim.

public class Insan implements Comparable { public int yas; public String ad; public Insan(int yas , String ad) { this.yas = yas; this.ad = ad; } public int compareTo(Object o1) { if (this.yas == ((Insan) o1).yas) return 0; else if ((this.yas) > ((Insan) o1).yas) return 1; else return -1; } }

Aşağıdaki kodla denememizi yapalım bakalım çalışıyor mu?

ArrayList test = new ArrayList(); test.add(new Insan(18, “Chuck Bass”)); test.add(new Insan(17, “Blair Waldorf”)); test.add(new Insan(27, “Behlul”)); test.add(new Insan(22, “Bihter”)); test.add(new Insan(55, “Adnan”)); test.add(new Insan(70, “Ramiz Karaeski”)); test.add(new Insan(65, “Kenan Birkan”)); test.add(new Insan(30, “Ezel”)); Collections.sort(test); for(Insan i : test) System.out.println(i.yas + ” ” + i.ad);

Şimdi biraz daha fantastik birşey yapalım. Mesela diyelim ki yaşları aynı olan insanları da ad sıralamasına sokmak istiyorum. Bu örnekte fantastik oldu ama kullanılır bir yerlerde. Neyse bakalım bunu yapabilmek için de compareTo methodumuzu nasıl eziyoruz.

public int compareTo(Object o1) { if (this.yas == ((Insan) o1).yas) { if (this.ad.compareTo(((Insan)o1).ad)>0) return 1; else return -1; } else if ((this.yas) > ((Insan) o1).yas) return 1; else return -1; }

Yukarıdaki koda da dikkatli bakarsanız birşeyin dikkatinizi çekmesi lazım. O da ya adları da aynı olursa öle bir durumda ilk olarak hangi nesneyi eklediysek onu yazacak ![:)](http://www.onurbaysan.com/blog/wp-includes/images/smilies/icon_smile.gif)

499 Words