huffman algoritmasında bir soru

arkadaşlar huffmanı tam anlamadım birşey soracaktım..normal dosyadaki bitleri okurken huffman nasıl benzeşim yapıyor..mesala bütün onu anlatımlarında diyoki...

a=110
b=100
aabbabacba gibi harfler veriyor..

burayı anlamadım...yani huffman kodlamadan önce bitlere harf atamasımı yapıcaz..

normal olarak dosyadaki 1101001100101010 gibi bir ifadede huffmanı kullansak burda hangisi hangisine benziyor nasıl bilecez..

yani arkadaşlar anlatabildim mi..

illa kafamından belli bir bite harf atamasımı yapmalıyız..yukarıda iki defa 100 kullanıldıgını yazılıma nasıl anlatıcaz..

Veri sıkıştırmak amacıyla kullanılan huffman algoritmasi,kullanılan karakterlerin kullanım sıraları,yani frekanslarına gore kodlama yaparak onları doğru sekilde sıkıştırmayı amaçlayan bir algoritmadır.Bir dili bu algoritma ile kodlamak istedigimizde,o dilde kac karakter kullanılıyorsa,o olcude 2'n=kullanılan karakter sayısı bagıntısını hesaplayabiliriz.Ornegin,dilimizde a,b,c ve d olarak 4 farklı karakterimiz varsa şayet,kullanılacak bit en fazla 2 olacaktır veya 8 farklı karakter neticesinde 3 bit yine yeterlidir(2'n).Yukarıdaki ILK atamalar tamamen keyfi degerde olabilir.Ornek olarak,yukarıdaki degerleri referans alacak olursak,baba sozcugunun kodlanmış hali aşagıdaki sekilde olmalıdır.
b -> 100 , a -> 110 , b -> 100 , a-> 110 => 100110100110 şeklinde olmalıdır.Yani,bir mesaj veya metin kodlanırken,o mesaj veya metin icerisindeki karakterlere deger atamaları yapılmak zorundadır.(Cunku amaç verileri kodlayarak bir sonuc uretmektir).Mesajın kodlanmış hali ise bit bit analiz yapılarak,(bu soru icin) 3'er bit ayrımı ile degerin hangi karaktere ait oldugu bilinebilir.Yazılım'a bakacak olursak,cesitli kontrol komutları ile LCV sıkıştırmasında oldugu gibi,karakterlere deger bildirimleri yapılabilir.Başarılar

yani muh34 diyosun ki...kendimiz bir karakter belirlemeliyiz mesala bir ascıı karakteri alıp ona belli bir bit atamalıyız..4 farklı karakterse 2 bit şöyleki;

a=00;
b=01;
c=10;
d=11;

gibimi yani a'daki degeri biz belirleyicez b'deki degeride öyle..o halde burda a karakteri yer kaplamazmı..birde bütün kombinasyonları biz nasıl bilicez...

Evet.ASCII 'a' karakteri sadece 1 byte'lik yer kaplar.Ortaya cıkan kodlama şayet bir array'da tutulacaksa buda bool veri tipli yaratılıp 2 byte'lık yer kaplayacaktır.Butun kombinasyonlari ise,yazacagınız programda algoritmayı kendiniz tasarlayabilir,veya kullandıgınız programlama dilinde varsa eğer lojik sonuc ureten template fonksiyonlarını uyarlayabilirsiniz.2'şer bitten oluşan muhtemel sonucları yukarıda belirtmişsiniz,bir dilde kac karakter var ise,2'n adet muhtemel sonuc olacaktır,buda bahsettiginiz gibi 000,001,010,011... seklinde giden lojik formattır.Başarılar

o halde her deger icin 1 byte yani 8 bit alan işgal etmiş olucaz..e sıkıştırma nerede kalıyo o zaman..

ayrıca muh34 yardımların icin teşekkür ederim..

Bakın programlama olarak huffman kodlamasını en iyi sıkıştırma yapılabilecek sekilde tasarlamak ayrı bir durum.Sizin anlamadıgınız noktalar karakterlere deger atama durumu idi,nitekim o noktaya deginmiştim ben.Verim açısından yani sıkıştırma durumu icin cok cesitli yontemler bulunmaktadır,elbetteki amac sıkıştırmayı gercekleştirmektir.Başarılar

eyvallah teşekküer ederim..demekki algoritma bu şekilde başarılı ve bu şekildede kullanılıyor..bu konuyu daha iyi araştıracam saglıcakla..

