How Huffman Trees Work - Computerphile Computerphile English Turkish

How Huffman Trees Work - ComputerphileYouTube↗ IA↗(long shot)
Education 190.2K views 3.2K likes 44 dislikes 18 Oct 2013 Show Contributors 1

Computerphile 2.6M subscribers N/A YouTube↗

Contributed subtitles

English AtDhungel

Click to Play Video

There's no better way than to check something really simple and show you how you [would] derive it using Huffman tree techniques

Gerçekten basit bir şeyi kontrol etmekten ve Huffman ağacı tekniklerini kullanarak nasıl türeteceğinizi göstermekten daha iyi bir yol yoktur.

Construct a tree from the probabilities, and I'm going to go up

Olasılıklardan bir ağaç inşa et, ve ben yukarı çıkacağım

And I'll hope I don't run out of space all these probabilities add up to one

Ve umarım ki tüm bu olasılıkların bire bir ekleyebileceği kadar yer kalmaz

Order them starting with the highest at the left and they lowest at the right you can do the way around if you like

Onları soldaki en yüksek ile başlayarak sıralayın ve sağdaki en düşük olarak isterseniz istediğiniz şekilde yapabilirsiniz

So long as you're consistent about it [now]. There's no problem here, because they're all a quarter they're ordered already the huffman algorithm

[Şimdi] konusunda tutarlı olduğunuz sürece. Burada sorun yok, çünkü hepsi bir çeyrek var, zaten zaten huffman algoritması için sipariş verildi.

Then says group in

Sonra grup içinde diyor

twos from the right

sağdan iki numara

Successively by going through this, I hope it'll be clear what I mean

Bunu başarılı bir şekilde yaparak, ne demek istediğimi anlayacağınızı umuyorum

starting at the right take the lowest two probabilities that you can see so I group these together as the

sağdan başlayarak görebileceğiniz en düşük iki olasılığı alın;

branches of a tree

bir ağacın dalları

Computer scientists always draw their trees nearly always upside down the leaves if you like the base of the trees down here

Buradaki ağaçların tabanını seviyorsanız, bilgisayar bilimcileri ağaçlarını her zaman yapraklarını neredeyse her zaman baş aşağı tutarlar.

But the actual root where it springs from is up at the top if you group a quarter and a quarter together

Ama birlikte bir çeyrek ve çeyrek gruplandırırsanız, kaynaklandığı asıl kök en üsttedir

That gives a combined probability of a half that node these two probabilities

Bu, bu iki olasılığı düğümleyen bir yarım birleşik bir olasılık verir

Have been coped with in some sense you're now left with 2/3 probability

Bir anlamda başa çıktınız mı, artık 2/3 olasılıkla kaldınız

situation take the lowest two

durum en düşük ikiyi alır

probabilities, you can see if there's any

olasılıklar olup olmadığını görebilirsiniz

[ambiguity] about which you should choose then choose the rightmost set of probabilities. Well here. There's no problem

Seçmeniz gereken [belirsizlik] ardından en doğru olasılık kümesini seçin. İyi burada. Sorun yok

So the next stage for the two lowest probabilities is to group those together and make a 1/2

Dolayısıyla, en düşük iki olasılık için bir sonraki aşama, bunları bir arada gruplamak ve 1/2

combined probability

birleşik olasılık

They're done the next stage, so this is almost going like recursively back up the tree is to say [R]

Bir sonraki aşamaya geçtiler, yani bu neredeyse yinelemeli olarak geri gidiyor gibi oluyor ağaç [R]

But we now group these together [the] half and the half we've now reassured ourselves that all the probabilities

Ama şimdi bunları gruplandırdık [yarım] ve yarısı şimdi kendimize tüm olasılıkların güvencesini verdik.

Here when grouped together and added up come to 1.0

Burada bir araya toplanıp toplandığında 1.0'a geliyoruz

And we'll be in deep [trouble] if they didn't that is your huffman tree with those probabilities

Ve eğer onlar olmasaydı, bu olasılıklara sahip huffman ağacınız olmasalardı, derin bir belaya gireceğiz

The next thing you do this is great fun is to decorate the tree. I now want to from this

Bunu yapacağınız bir sonraki şey, ağacı süslemek çok eğlenceli. Şimdi bundan istiyorum

Workout what the [correct] code the minimal code should be for a given state start to get the root of the tree?

