ინფორმაციის უდანაკარგოდ შეკუმშვა
უდანაკარგოდ ინფორმაციის შეკუმშვა გამოყენებითი მათემატიკის, კერძოდ კი ინფორმაციის თეორიის ერთ-ერთი დარგია. ის შეისწავლის ინფორმაციის შეკუმშვის ისეთ მეთოდებს, რომლების გამოყენებით შემდგომში საწყისი ინფორმაციის ზუსტი ასლის აღდგენა შეიძლება.
მაგალითად, ნებისმიერი კომპიუტერული არქივატორი (ZIP, RAR) იყენებს უდანაკარგო შეკუმშვის მეთოდებს. ზოგიერთი ინფორმაციის შეკუმშვა შესაძლებელია ასევე დანაკარგებითაც. მაგალითად JPEG ფორმატში შესაძლებელია ნახატების შეკუმშვა მათი ხარისხის გაუარესების ხარჯზე. ასეთი შეკუმშვის შედეგად ჩვენ ვეღარ აღვადგენთ საწყის ნახატს შეკუმშული ნახატიდან, რადგან ინფორმაციის ნაწილი დაკარგულია.
ინფორმაციის უდანაკარგო შეკუმშვა ძირითადად ხდება უფრო ხშირი ინფორმაციის უფრო მოკლე კოდებით, ხოლო უფრო იშვიათის უფრო გრძელი კოდებით წარმოდგენის ხარჯზე. ეს ზოგ ადგილას ზრდის ფაილს, ხოლო ზოგ ადგილას ამცირებს, მაგრამ რადგან კოდი ისეა შერჩეული, რომ უფრო ხშირი ინფორმაცია უფრო მოკლე კოდითაა წარმოდგენილი, ინფორმაცია უფრო მეტ ადგილას იკუმშება და საბოლოო ჯამში ვიღებთ უფრო პატარა ფაილს. თუმცა როდესაც ყველა კომბინაცია ერთნაირი სიხშირით გვხვდება (მაგალითად უკვე შეკუმშულ ფაილში), უდანაკარგო შეკუმშვა აღარ მოქმედებს.
ინფორმაციის უდანაკარგოდ შეკუმშვის ყველაზე მარტივი და ხშირად გამოყენებული ალგორითმი, რომელიც ასევე ყველა სხვა ალგორითმის ძირითადი პრინციპია, არის ჰაფმანის კოდირების ალგორითმი. ჰაფმანის კოდი ოპტიმალურია ყველა კოდს შორის თუ მონაცემთა გამოჩენის სიხშირეები (ალბათობები) წინასწარ გვაქვს მოცემული. თუმცა, რადგან ეს ძირითადად ასე არ არის, პრაქტიკაში უფრო რთული კოდები გამოიყენება. მაგალითად, ჰაფმანის ალგორითმზე დაფუძნებული, მაგრამ შედარებით უფრო რთული და ეფექტიანი ალგორითმებია:
- არითმეტიკული კოდირების ალგორითმი, რომელიც ჰაფმანის კოდის მოდიფიკაციაა გრძელი გზავნილებისთვის (ფაილებისთვის).
- ლემპელ-ზივ ალგორითმი, რომელიც ან რომლის მცირე მოდიფიკაციებიც (ძირითადად პატენტის მფლობელისთვის ფულის გადახდის თავიდან აცილების გამო), ძირითადად გამოიყენება თანამედროვე შემკუმშვის პროგრამებში.
შეკუმშვის ქვედა ზღვარი
რედაქტირებაკლაუდ შენონმა დაამტკიცა, რომ ინფორმაციის შეკუმშვისას თითოეული ინფორმაციის ნაწილის (შესაძლო ვარიანტის) წარმომადგენელი კოდის საშუალო სიგრძე არ შეიძლებოდა ყოფილიყო გადასაცემი ინფორმაციის ენტროპიაზე ნაკლები. მანვე გამოიგონა შენონის კოდი, რომელიც უბრალოდ თითოეულ შესაძლო ინფორმაციის ნაწილს შეუსაბამებს კოდს, რომლის სიგრძე ტოლია მთელ რიცხვამდე ზემოთ დამრგვალებული შესაბამისი ინფორმაციის რაოდენობის (ანუ ალბათობის ლოგარითმის 1/2-ის ფუძით). შენონის კოდით მიღებული კოდური სიტყვების საშუალო სიგრძე მაქსიმუმ 1 ბიტით არის მეტი ყველაზე მცირე შესაძლო სიგრძეზე, მაგრამ შენონის კოდი არ არის ოპტიმალური. ჰაფმანის კოდი ყოველთვის უფრო მეტად (ან არანაკლებად) კუმშავს ინფორმაციას, ვიდრე შენონის კოდი. თუმცა შენონის კოდს ის უპირატესობა აქვს, რომ უფრო მარტივი გამოსათვლელია.
შენონისა და ჰაფმანის კოდების დაახლოვება ოპტიმალურ სიგრძესთან შესაძლებელია ინფორმაციის გაერთიანებით. ანუ, თუ ყოველი 1 ბაიტიანი (8 ბიტი) სიმბოლოს ალბათობას ვითვლიდით და ისე ვაგებდით კოდს, შესაძლოა, იმავე ალგორითმის გამოყენებით მეტ შეკუმშვას მივაღწიოთ თუ ყველა 2 ბაიტიან სიმბოლოს განვიხილავთ. თუმცა ამას ბევრად მეტი გამოთვლითი სიმძლავრე დასჭირდება. არითმეტიკული კოდირების ალგორითმის უპირატესობა სწორად ამ გაერთიანების ეფექტურობიდან გამომდინარეობს.