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

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

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

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

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

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

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

Важен момент е, че в началотоКодирането на вероятността за възникване на букви трябва вече да е известно. От тях последното съобщение ще бъде съставено. Въз основа на тези данни се създава кодовото дърво на Huffman, въз основа на което ще се извърши процесът на кодиране на букви в архива.

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

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

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

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

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

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

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

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

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

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

За ускоряване на алгоритъма, определението на буквитеНеобходимо е да се направи не върху показателите за вероятност за възникване на това или онова писмо и за честотата на неговото възникване. Благодарение на това алгоритъмът става по-опростен и работата с него значително се ускорява. Това също така избягва операциите, свързани с плаващи запетаи и разделяне.

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

заключение

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

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