ჰაფმანის ალგორითმი გამოიყენება მონაცემების შეკუმშვის ან კოდირებისათვის. ჩვეულებრივ, ტექსტის ფაილის თითოეული სიმბოლო ინახება რვა ბიტად (ციფრი, 0 ან 1), რომელიც ემთხვევა ამ სიმბოლოს კოდირების გამოყენებით, რომელსაც ეწოდება ASCII. ჰაფმანის მიერ დაშიფრული ფაილი ანგრევს ხისტ 8 ბიტიან სტრუქტურას ისე, რომ ყველაზე ხშირად გამოყენებული სიმბოლოები ინახება მხოლოდ რამდენიმე ბიტად ('a' შეიძლება იყოს "10" ან "1000" ვიდრე ASCII, რაც არის "01100001"). ყველაზე ნაკლებად გავრცელებული სიმბოლოები ხშირად დაიკავებენ 8 ბიტზე მეტს ('z' შეიძლება იყოს "00100011010"), მაგრამ რადგან ისინი იშვიათად გვხვდება, მთლიანობაში ჰაფმანის კოდირება ქმნის ბევრად უფრო პატარა ფაილს ვიდრე ორიგინალი.
ნაბიჯები
2 ნაწილი 1: კოდირება
ნაბიჯი 1. დაითვალეთ დაშიფრული ფაილის თითოეული სიმბოლოს სიხშირე
შეიყვანეთ დამამცირებელი ხასიათი ფაილის დასასრულებლად - ეს იქნება მნიშვნელოვანი მოგვიანებით. ჯერჯერობით დაარქვით მას EOF (ფაილის დასასრული) და მონიშნეთ, როგორც 1 სიხშირით.
მაგალითად, თუ გსურთ ტექსტური ფაილის დაშიფვრა "ab ab cab", გექნებათ 'a' სიხშირით 3, 'b' სიხშირით 3, '' (სივრცე) სიხშირით 2, 'c' სიხშირით 1 და EOF სიხშირით 1
ნაბიჯი 2. შეინახეთ სიმბოლოები ხის კვანძებად და განათავსეთ ისინი პრიორიტეტულ რიგში
თქვენ ააშენებთ დიდ ბინარულ ხეს თითოეული პერსონაჟით, როგორც ფოთოლი, ასე რომ თქვენ უნდა შეინახოთ პერსონაჟები ისეთ ფორმატში, რომ ისინი გახდნენ ხის კვანძები. განათავსეთ ეს კვანძები პრიორიტეტულ რიგში თითოეული სიმბოლოს სიხშირით, როგორც მისი კვანძის პრიორიტეტი.
- ორობითი ხე არის მონაცემთა ფორმატი, სადაც თითოეული მონაცემი არის კვანძი, რომელსაც შეიძლება ჰყავდეს ერთი მშობელი და ორი შვილი. ის ხშირად დახაზულია როგორც განშტოებული ხე, აქედან მოდის სახელი.
- რიგი არის სათანადოდ დასახელებული მონაცემთა შეგროვება, სადაც პირველი, რაც რიგში დგას, ასევე პირველია, რაც გამოდის (როგორც რიგში დგომა). პრიორიტეტულ რიგში, მონაცემები ინახება მათი პრიორიტეტის მიხედვით, ისე, რომ პირველი რაც გამოჩნდება არის ყველაზე გადაუდებელი რამ, ყველაზე მცირე პრიორიტეტის მქონე ნივთი, ვიდრე პირველი, რაც შემოტანილია.
- "Ab ab cab" - ის მაგალითში თქვენი პრიორიტეტული რიგი ასე გამოიყურება: {'c': 1, EOF: 1, '': 2, 'a': 3, 'b': 3}
ნაბიჯი 3. დაიწყეთ თქვენი ხის აშენება
ამოიღეთ (ან გააცილეთ) ორი ყველაზე გადაუდებელი რამ პრიორიტეტული რიგიდან. შექმენით ახალი ხის კვანძი, რომ იყოთ ამ ორი კვანძის მშობელი, შეინახეთ პირველი კვანძი, როგორც მისი მარცხენა შვილი, ხოლო მეორე, როგორც მისი მარჯვენა შვილი. ახალი კვანძის პრიორიტეტი უნდა იყოს მისი შვილის პრიორიტეტების ჯამი. შემდეგ ჩართეთ ეს ახალი კვანძი პრიორიტეტულ რიგში.
პრიორიტეტული რიგი ახლა ასე გამოიყურება: {'': 2, ახალი კვანძი: 2, 'a': 3, 'b': 3}
ნაბიჯი 4. დაასრულეთ თქვენი ხის მშენებლობა:
გაიმეორეთ ზემოაღნიშნული ნაბიჯი, სანამ რიგში არ იქნება მხოლოდ ერთი კვანძი. გაითვალისწინეთ, რომ კვანძების გარდა, რომლებიც თქვენ შექმენით პერსონაჟებისთვის და მათი სიხშირეებისათვის, თქვენ ასევე მოგიწევთ გადახრა, ხეებად გადაქცევა და ხელახლა გააქტიურება მშობლის კვანძებად, კვანძებად, რომლებიც უკვე თავად არიან ხეები.
- როდესაც დაასრულებთ, რიგის ბოლო კვანძი იქნება კოდირების ხის ფესვი, ყველა დანარჩენი კვანძი განშტოებულია მისგან.
- ყველაზე ხშირად გამოყენებული სიმბოლოები იქნება ფოთლები, რომლებიც ყველაზე ახლოს არის ხის ზედა ნაწილთან, ხოლო იშვიათად გამოყენებული სიმბოლოები განთავსდება ხის ბოლოში, ფესვიდან უფრო შორს.
ნაბიჯი 5. შექმენით კოდირების რუკა. გაიარეთ ხე, რათა მიაღწიოთ თითოეულ პერსონაჟს. ყოველ ჯერზე, როდესაც ეწვევით კვანძის მარცხენა ბავშვს, ეს არის '0'. ყოველ ჯერზე, როდესაც თქვენ ეწვევით კვანძის სწორ შვილს, ეს არის '1'. როდესაც მიხვალთ პერსონაჟზე, შეინახეთ პერსონაჟი 0 და 1 -ების თანმიმდევრობით, რაც საჭირო იყო იქ მისასვლელად. ეს თანმიმდევრობა არის ის, რაც სიმბოლო იქნება დაშიფრული, როგორც შეკუმშულ ფაილში. შეინახეთ პერსონაჟები და მათი თანმიმდევრობა რუკაზე.
- მაგალითად, დაიწყეთ ფესვიდან. ეწვიეთ ფესვის მარცხენა შვილს და შემდეგ ეწვიეთ ამ კვანძის მარცხენა შვილს. მას შემდეგ, რაც კვანძს, სადაც ახლა ხართ, არ ჰყავს შვილები, თქვენ მიაღწიეთ პერსონაჟს. Ეს არის ' '. რამდენადაც თქვენ ორჯერ მიდიხართ მარცხნივ აქ მოსასვლელად, '' -ს კოდირება არის "00".
- ამ ხისათვის, რუკა ასე გამოიყურება: {'': "00", 'a': "10", 'b': "11", 'c': "010", EOF: "011"}.
ნაბიჯი 6. გამომავალ ფაილში შეიყვანეთ კოდირების რუკა სათაურის სახით
ეს საშუალებას მისცემს ფაილის დეკოდირებას.
ნაბიჯი 7. დაშიფრეთ ფაილი
ფაილის თითოეული კოდირებისთვის, ჩაწერეთ ორობითი თანმიმდევრობა, რომელიც თქვენ შეინახეთ რუკაზე. მას შემდეგ რაც დაასრულებთ ფაილის კოდირებას, დარწმუნდით, რომ დაამატეთ EOF ბოლომდე.
- ფაილისთვის "ab ab cab", დაშიფრული ფაილი ასე გამოიყურება: "1011001011000101011011".
- ფაილები ინახება როგორც ბაიტი (8 ბიტი, ან 8 ორობითი ციფრი). იმის გამო, რომ ჰაფმანის კოდირების ალგორითმი არ იყენებს 8 ბიტიან ფორმატს, დაშიფრულ ფაილებს ხშირად არ ექნებათ სიგრძე 8-ის ჯერადი. დანარჩენი ციფრები შეივსება 0-ით. ამ შემთხვევაში, ფაილის ბოლოს დაემატება ორი 0, რაც სხვა სივრცეს ჰგავს. ეს შეიძლება იყოს პრობლემა: როგორ იცოდა დეკოდირებელმა როდის შეწყვიტოს კითხვა? თუმცა, იმის გამო, რომ ჩვენ შევიტანეთ ფაილის ბოლოს ხასიათი, დეკოდირება მიიღებს ამას და შემდეგ შეწყვეტს, იგნორირებას უკეთებს ყველაფერს, რაც დამატებულია შემდეგ.
მე -2 ნაწილი 2: დეკოდირება
ნაბიჯი 1. წაიკითხეთ ჰაფმანის კოდირებული ფაილი
პირველი, წაიკითხეთ სათაური, რომელიც უნდა იყოს კოდირების რუკა. გამოიყენეთ ეს დეკოდირების ხის ასაშენებლად ისევე, როგორც თქვენ ააშენეთ ხე, რომელსაც იყენებდით ფაილის დასაშიფრებლად. ორი ხე იდენტური უნდა იყოს.
ნაბიჯი 2. წაიკითხეთ ორობითი ერთნიშნა ერთდროულად
წაიკითხეთ ხე, როდესაც კითხულობთ: თუ კითხულობთ '0' - ში, გადადით კვანძის მარცხენა შვილზე, სადაც ხართ და თუ '1' - ში, წადით მარჯვნივ. როდესაც თქვენ მიაღწევთ ფოთოლს (კვანძს შვილების გარეშე), თქვენ მიხვედით პერსონაჟზე. ჩაწერეთ პერსონაჟი გაშიფრული ფაილში.
იმის გამო, თუ როგორ ინახება სიმბოლოები ხეში, თითოეული პერსონაჟის კოდებს აქვთ პრეფიქსის თვისება, ისე რომ არცერთი პერსონაჟის ორობითი კოდირება ვერ მოხდება სხვა პერსონაჟის კოდირების დასაწყისში. თითოეული პერსონაჟის კოდირება უნიკალურია. ეს გაცილებით აადვილებს გაშიფვრას
ნაბიჯი 3. გაიმეორეთ სანამ არ მიაღწევთ EOF- ს
გილოცავთ! თქვენ გაშიფრეთ ფაილი.
