www.fatihkabakci.com

Personal Website and Computer Science TUR EN

HUFFMAN ALGORITMASI

Last update: 3/14/2012 10:21:00 AM

Yazan ve Cevaplayan:Fatih KABAKCI

Bu soru Chip Online sayfasında 08.10.2010 tarihinde demir12 adlı kullanıcı tarafından sorulmuştur.

Gelen 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..

Verilen Cevap:

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.

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,yaprak(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
MemberCommentDate:
guest 
huffman alqoritmasi

Mais
cvs weekly sales damske.com cvs promo
rite aid savings card boomasontennis.com rite aid online coupon
online cialis coupons blog.suntekusa.com free cialis coupon
detrola myhsbook.com detrol la
nizoral emulsiovoide nizoral nizoral tabletti
sildenafil 100mg celticcodingsolutions.com sildenafil 100mg
 		12/13/2015 10:21:00 AM
Name:


Question/Comment
   Please verify the image




The Topics in Computer Science

Search this site for





 

Software & Algorithms

icon

In mathematics and computer science, an algorithm is a step-by-step procedure for calculations. Algorithms are used for calculation, data processing, and automated reasoning.

Programming Languages

icon

A programming language is a formal constructed language designed to communicate instructions to a machine, particularly a computer. It can be used to create programs to control the behavior of a machine. Java,C, C++,C#

Database

icon

A database is an organized collection of data. The data are typically organized to model aspects of reality in a way that supports processes requiring information.

Hardware

icon

Computer hardware is the collection of physical elements that constitutes a computer system. Computer hardware refers to the physical parts or components of a computer such as the monitor, memory, cpu.

Web Technologies

icon

Web development is a broad term for the work involved in developing a web site for the Internet or an intranet. Html,Css,JavaScript,ASP.Net,PHP are one of the most popular technologies. J2EE,Spring Boot, Servlet, JSP,JSF, ASP

Mobile Technologies

icon

Mobile application development is the process by which application software is developed for low-power handheld devices, such as personal digital assistants, enterprise digital assistants or mobile phones. J2ME

Network

icon

A computer network or data network is a telecommunications network that allows computers to exchange data. In computer networks, networked computing devices pass data to each other along data connections.

Operating Systems

icon

An operating system is software that manages computer hardware and software resources and provides common services for computer programs. The OS is an essential component of the system software in a computer system. Linux,Windows

Computer Science

icon

Computer science is the scientific and practical approach to computation and its applications.A computer scientist specializes in the theory of computation and the design of computational systems.