კოდი როგორც ხე
prefix-free კოდი ასახავს ორობითი ხეს: ფესვი წარმოადგენს დეკოდირების დასაწყისს, მარცხენა ტოტები წარმოადგენენ ბიტს 0, მარჯვენა ტოტები წარმოადგენენ ბიტს 1, ხოლო ფოლიოები წარმოადგენენ სრულ კოდსიტყვებს.
გეომეტრიული შეზღუდვა: ყველა ფოლიო აღასრულებს ფესვიდან ფოლიოსთან სტეზას. ფოლიოს არ შეიძლება ჰქონდეს შთამომავალი (თუ ეს ყოფილიყო, მისი კოდსიტყვა იქნებოდა შთამომავლის კოდსიტყვის prefix, რაც prefix-free თვისებას დაარღვევდა).
ეს ეძლევა Kraft უტოლობას გეომეტრიული ინტერპრეტაცია:
თითოეული ფოლიო სიღრმეზე d 'იკავებს' ხის მთელი სიმძლავრის 2^(−d) წილს. სრული ორობითი ხის მთელი სიმძლავრე სიღრმეზე D არის 1. prefix-free კოდი იყენებს ფოლიოებს სხვადსხვა სიღრმეზე; Kraft ჯამი ზომავს მთელ დასაკავებელ ადგილას.
Kraft ჯამი = 1: სრული კოდი (ყველა ბილიკი მთავრდება ფოლიოზე — სრულ შეტევაში).
Kraft ჯამი < 1: არასრული კოდი (ხის ზოგიერთი სიმძლავრე არ გამოიყენება — შეიძლება დაემატოს მეტი სიმბოლო).
Kraft ჯამი > 1: შეუძლებელი prefix-free კოდებისთვის (ზოგიერთი ბილიკი მოუწევდა იგიაროს ფოლიო).
უფრო ღრმა ფოლიოები = გრძელი კოდები = ნაკლები სიმძლავრე
ფოლიო სიღრმეზე 1 იყენებს ხის სიმძლავრის ნახევრს (2^(−1) = 0.5).
ფოლიო სიღრმეზე 3 იყენებს მერვედს (2^(−3) = 0.125).
მოკლე კოდსიტყვის განთავსება ხის ზედა ნაწილში აბლოკირებს მის ყველა შთამომავალს გამოყენებისგან — თქვენ იცვლით ერთ მოკლე კოდს მრავალი პოტენციური გრძელი კოდის ნაცვლად.
Prefix-Free ხის აგება
განვიხილოთ 5 სიმბოლო სიგრძეებით l = {1, 2, 3, 3, 3}. Kraft ჯამი = 2^(−1) + 2^(−2) + 3·2^(−3) = 0.5 + 0.25 + 0.375 = 1.125 > 1.
ეს აჭარბებს 1-ს: ეს სიგრძეები შეუთავსებელი არის prefix-free კოდის თან. ერთი სიგრძე მაინც უნდა გაიზარდოს.
გამოსწორება: ცვილებული l_1 1-დან 2-მდე. ახალი სიგრძეები {2, 2, 3, 3, 3}: Kraft = 2·2^(−2) + 3·2^(−3) = 0.5 + 0.375 = 0.875 < 1. ვალიდი, მაგრამ არასრული.
გამოსწორება: ცვილებული l_1 2-დან 2-მდე, დაამატე l_2 = 3 დარჩენილი სიმძლავრის გამოსაყენებლად. Kraft = 0.875; დარჩენილი = 0.125 = 2^(−3): ადგილი ერთი უფრო depth-3 ფოლიოსთვის.
რატომ ენტროპია სამღებელი კოდის სიგრძე
Kraft უტოლობა შემზღუდავს კოდის სტრუქტურას (სიგრძეები უნდა ჯდეს ხეში). Shannon ენტროპია შემზღუდავს კოდის ეფექტურობას (საშუალო სიგრძე ვერ ამარცხებს თეორიულ ზღვარს).
ოპტიმალური კოდის სიგრძეები. სიმბოლოსთვის ალბათობით p_i, იდეალური კოდის სიგრძე არის log₂(1/p_i). იშვიათი სიმბოლოები სამეფო გრძელი კოდები; ხშირი სიმბოლოები სამეფო მოკლე კოდები. ეს ასახავს Kraft ტოლობას: 2^(−l_i) = p_i როდესაც l_i = log₂(1/p_i).
მაგრამ log₂(1/p_i) იშვიათად არის მთელი რიცხვი. დამრგვალება ზედა მხარეს ⌈log₂(1/p_i)⌉-მდე იძლევა Huffman სიგრძე, რომელიც აკმაყოფილებს H ≤ L < H + 1.
გეომეტრიული კითხვა. გამოსახეთ თითოეული სიმბოლო წერტილი ორობითი ხეზე სიღრმეზე l_i. Kraft ჯამი ზომავს მთელ ფოლიოს დაკრავას. ენტროპია ზომავს სიმძიმე საშუალო სიღრმე, სიმძიმე ალბათობის მიხედვით. Shannon თეორემა: ალბათობის-სიმძიმე საშუალო სიღრმე ≥ ალბათობის-სიმძიმე ინფორმაციის შინაარსი.
ენტროპია ზღვრის დადასტურება
მუშავებული მაგალითი: p = [1/2, 1/4, 1/8, 1/8] სიმბოლოებისთვის {A, B, C, D}.
ოპტიმალური სიგრძეები: l_A = log₂(2) = 1, l_B = log₂(4) = 2, l_C = log₂(8) = 3, l_D = log₂(8) = 3.
ეს ყველა მთელი რიცხვი არის — სრულ მატჩი. Huffman კოდი: A=0, B=10, C=110, D=111.
L = 0.5·1 + 0.25·2 + 0.125·3 + 0.125·3 = 0.5 + 0.5 + 0.375 + 0.375 = 1.75.
H = 0.5·1 + 0.25·2 + 0.125·3 + 0.125·3 = 1.75. L = H ზუსტად: ოპტიმალური კოდი.
სრული მუშავებული მაგალითი
სრული კონვეიერი: მოცემული ალბათობა, გამოთვალეთ ენტროპია, დადასტურეთ კოდი აკმაყოფილებს ზღვარს.
წყარო: p(A)=0.5, p(B)=0.25, p(C)=0.125, p(D)=0.125.
H = 1.75 bits (გამოთვლილი ზემოთ).
საბუი block კოდი: 4 სიმბოლო → 2 bits თითოეული → L = 2.0. ზასაფერი ენტროპიაზე: 2.0 − 1.75 = 0.25 bits/symbol = 12.5% ნარჩენი.
ცვლადი-სიგრძის კოდი ზოგს 12.5% შედარებაში fixed-სიგრძის. დიდი წერილებისთვის, ეს მნიშვნელოვანია.
ენტროპია ტემპი ინგლისური ენა. Shannon აკეთებ ენტროპია წერილი ინგლისური დაახლოებით 1.0 დან 1.3 bits თითოეული სიმბოლო, მიუხედავად გამოყენებითი 5-bit ASCII კოდი. ეს 4:1 თანაფარდობა ასახავს დიდი ზედმეტობა ბუნებრივ ენაზე — ხშირი წერილი cluster, სიტყვები გაიმეორა, გრამატიკული პირობები ზედა.
შემჭიდროება ვერ ამარცხებს ენტროპია
შემჭიდროება თანაფარდობა: H / (block კოდი სიგრძე). ჩვენი მაგალითი: 1.75/2.0 = 0.875 — 87.5% ეფექტურობა.
შეგიძლიათ შემჭიდროება ვე? მხოლოდ კონტექსტის გამოყენებით: თუ თქვენ კოდირება წყვილი ან სამეულ სიმბოლო ერთად, ერთობლივი ენტროპია H(X,Y) შეიძლება იყოს ნაკლები ვიდრე 2·H(X) გამო სტატისტიკური დამოკიდებულება. ეს არის მოთხოვნილება noiseless კოდირება თეორემა n-grams.