ჰაფმენის კოდი
From Wikipedia, the free encyclopedia
ჰაფმენის კოდირების ალგორითმი — ინფორმატიკასა და ინფორმაციის თეორიაში ინფორმაციის უდანაკარგოდ შეკუმშვის ერთ-ერთი ყველაზე მარტივი და ძირითადი ალგორითმი. როდესაც წინასწარ მოცემული გვაქვს სიმბოლოების ყველა შესაძლო ვარიანტი და მათი ალბათობები, მაშინ ჰაფმენის კოდი არის ყველაზე ოპტიმალური შეკუმშვის მეთოდი.
სიმბ. | სიხშ. | კოდი |
---|---|---|
ჰარი ( ) | 7 | 111 |
a | 4 | 010 |
e | 4 | 000 |
f | 3 | 1101 |
h | 2 | 1010 |
i | 2 | 1000 |
m | 2 | 0111 |
n | 2 | 0010 |
s | 2 | 1011 |
t | 2 | 0110 |
l | 1 | 11001 |
o | 1 | 00110 |
p | 1 | 10011 |
r | 1 | 11000 |
u | 1 | 00111 |
x | 1 | 10010 |
თუმცა რეალური ფაილების შეკუმშვისას წინასწარ არ ვიცით სიმბოლოების ალბათობების განაწილება და ამიტომ ჰაფმენის კოდის აგება წინასწარ არ ხერხდება. შესაბამისად, საჭიროა სხვა კოდირების მეთოდები, რომლებიც ორივე მონაწილეს (შემკუმშავს და გამხსნელს) წინასწარ ეცოდინება (პროგრამაში იქნება ჩადებული). ასეთი კოდების უმეტესოპბაც ჰაფმენის კოდზეა დაფუძნებული. მაგალითად არსებობს შეკუმშვის მეთოდი, რომელიც ჯერ სიმბოლოების განაწილებას იკვლევს, შემდეგ შესაბამის ჰაფმენის კოდს აგებს და ამ ჰაფმენის კოდს, ამ კოდით შეკუმშულ ინფორმაციასთან ერთად გზავნის (დებს შეკუმშულ ფაილში). ეს ალგორითმი ეფექტურია ზოგ შემთხვევაში, მაგრამ არა ისე, როგორც წინასწარ აგებული ჰაფმენის კოდი, რადგან თვითონ კოდის შენახვის ადგილი იკარგება. სხვა კოდირების მეთოდები, რომლებიც მეტნაკლებად კავშირშა ჰაფმენის კოდთან არის:
- არითმეტიკული კოდირების ალგორითმი
- ლემპელ–ზივ-ის კოდირების ალგორითმი (რომელიც გამოიყენება თანამედროვე zip შეკუმშვის პროგრამაში)