Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
гость
0 / 0 / 0
Регистрация: 17.04.2015
#1

Алгоритм сжатия методом Шеннона-Фано - C++

10.04.2007, 10:04. Просмотров 15260. Ответов 6
Метки нет (Все метки)

Народ, нужна помощь в поиске кода реализующего алгоритм кодирования и декодирования сообщения методом Шеннона-Фано на Си. Заранее благодарен.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
10.04.2007, 10:04
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Алгоритм сжатия методом Шеннона-Фано (C++):

Алгоритм Шеннона-Фано - C++
Помогите, реализовать Алгоритм Шеннона-Фано на С ++, так чтобы мы вводили сроку из символов, а на выходе получали закодированную сроку из...

Алгоритм шеннона фано - C++
Помогите реализовать алгоритм шеннона фано, курсовую скоро сдавать, а у меня ничего не готово, очень нужна помощь!!!!

Алгоритм Шеннона-Фано - C++
Приветствую всех в этой теме. Создаю архиватор по методу Шеннона-Фано. И трудность возникла в программной реализации получения кодовых...

Реализовать алгоритм Шеннона-Фано - C++
есть ли кого-то алгоритм шеннона-фано на c++ или java ? нужен код

Двоичный вывод (алгоритм Шеннона Фано) - C++
Здравствуйте! У меня вопрос по поводу реализации алгоритма Шеннона Фано. В соответствие с алгоритмом надо построить бинарное...

Сжатие методом Шеннона-Фано (Pascal -> C++) - C++
Есть код на pascal может кто-нибудь помочь перевести на с++ ? uses crt; var c:char; s,s1,s2:string; i,n,j,j1:byte; ...

6
WADDICK
0 / 0 / 0
Регистрация: 27.09.2006
Сообщений: 47
16.07.2007, 11:37 #2
Кодирование Шеннона-Фано является одним из самых первых алгоритмов сжатия, который впервые сформулировали американские учёные Шеннон (Shannon) и Фано (Fano). Данный метод сжатия имеет большое сходство с кодированием Хаффмана, которое появилось на несколько лет позже. Главная идея этого метода - заменить часто встречающиеся символы более короткими кодами, а редко встречающиеся последовательности более длинными кодами. Таким образом, алгоритм основывается на кодах переменной длины. Для того, чобы декомпрессор впоследствии смог раскодировать сжатую последовательность, коды Шеннона-Фано должны обладать уникальностью, то есть, не смотря на их переменную длину, каждый код уникально определяет один закодированый символ и не является префиксом любого другого кода.
Рассмотрим алгоритм вычисления кодов Шеннона-Фано (для наглядности возьмём в качестве примера последовательность 'aa bbb cccc ddddd'). Для вычисления кодов, необходимо создать таблицу уникальных символов сообщения c(i) и их вероятностей p(c(i)), и отсортировать её в порядке невозрастания вероятности символов.

c(i) p(c(i))
d 5 / 17
c 4 / 17
space 3 / 17
b 3 / 17
a 2 / 17

Далее, таблица символов делится на две группы таким образом, чтобы каждая из групп имела приблизительно одинаковую частоту по сумме символов. Первой группе устанавливается начало кода в '0', второй в '1'. Для вычисления следующих бит кодов символов, данная процедура повторяется рекурсивно для каждой группы, в которой больше одного символа. Таким образом для нашего случая получаем следующие коды символов:

символ код
d 00
c 01
space 10
b 110
a 111

Длина кода s(i) в полученной таблице равна int(-lg p(c(i))), если сиволы удалость разделить на группы с одинаковой частотой, в противном случае, длина кода равна int(-lg p(c(i))) + 1.

int(-lg p(c(i))) <= s(i) <= int(-lg p(c(i))) + 1

Успользуя полученную таблицу кодов, кодируем входной поток - заменяем каждый символ соответствующим кодом. Естественно для расжатия полученной последовательности, данную таблицу необходимо сохранять вместе со сжатым потоком, что является одним из недостатков данного метода. В сжатом виде, наша последовательность принимает вид:

111111101101101101001010101100000000000

длиной в 39 бит. Учитывая, что оргинал имел длину равную 136 бит, получаем коэффициент сжатия ~28% - не так уж и плохо.
Глядя на полученную последовательность, возникает вопрос: "А как же теперь это расжать ?". Мы не можем, как в случае кодирования, заменять каждые 8 бит входного потока, кодом переменной длины. При расжатии нам необходимо всё сделать наоборот - заменить код переменной длины символом длиной 8 бит. В данном случае, лучше всего будет использовать бинарное дерево, листьями которого будут являтся символы (аналог дерева Хаффмана).
Кодирование Шеннона-Фано является достаточно старым методом сжатия , и на сегодняшний день оно не представляет особого практического интереса (разве что как упражнение по курсу структур данных). В большинстве случаев, длина сжатой последовательности, по данному методу, равна длине сжатой последовательности с использованием кодирования Хаффмана. Но на некоторых последовательностях всё же формируются не оптимальные коды Шеннона-Фано, поэтому сжатие методом Хаффмана принято считать более эффективным. Для примера, рассмотрим последовательность с таким содержанием символов: 'a' - 14, 'b' - 7, 'c' - 5, 'd' - 5, 'e' - 4. Метод Хаффмана сжимает её до 77 бит, а вот Шеннона-Фано до 79 бит.

