Код дърво (дърво Хъфман кодиране, H-дърво) - двоично дърво. в която:
- листа, маркирани със символ, за който се разработва кодиране;
- възли (включително корените) отбелязани сумата от вероятностите за възникване на символи, съответстващи на листата на поддървото. чийто корен е съответния възел.
метод Хъфман получава на масата за въвеждане на символи на честоти на поява в оригиналния текст. Освен това въз основа на тази таблица е базирана Хъфман кодиране дърво.
Алгоритъм за построяване на Хъфман дърво.
Стъпка 1 от въведените символи с азбуката образуват списък на свободните възли. Всеки лист има тегло. което може да бъде или еднаква вероятност, или на броя на повторения на герой в сгъстен текста.
Стъпка 2. Изберете два наказателни дърво възел с най-ниски тегла.
Стъпка 3. Създаване на родителите с тегло, равно на общото им тегло.
Стъпка 4. Родителят се добавя към списъка с безплатни възли, и двете му деца са отстранени от този списък.
Стъпка 5. Една дъга. напускане на родителя се определя малко 1, а другият - бит 0.
Стъпка 6: Повторете стъпки, като се започне с второто, толкова дълго, колкото списъка с безплатни възли не остане само един свободен възел. Той е считан за корена на дървото.
Има два подхода за изграждане на код дърво от корена към листата и от листата към корена.
Един пример за изграждането на код дървото. При един изходен поредица от символи:
Първоначалната му обем е 20 байта (160 бита). В съответствие с тези, показани на фиг. 41.1 данни (таблица поява вероятност на символите, код дърво и маса на оптимални префикс кодове), кодирани първоначалната последователност на символите са както следва:
Следователно, неговия обем е равен на 42 бита. Степента на сгъстяване е приблизително равна на 3.8.
Фиг. 41.1. Създаване на оптимални префикс кодове
Класически Хъфман има един съществен недостатък. За да възстановите съдържанието на компресирания текста при декодиране е необходимо да се знае таблицата с честота, която е била използвана за кодиране. Следователно дължината на сгъстен текста се увеличава с дължината на таблицата с честота, която трябва да бъде изпратена в навечерието на данни, които могат да отричат всички усилия в компресиране на данни. Освен това, необходимостта от пълна статистическа честота, преди всъщност кодиране изисква две пасажи в текста, по един за изграждане на модел на текста (таблицата с честота и дървото Хъфман), а другата за действителното кодиране.
Пример 2. Софтуер Изпълнение Хъфман алгоритъм с използване на код дървото.
За изпълнение на декодиране трябва да има код дърво. който трябва да се съхранява заедно с компресирани данни. Това води до известна леко увеличение в обема на компресирани данни. Те използват различни формати, които се съхраняват на дървото. Обръщаме внимание на факта, че възлите на код на дърветата са празни. Понякога един магазин не е самото дърво. и първоначалните данни за образуването му, който е информация за вероятностите за възникване на символи или номера. Когато този процес за декодиране, се предшества от създаването на нов код дърво, което е същото като за кодиране.
Основни термини
компресиране на данни - процес, който гарантира намаляване на обема на данните чрез намаляване на неговото напускане.
Lossless компресия (напълно обратимо) - е метод за компресиране на данни, в която част от предварително кодирани данни се възстановява след разопаковане напълно без модификация.
Компресия със загуби - метод за компресиране на данни, в която да се увеличи максимално съотношение на компресиране на оригиналния масив от данни част от данните, съдържащи се в нея се изхвърля.
Алгоритъмът на компресиране на данни (архивиране алгоритъм) - алгоритъмът е. което елиминира запис данни съкращения.
Азбука код - набор от символи вход.
Код символ - е най-малката единица на данни, за да бъдат компресирани.
Кодовата дума - последователност от кодови символи от кода на азбука.
Token - единица за данни, написани на компресиран поток някакъв алгоритъм за компресиране.
Фразата - това е част от данните, които се поставят в речника за използване при компресия.
Кодиране - е процес на компресиране на данните.
Декодиране - процес на обратна кодиране в който се извършва възстановяване на данни.
Компресия - е стойност, за да покаже ефективността на метода на пресоване, равен на съотношението на размера на изходния поток на входния поток.
Степента на сгъстяване - е реципрочната стойност на степента на сгъстяване.
Средната продължителност на кодова дума - стойност, която се изчислява като среднопретеглена сума на всички вероятностите за кодови думи.
Статистически методи - това методи за компресия възлага кодове с различна дължина символите на входния поток, по-късите кодове са предназначени за символи или групи от символи с по-висока вероятност за поява на входящ поток.
В речника компресия - на техники за компресиране, съхранение парчета от данни в структура от данни, наречени речника.
Haffmanovskoe кодиране (компресиране) - метод за компресиране, която определя символите на кодовете на азбуката с различна дължина на базата на вероятността за поява на тези символи.
Префикс код - код, който не кодова дума е префикс на всяка друга кодова дума.
Оптимално префикс код - код префикс. с минимална средна дължина.
Код дърво (дърво Хъфман кодиране, H-дърво) - двоично дърво. в която: листата отбелязани със символ, за който се разработва кодиране; възли (включително корените) отбелязани сумата от вероятностите за възникване на символи, съответстващи на листата на поддървото. чийто корен е съответния възел.
кратко резюме
- компресиране на данни е процес, който гарантира намаляване на обема на данните чрез намаляване на неговото напускане.
- компресия на данните може да бъде със загуби и без загуби.
- Компресия характеризира степента на компресия на данни.
- Има два основни начина за компресиране: статистически методи и речника за компресия.
- Хъфман алгоритъм се отнася до статистическите методи за компресиране на данни.
- Идеята за Хъфман алгоритъм е това: да знае вероятността от възникване на символи в изходния код, е възможно да се опише процедурата за изграждане на кодове с различна дължина, състояща се от едно цяло брой битове.
- Huffman кодове са уникални префикс, което ни позволява да ги декодира уникално, въпреки променливата им дължина.
- Хъфман гъвкав, той може да бъде използван за компресиране на данни от всякакъв вид, но това не е много ефективна за малки размери на файла.
- Класически Хъфман алгоритъм на базата на код дървото изисква съхранение на код дървото, което увеличава сложността.
Свързани статии