Вероятностный метод сжатия Шеннона-Фано

1.

Вероятностный метод сжатия Шеннона-Фано
Метод Шеннона-Фано является двухпроходным:
- при первом проходе текста:
составляется список всех символов
рассчитывается частота появления каждого символа
определяется код сжатия переменной длины каждого символа
- при втором проходе текста с помощью кода сжатия производится
сжатие текста.

2.

Порядок применения метода сжатия Шеннона-Фано следующий:
1. Составляется список всех символов текста и рассчитывается частота
появления каждого символа

3.

Порядок применения метода сжатия Шеннона-Фано следующий:
2. Составление таблицы Шеннона-Фано
2.1. Символы, встречающиеся в файле, выписываются в столбец в порядке
убывания частоты их появления.
2.2. Все символы разделяют на две подгруппы так, чтобы в каждой из
подгруппы были примерно равные суммы частот символов.
Для символов первой подгруппы первый бит кода устанавливаются
в «0»,
Для символов второй подгруппы первый бит кода устанавливаются
в «1».
2.3. После этого каждую подгруппу делят снова на две подподгруппы так,
чтобы в каждой из подподгруппы были примерно равные суммы частот
символов.
Для символов первой подподгруппы второй бит кода
устанавливаются в «0»,
для символов второй подподгруппы второй бит кода устанавливаются
в «1».
2.4. Процедуру разделения на подгруппы и присвоения следующих бит в код
символа повторяет до тех пор, пока в подгруппе не останется по одному
символу.
2.5. Коды символов, полученные с помощью метода Шеннога-Фано, являются
префиксными и удовлетворяют условию Фано.

4.

Порядок применения метода сжатия Шеннона-Фано следующий:
3. Кодирование текста с помощью полученных символов
Каждый символ текста заменяется соответствующим двоичным кодом

5.

Рассмотрим кодирование фразы:
Мама мыла раму. Раму мыла мама.
(31 символов)
М
1
а
8
м
7
ы
2
л
2
р
1
у
2
Р
1
.
2
пробел 5

6.

Рассмотрим
кодирование фразы:
Мама мыла раму. Раму
мыла мама.
(31 символов)
Cимволы
Частоты
1-й бит
2-й бит
а
8
0
0
00
м
7
0
1
01
пробел
5
1
0
0
ы
2
1
0
1
0
1010
у
2
1
0
1
1
1011
л
2
1
1
0
0
1100
.
2
1
1
0
1
1101
р
1
1
1
1
0
1110
Р
1
1
1
1
1
0
11110
М
1
1
1
1
1
1
11111
3-й бит
4-й бит
5-й бит
Код
100
Проверяем выполнение условий Фано.
Кодируем:
М а м а _ м ы
л
а _ р
а м у
.
_
11111 00 01 00 100 01 1010 1100 00 100 1110 00 01 1011 1101 100
Р
а м у
_ м ы
л
а _ м а м а
.
11110 00 01 1011 100 01 1010 1100 00 100 01 00 01 00 1101

7.

Группируем на тетрады:
В двоичном виде:
1111 1000 1001 0001 1010 1100 0010 0111 0000 1101 1110 1100 1111
0000 1101 1100 0110 1011 0000 1000 1000 1001 101
В 16-ричном виде:
F8 91 AC 27 0D EF 0D C6 B0 88 916101b
Рассчитаем количественные характеристики сжатия текста:
До сжатия:
Число символов в фразе: N=31 символ
Длина кода символа (ASCII): l0=8 (бит)
Общее число бит L0=8*31=248 (бит)
После сжатия:
Общее число бит Lc=4*22+3=91 (бит)
Средняя длина кода символа в битах: lc=91 бит/31=2,94 бит/символ
Коэффициент сжатия:
k=L0/Lc=248/91=2.72
k=l0/lc=8/2.94=2.72