символ код Хаффмана код Шеннона-Фано
a 0 00
b 111 01
c 101 10
d 110 110
e 100 111
Кстати, в одном источнике (не буду указывать каком), эту последовательность сжали методом Шеннона-Фано до 84 бит, а методом Хаффмана до тех же 77. Такие отличаи в степени сжатия возникают из-за нестрогого определения способа деления символов на группы.
Как же мы делили на группы ? Достаточно просто:

1. вероятноть первой группы (p1) и второй (p2) равна нулю;
2. p1 <= p2 ?
* да: добавить в первую группу символ с начала таблицы;
* нет: добавить во вторую группу символ с конца таблицы;
3. если все символы разделены на группы, то завершить алгоритм, иначе перейти к шагу 2.

Из-за такой неопределённости у некоторых людей возникают даже такие мысли: "... программа иногда назначает некоторым символам ..." и так далее - рассуждения о длине кодов. Если вы не пишете AI, то такое понятие, как "программа иногда" что-то делает, звучит смешно. Правильно реализованный алгоритм - работает строго опеределённо.
0
Вложения
Тип файла: zip tiger_shannon-fano.zip (25.0 Кб, 1029 просмотров)
banderos_a
0 / 0 / 0
Регистрация: 15.07.2007
Сообщений: 1
18.07.2007, 13:04 #3
Попробуй помскать на сервере Корбины. Там что-то вроде я такое встречал. Довольно таки полный учебник по этому методу.
0
Warrusha
0 / 0 / 0
Регистрация: 17.03.2009
Сообщений: 1
20.03.2009, 13:15 #4
http://www.algolist.ncstu.ru/compress/standard/shannon_fano.php

это тоже достаточно полное и понятное описание метода
0
*.f90
0 / 0 / 0
Регистрация: 23.01.2012
Сообщений: 13
30.01.2012, 20:35 #5
Цитата Сообщение от WADDICK Посмотреть сообщение
Как же мы делили на группы ? Достаточно просто:

1. вероятноть первой группы (p1) и второй (p2) равна нулю;
2. p1 <= p2 ?
* да: добавить в первую группу символ с начала таблицы;
* нет: добавить во вторую группу символ с конца таблицы;
3. если все символы разделены на группы, то завершить алгоритм, иначе перейти к шагу 2.
не понял откуда взялись p1 и p2 ?
ведь у нас есть только 2 массива p() и c() (вер-ти и символы)
0
talis
792 / 544 / 37
Регистрация: 11.05.2010
Сообщений: 1,298
Записей в блоге: 1
01.02.2012, 19:50 #6
Цитата Сообщение от *.f90 Посмотреть сообщение
не понял откуда взялись p1 и p2 ?
ведь у нас есть только 2 массива p() и c() (вер-ти и символы)
*.f90, надо понимать, p1 - это суммарная вероятность первой группы, а p2 - суммарная вероятность второй группы.

Далее, таблица символов делится на две группы таким образом, чтобы каждая из групп имела приблизительно одинаковую частоту по сумме символов. Первой группе устанавливается начало кода в '0', второй в '1'.
1
*.f90
0 / 0 / 0
Регистрация: 23.01.2012
Сообщений: 13
09.02.2012, 15:04 #7
Цитата Сообщение от talis Посмотреть сообщение
*.f90, надо понимать, p1 - это суммарная вероятность первой группы, а p2 - суммарная вероятность второй группы.
не совсем понял... т.е.
1. вероятноть первой группы (p1) и второй (p2) равна нулю;
2. p1 <= p2 ?
* да: p1=p1+p(с начала таблицы) + символ с начала таблицы
* нет: p2=p2+p(с конца таблицы) + символ с конца таблицы
3. пункт говорит, что делается всё в цикле чтоб просмотреть все p и занести символы в 2 таблицы, так ?
0
09.02.2012, 15:04
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
09.02.2012, 15:04
Привет! Вот еще темы с ответами:

Кодирование Шеннона-Фано - C++
Окей мы посчитали вероятности символов и прочие штуки.. Далее нужно создать таблицу уник. символов.. Сделали.. отсортировали... В...

Метод Шеннона фано - C++
Помогите пожалуста реализовать самый простой способ этого алгоритма сжатия на С/С++ Добавлено через 14 минут с задаными ...

Метод Шеннона-Фано - C++
метод Шеннона-Фано, рассортировал вероятности по убыванию, а после не могу ничего сделать(( помогите плиз, там надо пополам делить и 0 или...

Метод архивации Шеннона-Фано - C++
Не подскажите,может есть у кого исходник кода архивации(сжатия и восстановления) методом Шеннона-Фано на С++?


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
7
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.