На пръв поглед изглежда труден за схващане, но, както може би повечето алгоритми, които съм разглеждал на този етап, само трябва да се приложи няколко пъти, за да бъде разбран достатъчно добре.
---
ОПИСАНИЕ:
Алгоритъмът на Хъфман служи за компресиране на информация и е добър пример за алчен алгоритъм (тъй като винаги взема "най-доброто"). Идеята зад него е, че ако имаме някакво съобщение, можем да го преобразуваме в код от 0-ли и 1-ци.
За целта се използва т.нар. "дърво на Хъфман", от което се извежда и "код на Хъфман".
Ако се чудите "какво по дяволите е дърво" - ето тук има отлично обяснение на нещата, които ще трябва да знаете предварително. :)
АЛГОРИТЪМ:
1. Създават се дървета от по един възел, съответстващи на буквите от азбуката в съобщението.
2. Записват се честотите на срещане на всяка буква в корените на тези дървета
3. Избират се две дървета с минимално тегло и се обединяват в едно, като неговото тегло се получава от сумата на теглата на двете поддървета.
4. Горното действие се повтаря до получаване на единствено дърво.
ПРИМЕР:
Съобщение: baabbcdddebbaccbdbda
Първото, което трябва да направим, е да видим кои са буквите, които участват в съобщението и колко пъти се среща всяка от тях. В случая имаме участието на само 5 букви - a, b, c, d, e.
Ето и колко пъти се среща всяка от тях:
а - 4 срещания
b - 7 срещания
c - 3 срещания
d - 5 срещания
e - 1 срещане
Следващата стъпка е да създадем 5 дървета с по 1 възел (или "връх"). Тъй като имаме само 1 възел, той представлява корен на съответното дърво.
Повтаряме същото! Този път най-малките стойности са 4 и 4 (не, няма значение, че стойностите са еднакви). Следваме същия принцип и получаваме следното:
Схванахте вече. Но нека отново ви кажа какво следва... 7 и 5! Ето и резултатът:
Хайде още 1 път... Разбира се, стойностите са 8 и 12, тъй като други няма. Резултатът:
Стигнахме до забавната част - вече имаме само 1 дърво. Сега следва да номерираме всяко ляво ребро с 0, и всяко дясно ребро с 1 (ребрата са стрелките), подобно на алгоритъма на Шенън-Фано.
Най-накрая получаваме дървото на Хъфман:
И сега... как да получим кода? Много просто - следваме пътя до всяка буква. Как да стигнем до буквата 'b' например? Започваме от корена 20 и преминаваме към 12 (реброто между двата възела е с тегло 1), от 12 отиваме към 7 (реброто между двата възела е с тегло 1).
В случая ни интересува последователността от теглата на ребрата до възела на дадената буква. Иначе казано, понеже първото ребро има тегло 1 и второто също има тегло 1, кодът на буквата 'b' е 11.
Аналогично намираме кода на всяка от останалите букви и получаваме следната таблица:
Така... какво беше съобщението? А, да:
За целта се използва т.нар. "дърво на Хъфман", от което се извежда и "код на Хъфман".
Ако се чудите "какво по дяволите е дърво" - ето тук има отлично обяснение на нещата, които ще трябва да знаете предварително. :)
АЛГОРИТЪМ:
1. Създават се дървета от по един възел, съответстващи на буквите от азбуката в съобщението.
2. Записват се честотите на срещане на всяка буква в корените на тези дървета
3. Избират се две дървета с минимално тегло и се обединяват в едно, като неговото тегло се получава от сумата на теглата на двете поддървета.
4. Горното действие се повтаря до получаване на единствено дърво.
ПРИМЕР:
Съобщение: baabbcdddebbaccbdbda
Първото, което трябва да направим, е да видим кои са буквите, които участват в съобщението и колко пъти се среща всяка от тях. В случая имаме участието на само 5 букви - a, b, c, d, e.
Ето и колко пъти се среща всяка от тях:
а - 4 срещания
b - 7 срещания
c - 3 срещания
d - 5 срещания
e - 1 срещане
Следващата стъпка е да създадем 5 дървета с по 1 възел (или "връх"). Тъй като имаме само 1 възел, той представлява корен на съответното дърво.
Чудесно! Сега трябва да открием 2-те дървета с най-малко тегло (най-малка стойност) в корена. Лесно виждаме, че тези стойности са 3 и 1. Обединяваме ги в ново двоично подредено дърво. Това ново дърво ще има корен с тегло 4 (сумата от теглата на предишните 2 тегла), и наследници с тегла 3 и 1.
Тъй като дървото е подредено, това означава че вляво добавяме по-малката стойност, а вдясно по-голямата (не правете същата грешка като мен - бях ги обърнал и резултатът не беше красив 👲).
След всичко това стигаме до следната ситуация:
Схванахте вече. Но нека отново ви кажа какво следва... 7 и 5! Ето и резултатът:
Хайде още 1 път... Разбира се, стойностите са 8 и 12, тъй като други няма. Резултатът:
Стигнахме до забавната част - вече имаме само 1 дърво. Сега следва да номерираме всяко ляво ребро с 0, и всяко дясно ребро с 1 (ребрата са стрелките), подобно на алгоритъма на Шенън-Фано.
Най-накрая получаваме дървото на Хъфман:
И сега... как да получим кода? Много просто - следваме пътя до всяка буква. Как да стигнем до буквата 'b' например? Започваме от корена 20 и преминаваме към 12 (реброто между двата възела е с тегло 1), от 12 отиваме към 7 (реброто между двата възела е с тегло 1).
В случая ни интересува последователността от теглата на ребрата до възела на дадената буква. Иначе казано, понеже първото ребро има тегло 1 и второто също има тегло 1, кодът на буквата 'b' е 11.
Аналогично намираме кода на всяка от останалите букви и получаваме следната таблица:
|
a
|
00
|
|
b
|
11
|
|
c
|
011
|
|
d
|
10
|
|
e
|
010
|
Така... какво беше съобщението? А, да:
baabbcdddebbaccbdbda
Сега просто заменяме всяка буква в съобщението с нейния код.
Получаваме кода на Хъфман:
11 | 00 | 00 | 11 | 11 | 011 | 10 | 10 | 10 | 010 | 11 | 11 | 00 | 011 | 011 | 11 | 10 | 11 | 10 | 00
b a a b b c d d d e b b a c c b d b d a
=> 11000011110111010100101111000110111110111000
Вече сте богове на компресирането. 😅
Няма коментари:
Публикуване на коментар