Egzersiz ağacın kökünü almaya başlamak için belirli bir durum için minimum kodun [doğru] kodunun ne olması gerekir?

Annotate the left going Branch with [zero] and the right going bra with a 1 you can do it the other way around

Soldaki Şube'yi [sıfır] ile açıklama ve sağdaki sütyeni 1 ile açma

Uniformly throughout if you want to it will come to a side different looking huffman code

Tekdüze boyunca eğer istersen bir tarafa farklı görünen huffman kodu gelecek

But it will have just the same properties as the one I'm going to derive when you come to this node

Ama bu düğüme geldiğinde türeteceğim özelliklerle aynı özelliklere sahip olacak.

And you say I'm now going to descend to the left again the rule is you add a zero of what you've already got

Ve şimdi tekrar sola doğru ineceğimi söylüyorsun, kural zaten sahip olduklarının sıfırını eklemelisin.

seen it with zero zero

sıfır sıfır ile gördüm

How about this state?

Peki ya bu durum?

You come down on a zero, but then you go to the right?

Sıfırdan aşağı iniyorsun ama sonra sağa mı gidiyorsun?

Every time you go to the right you add one to what you've already got

Ne zaman sağa gidersen, sahip olduklarına bir tane ekleyeceksin.

We've already got a 0 out of 1 and here. We are look it works for the rest

Biz zaten 1 üzerinden 0 var. Geri kalanlar için işe yaradığını düşünüyoruz.

Go down to the right with a 1 then go down to the left

1 ile sağa gidin, ardından sola

Every time you go down to the left add a zero to what you've got there. We are

Sola doğru indiğin her seferinde, sahip olduklarına bir sıfır ekle. Biz

1

1

Down to the right had a 1 that's that one

Sağa doğru bir tane 1 vardı

So there we are what huffman basically said in 1952 when he did this?

Öyleyse, 1952'de bunu yaparken, temelde huffman'ın söylediği şey nedir?

was [that] this was the

[method] of getting a

compact code in other words the best you could [possibly] do for those probabilities and

Başka bir deyişle, bu olasılıklar için [muhtemelen] yapabileceğiniz en iyi kod

I think David Hoffman's. Thesis is famous for only being about 12 pages long

Bence David Hoffman'ın. Tez sadece yaklaşık 12 sayfa uzunluğundadır.

I think many of us would love to write a thesis saying

Bence çoğumuz bir tez yazmayı seviniriz

Here is an unsolved problem. I've done it. Please give me a phd. Yes. It's only 12 pages long but to be fair to

İşte çözülmemiş bir problem. Yaptım. Lütfen bana doktora yapın. Evet. Sadece 12 sayfa uzunluğunda ama adil olmak

To those who are examining him. It's easy enough to prove that it works for something like this

Onu muayene edenlere. Bunun gibi bir şey için işe yaradığını kanıtlamak yeterince kolay

which [is] so easy because they are all exact negative powers of [2]

ki bu çok kolay çünkü hepsi [2] nin kesin negatif güçleri.

The harder thing is to prove that it still gives the best possible compromise even when the probabilities don't work in your favor

Zor olan, olasılıklar sizin lehinize işe yaramadığında bile, hala mümkün olan en iyi uzlaşmayı verdiğini kanıtlamaktır.

I have to sort of sound a word of warning here

Burada bir tür uyarı sesi duymalıyım

Let me do the San Francisco [entropy] on the San Francisco page if I can find space to squeeze it in

Sıkmak için yer bulabilirsem, San Francisco sayfasında San Francisco [entropi] yapmama izin verin

If you remember the entropy is the sum over all the [weather] states

Entropiyi hatırlarsanız, tüm [hava durumu] durumlarının toplamıdır.

They typically see in textbooks things looking like this

Genellikle ders kitaplarında böyle görünen şeyleri görürler.

from the first weather to the fourth

ilk havadan dördüncü

Weather situation take the sum over p. I log to the Base 2 1 over p

Hava durumu toplamı p. Base 2 1’e p üzerinden giriş yapıyorum

I that of course come down to being the sum over

Ben elbette toplamı olmak için aşağı gel

Minus p. I log p I is

Eksi s. Giriş ben p

equally valid so what we do for the entropy is we take the weighted sum [of]

entropi için yaptığımız eşit ağırlıkta toplamı almaktır.

The probability of the state happening times the log of the probability of it happening

Devletin olma olasılığı, meydana gelme olasılığının günlüğünü katlar.

