Теоретичната част
Хъфман алгоритъм
Един от първите алгоритми за ефективно кодиране на информация беше предложен от Хъфман през 1952. Този алгоритъм се превърна в отправна точка за много програми за компресиране на данни. Например, кодирането Хъфман се използва в програми за компресиране ARJ. Пощенски код. RAR. алгоритъм за компресия JPEG графични изображения с загуби. както и интегрирана в съвременните факс машини.
Ефективно кодиране Хъфман е да представи най-вероятно (често) буквите двоични кодове най-малка дължина и най-малко вероятно - толкова по-голяма от дължината на кодовете (ако всички кодови думи в дължина са изчерпани). Това се прави така, че средната дължина на кода на буквата на оригиналното съобщение е било минимално.
Преди началото на кодирането, трябва да се знае, че вероятността от настъпване на всяка буква от които ще бъде в съобщението. Въз основа на таблицата на вероятностите е конструиран Хъфман код дърво, с който кодира букви.
Изграждане на код Хъфман дърво
За да се убедите, помислете алгоритъма Хъфман, графичен начин за изграждане на кодиране дърво. Преди да се въведат някои определения, приети за да се опише алгоритъм Хъфман използването на този метод.
Count - набор от множество възли и множество дъги насочени от един възел към друг.
Wood - графика със следните свойства:- всеки един от възлите не включва повече от една дъга;
- само един възел не е част от всяка дъга (този възел се нарича корен на дървото);
- движещи се по протежение на дъгите от корена, можете да получите на всеки възел.
дърво листа - възел, от който не оставя дъга. В един чифт дърво възли свързани помежду си с дъга, този, от който става ясно, се нарича майка. а от друга - на детето.
Две възли се наричат братя. ако те имат една и съща майка.
Binary Tree - дърво, което от всички възли, с изключение на листата, оставя точно две дъги.
Tree Хъфман кодиране - двоично дърво, в която всеки възел има тегло. и при което теглото майка е общото тегло на децата.
Алгоритъм за построяване на дърво Хъфман кодиране е както следва:- входни азбука писма формират списъка на свободните възли бъдеще кодиране дърво. Всеки възел в този списък е с тегло, равно на вероятността за поява на съответните буквите в съобщението.
- Избрани две свободни дърво възел с най-ниски тегла. Ако има повече от два възела с най-ниски свободни тежести, можете да вземете всяка двойка.
- Създава своя родител с тегло, равно на общото им тегло.
- Родител добавен в списъка на свободните възли, и двете му деца са отстранени от този списък.
- Един дъга простираща се от възел майка, е свързано с малко един, друг - 0.
- Точки 2, 3, 4, 5 се повтарят толкова дълго, колкото на списъка с безплатни възли не остане само един възел. Този възел ще бъде в основата на дървото. Теглото му е установено, че един от тях - общо вероятността за всички букви от съобщението.
Сега, да преминат към код дървото от горе до долу и след писмено нули и единици, съответстващи на дъги, можете да ги получавате вход азбука.
Помислете например за изграждането на кодиране дървото на Хъфман за дадено в таблица 1 от осемте букви от азбуката.
Изграждане на дърво с листа започват да списъкът (виж. Фиг. 1), както и изпълнение на етапите.
Фиг. 1. Списъкът на свободна листа възли.
В първия етап на двете листата на дървото са избрани с най-ниски стойности за теглото Z7 и z8. Те са свързани към възела майка, теглото на който е разположен в 0.04 0.02 = 0.06. Тогава Z7 и Z8 възли са отстранени от списъка със свободни. Node Z7 0 съответства на клон основния възел Z8 - 1. кодиране клонове дърво след първата стъпка е показано на фиг. 2.
Фиг. 2. Хъфман кодиране дърво след първата стъпка.
Във втората стъпка "Flyweight" чифт е Z6 лист и свободен възел (Z7 + z8). За тях е създаден родител с тегло 0,16. Node Z6 0 съответства на клон основния възел (Z7 + z8) - клон 1. В тази стъпка, дървото кодиране, както следва (виж Фигура 3 ..).
Фиг. 3. Хъфман кодиране дърво след втората стъпка.
В третия етап на най-малко вероятността са Z5. Z4. z3 и свободен възел (Z6 + Z7 + z8). Така, в този етап може да бъде създаден за родител и Z5 (Z6 + Z7 + z8) с тегло 0.26. пристигат в кодиращата дърво, показано на фиг. 4. Моля, имайте предвид, че в тази ситуация има няколко опции за свързване на възлите с най-ниски тегла. Освен това, всички тези варианти са правилни, въпреки че това може да доведе до различни набори от кодове, които, обаче, ще имат същата ефективност за даден вероятностно разпределение.
Фиг. 4. Хъфман кодиране дърво след третата стъпка.
Четвъртата стъпка е "Flyweight" са чифт листа Z3 и Z4. Huffman кодиране дърво е показано на фиг. 5.
Фиг. 5. Хъфман кодиране дърво след четвъртата стъпка.
На петия етап изберете сайтове с най-ниски тегла на 0.22 и 0.20. Хъфман кодиране дърво след петото стъпало е показано на фиг. 6.
Фиг. 6. Хъфман кодиране дърво след петия етап.
В шести етап е три свободно възел с тегло 0.42. 0.32 и 0.26. Изборът на най-малката тежест на 0.32 и 0.26. Huffman кодиране дърво след шестия етап, показан на фиг. 7.
Фиг. 7. Хъфман кодиране дърво след шестата стъпка.
Седмият етап е да се комбинират двата останали свободни върховете, а след това получи крайния Хъфман кодиране дървото е показано на фигура. 8.
Фиг. 8. Крайният дърво Хъфман кодиране.
Въз основа на конструирани дървесни буквени кодове представени отразяващ път от корен възел на листото, съответстващ на желаната буква. В този пример, входният азбука са кодирани, както е показано в таблица 2.
Таблица 3 показва, че кодовете също ще получат префикс, а най-вероятно отговарят на буквите от най-кратки кодове.
Практическото изпълнение на алгоритъма
За да се подобри ефективността на компресия е необходимо да се строителство код дърво, използвано данни за вероятността от възникване на писма в този файл, а не като средни стойности за голям брой текстове. Съответно необходимите статистически данни за поява на писма компресиран файл, който може да бъде получена предварително преминаване през файла.
За да се ускори работата взети за определяне на вероятността от възникване не пи букви. и честотата на поява (брой повторения) Ni буквите във файла. Това може значително да се опрости и ускори алгоритъм (не е необходимо да се забави операции с плаваща запетая и операции по разделяне). При този подход, алгоритъмът не се променя, тъй като честотата е пряко пропорционално на вероятностите. Трябва да се отбележи, че теглото на коренът на кодирането на дърво в този случай е равна на общия брой на писма във файла се обработват.
интерактивно обучение
След като се запознаете с теоретичната част на работата, ви предлагаме да практикуват в изграждането на Huffman код дървета с помощта на интерактивна система за обучение. За да направите това, просто отидете на този линк.
Свързани статии