Лаб2(Хаффман)
.docЛабораторная работа №2 «Алгоритм Хаффмана»
Цель: сжать текст по алгоритму. Рассчитать коэффициент сжатия.
Методические указания
Алгоритм основан на том факте, что некоторые символы из стандартного 256-символьного набора в произвольном тексте могут встречаться чаще среднего периода повтора, а другие, соответственно, – реже. Следовательно, если для записи распространенных символов использовать короткие последовательности бит, длиной меньше 8, а для записи редких символов – длинные, то суммарный объем файла уменьшится.
Хаффман предложил очень простой алгоритм определения того, какой символ необходимо кодировать каким кодом для получения файла с длиной, очень близкой к его энтропии (то есть информационной насыщенности). Пусть у нас имеется список всех символов, встречающихся в исходном тексте, причем известно количество появлений каждого символа в нем. Выпишем их вертикально в ряд в виде ячеек будущего графа по правому краю листа (рис. 1а). Выберем два символа с наименьшим количеством повторений в тексте (если три или большее число символов имеют одинаковые значения, выбираем любые два из них). Проведем от них линии влево к новой вершине графа и запишем в нее значение, равное сумме частот повторения каждого из объединяемых символов (рис.1б). Отныне не будем принимать во внимание при поиске наименьших частот повторения два объединенных узла (для этого сотрем числа в этих двух вершинах), но будем рассматривать новую вершину как полноценную ячейку с частотой появления, равной сумме частот появления двух соединившихся вершин. Будем повторять операцию объединения вершин до тех пор, пока не придем к одной вершине с числом (рис.1в и 1г). Для проверки: очевидно, что в ней будет записана длина кодируемого файла. Теперь расставим на двух ребрах графа, исходящих из каждой вершины, биты 0 и 1 произвольно – например, на каждом верхнем ребре 0, а на каждом нижнем – 1. Теперь для определения кода каждой конкретной буквы необходимо просто пройти от вершины дерева до нее, выписывая нули и единицы по маршруту следования. Для рисунка 1 символ "А" получает код "100", символ "Б" – код "0", символ "К" – код "101", а символ "О" – код "11".
Рис.1(а, б, в, г).
В теории кодирования информации показывается, что код Хаффмана является префиксным, то есть код никакого символа не является началом кода какого-либо другого символа. Проверьте это на нашем примере. А из этого следует, что код Хаффмана однозначно восстановим получателем, даже если не сообщается длина кода каждого переданного символа. Получателю пересылают только дерево Хаффмана в компактном виде, а затем входная последовательность кодов символов декодируется им самостоятельно без какой-либо дополнительной информации. Например, при приеме "01001101000" им сначала отделяется первый символ "Б" : "0-1001101000", затем снова начиная с вершины дерева – "А" "0-100-1101000", затем аналогично декодируется вся запись "0-100-11-0-100-0" "БАОБАБ".
Оформление работы
1. Наименование работы
2. Фамилия и группа студента
3. Цель
4. Задание по вариантам (текст, который нужно заархивировать)
5. Таблица символов встречающихся в тексте и их количество
Символ |
A |
Б |
|
|
_ |
ИТОГО |
кол |
4 |
8 |
|
|
|
|
Исходный размер |
32 |
|
|
|
|
777777 |
код |
010 |
11100 |
|
|
|
|
Итоговый размер |
12 |
|
|
|
|
777 |
|
|
|
|
|
|
|
6. Дерево Хаффмана:
7. Заархивированный текст:
0101010110110010101010
8. Вывод:
Во сколько раз уменьшился
Варианты заданий
Вариант №1
У Феофана Митрофаныча три сына Феофаныча.
Флюорографистфлюорографировалфлюорографистку.
Цыплёнок цапли цепко цеплялся за цеп.
Четверть четверика гороха, без червоточинки.
Чешуя у щучки, щетинка у чушки.
Вариант №2
Шесть мышат в камышах шуршат.
Шла Саша по шоссе и сосала сушку.
Шли сорок мышей и шесть нашли грошей, а мыши, что поплоше, нашли по два гроша.
Это колониализм? - Нет, это не колониализм, а неоколониализм!
Вариант №3
Я - вертикультяп. Могу вертикультяпнуться, могу вывертикультяпнуться.
Яшма в замше замшела. Тощий немощный Кощей Тащит ящик овощей.
Ты, сверчок сверчи, сверчи, Сверчать сверчаток научи.
Вариант №4
Свил паук себе гамак в уголке, на потолке, Чтобы мухи, просто так, покачались в гамаке.
Расскажите про покупки. Про какие про покупки? Про покупки, про покупки,
Вариант №5
Про крупу да про подкрупки.
От топота копыт пыль по полю летит.
Тридцать три корабля лавировали,
лавировали да не вылавировали.
Вариант №6
Шли сорок мышей, несли сорок грошей,
две мыши поплоше несли по два гроша.
В четверг четвертого числа, в четыре с четвертью часа, Четыре черненьких чумазеньких чертенка чертили
черными чернилами чертеж чрезвычайно чисто.
Вариант №7
Ежик в бане вымыл ушки, шею, кожицу на бpюшке.
А на встpечу ему волк, на ежа зубами - щелк.
Еж иголки показал, волк со стpаху убежал.
Ехал Гpекачеpезpеку, видит Гpека в pеке - pак.
Сунул Гpекаpуку в pеку, pак за pукуГpеку - цап!
Вариант №8
И при Прокопе кипит укроп,
И без Прокопа кипит укроп;
И ушёл Прокоп – кипит укроп,
И пришёл Прокоп – кипит укроп.
Идет козел с косой козой, идет козел с босой козой,
идет козa с косым козлом, идет козa с босым козлом.
Вариант №9
Из кузова в кузов шла перегрузка арбузов.
В грозу в грязи от груза арбузов развалился кузов.
Из-под Костромщины шли четверы мужчины;
говорили они про торги да про покупки,
про крупу да про подкрупки.
Вариант №10
Два дровосека, два дровокола,
два дроворуба говорили про
Ларю, проЛарьку, про Ларину жену.
Два дровосека, два дроворуба говорили про Ларьку,
про Варьку, про Ларину жену.
Вариант №11
Ловко лавируя в ларингологии,
лекарь-ларинголог легко излечивал ларингиты.
Маланья-болтунья молоко болтала, выбалтывала, не выболтала.
Милости прошу к нашему шалашу: я пирогов покрошу и откушать попрошу.
Вариант№12
От топота копыт пыль по полю летит.
Окола кола вьюн и хмель вьются на плетень. Вьются, плетутся, заплетаются, расперезавиваются.
Прыгают в поле сорок сорок, десять взлетели, сели на ели. Сколько осталось в поле сорок?
Вариант№13
Павел Павлушку пеленовал, пеленовал и распелёновывил.
Поезд мчится скрежеща: ж, ч, ш, щ, ж, ч, ш, щ
Полили ли лилию? Видели ли Лидию? Полили Лилию, видели Лидию.
Прецедент с претендентом.
Привёз Пров Егорке во двор дров горку.
Вариант№14
Протокол про протокол протоколом запротоколировали.
Работники предприятие приватизировали,
приватизировали да не выприватизировали.
Рано коваль встал, сталь ковал, ковал,
сталь перевыковывал, да не перековал.
Вариант№15
Рапортовал, да не дорапортовал, дорапортовал, да зарапортовался.
Расскажите про покупки! - Про какие про покупки? –
Про покупки, про покупки, про покупочки свои.
Регулировщик лигуриец регулировал в Лигурии.
Рыла свинья белорыла, тупорыла; полдвора рылом изрыла, вырыла, подрыла.
Вариант№16
Иван Топорышкин пошел на охоту С ним пудель пошел перепрыгнув забор, Иван, как бревно, провалился в болото, А пудель в реке утонул, как топор. Иван Топорышкин пошел на охоту С ним пудель вприпрыжку пошел, как топор
Вариант№17
Иван провалился бревном на болото, А пудель в реке перепрыгнул забор. Иван Топорышкин пошел на охоту С ним пудель в реке провалился в забор, Иван, как бревно, перепрыгнул болото, А пудель вприпрыжку попал на топор.
Вариант№18
Саша шапкой шишку сшиб.
Сиреневенькая зубовыковыривательница.
Сняли с Надежды цветные одежды, Без одежд Надежда не манит как прежде.
Стаффордширский терьер ретив, а черношерстный ризеншнауцер резв.
Вариант№19
Саша - само совершенство, а еще самосовершенствуется!
Самшит, самшит, как ты крепко сшит.
Свинья тупорыла-толсторыла двор рылом рыла, всё изрыла, срыла, перерыла, везде понарыла, повырыла, подрыла.
Свиристель свиристит свирелью.