And we've discovered in the entropy in compression video the entropy

Entropinin sıkıştırma videosunda entropiyi keşfettik

Overall is two bits

Genel olarak iki bit

Of course it is [it's] exact power of two all the weather states are the same

Tabii ki bu [hava] ikisinin gücü tam olarak tüm hava durumları aynı

But then we worked out [to] the average length of the code and the average length of the code is two bits

Ancak daha sonra kodun ortalama uzunluğunu hesapladık ve kodun ortalama uzunluğu iki bit

Yeah, they all occur with probability or quarter, but they're all two bits long so the average

Evet, hepsi olasılık veya çeyreklikle ortaya çıkıyor, ama hepsi iki bit uzunluğunda, yani ortalama

Length of [the] message [you] set is also two bits. This is so simple and so straightforward

[]] Mesajının [set] uzunluğu da iki bittir. Bu çok basit ve çok basit

That's the efficiency

Which is measured as h?

Hangisi h olarak ölçülür?

Over L in this particular case is 2 over 2

Bu özel durumda L üzerinde 2, 2'dir

2 bits for Entry [2] bits there is length which is equal to 100%

Giriş için 2 bit [2] bit var, uzunluğu% 100'e eşit

You can hit the entropy limit with this weather system

Entropi limitini bu hava durumu sistemi ile vurabilirsiniz.

Encoded in this way because these probabilities are all negative powers of 2 for those of you. Who've encountered

Bu şekilde kodlanmıştır, çünkü bu olasılıklar sizin için 2 negatif güçtür. Kimler karşılaştı

Entropy in Physics or chemistry take great care?

Fizikte veya kimyada entropi büyük özen gösteriyor?

information theorists call Entropy h

bilgi kuramcıları Entropy h'yi çağırıyor

don't do that in your chemistry exam in chemistry h is reserved for the amount of heat in a system, and

Bunu kimyada yaptığınız sınavda yapmayınız, h sistemdeki ısı miktarına ayrılmıştır ve

Certainly [remembering] back to my chemistry days. I think they use the symbol s for entropy so don't get confused

Kesinlikle kimya günlerime döndüğümü hatırlamak. Sanırım s sembollerini entropi için kullanıyorlar, bu yüzden kafan karışmasın

Shannon used h for antifreeze, so I will what about if we have?

Shannon antifriz için h kullandı, peki ya biz?

Whether states or some system where these probabilities are [not]?

Devletlerin mi yoksa bu olasılıkların bulunduğu bir sistemin mi [değil]?

Exact powers of two we'll look at a fishing trip. Let's say

İkisinin tam güçleri, bir balık avı gezisine bakacağız. Diyelimki

That we want a system with probabilities of one third

Üçte biri olasılıklı bir sistem istiyoruz

Ninth this person with a pretty good set of fishing kit and a good selection of fish to catch

Dokuzuncu kişi oldukça iyi bir balıkçılık seti ve yakalamak için iyi bir balık seçkisine sahiptir

Actually at the end of the day ends up that one third of his

Aslında günün sonunda, onun üçte biri kadar biter.

[or] her catch is called another one third is sea bass one ninth

[veya] avını başka üçte biri denir, levrek ise dokuzuncu

proportion of the catch is tuna one ninth is a baby shark and

yakalamanın oranı orkinos, dokuzuncu bebek köpekbalığı ve

We got a bit stuck for inspiration here Barracuda, whether you could get them all from the same boat. I don't know but let's say

Barracuda'da ilham almak için biraz sıkışıp kaldık, hepsini aynı tekneden alabilirmisiniz. Bilmiyorum ama diyelim

this person wants to

bu kişi istiyor

Transmit back in the shortest possible Toad

Mümkün olan en kısa Kurbağada geri iletin

What the predominant catches that he's got so he wants to signal whether he's you know?

Baskın olan ne yakalar? Bu yüzden tanıdığınızı işaret etmek ister.

He's got a good lot of Cod today

Bugün çok fazla Cod var.

Or is it bass or is it whatever first thing always is check your probabilities add up that except to three thirds

Veya bas veya her zaman ilk iş ne olursa olsun, üçte bir dışında

Which is one here we go

Hangisi buradayız

Huffman tree. We're still going to use log to the base 2 from the right take the pair of lowest probabilities

Huffman ağacı Sağdan taban 2'ye log kullanmaya devam edeceğiz, sağdaki en düşük olasılık çiftini al

You can see and those are these [1/9]

