ჰაფმენის კოდი: განსხვავება გადახედვებს შორის

{{ვიკი}}

ჰაფმანის კოდირების ალგორითმი არის ინფორმაციის შეკუმშვის ერთერთი ყველაზე მარტივი და ძირითადი ალგორითმი. როდესაც წინასწარ მოცემული გვაქვს სიმბოლოების ყველა შესაძო ვარიანტი და მათი ალბათობები, მაშინ ჰაფმანის კოდი არის ყველაზე ოპტიმალური შეკუმშვის მეთოდი.

თუმცა რეალური ფაილების შეკუმშვისას წინასწარ არ ვიცით სიმბოლოების ალბათობების განაწილება და ამიტომ ჰაფმანის კოდის აგება წინასწარ არ ხერხდება. შესაბამისად, საჭიროა სხვა კოდირების მეთოდები, რომლებიც ორივე მონაწილეს (შემკუმშავს და გამხსნელს) წინასწარ ეცოდინება (პროგრამაში იქნება ჩადებული).

ასეთი კოდების უმეტესოპბაც ჰაფმანის კოდზეა დაფუძნებული. მაგალითად არსებობს შეკუმშვის მეთოდი, რომელიც ჯერ სიმბოლოების განაწილებას იკვლევს, შემდეგ შესაბამის ჰაფმანის კოდს აგებს და ამ ჰაფმანის კოდს, ამ კოდით შეკუმშულ ინფორმაციასთან ერთად გზავნის (დებს შეკუმშულ ფაილში). ეს ალგორითმი ეფექტურია ზოგ შემთხვევაში, მაგრამ არა ისე, როგორც წინასწარ აგებული ჰაფმანის კოდი, რადგან თვითონ კოდის შენახვის ადგილი იკარგება.

სხვა კოდირების მეთოდები, რომლებიც მეტნაკლებად კავშირშა ჰაფმანის კოდთან არის:

 

დავუშვათ გვაქვს ურთიერთობის არხი (მაგალითად სატელეფონო, საინტერნეტი ... ა.შ.) და ამ არხზე გვსურს გადავცეთ ინფორმაცია. ინფორმაციის გადაცემა ნიშნავს ბევრი სხვადასხვა ვარიანტიდან ერთერთის არჩევას და მის მიწოდებას არხის მეორე მხარეს. მაგ: ვირჩევთ ერთერთს შემდეგიდან:

ამ ინფორმაციას ვაგზავნით დღე. ინფორმაციას გადავცემთ ორობით კოდში (ანუ 0 და 1 ებით)

თუ მეტი ინფორმაცია არ გვაქვს, ყველაზე მარტივი იქნებოდა შეგვექმნა კოდი, რომელშიც თითო გზავნილს ორი სიმბოლოთი გადავცემთ. დავუშვათ:

ასე ჩვენ ყოველ დღე 2 ბიტს (ანუ ორობით სიმბოლოს) გადავცემთ.

მაგრამ ახლა წარმოვიდგინოთ, რომ ამ ინფორმაციას გადმოვცემთ ავსტრალიიდან, სადაც 95% შემთხვევაში მზიანი ამინდია, 4% შემთხვევაში მოღრუბლული, 0.9% შემთხვევაში წვიმს და მხოლოდ 0.1% შემთხვევაში თოვს. (პირობითად). მაშინ ჩვენ საშალება გვაქვს, რომ მზიანი ამინდი ერთ სიმბოლოიანი კომბინაციით ავღნიშნოთ, ხოლო დანარჩენები დავაგრძელოთ, და ამის ხარჯზე უფრო ხშირად 1 სიმბოლო გავგზავნოთ, ვიდრე მეტი.

მაგალითადი:

მართალია ზოგი სიტყვა დაგრძელდა, მაგრამ მხოლოდ 1% შემთხვევაში ვკარგავთ ჩვენ ზედმეტ სიმბოლოს, ზოლო 95% შემთხვევაში ვიგებთ.