muh34 birşey daha soracaktım....şimdi diyelim...elimizde 2 deger var.
a=00;
b=0000;
c=11
vede şöyle bir bit cıktısı..

110000 gibi burası ne anlama geliyor caa anlamına mı cb anlamına mı geliyor..

bunu neden soruyorum..huffmanı üzerinde çalıştıgım bir algoritmada kullanıcamda..

algoritma sürekli degerler üretiyor..00 veya 0000 gibisinde yanyana arka arkaya gelen 00 00 ile 0000 farklı anlamlar ifade ediyor..yani aa ifadesi b algılanmaması lazım..ayrac felanda kullanamıyorum sence bu konuda ne yapsam...

Bu soruya net bir cevap verebilmem icin kodunuzu inceleyip tam olarak hangi noktada ne yapmak istediginize bakmam gerekir,cunku yukarıdaki bit cıktısı cakısmaya da sebeb olabilir,fakat programlama mantıgı ile ilgili genel olarak soyle bir yorum yapacak olursam,Bit haritasını kac bit uzerinden taradıgınız onemlidir.Ornegin cıktı mesajı 110000 ise,2'ser bit formatı ile tarama yaptıgınızda 'caa' mesajı anlamına gelir.Aksi takdirde keyvalue'ların çakışması olağandır ve huffman agacına bakmak gerekebilir.Suanki ortamda umarım yardımcı olabilmişimdir,yinede bir problem oldugunda yazabilirsiniz.Başarılar

algortimaya baktıgınızda birde şunu soracaktım belki huffmanl alakası yokta utp-8 gibi bir yöntem kullanılabilirmi veya

şöyle bir düşüncede var aklımda..

her cıkan degeri rle ile sıkıştırsak örnegin..

0000' oluyo ya..

ilk dger cıktı 00 ikinci deger.00
rle ile 2o2o şeklinde kaydedsek mümkünmüdür acaba..

Uygulamak istediginiz sıkıştırmanın temelinde iyi bir huffman agacı olusturmanız problemin cozumunde yetecektir.Ayraç vb karakterleri kullanmanıza gerek yoktur,cunku agactaki her dugum bir dataya sahiptir ve birbirinden bagımsızdır.Şayet bir array uzerinden dosya tabanına erişmeye çalışşaydık ozaman dediginiz durum gundeme gelebilirdi,ancak ote yandan huffman modelinin anlamı kalmayıp sıkıştırma düşük bir oranda gerceklesirdi.Ilk olarak elimizde saglam bir tree olması gerekiyor.O halde veri modelimiz icin bir agaca ihtiyacımız olacak.Dugumun veri yapısı ise,kesinlikle sifrelenmiş bir datayı kapsaması gerekiyor,ayrıca sizin gerekli gordugunuz verilerde dugumun icerisinde olabilir.
 
Her dugum icerisinde veriler yandaki gibi olabilir -> SIFRE(bit grubu),ISIM,MESAJ gibi..
 
ornegin,sizin verdiginiz ornek olan 0000 veya 00 bu sayede farklı bilgi olacaktır,bunu gozle gorerek daha iyi anlamanın yolu olarak her dugume bir keyword verebilirsiniz.
 
Sıra agac olusturulduktan sonra data akışını dosya'ya uygulamak konusuna gelir.Bunu,Kok(root)'ten baslarayak,yaprakl(leaf)'lara kadar butun sifreyi dosyaya aktarmak ile saglanacaktır.Bu işlemden sonra şifre,mesaj veya her ne bilgi var ise,istediginiz veri modelini kullanarak dosyadan cekebilirsiniz(tavsiye edilen yine agac uzerinden).
 
Ozet olarak algoritmanın kaba kodu(pseudo code) cıkarılacak olursa,
 
1 -> huffman algoritmasi icin,karakter frekanslarına gore kodlama yap(Mesaj -- 001 vb).
2 -> if(dagılım eşit ise) blok sıkıştırma algoritması ile aynı oranda başarı saglayacaktır.
3 -> Yaptıgın Kodlama metoduna gore bir agaç(tree) oluştur.
4 -> Olusturdugun agaçtan,gerekli dosya tabanına veri akışını sagla.
5 -> if(Akış tamamlandı ise) Kullanmak istedigin veri modeli ile bu bilgileri check et
Aksi takdirde Agaç yapısına don.
 
Gerekli pseudo kod mantıgını reel koda donusturmek su asamada daha kolay olacagını dusunuyorum.Başarılar