Görüyorsunuz ve bunlar bunlar [1/9]

So that makes two ninths cross out the ones you've coped with

Bu, dokuzuncuların başa çıkanlar ile çarpışmasını sağlıyor.

You've now got one third one third one ninth to ninth the two lowest probabilities. You can still see are

Şimdi en düşük iki olasılığın üçte üçte biri, dokuzda dokuzda biriniz var. Hala görebilirsin

[two] [ninths] and [1/9] which is going to combine to make a 1/3?

[iki] [dokuzuncu] ve [1/9] 1/3 yapmak için bir araya gelecekler?

sıradaki aşama

The two lowest probabilities you can see well you've got a third a third a third we have coped with [that]

Görebildiğiniz en düşük iki olasılık, bununla baş ettiğimiz üçte üçte birine sahipsiniz [bu]

We've coped with that if you get a choice of either that pair or that pair of thirds

Eğer o çifti ya da üçte birini seçerseniz, bununla başa çıktık.

[it] doesn't matter which actually you'll get slightly different codes

[hangisi] aslında hangisinin biraz farklı kodlar alacağı önemli değil

But with similar properties one third and this [one] [third]

Ancak benzer özelliklere sahip üçte biri ve bu [bir] [üçüncü]

Gets combined into two thirds and the final stage you can all see is dead easy

Üçte ikilik bir araya getirilir ve tüm görebileceğiniz son aşama ölü kolaydır.

We triumphantly

Biz muzaffer olarak

We do add up to a total probability of [1.0]

Toplam olasılığı [1.0] ekliyoruz

Now comes the fun bit of writing down the huffman codes for this in binary. You're descending left. So that's a [0]

Şimdi bunun için huffman kodlarını yazmanın eğlenceli bir parçası geliyor. Sola doğru iniyorsun. Yani bu bir [0]

You're going right? So that's a 1 you. Come down on this one

Doğru gidiyor musun? Demek bu bir 1 sizsiniz. Bu konuda aşağı gel

So that's a 1 and then a 0 this arm gets 1 1 but then you come [down] here

Yani bu 1 ve sonra 0, bu kol 1 1 alır, ama sonra buraya inersiniz

That's going to be 1 1 0 therefore this arm coming down here is 1 1 1 this one is 1 1 [0] and that

Bu 1 1 0 olacak, bu yüzden buraya gelen bu kol 1 1 1, bu da 1 1 [0] ve

One is 1 1 so those are your huffman codes when you take?

Biri 1 1, yani aldığınızda bunlar huffman kodlarınız mı?

h as the sum of your

toplamı olarak h

this is now from

State number 1 1 2 3 4 5 state number [1] is I've caught card [stay] number 2 is of Court [bath]

Durum numarası 1 1 2 3 4 5 durum numarası [1] yakaladım kart [kal] 2 numara mahkeme [banyo]

Up to five of your minus p. I log to the base 2 of p I

Eksi beşe kadar s. P üssünün 2 tabanına giriş yapıyorum.

You are going to find to your dismay that

Bunu dehşete düşüreceksin

The Entropy comes out to being [2] point 1 1 3 bits

Entropi [2] puan 1 1 3 bit olarak ortaya çıkıyor

I've looked this up on my calculator if any of you aren't sure how to take

Herhangi birinin nasıl alacağından emin değilseniz, hesap makinemde bunu araştırdım

Log the base to other third then

Tabanı diğer üçte birine kaydedin

We must keep ganging up on brady to do a number file on

Üzerinde bir numara dosyası yapmak için Brady’de gangster çekmeye devam etmeliyiz.

powers of number bases and logarithms

Sayı üsleri ve logaritmaların güçleri

The average length when you work it out is

Bunu yaparken ortalama uzunluğu

2 point 2 to 2 bits

2 punto 2 ila 2 bit

so the efficiency

yani verimlilik

is

1 over the other two point 1 1 3 over 2 point 2 2 2 is equal to

1 diğer 2 noktasından 1 1 3 2 noktasından 2 2 2 eşittir

95 Point one percent

95 Puan bir yüzde

Not bad, not bad

Kötü kötü değil

but not nearly as good as the weather stays why why is because these things are not exact negative powers of 2

ancak hava nedenleri kadar iyi olmasa da neden böyle olduklarını soruyorlar çünkü bu şeyler 2'nin tam negatif gücü değil

With these things being exact negative powers of three I can confidently

