Алгоритъмът на Хъфман се използва за компресиране или кодиране на данни. Обикновено всеки знак в текстов файл се съхранява като осем бита (цифри, 0 или 1), които се съпоставят с този знак, използвайки кодиране, наречено ASCII. Кодиран от Хафман файл разгражда твърдата 8-битова структура, така че най-често използваните знаци се съхраняват само в няколко бита ('a' може да бъде "10" или "1000", а не ASCII, което е "01100001"). Следователно най -малко често срещаните знаци често заемат много повече от 8 бита ('z' може да бъде "00100011010"), но тъй като те се срещат толкова рядко, кодирането на Huffman като цяло създава много по -малък файл от оригинала.
Стъпки
Част 1 от 2: Кодиране
Стъпка 1. Пребройте честотата на всеки символ във файла, който ще бъде кодиран
Включете фиктивен знак, за да маркирате края на файла - това ще бъде важно по -късно. Засега го наричайте EOF (край на файла) и го маркирайте като с честота 1.
Например, ако искате да кодирате текстов файл, четящ „ab ab cab“, ще имате „a“с честота 3, „b“с честота 3, „(интервал) с честота 2,„ c “с честота 1, и EOF с честота 1
Стъпка 2. Съхранявайте символите като дървесни възли и ги поставяйте в приоритетна опашка
Ще изграждате голямо двоично дърво с всеки знак като лист, така че трябва да съхранявате знаците във формат, така че да могат да станат възли на дървото. Поставете тези възли в приоритетна опашка с честота на всеки символ като приоритет на нейния възел.
- Двоичното дърво е формат на данни, където всяка част от данни е възел, който може да има до един родител и две деца. Често е нарисувано като разклонено дърво, откъдето идва и името.
- Опашката е подходящо наречена колекция от данни, където първото нещо, което влиза в опашката, е и първото нещо, което излиза (като чакане на опашка). В опашка с приоритет данните се съхраняват по техния приоритет, така че първото нещо, което ще излезе, е най -спешното, това с най -малкия приоритет, а не първото нещо, поставено в ред.
- В примера „ab ab cab“приоритетната ви опашка ще изглежда така: {'c': 1, EOF: 1, '': 2, 'a': 3, 'b': 3}
Стъпка 3. Започнете да изграждате вашето дърво
Премахнете (или извадете на опашка) двете най -спешни неща от опашката за приоритет. Създайте нов дървесен възел, който да бъде родител на тези два възела, като съхраните първия възел като ляво дете, а втория като дясно дете. Приоритетът на новия възел трябва да бъде сумата от приоритетите на неговото дете. След това поставете този нов възел в опашката с приоритет.
Опашката за приоритет сега изглежда така: {'': 2, нов възел: 2, 'a': 3, 'b': 3}
Стъпка 4. Завършете изграждането на вашето дърво:
повторете горната стъпка, докато в опашката има само един възел. Обърнете внимание, че в допълнение към възлите, които сте създали за героите и техните честоти, вие също ще извадите от опашката, ще се превърнете в дървета и ще поставите повторно в родителските възли, възли, които вече са дървета.
- Когато приключите, последният възел в опашката ще бъде коренът на кодиращото дърво, като всички останали възли се разклоняват от него.
- Най -често използваните знаци ще бъдат листата, които са най -близо до върха на дървото, докато рядко използваните знаци ще бъдат позиционирани в долната част на дървото, по -далеч от корена.
Стъпка 5. Създайте карта за кодиране. Разходете се през дървото, за да стигнете до всеки герой. Всеки път, когато посещавате лявото дете на възел, това е '0'. Всеки път, когато посещавате дясното дете на възел, това е „1“. Когато стигнете до герой, съхранявайте знака с последователността от 0 и 1, необходими за да стигнете до него. Тази последователност е това, което символът ще бъде кодиран като в компресирания файл. Съхранявайте героите и техните последователности в карта.
- Например, започнете от корена. Посетете лявото дете на корена и след това посетете лявото дете на този възел. Тъй като възелът, в който се намирате сега, няма деца, достигнахте герой. Това е ' '. Тъй като сте ходили два пъти наляво, за да стигнете до тук, кодирането за '' е "00".
- За това дърво картата ще изглежда така: {'': "00", 'a': "10", 'b': "11", 'c': "010", EOF: "011"}.
Стъпка 6. В изходния файл включете кодиращата карта като заглавка
Това ще позволи на файла да бъде декодиран.
Стъпка 7. Кодирайте файла
За всеки кодиран знак във файла напишете двоичната последователност, която сте съхранили в картата. След като приключите с кодирането на файла, не забравяйте да добавите EOF до края.
- За файла "ab ab cab" кодираният файл ще изглежда така: "1011001011000101011011".
- Файловете се съхраняват като байтове (8 бита или 8 двоични цифри). Тъй като алгоритъмът за кодиране на Huffman не използва 8-битов формат, кодираните файлове често няма да имат дължини, кратни на 8. Останалите цифри ще бъдат попълнени с 0. В този случай две 0 ще бъдат добавени в края на файла, което прилича на друго пространство. Това може да е проблем: как декодерът ще знае кога да спре да чете? Въпреки това, тъй като включихме символ на края на файла, декодерът ще стигне до това и след това ще спре, игнорирайки всичко друго, което е добавено след това.
Част 2 от 2: Декодиране
Стъпка 1. Прочетете в Huffman-кодиран файл
Първо прочетете заглавката, която трябва да бъде картата за кодиране. Използвайте това, за да изградите дърво за декодиране по същия начин, по който сте построили дървото, което сте използвали за кодиране на файла. Двете дървета трябва да са идентични.
Стъпка 2. Четете в двоичното число една по една цифра
Пресечете дървото, докато четете: ако четете в „0“, отидете до лявото дете на възела, в който се намирате, и ако четете в „1“, отидете до дясното дете. Когато стигнете до лист (възел без деца), вие сте стигнали до герой. Запишете знака в декодирания файл.
Поради начина, по който символите се съхраняват в дървото, кодовете за всеки знак имат свойство префикс, така че двоичното кодиране на никой знак не може да възникне в началото на кодирането на друг символ. Кодирането за всеки знак е напълно уникално. Това прави декодирането много по -лесно
Стъпка 3. Повторете, докато достигнете EOF
Честито! Декодирахте файла.
