Huffman кодове: примери, приложения

В момента малко хора мислят за това как работи компресията. В сравнение с миналото, използването на персонален компютър става много по-лесно. И на практика всеки, който работи с файловата система, използва архиви. Но малко хора мислят за това как работят и за какъв принцип е компресирането на файловете. Първата версия на този процес бяха Huffman кодовете и те все още се използват в различни популярни архивари. Много потребители дори не мислят колко лесно е да компресирате файла и според коя схема работи. В тази статия ще разгледаме как се прави компресията, какви нюанси помагат за ускоряване и опростяване на процеса на кодиране и ще разберем какъв е принципът за изграждане на кодиращо дърво.

История на алгоритъма

Първият алгоритъм за ефективно кодиране на електронна информация е кодът, предложен от Хъфман в средата на ХХ в., А именно през 1952 г. Понастоящем той е основният основен елемент на повечето програми, създадени за компресиране на информация. В момента един от най-популярните източници, използващи този код, са ZIP, ARJ, RAR архиви и много други. Този алгоритъм на Huffman също се използва за компресиране на JPEG изображения и други графични обекти. Е, всички съвременни факс машини използват и кодиране, изобретен през 1952 година. Въпреки факта, че от създаването на кода е изминало толкова много време, до днес той се използва в най-новите черупки и оборудване на стари и съвременни видове.

Принципът на ефективно кодиране

Алгоритъмът на Huffman се основава на схема, която позволява да се заменят най-вероятните, най-често срещаните символи двоични кодове система. И тези, които са по-рядко срещани, се заменят с по-дълги кодове. Преходът към дълги Huffman кодове се извършва само след като системата използва всички минимални стойности. Тази техника ви позволява да сведете до минимум дължината на кода за всеки знак на оригиналното съобщение като цяло. Важно е, че в началото на кодирането вече е известна вероятността за появата на букви. От тях последното съобщение ще бъде съставено. Въз основа на тези данни се създава кодовото дърво на Huffman, въз основа на което ще се извърши процесът на кодиране на букви в архива.

Кодът на Хуфман, пример

За да илюстрираме алгоритъма, нека вземем графичен вариант на конструиране на кодово дърво. За да се използва този метод, е полезно да се изясни определението на някои стойности, необходими за концепцията на този метод. Наборът от дъги и възли, които са насочени от възел към възел, обикновено се нарича графика. Самото дърво е графика с набор от определени свойства:

• във всеки възел не може да влиза повече от една от дъгите;
• един от възлите трябва да бъде коренът на дървото, т.е. никоя дъга не трябва да влезе в него;
• ако от корена започне да се движи по дъги, този процес трябва да позволи да се получи напълно в някой от възлите.

Съществува и такава концепция, която е включена в кодовете на Huffman, като лист от дърво. Това е възел, от който никоя дъга не трябва да избяга. Ако два възела са свързани чрез дъга, тогава единият от тях е родителят, а другото дете, в зависимост от кой възел е дъгата и кой е в нея. Ако два възела имат един и същ родителски възел, те обикновено се наричат ​​братски възли. Ако освен листата има няколко дъги в възлите, това дърво се нарича двоично. Това е точно дървото на Хъфман. Особеността на възлите на тази конструкция е, че теглото на всеки родител е равно на сумата от теглото на всичките му възлови деца.

Алгоритъм за изграждане на дърво според Huffman

Конструкцията на Huffman кода се прави от буквите на входната азбука. Ще бъде създаден списък с тези възли, които са свободни в бъдещото кодово дърво. Теглото на всеки възел в този списък трябва да бъде същото като вероятността за възникване на буквата на съобщението, съответстващо на тази възлова точка. В този случай сред няколкото свободни възли на бъдещото дърво се избира най-малкото, което тежи най-малко. В същото време, ако минималните индикатори се наблюдават в няколко възли, тогава е възможно да се избере свободно някоя от двойките. След това се създава родителската възлова точка, която трябва да претегля толкова, колкото и теглото на тази двойка възли. След това родителят се изпраща в списъка с безплатни възли и децата се изтриват. В същото време дъгите получават съответни индекси, такива и нули. Този процес се повтаря точно толкова дълго, колкото е необходимо, за да се остави само един възел. След това двоичните числа се записват отгоре надолу.

Подобряване на ефективността на компресията

За да се увеличи ефикасността на компресията, при създаването на кодовото дърво е необходимо да се използват всички данни относно вероятността от букви, които се появяват в даден файл, прикрепен към дървото, и да не се позволява да бъдат разпръснати върху голям брой текстови документи. Ако първо минавате през този файл, можете веднага да изчислите статистиката за това колко често се срещат букви от обект, който ще се компресира.

Ускоряване на процеса на компресия

За да ускорите работата алгоритъм, определение буквите трябва да се извършват не според индексите на вероятността за възникване на определена буква, а по честотата на нейното възникване. Благодарение на това алгоритъмът става по-опростен и работата с него значително се ускорява. Това също така избягва операциите, свързани с плаващи запетаи и разделяне. Освен това, в този режим, динамичният Huffman код, или по-скоро самият алгоритъм, не подлежи на никакви промени. Това се дължи главно на факта, че вероятностите са пряко пропорционални на честотите. Струва си да обърнем специално внимание на факта, че крайното тегло на файла или така наречения корен възел ще бъде равно на сумата от броя букви в обекта, който ще бъде обработен.

заключение

Кодовете на Huffman са прост и дългогодишен алгоритъм, който все още се използва от много известни програми и компании. Нейната простота и яснота правят възможно постигането на ефективни резултати от компресията за файлове от всякакъв размер и значително намаляват пространството, което заемат на диска за съхранение. С други думи, алгоритъмът Huffman е дълго проучена и добре проектирана схема, чието значение не намалява до този момент. И благодарение на способността да се намали размерът на файловете, прехвърлянето им през мрежата или по други начини, става по-лесно, по-бързо и по-удобно. Работейки с алгоритъма, можете да компресирате абсолютно всяка информация, без да навредите на структурата и качеството му, но с максималния ефект от намаляването на теглото на файла. С други думи, кодирането на Huffman кода е и остава най-популярният и действителен метод за компресиране на размера на файла.