ჰაფმენის კოდი

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

სიმბ.	სიხშ.	კოდი
ჰარი ( )	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 შეკუმშვის პროგრამაში)

ამოცანის დასმა რედაქტირება

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

აქ მზიანი ამინდია
აქ ღრუბლიანი ამინდია
აქ წვიმს
აქ თოვს

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

აქ მზიანი ამინდია – 00
აქ ღრუბლიანი ამინდია – 01
აქ წვიმს – 10
აქ თოვს – 11

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

აქ მზიანი ამინდია – 0
აქ ღრუბლიანი ამინდია – 10
აქ წვიმს – 110
აქ თოვს – 111

მართალია ზოგი სიტყვა დაგრძელდა, მაგრამ ამ სიტყვებს მხოლოდ 1% შემთხვევაში ვიყენებთ, ანუ 1% შემთხვევაში ვკარგავთ ზედმეტ ბიტს. სამაგიეროდ 95% შემთხვევაში ჩვენი გადასაცემი ინფორმაციის შესაბამისი კოდი 1 ბიტით მოკლეა. ჩვენ აშკარად გავაუმჯობესეთ ჩვენი კოდი. ახლა 1000–ჯერ ინფორმაციის გადაცემისას ჩვენ მოგვიწევს საშუალოდ 950 * 1 ბიტი + 40 * 2 ბიტი + 10 * 3 ბიტი = 1060 ბიტის გადაცემა. მაშინ, როდესაც აქამდე, სტანდარტული თანაბარი 2 ბიტიანი კოდით, ჩვენ გვიწევდა 1000 * 2 ბიტი = 2000 ბიტის გადაცემა. ამ მაგალითზე ჩვენ ვრწმუნდებით, რომ კოდური სიმბოლოები სხვადასხვანაირი გადანაწილებით ჩვენ შეგვიძლია ინფორმაცია შევკუმშოთ. საინტერესოა კერძოდ როგორი კოდური სიტყვების შერჩევით მივიღებთ ჩვენ ყველაზე ეკონომიურ კოდს. სწორად ამ ამოცანის ამოხსნა ცდილობდა ჰაფმენი, როდესაც თავისი კოდირების ალგორითმი გამოიგონა. ჰაფმენის კოდი არის ისეთი კოდი, რომლის გამოყენებითაც საშუალოდ ყველაზ ნაკლები ბიტის გადაცემა მოგვიწევს მოცემული შეტყობინებების გასაგზავნად.

ჰაფმენის კოდის აგება რედაქტირება

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

( ა – 0.3 ; ბ – 0.05 ; გ – 0.25 ; დ – 0.15 ; ე –0.25 ).

უპირველეს ყოვლისა ვალაგებთ სიმბოლოებს ალბათობის ზრდადობის მიხედვით.

( ბ – 0.05 ; დ – 0.15 ; გ – 0.25 ; ე – 0.25 ; ა – 0.30 )

თანაბარი ალბათობებიანი სიმბოლოები შეგვიძლია დავალაგოთ ნებიმიერი მიმდევრობით. ამითი კოდი შეიძლება შეიცვალოს, მაგრამ არ შეიცვლება კოდის ეფექტურობა. ანუ მივიღებთ სხვადასხვა კოდს, მაგრამ ორივე ერთნაირად შეკუმავს ჩვენს ინფორმაციას. შემდეგ პირველ ორ სიმბოლოს ვაერთიანებთ ერთ სიმბოლოდ ბდ, რომელსაც ექნება შესაბამისი ალბათობა 0.05 + 0.15 ანუ 0.20. ბ-ს ავღნიშნავთ როგორც ბდ⁰ ხოლო დ-ს როგორც ბდ¹. მიღებული ოთხსიმბოლოიან სისტემას ისევ ვალაგებთ ზრდადობის მიხედვით და ვიმეორებთ იგივეს, სანამ არ მივიღებთ სულ ერთსიმბოლოიან სისტემას, რომლიდანაც სხვადასხვა ინდექსების დამატებით ყველა 5 სიმბოლოს აღდგენაა შესაძლებელი. ჩვენს შემთხვევაში ეს მოხდება შემდეგნაირად

( ბდ - 0.20 ; გ - 0.25 ; ე - 0.25 ; ა - 0.30 ) ბ = ბდ⁰ ; დ = ბდ¹

( ე - 0.25 ; ა - 0.30 ; (ბდ)გ - 0.45 ) ბ = (ბდ)გ^0,0 ; დ = (ბდ)გ^0,1 ; გ = (ბდ)გ¹

( (ბდ)გ - 0.45 ; ეა - 0.55 ) ბ,დ,გ = იგივე ; ე = ეა⁰ ; ა = ეა¹

და საბოლოოდ: მივიღეთ: ( (((ბდ)გ)(ეა)) – 1.00 ) სადაც: ბ = (((ბდ)გ)(ეა))^0,0,0 ; დ = (((ბდ)გ)(ეა))^0,0,1 ; გ = (”-”)^0,1 ; ე = (”-”)^1,0 ; ა = (”-”)^1,1 ;

ჩვენს მიერ მიღებული ინდექსები არის ამ ალბათობებისთვის მიღებული ოპტიმალური კოდი ანუ კოდირება უნდა მოხდეს შემდეგნაირად:

ბ - 000

დ - 001

გ - 01

ე - 10

ა - 11

ანალოგიურად ვაგებთ ჰაფმენის კოდს სიმბოლოების და ალბათობების ნებისმიერი ნაკრებისთვის. ჯერ ვალაგებთ სიმბოლოებს ზრდადობის მიხედვით, შემდეგ ვაერთიანებთ პირველ ორს და იგივეს ვიმეორებთ სანამ ერთ სიმბოლომდე არ დავალთ. შემდეგ ისევ უკან ვყოფთ ყველა სიმბოლოს, ოღონს გაყოფისას ერთ ნაწილს ავღნიშნავთ როგორც (უკვე მიღებულს+”0”) ხოლო მეორეს როგორც (უკვე მიღებულს+”1”). როდესაც ასე ისევ ინდივიდუალურ სიმბოლოებამდე ჩავალთ მიღებული გვექნება კოდი, რომელსიც არის ჰაფმენის კოდი.

ლიტერატურა რედაქტირება

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 16.3, pp. 385–392.

რესურსები ინტერნეტში რედაქტირება

შეგიძლიათ იხილოთ მედიაფაილები თემაზე „ჰაფმენის კოდი“ ვიკისაწყობში.
Huffman coding in various languages on Rosetta Code