🗊Презентация Сжатие информации. Алгоритм Хаффмана

Сжатие информации Алгоритм Хаффмана

Сжатие информации Сжатие данных – сокращение объема данных при сохранении закодированного в них содержания.

Сжатие информации Сжатие происходит за счет устранения избыточности кода, например, за счет упрощения кодов, исключения из них постоянных битов или представления повторяющихся символов в виде коэффициента повторения. Важнейшая характеристика процесса сжатия – коэффициент сжатия. Коэффициент сжатия – отношение объема исходного сообщения к объему сжатого.

Алгоритмы сжатия

Сжатие с использованием кодов переменной длины

Префиксные коды

Префиксные коды

Префиксные коды

Префиксные коды

Алгоритм Хаффмана Алгоритм Хаффмана — адаптивный алгоритм оптимального  префиксного кодирования алфавита с минимальной избыточностью. Был разработан 1952 году аспирантом Массачусетского технологического института Дэвидом Хаффманом при написании им курсовой работы. В настоящее время используется во многих программах сжатия данных.

1. Символы исходного алфавита образуют вершины. Вес каждой вершины вес равен количеству вхождений данного символа в сжимаемое сообщение. 1. Символы исходного алфавита образуют вершины. Вес каждой вершины вес равен количеству вхождений данного символа в сжимаемое сообщение. 2. Среди вершин выбираются две с наименьшими весами (если таких пар несколько, выбирается любая из них). 3. Создается следующая вершина графа, из которой выходят две дуги к выбранным вершинам; одна дуга помечается цифрой 0, другая — символом 1. Вес созданной вершины равен сумме весов, выбранных на втором шаге вершин. 4. К новым вершинам применяются шаги 2 и 3 до тех пор, пока не останется одна вершина с весом, равным сумме весов исходных символов.

НА_ДВОРЕ_ТРАВА,_НА_ТРАВЕ_ДРОВА

Задача А9

Задача А9. Решение.

Задача А9. Решение.

Для самостоятельной работы

Задача А9

Задача А9