Алгоритм Шеннона — Фано

Кодирование Хаффмана

Один из первых алгоритмов эффективного кодирования информации был предложен Д. А. Хаффманом в 1952 году. Идея алгоритма состоит в следующем: зная вероятности символов в сообщении, можно описать процедуру построения кодов переменной длины, состоящих из целого количества битов. Символам с большей вероятностью ставятся в соответствие более короткие коды. Коды Хаффмана обладают свойством префиксности (т.е. ни одно кодовое слово не является префиксом другого), что позволяет однозначно их декодировать.

Классический алгоритм Хаффмана на входе получает таблицу частот встречаемости символов в сообщении. Далее на основании этой таблицы строится дерево кодирования Хаффмана (Н-дерево). ^[1]

1. Символы входного алфавита образуют список свободных узлов. Каждый лист имеет вес, который может быть равен либо вероятности, либо количеству вхождений символа в сжимаемое сообщение.

2. Выбираются два свободных узла дерева с наименьшими весами.

3. Создается их родитель с весом, равным их суммарному весу.

4. Родитель добавляется в список свободных узлов, а два его потомка удаляются из этого списка.

5. Одной дуге, выходящей из родителя, ставится в соответствие бит 1, другой — бит 0.

6. Шаги, начиная со второго, повторяются до тех пор, пока в списке свободных узлов не останется только один свободный узел. Он и будет считаться корнем дерева.

Источник: http://ru.wikipedia.org/wiki/Код_Хаффмана

Формула энтропии

Источник: http://ru.wikipedia.org/wiki/Информационная_энтропия

Алгоритм Шеннона — Фано

1. Символы первичного алфавита m₁ выписывают в порядке убывания вероятностей.

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

3. В префиксном коде для первой части алфавита присваивается двоичная цифра «0», второй части — «1».

4. Полученные части рекурсивно делятся и их частям назначаются соответствующие двоичные цифры в префиксном коде.

Источник: http://ru.wikipedia.org/wiki/Алгоритм_Шеннона_-_Фано

Постановка задачи.

Дан кусок текста. Для успешного выполнения задания необходимо:

1. Определить вероятность появления в сообщении каждого символа по заданному примеру (учитывать пробел, регистр и знаки препинания). Определить оптимальное количество бит, которое нужно затратить для кодировки данного сообщения
2. Построить дерево Хаффмана. Присвоить двоичные коды сообщениям. Определить количество бит в сообщении, закодированном этими кодами. Оценить избыточность кода.
3. Построить код Шеннона-Фано. Определить количество бит, полученное с помощью этого кода. Оценить избыточность кода.
4. Заархивировать текстовый файл с заданием, оценить степень сжатия.

Пошаговое решение.

1) Определил частоту встречаемости каждого символа.

Вычислил вероятность появления каждого символа.

По полученным данным вычислил энтропию и оптимальное количество бит, необходимо для того чтобы закодировать сообщение.

Результаты:

общее число симоволов = 10341

space вероятность.18499 частота= 1913

e вероятность.09873 частота= 1021

t вероятность.07098 частота= 734

a вероятность.06411 частота= 663

h вероятность.05957 частота= 616

o вероятность.05763 частота= 596

n вероятность.05377 частота= 556

i вероятность.04642 частота= 480

s вероятность.04593 частота= 475

r вероятность.04042 частота= 418

d вероятность.03965 частота= 410

l вероятность.03269 частота= 338

u вероятность.02263 частота= 234

w вероятность.02089 частота= 216

m вероятность.0176 частота= 182

g вероятность.01673 частота= 173

f вероятность.01528 частота= 158

y вероятность.01422 частота= 147

c вероятность.01334 частота= 138

, вероятность.01238 частота= 128

. вероятность.01054 частота= 109

b вероятность.00986 частота= 102

k вероятность.00851 частота= 88

p вероятность.00832 частота= 86

v вероятность.006 частота= 62

I вероятность.00319 частота= 33

' вероятность.0029 частота= 30

- вероятность.00271 частота= 28

H вероятность.00232 частота= 24

A вероятность.00184 частота= 19

? вероятность.00174 частота= 18

z вероятность.00145 частота= 15

M вероятность.00135 частота= 14

S вероятность.00106 частота= 11

x вероятность.00097 частота= 10

T вероятность.00097 частота= 10

W вероятность.00097 частота= 10

R вероятность.00087 частота= 9

B вероятность.00087 частота= 9

Y вероятность.00087 частота= 9

q вероятность.00068 частота= 7

! вероятность.00058 частота= 6

L вероятность.00048 частота= 5

E вероятность.00048 частота= 5

N вероятность.00048 частота= 5

; вероятность.00039 частота= 4

j вероятность.00039 частота= 4

C вероятность.00039 частота= 4

D вероятность.00029 частота= 3

O вероятность.00019 частота= 2

