რატომ არის ხარბი სტრატეგია ოპტიმალური
ჰაფმანის ალგორითმი არის ხარბი ალგორითმი: თითოეულ ეტაპზე, იგი მოიქმედებს ლოკალურად ოპტიმალური არჩევანი (დააკავშიროს ორი ყველაზე იაფი კვანძი) მომავალი მოვლენების გათვალიწინების გარეშე. ხარბი ალგორითმები ყოველთვის გლობალურად ოპტიმალური არ არის — მაგრამ აქ ისინი არის.
ოპტიმალობის არგუმენტი
დავუშვათ, კოდი C აქვს მინიმალური საშუალო სიგრძე L. განვიხილოთ ორი სიმბოლო უმცირესი ალბათობით, თქვით p_a და p_b. ნებისმიერ ოპტიმალურ კოდში, ეს ორი სიმბოლო უნდა იყოს თავმიყობილი ფოლიოები ხის ღრმეს დონეზე. რატომ?
თუ მათ მშობელი არ ჰქონდათ, თქვენ შეიძლებოდა უფრო ღრმა სიმბოლო ჩანაცვალო უფრო მოკლე კოდით — შემცირებული L. ამიტომ ღრმეს ფოლიოები უნდა იყოს უმცირესი ალბათი სიმბოლოები.
ახლა, თუ თქვენ დააკავშირებთ a და b მეტა-სიმბოლოში ab (p_ab = p_a + p_b-ით), ნებისმიერი ოპტიმალური კოდი შემცირებული ანბანის მინუს ერთი სიმბოლო ზუსტად ჰაფმანის კოდი არის შემცირებულ პრობლემაზე. ინდუქცია ასრულებს არგუმენტს.
გეომეტრიული ხედვა
ჰაფმანის ალგორითმი აშენებს ორობით ხეს ქვემოდან ზემოთ, უმცირესი ალბათი სიმბოლოებით ყველაზე მეტ სიღრმეზე. ეს მინიმალური Σ p_i · სიღრმე(i) = L.
ექვივალენტი ხედვა: თქვენ დაუკისრებთ ნიშნებს ხის ფოლიოებს დაწონილი გზის სიგრძის მინიმიზაციის მიზნით, სადაც თითოეული ფოლიო წონა არის მისი ალბათობა.
ხარბი ეტაპების შესრულება
ალბათობა: p(A)=0.4, p(B)=0.3, p(C)=0.2, p(D)=0.1. ჯამი = 1.0 ✓
ეტაპი 1: ორი ყველაზე დაბალი: C(0.2), D(0.1). დააკავშირო → CD(0.3). სია: A(0.4), B(0.3), CD(0.3).
ეტაპი 2: ორი ყველაზე დაბალი: B(0.3), CD(0.3) (თანასწორობა — ორივე ვალიდური). დააკავშირო → BCD(0.6). სია: A(0.4), BCD(0.6).
ეტაპი 3: დააკავშირო A(0.4), BCD(0.6) → ფესვი(1.0). მივაკუთვნო A=0, BCD=1.
უკან: BCD → B=10 (l=2), CD=11 → C=110 (l=3), D=111 (l=3).
L = 0.4·1 + 0.3·2 + 0.2·3 + 0.1·3 = 0.4+0.6+0.6+0.3 = 1.9 ბიტი.
კოდის სიგრძეების ვარიანსი
ორი ჰაფმანის კოდი შეიძლება აღწევდეს ერთსა და იმავე L-ს, მაგრამ განსხვავებული კოდის სიგრძის განაწილებით. კოდის სიგრძეების ვარიანსი ამ გავრცელებას ზომავს:
Var(l) = E[l²] − (E[l])²
სადაც E[l] = L (საშუალო კოდის სიგრძე) და E[l²] = Σ p_i · l_i².
რატომ აქვს მნიშვნელობა ვარიანსი:
1. ბუფერის მოთხოვნილებები. რეალურ დროში გაშიფვრისას, თითოეული სიმბოლო მოითხოვს ცვლადი რაოდენობის ბიტებს. მაღალი ვარიანსი ნიშნავს, რომ ზოგიერთი სიმბოლო მოითხოვს მრავალ ბიტს — დაგჭირდებათ უფრო დიდი შეყვანის ბუფერი, რათა გარანტირებული გქონდეთ, რომ ყოველთვის შეგიძლიათ სრული სიმბოლოს წაკითხვა.
2. გაშიფვრის ლატენტობა. მაღალი ვარიანსის კოდებს აქვთ გრძელი უარეს შემთხვევაში გაშიფვრის გზები. დაბალი ვარიანსის (სქელი) კოდები უჯრდება უარეს შემთხვევაში უფრო მკაცრად.
3. სტაბილურობა. დაკარგული ბიტი მაღალი ვარიანსის კოდში იწვევს მეტ სინქრონიზაციის ზიანს, რადგან გრძელი კოდები დაკმაყოფილებით უნდა წაიკითხოს.
ჰემინგის რეკომენდაცია: როდესაც მრავალი ვალიდური ჰაფმანის კოდი არსებობს (ჩვევის არჩევანი), უპირატესობა მიეცეთ ის კოდს დაბალი ვარიანსით — სქელი ხე.
ორი ხის ვარიანსის გამოთვლა
გამოიყენე p(A)=0.4, p(B)=0.3, p(C)=0.2, p(D)=0.1 და კოდი A=0, B=10, C=110, D=111:
E[l] = L = 1.9
E[l²] = 0.4·1² + 0.3·2² + 0.2·3² + 0.1·3² = 0.4+1.2+1.8+0.9 = 4.3
Var = 4.3 − 1.9² = 4.3 − 3.61 = 0.69
3-სიმბოლო ჰაფმანის კოდი დასაწყისიდან დასასრულამდე
სრული დასაწყისიდან დასასრულამდე მაგალითი: აგე ჰაფმანის კოდი, გამოთვალო L, გამოთვალო H, დადასტურე L ≥ H, გამოთვალო Var.
წყარო: p(X)=0.6, p(Y)=0.3, p(Z)=0.1.
ჰაფმანის აგება:
ეტაპი 1: დალაგებული: X(0.6), Y(0.3), Z(0.1). ორი ყველაზე დაბალი: Y(0.3), Z(0.1).
დააკავშირო → YZ(0.4). სია: X(0.6), YZ(0.4).
ეტაპი 2: დააკავშირო X(0.6), YZ(0.4) → ფესვი(1.0). მივაკუთვნო X=0, YZ=1.
YZ → Y=10, Z=11.
კოდი: X=0 (l=1), Y=10 (l=2), Z=11 (l=2).
L = 0.6·1 + 0.3·2 + 0.1·2 = 0.6 + 0.6 + 0.2 = 1.4 ბიტი.
ენტროპია: H = −0.6·log₂(0.6) − 0.3·log₂(0.3) − 0.1·log₂(0.1)
log₂(0.6) ≈ −0.737, log₂(0.3) ≈ −1.737, log₂(0.1) ≈ −3.322
H = 0.6·0.737 + 0.3·1.737 + 0.1·3.322 = 0.442 + 0.521 + 0.332 = 1.295 ბიტი.
L = 1.4 ≥ H = 1.295 ✓. L/H = 1.4/1.295 ≈ 1.081. ენტროპიის ზემოთ 8.1%.
ვარიანსი: E[l²] = 0.6·1 + 0.3·4 + 0.1·4 = 0.6+1.2+0.4 = 2.2. Var = 2.2 − 1.4² = 2.2 − 1.96 = 0.24.
შენი ჯერი: სრული მილი
log₂ მნიშვნელობები მითითებისთვის: log₂(0.5)=−1.000, log₂(0.25)=−2.000, log₂(0.125)=−3.000, log₂(0.375)≈−1.415, log₂(0.625)≈−0.678.