Huffman კოდები მაგალითები გამოყენების

ამ ეტაპზე, რამდენიმე ადამიანი ვფიქრობ იმაზე, როგორ ფაილი შეკუმშვის. შედარებით გამოყენების პერსონალური კომპიუტერი გახდა ბევრად უფრო ადვილია. და თითქმის ყველა ადამიანს მუშაობის ფაილი სისტემა იყენებს ფაილი. მაგრამ რამდენიმე ადამიანი, ვიფიქროთ, თუ როგორ მუშაობს და რა საფუძველზე არის ფაილი შეკუმშვის. პირველი მობილური ამ პროცესში იყო Huffman კოდები და ისინი გამოიყენება დღეს სხვადასხვა პოპულარული archivers. ბევრი წევრებს არ ვფიქრობ, რომ, თუ რამდენად ადვილი ფაილი შეკუმშვის ხდება და იგი მუშაობს სქემა. ამ სტატიაში ჩვენ განვიხილავთ, თუ როგორ შეკუმშვის არის ის, რაც ნიუანსი დახმარება სიჩქარე და გამარტივების პროცესი კოდირების, ისევე, როგორც ვხედავთ, თუ რა პრინციპით ხე კოდირება.

ისტორია ალგორითმი

პირველივე ალგორითმი ეფექტური კოდირება ელექტრონული ინფორმაციის გახდა კოდი Huffman შემოთავაზებული, როგორც ადრე, როგორც შუა მეოცე საუკუნის, კერძოდ, 1952 წელს. ეს იყო ის, ვინც იმ მომენტში ბაზის ელემენტს უმრავლესობის პროგრამების მიერ შეკუმშოს ინფორმაცია. ამ ეტაპზე, ერთ-ერთი ყველაზე პოპულარული წყაროების გამოყენებით ამ კოდექსით არქივები ZIP, ARJ, RAR და მრავალი სხვა. გარდა ამისა, Huffman ალგორითმი გამოიყენება შეკუმშოს JPEG გამოსახულებები და სხვა გრაფიკული ობიექტები. ისე, ყველა ფაქსები ასევე თანამედროვე კოდირება, გამოიგონა 1952 წელს. მიუხედავად იმისა, რომ მას შემდეგ, რაც შექმნის კოდი აიღო ამდენი დრო, რომ ამ დღეს იგი გამოიყენება სხვადასხვა ახალი გარსების და აღჭურვილობა ძველ და თანამედროვე ტიპის.

პრინციპი ეფექტური კოდირება

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

Huffman კოდი, მაგალითად

იმის საჩვენებლად, ალგორითმი, განიხილოს გრაფიკული ვარიანტი მშენებლობის კოდი ხე. ამ მეთოდის გამოყენება იქნება ეფექტური, აუცილებელია განვმარტო განმარტებას გარკვეული ღირებულებები საჭირო კონცეფცია პროცესში. კომპლექტი გავურბივარ კვანძების და რკალების, რომლებიც მიმართულია კვანძის კვანძის, მოუწოდა გრაფაში. ხე თავად არის გრაფაში კომპლექტი კონკრეტული თვისებები:

• თითოეულ კვანძის შეიძლება შეიცავდეს არა უმეტეს ერთი რკალების;
• ერთი კვანძების უნდა იყოს ხის ფესვი, რომ არის, ეს არ უნდა იყოს ნაწილი arc ყველა;
• თუ ღეროვანი დაიწყოს მოძრავი გასწვრივ რკალის, უნდა დავუშვათ, რომ მთლიანად ნებისმიერ კვანძების.

ასევე არსებობს ასეთი რამ, ნაწილი Huffman კოდები, როგორც ფოთოლი ხე. ეს არის კვანძის რომელიც არ უნდა რაიმე რკალი. თუ ორ კვანძების უკავშირდება მიერ რკალის, მათ შორის ერთი არის მშობელი სხვა ბავშვს, დამოკიდებულია, რომელიც კვანძის arc გადის და რა შედის. თუ ორ კვანძების აქვს იგივე მშობელი კვანძი, ისინი მოუწოდა დის საიტები. იმ შემთხვევაში, თუ ფოთლები, ფოთლები კვანძების რამდენიმე რკალების, მაშინ მას უწოდებენ ორობითი ხე. უბრალოდ, ასე რომ არის Huffman ხე. თავისებურება მშენებლობისთვის ერთეული არის, რომ წონის თითოეულ მშობელს უდრის თანხა წონის მისი ყველა შვილი კვანძების.

ალგორითმი მშენებლობის ხე Huffman

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

გაუმჯობესების ეფექტურობის შეკუმშვის

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

დაჩქარების შეკუმშვის პროცესში

დააჩქაროს ალგორითმი, განმარტება წერილები უნდა გაკეთდეს არა იმ თვალსაზრისით, ალბათობა კლების კონკრეტული წერილი და სიხშირის კლების მიხედვით. ეს ალგორითმი ხდება უფრო ადვილია, და მათთან მუშაობა უფრო სწრაფად. იგი ასევე თავს არიდებს ოპერაციების ასოცირდება მცურავი პუნქტიანი გაყოფა. გარდა ამისა, მუშაობა ამ რეჟიმში, დინამიური Huffman კოდი, უფრო სწორად ალგორითმი თავისთავად არ ექვემდებარება რაიმე ცვლილებები. ეს არის ძირითადად იმის გამო, რომ ალბათობა პირდაპირპროპორციულია სიხშირე. ღირს გადახდის ყურადღება იმ ფაქტს, რომ საბოლოო წონა ფაილი, ან ე.წ. root კვანძის უდრის თანხა რაოდენობის სიმბოლოების ობიექტი განიხილება.

დასკვნა

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