Главная страница
Навигация по странице:

  • Задание на работу

  • Ход выполнения работы

  • Выводы

  • Ответы на контрольные вопросы

    		•

    Лабораторная работа №9. Лабораторная работа № 9. Лабораторная работа Вариант Методы эффективного кодирования информации Цель работы


    Скачать 204 Kb.
    НазваниеЛабораторная работа Вариант Методы эффективного кодирования информации Цель работы
    АнкорЛабораторная работа №9
    Дата21.06.2022
    Размер204 Kb.
    Формат файлаdoc
    Имя файлаЛабораторная работа № 9.doc
    ТипЛабораторная работа
    #608924

    Лабораторная работа № 9. Вариант 6.

    Методы эффективного кодирования информации

    Цель работы:

    Изучить алгоритм Хаффмена для оптимального префиксного кодирования алфавита с минимальной избыточностью.

    Задание на работу

    Построить кодовое дерево и код Хаффмена для последовательности символов в соответствии с вариантом (таблица 1).

    Таблица 1 - Варианты заданий на работу

    Вариант
    Текст

    6
    is assumed that each symbol requires the same

    Подсчитайте энтропию исходного сообщения и среднюю длину кодирующего сообщения.

    Ход выполнения работы

    Используя алгоритм Хаффмана, определим вероятности появления символов в данной фразе и найдем оптимальный код.

    Перепишем данную фразу «is assumed that each symbol requires the same» в виде:

    « aaaabcdeeeeeehhhiilmmmoqrrsssssstttuuy». В таблице отметим частоту появления символов в данном тексте.

    Таблица 2 – Частота появления символов

    символ
    Частота появления в тексте



    7

    a
    4

    b
    1

    c
    1

    d
    1

    e
    6

    h
    3

    i
    2

    l
    1

    m
    3

    o
    1

    q
    1

    r
    2

    s
    6

    t
    3

    u
    2

    y
    1

    Итого:
    ∑=45

    Энтропия исходного сообщения равна: H = -7/45*log2(7/45) – 2*6/45*log2(6/45) - 4/45)*log2(4/45) - 3*3/45*log2(3/45) - 3*2/45*log2(2/45) - 7*1/45*log2(1/45) ≈ 0.4176+ 0.7752+ 0.3104+ 0.7814+ 0.5989 + 0.8543 = 3.7377;

    Заполняем таблицу следующим образом: в первом столбце указываем все встречающиеся символы, во втором столбце вероятность в порядке убывания.

    В столбец шаг 1 вместо двух минимальных вероятностей предыдущего столбца (отмечено зеленым цветом) заменяем суммой этих вероятностей, результат в столбце шаг 1 в клетке зеленого цвета. Далее процесс повторяется по аналогии.

    Таблица 2 - Процедура оптимального двоичного кодирования

    символ
    вероятность
    шаг







    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16




















































    26
    1














































    19
    19













































    14
    14













































    12
    12
    12










































    11
    11
    11










































    8
    8
    8
    8







































    7
    7
    7
    7







































    7
    7
    7
    7
    7




































    7
    6
    6
    6
    6




































    7
    6
    6
    6
    6
    6

































    7
    6
    6
    6
    6
    6

































    7
    6
    6
    5
    5
    5
    5






























    7
    6
    6
    4
    4
    4
    4






























    7
    6
    6
    4
    4
    4
    4
    4



























    7
    6
    6
    4
    4
    4
    4
    4


























    7/45
    6
    6
    4
    3
    3
    3
    3
    3
























    e
    6/45
    6
    4
    3
    3
    3
    3
    3



























    s
    6/45
    4
    3
    3
    3
    3
    3
    3



























    a
    4/45
    3
    3
    3
    3
    3
    3






























    h
    3/45
    3
    3
    2
    2
    2
    2






























    m
    3/45
    3
    2
    2
    2
    2

































    t
    3/45
    2
    2
    2
    2
    2

































    i
    2/45
    2
    2
    2
    2




































    r
    2/45
    2
    2
    2
    2




































    u
    2/45
    2
    2
    2







































    b
    1/45
    1
    1
    1







































    c
    1/45
    1
    1










































    l
    1/45
    1
    1










































    d
    1/45
    1













































    o
    1/45
    1













































    q
    1/45
















































    y
    1/45






















































    Примечание: все числа в столбцах «шаг 1 – 15» делятся на 45

    Результаты кодирования по методу Хаффмена заносим в таблицу 3.

    Таблица 3 - Результат кодирования по методу Хаффмена

    №
    символ
    Pi
    Li
    PiLi
    Код

    1


    7/45
    3
    21/45
    001

    2
    e
    6/45
    3
    18/45
    011

    3
    s
    6/45
    3
    18/45
    010

    4
    a
    4/45
    3
    12/45
    111

    5
    h
    3/45
    4
    12/45
    0001

    6
    m
    3/45
    4
    12/45
    1001

    7
    t
    3/45
    4
    12/45
    1000

    8
    i
    2/45
    4
    8/45
    1011

    9
    r
    2/45
    5
    10/45
    00001

    10
    u
    2/45
    5
    10/45
    00000

    11
    b
    1/45
    5
    5/45
    10101

    12
    c
    1/45
    5
    5/45
    11011

    13
    l
    1/45
    5
    5/45
    11010

    14
    d
    1/45
    5
    5/45
    11001

    15
    o
    1/45
    5
    5/45
    11000

    16
    q
    1/45
    6
    6/45
    101001

    17
    y
    1/45
    6
    6/45
    101000







    ∑Pi=1



    M L(x)=3.777778




    Для получения кодов для каждого символа построим дерево кодирования Хаффмана. На рисунке 1 числами от 1 до 16 (включительно) показана последовательность выполнения построения дерева.



    Рисунок 1 - Кодовое дерево
    Средняя длина сообщения, кодирующего заданную последовательность, равна:

    ML(x)=∑Li*pi=21/45+2*18/45+4*12/45+8/45+2*10/45+5*5/45+2*6/45=3.777778
    Выводы: В данной работе рассмотрен способ эффективного кодирования информации с использованием методик Хаффмена.

    Контрольные вопросы

    1. Какова суммарная вероятность всех символов, участвующих в кодировании по методу Хаффмена?

    2. Сколько раз кодеру Хаффмена необходимо просматривать сжимаемый текст для получения окончательного результата?

    3. Может ли среднее количество бит на единицу сообщения для кодирования по методу Хаффмена быть меньше энтропии сообщения? Почему?

    4. Нужно ли при кодировании по методу Хаффмена кроме сжатого сообщения передавать какую-либо дополнительную информацию? Поясните ответ.

    5. Какой вариант сжатия – обратимое или необратимое – реализует алгоритм Хаффмена?

    6. Почему кодирование по Хаффмену называется префиксным?

    Ответы на контрольные вопросы


    1. Суммарная вероятность всех символов, участвующих в кодировании по методу Хаффмена, равна1.

    2. (n-1) раз, где n-количество сжимаемых символов.

    3. Доказано, что среднее количество бит, приходящихся на одно кодируемое значение дискретной случайной величины, не может быть меньшим, чем энтропия этой дискретной случайной величины.

    4. Для декодирования необходимо иметь таблицы вероятностей для каждого типа сжимаемых данных.

    5. Рассматривается обратимое сжатие или сжатие без наличия помех, где первоначальный текст может быть в точности восстановлен из сжатого состояния.

    6. Построенный код каждого символа данного текста не совпадает с началом более длинной комбинации. коды, в которых никакое кодовое слово не является префиксом любого другого кодового слова. Эти коды имеют переменную длину.

    Литература

    1. Huffman D. A Method for the Construction of Minimum-Redundancy Codes. Proceedingsof IRE, vol.40, N9, pp.1098-1101, September 1952.

    2. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. – М.: МЦНМО, 2001. – 960 с.

    написать администратору сайта