muh34 yardıma ihtiyacım var kardeşim bilmiyorum maildende yazabilirdemde burdan sorayım dedim şimdi huufmanı ögrenmeye sıfırdan başladım ve şunu okudum..aşagıda frekans tablosu oluşturup oluşturmamadan bahsediliyor..bizim bu algoritmada eş zamanlı olrak huffmanı kullanmam lazım..yani algoritma deger üretlilirken her üretilen deger benzeri degerine katılmalı ama hangi degeri üreticeni bilemiyoruz..aşagıdaki acıklamaya göre statik mi dinamik mi kullanmam gerek yardımcı olursan sevinirim saygılarımla..

"Bir veri kümesini Huffman tekniği ile sıkıştırabilmek için veri kümesinde bulunan her bir sembolün ne sıklıkta tekrarlandığını bilmemiz gerekir. Örneğin bir metin dosyasını sıkıştırıyorsak her bir karakterin metin içerisinde kaç adet geçtiğini bilmemiz gerekiyor. Her bir sembolün ne sıklıkta tekrarlandığını gösteren tablo frekans tablosu olarak adlandırılmaktadır. Dolayısıyla sıkıştırma işlemine geçmeden önce frekans tablosunu çıkarmamız gerekmektedir. Bu yönteme Statik Huffman tekniği de denilmektedir. Diğer bir teknik olan Dinamik Huffman tekniğinde sıkıştırma yapmak için frekans tablosuna önceden ihtiyaç duyulmaz. Frekans tablosu her bir sembolle karşılaştıkça dinamik olarak oluşturulur. Dinamik Huffman tekniği daha çok haberleşme kanalları gibi hangi verinin geleceği önceden belli olmayan sistemlerde kullanılmaktadır. Bilgisayar sistemlerindeki dosyaları sıkıştırmak için statik huffman metodu yeterlidir. Nitekim bir dosyayı baştan sona tarayarak herbir sembolün hangi sıklıkla yer aldığını tespit edip frekans tablosunu elde etmemiz çok basit bir işlemdir."

2-şimdi muh34 verilen yazıda frekans tablosu oluşturulup agac kurulduktan sonra her frekansa şu degerler karşılık geliyo 

degerler şu şekilde;
a=0
b=10
k=110
d=1110
e=11111
g=11110

ve birde şu acıklama var;

Sıkıştırılmış veride artık ASCII kodları yerine Huffman kodları kullanılacaktır. Dikkat ederseniz hiçbir Huffman kodu bir diğer Huffman kodunun ön eki durumunda değildir. Örneğin ön eki "110" olan hiç bir Huffman kodu mevcut değildir. Aynı şekilde ön eki "0" olan hiç bir Huffman kodu yoktur. Bu Huffman kodları ile kodlanmış herhangi bir veri dizisinin "tek çözülebilir bir kod" olduğunu göstermektedir. Yani sıkıştırılmış veriden orjinal verinin dışında başka bir veri elde etme ihtimali sıfırdır. (Tabi kodlamanın doğru yapıldığını varsayıyoruz.)

===>burda ön eki kısmı kafamı karıştırdı bizde böyle bir sorunla karşılaşmayız degilmi..

muh34 yukarıdaki sorularım haricinde huffman algoritmasını şimdi nasıl çalışacagını anladım..bunun üzerine benim algoritmayı tekrar degerlendirip mantıgını ve nasıl çalışcagını dosyaya yazıp tekrar seninle paylaşmak istiyom..yalnız bu konuda sorularım olursa buraya yazıcam bakalım dogru düşünebilecekmiyim..yardımcı olursan cok teşekkür ederim..

muh34 1.sordugum soruda cevabı kendim verdim..sanırım burda dinamik huffman yöntemini kullanıcam nasıl anlık veri iletiminde her karakterin kac defa tekrarlanıcagı bilinmiyorsa burda eş zamanlı olarak sıkıştırlan hangi degerin olucanı bilemeyiz yani şimdi mesala algortimanın birinci kısmı yani benim düşündügüm kısım kod üretecek huffman ikinci olacak ama 1.sinde ne kod üreteceni bilmedimiz icin static kullanamayız cünkü statikde ilk önce karakterler sayılıyor sonra kodlama yapılıyor.ama burda ben sayma yapamam cünkü dosyaya sıkıştırdıgım şekli kaydedemiyorum..0000 ne oldunu bilemem..

Yukarıdaki veri tablosunda 'on eki' kelimesi,cıktıların birbirlerine karıştırılmadıgının ispatını nitelendirmektedir.Statik tarama,frekans tablosunun onceden belirlenmiş halidir.Programlama acısından,frekans tablosunu manual(el ile) ayarlayarak bu teknigide kullanabilirsin,ancak dinamik frekans tablosu her zaman daha verimli olacaktır.Size daha onceden bahsettigim gibi bir agactan dosya'ya veri akışını saglamanız gerekmektedir.
1 -> Dosya Acilir.
2 -> if(Dosya Hata Uretmez ise)
      Agacın yapraklarina ulasana kadar dosya'ya veri akışı(dugum->bilgileri) gerceklestirilir.
3 -> Dosya Kapatılır.
Gerekli Dosya işlem yapısı yukarıdaki basit pseudo code ile Tasarlanabilir.
Başarılar

Yukarıdaki verdigim kaba kodun C dilindeki kodlamasıda asagıdaki gibidir
 
FILE *huffman;
if((huffman=fopen("huffman.txt","a"))==NULL) {
printf("Dosya Acma Hatasi\n");
exit(1);
}
void birFonksiyon(parametre agaci ve dosya adını alabilir)  {
birFonksiyon(agac'in sag kolu);
fscanf(huffman,"datalara gore gerekli cevrim karakterleri(%d gibi)",huffman->sifre);
birFonksiyon(agac'in sol kolu);
}
printf("Huffman Agaci Dosya'ya basarili bir sekilde kaydedilmistir\n");
fclose(huffman);
 
Başarılar
 

muh34 hocam önemli diyerek mail adresinize bir mail yolladım aynı soruyu burdan sormak istyiorum..

 fatih hocam size aklıma şimşek gibi çakan önemli bir konu icin burdan mesaj attım..umarım sizi rahatsız etmiyorum...yardımcı olursanız sevinirim..
ya ben neden huffman algoritmasına ihtiyac duyuyorum ki;
huffman her karakter icin agac dalalrının sıralanmasına göre bir deger üretiyor...aşagıdaki örnekte mesala..;
http://www.csharpnedir.com/artic ... e%20Uygulamas%C4%B1
şimdi huffmanda mesala a=10 b=1100 diyelim 30 tane a 50 tane b var o halde 30*a+50*b oluyor....
ya benim aklıma şu fikir geldi benim size gönderdiigm algoritmada tablo icerisindeki degerler;
ya 1 yada 0 ve bunların fazlalıklarına göre degişiyor...size gönderdiigm dosyadan tekrar inceleybilirsiniz..yani aklıma şu geldi...madem huffman veri sıklıgıyla boyutunu carpıyor a benim algoritmada zaten iki veri var..digerleri bunların sayısı...
mesala;
a=1;
b=0; 
iki tane deger var..normal olarak bit karakterleri..
mesala cıktı nasıl oluyo..
1111100011100100010 gibi atıyorum...yada 0000111111000001000111000 gibi yani hep sıfır veya bir gruplarından oluşuyor....
bunu rle ile yazsam bir sakıncası olurmu...
mesala size gönderdigim dosyadaki o örnegi alalım o kutuları...
tabii burda ifade etmek icin ascıı karakterlerini kullanıcam gercekte rle ile kodlucaz...
11 00 00 0 - 0 1 0 0=>>bunu şu şekilde yazsak(tire boşluk)
2a 2b 2b b - b a b b
veya 
111 11 11111 11 000 00 0000
1a   2a  5a      2a 3b   2b 4b   gibi;
bir sorun olurmu,
yani cıktıya rle yöntemi uygulasam arka arkaya gelen 2a2a'da sorun olurmu bence olmaması lazım..degil mi..
eger böyle yap derseniz böyle yapıcam..bu konu beni heyecanlandırdı cevabınızı merakla bekliyorum..
yoksa huffman icin her karaktere bir deger atamam gerekiyo..yani
a=0;
b=00;
c=000;
d=0000;
sonra bunları dinamik onların frekanslarını saydırmak lazım...
yani burda 2 durum var..huffman gibi farklı degerlerin ve kümlerim yok..
2.cisi her ihitmali nasıl göz önün bulunduracam arka arka 99 tane 1 gelse 99 karakteri nasıl tanımlacam..
belki bu dediklerimde hatam olabilir ama rle yöntemini nasıl bulundunuz hem kodlaması kolay olur hemde çalışma hızı cok düşmez diye tahmin ediyorum..
tabii burda rlenin hafızada nasıl yerleştigide öenmli;
cıktı ;
11 11 00 00 1 111 00
rle ile;(tam olarak rleninde nasıl çalıştınıda bilmiyorum ama..
[2]1[2]1[2]0[2]01[3]1[2]0 
yani bu şekilde çalışmazmı..
bana yardım ettiginiz icin tekrar teşekkür ederism iyi çalışmalar fatih hocam..

rle algoritması da sıkıştırma algoritmalarından bir tanesidir.Fakat rle metotu devamlı tekrar belirten veriler icin başarılı calısan bir algoritmadır.Fakat kodlama acısından size daha kolay geliyor ise bu algoritma uzerinden devam edebilirsiniz.Sonuc olarak yapmak istediginiz mantıga gore rle algoritmasıda huffman'ın amacı dogrultusunda calısır(Veri Sıkıştırma).Başarılar

Alıntı: muh34  

rle algoritması da sıkıştırma algoritmalarından bir tanesidir.Fakat rle metotu devamlı tekrar belirten veriler icin başarılı calısan bir algoritmadır.Fakat kodlama acısından size daha kolay geliyor ise bu algoritma uzerinden devam edebilirsiniz.Sonuc olarak yapmak istediginiz mantıga gore rle algoritmasıda huffman'ın amacı dogrultusunda calısır(Veri Sıkıştırma).Başarı

ama rledede yine bir arkadaş

"Verileri bir diziye aktaracaksın diyelim. char data[0]=31, data[1]=21 vs. Sadece indeks ile istediğin dataya ulaşırsın karışmaz. Hatta veri sadece 1 lerden oluşuyorsa, 31,21 e bile gerek yok, direkt 3,2 şeklinde kullanabilirsin."

deyince dataları karıştırmıcana emin olduktan sonra ögrendim ve rahatladım ki;rleyide kullanabilirim..yalnız aylardır bu konuyu araştırıyom utp-8 vs yöntemlerine baktım..ama nicin bu kadar kolay yöntemleri düşünmedim diyorum..

artık gönül rahatlıgı ile rlede kodlayabilirim..

teknik olarak rledede bazı sorunlar cıkıyomuş belli degerlerden sonra felan ama yıllarca kullanılan bir algoritma saglam olur..ayrı problemler oluncada test etmek lazım..

tekrar teşekürler muh34 saglıcakla..iyi çalışmalar..

muh34 hocam bizim algoritmada deger olarak boşluk degeride cıkıyor bunu huffmanda nasıl saklıyacagız yani huffmanda direk ayrac karakterimi diyecegiz..

muh34 bi kac gündür eleyi araştırıyodumda..rleyle işin icinden cıkamayacamızı anladım..cünkü tam olarak sorunu cözmüyo sanki birde boşluga vs ne diyecegiz onu bulamadım ama huffmala rastgele bir deger atamyı düşünüyorum yani boş yapragı nasıl ifade edicem yoksa şimdi yapıcaklarım şunlar..;

sende söylemiştinde kusura bakma tekrar edicem bir yanlışım varsa affola;

ilk önce her karaktere bir deger atarız..

00=>a
000=>b
0000=>c
00000=>d
1=>e
11=>f
111=>g
10=>k(boşluk)

sonra bunların frekansını alır bir huffman agacı cizeriz..

huffman bize yeni kod tablosu üretir...(burda ne olucanı bilmiyorum)

sonra tersten eski şekline döneriz...

Bir agac yapısında yaprak(leaf) tanımı cocugu olmayan dugumlere verilen addır.Sizin tabir ettiginiz boş yaprak tanımlama sureci ise,agac en alt noktası icin bellekten Agac hacmi kadar yer acarak,dugumu boş bir sekilde agaca yerlestirmektir.Buna gore yaprak agacta var olacaktır ancak icerisinde hicbir bilgi bulunmayacaktır.Kural geregi ise yaprak agac'ın en alt noktasında olup bir sonraki isaret ettigi bolge boş yani NULL olacaktır.
 
Frekans alımından sonra ise agac olusturulduktan sonra,tahmin edildigi gibi,her veri bir dugumun icerisinde olacaktır.Ornegin
                                        KOK (33)
                        a (11)                                 c(12)
                g(3)             d(8)                f(6)             e(6)
 
Şeklindeki agac uzerinde bir noktanın degeri,sol tarafa giderken 0,sag tarafa giderken 1 seklinde olacaktır.Misal olarak yukarıdaki agactaki d karakterinin kodlaması kok(33)'un solu -> 0 ve a(11)'in sagi -> 1 olacaktır.d karakterinin nihayi degeri 01 olur.Huffman agacının uretecegi kod tablosu bu sekilde olacaktır.
 
Başarılar

eyvallah yardımların icin cok teşekkür ederim muh34 iyiki varsın...