J вероятность.0001 частота= 1

: вероятность.0001 частота= 1

Q вероятность.0001 частота= 1

F вероятность.0001 частота= 1

энтропия = 4.305131

оптимальное количество бит на данное сообщение = 44519.36(энтропия*n)

2) Посадил Дерево Хаффмана:

3)Получил код Хаффмана

space 001

e 101

t 0101

a 0110

h 0111

o 1111

n 1110

i 1101

s 1001

r 00001

d 00011

l 01001

u 10001

w 000001

m 000101

g 010000

f 010001

y 110001

c 110011

, 110011

. 100001

b 0000001

k 0001000

p 0001001

v 1000001

I 11000011

' 10000001

- 000000000

H 000000011

A 110000000

? 110000100

z 100000000

M 100000001

S 0000000010

x 1100000010

T 1100000011

W 1100001010

R 1100001011

B 1100000111

Y 1100000110

q 00000000110

! 00000000111

L 00000001010

E 00000001011

N 00000001001

; 11000001011

j 11000001010

C 11000001001

D 000000010001

O 110000010001

J 1100000100000

: 1100000100001

Q 0000000100000

F 0000000100001

4) Умножив длину каждого символа (в битах) на его частоту встречаемости, получим количество байт, необходимое для кодирования данного сообщения.

Результат: 44951 бит.

Чтобы найти избыточность кода, вычтем из этого значения оптимальное количество байт.

Результат: 432.3 бита.

5)Программным методом получил код Шеннона-Фано

Результат:

space 000

e 001

t 011

a 0101

h 0100

o 1100

n 1101

i 1111

s 11101

r 11100

d 10100

l 10101

u 10111

w 101101

m 101100

g 100100

f 100101

y 100111

c 1001101

, 1001100

. 1000100

b 1000101

k 1000111

p 1000110

v 10000100

I 10000101

' 10000111

- 100001101

H 100001100

A 100000100

? 100000101

z 1000001110

M 1000001111

S 1000001101

x 1000001100

T 1000000100

W 1000000101

R 1000000111

B 10000001101

Y 10000001100

q 10000000100

! 10000000101

L 10000000111

E 10000000110

N 10000000010

; 100000000111

j 100000000110

C 100000000010

D 100000000011

O 1000000000010

J 1000000000011

: 1000000000001

Q 10000000000001

F 10000000000000

Фрагмент программы (на VB), с помощью которой был получен код:

______________________________________________________________

Public Sub delenie(ByVal l As List(Of type_mas))

Dim polovina1 As New List(Of type_mas)

Dim polovina2 As New List(Of type_mas)

If l.Count > 1 Then

Dim i, schet_nach, schet_kon, kol1, kol2 As Integer

schet_nach = 0

schet_kon = l.Count - 1

kol1 = 0

kol2 = 0

While kol1 + kol2 <> l.Count ''сам процесс деления

If sum(polovina1) <= sum(polovina2) Then

polovina1.Add(l(schet_nach))

kol1 = kol1 + 1

schet_nach = schet_nach + 1

Else

polovina2.Add(l(schet_kon))

kol2 = kol2 + 1

schet_kon = schet_kon - 1

End If

End While

add_code("0", polovina1)

add_code("1", polovina2)

delenie(polovina1)

delenie(polovina2)

End If

End Sub

Public Sub add_code(ByVal s As String, ByVal listik As List(Of type_mas))

Dim t As type_mas

For i = 0 To listik.Count - 1

For k = 0 To start.Count - 1

If listik(i).znach = start(k).znach Then

t = start(k)

t.code = t.code + s

start.RemoveAt(k)

start.Insert(k, t)

End If

Next

Next

End Sub

Function sum(ByVal listik As List(Of type_mas)) As Integer

Dim rez As Integer = 0

For k = 0 To listik.Count - 1

rez = rez + listik(k).chastota

Next

Return rez

End Function

_____________________________________________________________________

6) Умножив длину каждого символа (в битах) на его частоту встречаемости, получим количество байт, необходимое для кодирования данного сообщения.

Результат: 45193 бита.

Чтобы найти избыточность кода, вычтем из этого значения оптимальное количество байт.

Результат: 673.64 бита.

7) Заархивировал текстовый файл «13.txt».

Степень сжатия = ((размер до архивации) – (размер после архивации))/(размер до архивации)*100

Результат: n1=10755; n2 = 4800; степень сжатия = 5955/10755*100% = 55 %

ВЫВОД:

В ходе выполнения данной работы я ознакомился с 2-мя методами кодирования сообщений и выяснил, что алгоритм Шеннона-Фано не гарантирует получения оптимального (наименее избыточного) кода, что связано с тем, что Выбор разбиения на уровне n может ухудшить варианты разбиения на следующем уровне (n + 1) и привести к неоптимальности кода в целом

Поиск по сайту: