|
'''ჰაფმანისჰაფმენის კოდირების ალგორითმი''' — [[ინფორმატიკა]]სა და [[ინფორმაციის თეორია]]ში [[უდანაკარგო ინფორმაციის შეკუმშვა|ინფორმაციის უდანაკარგოდ შეკუმშვის]] ერთ-ერთი ყველაზე მარტივი და ძირითადი [[ალგორითმი]]. როდესაც წინასწარ მოცემული გვაქვს სიმბოლოების ყველა შესაძო ვარიანტი და მათი ალბათობები, მაშინ ჰაფმანისჰაფმენის კოდი არის ყველაზე ოპტიმალური შეკუმშვის მეთოდი.
თუმცა რეალური ფაილების შეკუმშვისას წინასწარ არ ვიცით სიმბოლოების ალბათობების განაწილება და ამიტომ ჰაფმანისჰაფმენის კოდის აგება წინასწარ არ ხერხდება. შესაბამისად, საჭიროა სხვა კოდირების მეთოდები, რომლებიც ორივე მონაწილეს (შემკუმშავს და გამხსნელს) წინასწარ ეცოდინება (პროგრამაში იქნება ჩადებული).
ასეთი კოდების უმეტესოპბაც ჰაფმანისჰაფმენის კოდზეა დაფუძნებული. მაგალითად არსებობს შეკუმშვის მეთოდი, რომელიც ჯერ სიმბოლოების განაწილებას იკვლევს, შემდეგ შესაბამის ჰაფმანისჰაფმენის კოდს აგებს და ამ ჰაფმანისჰაფმენის კოდს, ამ კოდით შეკუმშულ ინფორმაციასთან ერთად გზავნის (დებს შეკუმშულ ფაილში). ეს ალგორითმი ეფექტურია ზოგ შემთხვევაში, მაგრამ არა ისე, როგორც წინასწარ აგებული ჰაფმანისჰაფმენის კოდი, რადგან თვითონ კოდის შენახვის ადგილი იკარგება.
სხვა კოდირების მეთოდები, რომლებიც მეტნაკლებად კავშირშა ჰაფმანისჰაფმენის კოდთან არის:
* არითმეტიკული კოდირების ალგორითმი
* ლემპელ–ზივ –ის კოდირების ალგორითმი (რომელიც გამოიყენება თანამედროვე zip შეკუმშვის პროგრამაში)
* აქ თოვს – 111
მართალია ზოგი სიტყვა დაგრძელდა, მაგრამ ამ სიტყვებ მხოლოდ 1% შემთხვევაში ვიყენებთ, ანუ 1% შემთხვევაში ვკარგავთ ზედმეტ ბიტს. სამაგიეროდ 95% შემთხვევაში ჩვენი გადასაცემი ინფორმაციი შესაბამისი კოდი 1 ბიტით მოკლეა. ჩვენ აშკარად გავაუმჯობესეთ ჩვენი კოდი. ახლა 1000–ჯერ ინფორმაციის გადაცემისას ჩვენ მოგვიწევს საშუალოდ 950 * 1 ბიტი + 40 * 2 ბიტი + 10 * 3 ბიტი = 1060 ბიტის გადაცემა. მაშინ, როდესაც აქამდე, სტანდარტული თანაბარი 2 ბიტიანი კოდით, ჩვენ გვიწევდა 1000 * 2 ბიტი = 2000 ბიტი გადაცემა.
ამ მაგალითზე ჩვენ ვრწმუნდებით, რომ კოდური სიმბოლოები ხვადასხვანაირი გადანაწილებით ჩვენ შეგვიძლია ინფორმაცია შევკუმშოთ. საინტერესოა კერძოდ როგორი კოდური სიტყვების შერჩევით მივიღებთ ჩვენ ყველაზე ეკონომიურ კოდს. სწორად ამ ამოცანის ამოხსნა ცდილობდა ჰაფმანიჰაფმენი, როდესაც თავისი კოდირების ალგორითმი გამოიგონა. ჰაფმანისჰაფმენის კოდი არის ისეთი კოდი, რომლის გამოყენებითაც საშუალოდ ყველაზ ნაკლები ბიტის გადაცემა მოგვიწევს მოცემული წერილები გააგზავნად.
== ჰაფმანისჰაფმენის კოდის აგება ==
ჰაფმანიჰაფმენი კოდი აიგება ნებისმიერი რაოდენობის ინფორმაციაზე, თუ წინასწარ მოცემული გვაქვს თითოეული ინფორმაციი გადაცემის საჭიროების [[ალბათობა]]. განვიხილოთ კოდი აგება მაგალითზე.
დავუშვათ მოცემული გვაქვს შემდეგი ალბათობები
ა - 11
ანალოგიურად ვაგებთ ჰაფმანისჰაფმენის კოდს სიმბოლოების და ალბათობების ნებისმიერი ნაკრებისთვის. ჯერ ვალაგებთ სიმბოლოებს ზრდადობის მიხედვით, შემდეგ ვაერთიანებთ პირველ ორს და იგივეს ვიმეორებთ სანამ ერთ სიმბოლომდე არ დავალთ. შემდეგ ისევ უკან ვყოფთ ყველა სიმბოლოს, ოღონს გაყოფისას ერთ ნაწილს ავღნიშნავთ როგორც (უკვე მიღებულს+”0”) ხოლო მეორეს როგორც (უკვე მიღებულს+”1”). როდესაც ასე ისევ ინდივიდუალურ სიმბოლოებამდე ჩავალთ მიღებული გვექნება კოდი, რომელსიც არის ჰაფმანისჰაფმენის კოდი.
[[კატეგორია:ინფორმატიკა]]
| 