როგორ აკეთებს ჰაფმენი ოპტიმალურ კოდს
ჰამინგი წარმოადგენს ჰაფმენის კოდირებას როგორც ხარბი ალგორითმი, რომელიც აკეთებს მინიმალური საშუალო სიგრძის პრეფიქსის გარეშე კოდს. ძირითადი იდეა: აკეთე ხე ქვემოდან ზემოთ, ყოველთვის შერწყმე ორი ყველაზე ნაკლებად ალბათური სიმბოლო.
წინა გადასვლა (აგება)
1. დაალაგე ყველა სიმბოლო ალბათობით, ყველაზე მაღლიდან ყველაზე დაბლამდე.
2. აიღე ორი ყველაზე დაბალი ალბათობის სიმბოლო. აერთიანე ისინი ახალი მეტა-სიმბოლოში, რომლის ალბათობა = ორის ჯამი.
3. დამატე მეტა-სიმბოლო მის დალაგებულ პოზიციაში.
4. გაიმეორე სანამ მხოლოდ ორი სიმბოლო დარჩება.
5. მიეკუთვნე 0 და 1 დარჩენილ ორ სიმბოლოს.
უკან გადასვლა (კოდების მიკუთვნება)
გააუქმე შერწყმები საპირისპირი თანმიმდევრობით: თითოეული დაყოფის დროს, ორი სიმბოლო, რომელიც შეწყვილდა, მიიღებს იგივე პრეფიქსის ბიტებს, როგორც მათი გაერთიანებული მშობელი, პლუს დამატებითი 0 (ერთი შვილი) ან 1 (მეორე შვილი). 0/1 მიკუთვნება თვითნებურია — ორივე ვალიდურია.
რატომ არის ეს ოპტიმალური: თუ სხვა კოდს ჰქონდა უფრო მცირე საშუალო სიგრძე L', იგივე წინა შემცირება გამოიწვევდა საბოლოოდ ორი სიმბოლო უფრო მცირე საშუალო სიგრძით, ვიდრე 1 ბიტი — შეუძლებელი 2-სიმბოლოს კოდისთვის. წინააღმდეგობა.
ალგორითმის თვალყოლი
მაგალითი ჰამინგიდან: ოთხი სიმბოლო A, B, C, D p(A)=0.5, p(B)=0.25, p(C)=0.125, p(D)=0.125 ალბათობით.
წინა გადასვლა:
ნაბიჯი 1: დალაგებული: A(0.5), B(0.25), C(0.125), D(0.125). ყველაზე დაბალი ორი: C, D.
ნაბიჯი 2: შერწყმე CD ალბათობა 0.25. ახალი სია: A(0.5), B(0.25), CD(0.25).
ნაბიჯი 3: ყველაზე დაბალი ორი: B(0.25), CD(0.25). შერწყმე BCD ალბათობა 0.5.
ნაბიჯი 4: დარჩა ორი სიმბოლო: A(0.5), BCD(0.5). მიეკუთვნე A=0, BCD=1.
უკან გადასვლა:
BCD → B მიიღებს 10, CD მიიღებს 11. CD → C მიიღებს 110, D მიიღებს 111.
საბოლოო კოდი: A=0 (l=1), B=10 (l=2), C=110 (l=3), D=111 (l=3).
L = 0.5·1 + 0.25·2 + 0.125·3 + 0.125·3 = 1.75 ბიტი.
ჰაფმენის კოდის მრავალი ვალიდური ვერსია
ჰამინგი აღნიშნავს არაერთგულობის ორ წყაროს:
1. თვითნებური 0/1 მიკუთვნება. თითოეულ დაყოფაზე, შეგიძლია 0-ს მიეკუთვნო ორივე შვილიდან ნებისმიერს. 0 და 1 შეცვლა მთელი პროცესში იძლევა სხვადსხვა კოდს იდენტური L-ით.
2. თანასწორობის დაშლა. როდესაც ორი კვანძს აქვს თანაბარი ალბათობა, ორივე შეიძლება განთავსდეს 'უფრო მაღლა' (პირველი შერწყმა). სხვადსხვა თანასწორობის დაშლის არჩევანი შეიძლება წარმოქმნას სტრუქტურულად სხვადსხვა ხეები — 'გრძელი' vs 'მკრთალი' — იგივე L-ით მაგრამ სხვადსხვა კოდის სიგრძის განაწილებით.
გრძელი vs მკრთალი
გრძელი ხე (დახრილი): ერთი სიმბოლო თითოეულ სიღრმის დონეზე (ფიბონაჩის სტილის სტრუქტურა). კოდის სიგრძე ძალიან განსხვავდება: ერთი სიმბოლო მიიღებს მოკლე კოდს, სხვები კასკადირებული გრძელი კოდებამდე.
მკრთალი ხე (დაბალანსებული): სიმბოლოები თანაბრად გადანაწილებულია სიღრმის დონეებზე. კოდის სიგრძე კლასტერდება საშუალო სიგრძის ირგვლივ. დაბალი ვარიაცია.
ჰამინგის რეკომენდაცია: არჩევანის მიმცემ შემთხვევაში, ხელი მკრთალ ხეს. იგივე L, მაგრამ უფრო მცირე ვარიაცია კოდის სიგრძეებში → უფრო ერთგვაროვანი დეკოდირების დრო → უფრო მცირე ბუფერის მოთხოვნა რეალურ დროში მომუშავე აპლიკაციებში.
კოდის სიგრძის ვარიაციის გამოთვლა
კოდის სიგრძის ვარიაცია: Var = E[l²] − (E[l])²
{A=0 l=1, B=10 l=2, C=110 l=3, D=111 l=3} კოდისთვის p=[0.5, 0.25, 0.125, 0.125] ალბათობით:
E[l] = L = 1.75
E[l²] = 0.5·1² + 0.25·2² + 0.125·3² + 0.125·3² = 0.5 + 1.0 + 1.125 + 1.125 = 3.75
Var = 3.75 − 1.75² = 3.75 − 3.0625 = 0.6875
ალტერნატიული მკრთალი კოდი თანაბარი ალბათობის სიმბოლოებისთვის იყენებს ყველა სიგრძის 2 კოდებს: L=2, Var=0.
კომპრესიის მოგება სიმბოლოს განაწილების წინააღმდეგ
ჰამინგის წესი: ჰაფმენის კოდირება მოგებული მხოლოდ იმ შემთხვევაში, თუ სიმბოლოს ალბათობები მნიშვნელოვნად განსხვავდება.
თანაბარი ალბათობები. თუ ყველა 2^k სიმბოლოს აქვს თანაბარი ალბათობა 1/2^k, ჰაფმენი აკეთებს ბლოკ კოდს: თითოეულ სიმბოლოს აქვს სიგრძე k. L = H = k. რეალური მოგება ცხადი ბლოკ კოდთან შედარებით.
დახრილი ალბათობები. თუ ერთი სიმბოლო დომინირებს (p >> 1/2^k სხვებისთვის), ჰაფმენი მიენიჭებს მას ძალიან მოკლე კოდს (სიგრძე 1 ან 2), მკრთალად მცირდება L.
მძიმის კოდი (ჰამინგის ტერმინი). როდესაც თითოეული ალბათობა აღემატება დარჩენილის 2/3-ს, ჰაფმენი ბუნებრივად აკეთებს: p(s1)→0, p(s2)→10, p(s3)→110, ..., დაკლებული ორი თანაბარი სიგრძის კოდამდე. ეს არის 'მძიმის კოდი': ბოლოს ნული 1-ების დაშორების შემდეგ მას მძიმის როლი აკეთებს.
ჰამინგი აღნიშნავს: რეალური ადგილებზე მონაცემების კომპრესია (სარეზერვო, ფაილის არქივი) შეიძლება შეამციროს დიდიმე ნახევარზე მეტით, როდესაც წყარომ აქვს დახრილი ალბათობები — ინგლისური ტექსტი ერთეულ პირველი მაგალითი.
ჰაფმენი vs ბლოკ კოდი: რიცხვითი შედარება
ჰამინგის მეორე მაგალითი: p(s1)=1/3, p(s2)=1/5, p(s3)=1/6, p(s4)=1/10, p(s5)=1/12, p(s6)=1/20, p(s7)=1/30, p(s8)=1/30.
ბლოკ კოდი: 8 სიმბოლო → 3 ბიტი თითოეული → L_block = 3.
ჰამინგი ითვლის ჰაფმენის კოდს და გამოაცხადებს L_Huffman ≈ 2.58 ბიტი.
დაზოგვა: (3 − 2.58)/3 ≈ 14% კომპრესია ბლოკ კოდირებაზე.
როდესაც სიმბოლოს ალბათობები მნიშვნელოვნად განსხვავდება (1/3 vs 1/30 აქ, 10:1 თანაფარდობა), ცვლადი სიგრძის კოდირება ანგარიშვერი მოგებული.
თვითკომპილირებული პროგრამები
ჰამინგი დამთავრებს თავი 11-ს აუცრელი იდეით: ჰაფმენის კოდერი შეუძლია თავი შეკოდოს. დეკოდირების ხე (რომელიც ეტყობა დეკოდერს როგორ წაიკითხოს კომპრესიული მესიჯი) გადაიცემა კომპრესიული მონაცემების ერთად. მიმღები არ სჭირდება ცოდის წინა ცოდნა.
კოდერი: ნიმუშები მონაცემები, აფასებს ალბათობებს, აკეთებს ჰაფმენის კოდს, კოდირებს დეკოდირების ხეს როგორც სათაური, შემდეგ კოდირებს მონაცემები.
დეკოდერი: კითხულობს სათაურს ხის რეკონსტრუქციისთვის, შემდეგ დეკოდირებს მონაცემები მისი გამოყენებით.
ჰამინგის წერტილი: მთელი პროცესი შეიძლება გაეშვა როგორც ბიბლიოთეკის ფუნქცია ადამიანის ჩარევის გარეშე. თქვენ ეძახით მას, იგი კომპრესირდება და დეკომპრესირდება ავტომატურად. თანამედროვე არქივირების ფორმატი (ZIP, gzip, bzip2) აკეთებს ზუსტად ამ სქემს.
ღრმა პრინციპი: ინტელექტი ალგორითმში, არა ფიქსირებულ კოდის ცხრილში. ალგორითმი ადაპტირდება, რა მონაცემიც მიიღებს. ეს პატერნი ჰამინგი ხედავს ყველა დიდ საინჟინრო სისტემაში: ადაპტირებადობა ჩაშენებული, არა ბოლოს დაკრეფილი.