Bu şeylerin üçünün kesin negatif gücü olduğu için güvenle

Predict that if only we could calculate entropy in trace

Tahmin edersek, eğer izinde entropi hesaplayabilirsek

so so long as your

properties of your line

hattınızın özellikleri

Were such that errors were relatively infrequent?

Öyle ki hatalar göreceli olarak az mıydı?

Similar videos:

What on Earth is Recursion? - Computerphile
Computerphile
565.8K views 16.8K likes 123 dislikes 16 May 201429% match

ALGOL 60 at 60 - Computerphile
Computerphile
73.7K views 3.1K likes 20 dislikes 04 Jun 202029% match

PDF, What is it FOR? - Computerphile
Computerphile
409K views 12K likes 144 dislikes 16 Sep 201628% match

Why C is so Influential - Computerphile
Computerphile
1.6M views 22.5K likes 1.6K dislikes 25 Aug 201728% match

Where HTML beats C? - Computerphile
Computerphile
551.2K views 11K likes 1.3K dislikes 27 May 201627% match

What is Bootstrapping? - Computerphile
Computerphile
375.1K views 5.5K likes 287 dislikes 19 Mar 201426% match

Fibonacci Programming - Computerphile
Computerphile
198.8K views 3.3K likes 52 dislikes 17 Jun 201425% match

Parsing Explained - Computerphile
Computerphile
134.2K views 3.6K likes 45 dislikes 13 Nov 201925% match

P vs NP on TV - Computerphile
Computerphile
527.4K views 7.8K likes 537 dislikes 08 Feb 201425% match

Where did Bytes Come From? - Computerphile
Computerphile
195.3K views 6.1K likes 60 dislikes 01 May 201825% match

Unicorn AI - Computerphile
Computerphile
339.5K views 7.8K likes 189 dislikes 04 Jul 201924% match

Reflections on Trusting Trust - Computerphile
Computerphile
66K views 3.7K likes -1 dislikes 23 Mar 202124% match

What is a Monad? - Computerphile
Computerphile
357.7K views 7.6K likes 1.2K dislikes 24 Nov 201724% match

YouTube's Secret Algorithm - Computerphile
Computerphile
318.7K views 6.3K likes 165 dislikes 24 Apr 201423% match

Compression - Computerphile
Computerphile
373.2K views 7K likes 71 dislikes 21 Jun 201323% match

Programming in PostScript - Computerphile
Computerphile
181.1K views 3.5K likes 42 dislikes 11 Apr 201423% match

Quick Sort - Computerphile
Computerphile
285.1K views 6.4K likes 94 dislikes 25 Jun 201323% match

50 Years of Computer Science: Professor Brailsford Q&A - Computerphile
Computerphile
81.3K views 3K likes 17 dislikes 22 Apr 202023% match

Reverse Polish Notation and The Stack - Computerphile
Computerphile
195.5K views 5.4K likes 24 dislikes 21 Mar 201422% match

Mac or PC? - Computerphile
Computerphile
587.9K views 9.7K likes 314 dislikes 21 May 201422% match

The Great 202 Jailbreak - Computerphile
Computerphile
460K views 7K likes 80 dislikes 12 Dec 201322% match

Computing Limit - Computerphile
Computerphile
358.4K views 11.3K likes 443 dislikes 03 Nov 201722% match

Bitcoin Problems - Computerphile
Computerphile
307.7K views 5.3K likes 599 dislikes 12 Feb 201622% match

Program Correctness - Computerphile
Computerphile
48.8K views 2K likes 253 dislikes 27 Nov 202022% match

How Password Managers Work - Computerphile
Computerphile
368.2K views 11.1K likes 107 dislikes 01 May 201922% match

The Perfect Code - Computerphile
Computerphile
491.4K views 10.6K likes 196 dislikes 08 Mar 201722% match

Programming Loops vs Recursion - Computerphile
Computerphile
1.1M views 26.6K likes 417 dislikes 22 Sep 201721% match

Pascal (Not Just Nickel & Dime) - Computerphile
Computerphile
43.6K views 2.1K likes 18 dislikes 14 Aug 202021% match

Essentials: Pointer Power! - Computerphile
Computerphile
326.4K views 8.5K likes 203 dislikes 18 Aug 201721% match

Why Use Binary? - Computerphile
Computerphile
588.4K views 10.9K likes 133 dislikes 04 Dec 201521% match

Settings Privacy About Contact Donate