huffman encoding

• dil'e de uygunlanmasının türlü faydalar sağlayacağını düşündüğüm yöntem. şöyle ki:
  
  tüm ad, sıfat ve fiil köklerinin günlük kullanımlarına ait bir istatistik çıkartılsın ve en çok kullanılan ada en kısa kelime karşılık olarak seçilsin. misal transformatör kelimesi kitlelerce öd kelimesinden daha sık kullanılıyorsa bundan sonra transformatör'e öd, öd'e transformatör diyelim, basit ve kısa bir sesi hayatımızda ortalama 3 kere kullanacağımız kavramlara harcamayalım. böylece mesela her sabah birbirimize günaydın diyeceğmize "te" der, hem enerjiden hem de zamandan tasarruf etmiş oluruz.
  
  kökler değiştirildikten sonra türetme ekleri için de benzer bir uygulamaya gidilebilir, en çok kullanılan ek en kısa harf kombinasyonu ile ilintilendirerek optimizasyonun başarısı arttırılabilir.
• gençliğimde bir benzerini ama daha da şekillisini yapmaya çalıştığım algoritma idi. şöyleki teoride ve pratikte 600 mb lık divx dosyasını 1 diskete 1.44 mb e sığdırabiliyordum, evet doğru 600 mb 1.44 mb a küçülüyordu, fakat ufak bir sorun vardı o 1.44 lük veri tekrar 600 mb olamıyordu. bir yerde küçük bir hata vardı ^*. %98 loss oranı ile dünya rekorunu kırmıştım kendi çapımda.
• sıkıştıracağınız array içinde tekrarlayan pattern sayısı az ise veya sözlük, uygulamadaki adıyla frekans tablonuz genişse, yani örneğin datanın içinde birbirinden farklı 200 byte varsa bu 200. byte'ı encode etmek için 200 bit kullanacağınızdan sıkıştırma yerine çok farklı fantezilere gelebilen algoritmadır.
• aslinda yontem oldukca basit.. tum olaylarin frekansini bulur, yazarsiniz yanyana.. sonra en kucuk ikisini alarak her seferinde toplaya toplaya gidersiniz, bu isi yaparken de soz konusu ikiliden birinin koduna 0 digerine 1 eklersiniz.. bi de ornek verelim.. diyelim olaylarin frekanslari 0.6, 0.3, 0.08, 0.02 olsun..
  
  .....0.02 0.08 0.3 0.6
  ........\0 /1
  .........0.1 0.3 0.6
  ...........\0 /1
  ............0.4 0.6
  ..............\0 /1
  ................1
  
  simdi bu treedeki 1 ve 0'lari asagidan yukari istediginiz olaya giden yol ustunden okuyun.. cikan diziler istediginiz kodlar olacak (optimum bunlar):
  0.6 1
  0.3 01
  0.08 001
  0.02 000
• robert fanonun (bkz: fano code) mitde verdigi dunyanin ilk information theory dersinde david huffman in donem odevi adi altinda buldugu entropy coding algoritmasidir. kodlanan seri buyudukce bitrate birinci derece entropiye yakla$ir. unique degildir, yani bir seri icin birden cok huffman code bulunabilir. $uphesiz bunlardan en lezizi minimum varyansa sahip olanlari olacaktir. bu da ayni suffixe sahip kodlarin kod olu$turma sirasinda huffman treenin stackinde mumkun mertebe gozden uzak yerlere itilmesiyle biz farkina varmadan oluverir. seri icin elde edilebilecek kodlarin hepsi optimumdur. zira huffman code dan daha iyi symbol by symbol encoding bulunamayacaktir, teorik olarak mumkun degildir, tren kacmi$ adam donem odevi maskesi altinda olayi bitirmi$tir. jpeg gibi compression yontemleriyle kar$ila$tirilmasi abestir, cunku lossy compression yontemlerinin cogunun (jpeg dahil) en son coding a$amasi huffman codingdir. exponential distributiona sahip bir kaynagimiz oldugunda ne zip, ne arithmetic coding ne lzw ne bok ne de tezek.. huffmanin seride cok ciddi bir periyodiklik yoksa teker teker hepsinin eline verecegi allahin emridir. realtime uygulamalar icin adaptive olanini da yapmi$tir insan evladi: (bkz: adaptive huffman encoding)
• lossless bir compression yontemidir^*. yani mpeg, jpeg gibi compression yontemlerinde var olan az da olsa data kaybetme sorunu bu yontemle yasanmaz.
• ahmet huffman tarafindan bulunmu$ bir stream'deki en cok kullanilan karakterin en kisa bit string ile ifade edilmesine dayali compression algoritmasi.. (bkz: huffman)
• bir karakter katarı içindeki karakterlerin katar içinde var olma sıklığı tablo haline dönüştürüldükten sonra en çok kullanılanın en az bit ile temsil edileceği bir şekilde katarın yeniden kodlanmasına olanak sağlayan sistem. böyle bir şey anlamadınız tabi, örnek vereyim:
  
  http://members.comu.edu.tr/…ontent/week6/hafta6.pdf
  
  en basitinden şu düşünülebilir; bir karakter bir bayt yer kaplar. bir bayt ise sekiz bitten oluşur. fakat huffman ile kodlanmış bir katarda bir karakter tek bir bit ile bile temsil edilebilir. bu da bize sıkıştırma sağlar.
• input'a göre %20~%90 kazanç sağlar...
• genelde yerel tekrarları daha iyi sıkıştırabilen (örn: lzw, lz77, hatta rle) bir sıkıştırma algoritmasıyla beraber kullanılır. kendisi tüm veriye yönelik bir frekans tablosundan oluşturulduğundan yerel entropi değişimlerini iyi karşılayamaz.