Форум программистов, компьютерный форум CyberForum.ru

Двоичный вывод (алгоритм Шеннона Фано) - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 33, средняя оценка - 4.94
Rixard
0 / 0 / 0
Регистрация: 14.07.2011
Сообщений: 4
19.07.2011, 00:53     Двоичный вывод (алгоритм Шеннона Фано) #1
Здравствуйте!

У меня вопрос по поводу реализации алгоритма Шеннона Фано.

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

Но проблема в следующем. Как хранить двоичные числа**???

Постараюсь описать проблему подробней.

например после построения дерева у символа "а" получилась такая последовательность 1101.
Я не знаю как правильно сохранить этот результат.Пока что я сохраняю его как число в переменной int.
1101 = 13

так что символу "а" у меня соответствует число 13.

в конечном итоге получается такая таблица:

a : 13
b : 0
c: 1
d : 28
.
.
.
g : 124

и т.д.

затем я заменяю последовательность символов этими числами.И у меня получается последовательность чисел соответствующая заданному тексту.

А теперь вопрос, как из этого получить файл??

если просто записать числа, то каждое число весит 4 байта поэтому размер текста только увеличивается в четыре раза.( в идеале 0 и 1 должны весить 1 бит, 2 и 3 два бита и т.д., но на практике все числа весят одинаково 4 байта)

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

Во общем надеюсь я смог описать проблему, и буду надеяться что вы мне поможете.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
19.07.2011, 00:53     Двоичный вывод (алгоритм Шеннона Фано)
Посмотрите здесь:

Алгоритм сжатия методом Шеннона-Фано C++
Метод Шеннона фано C++
Метод Шеннона-Фано C++
C++ Реализация алгоритма кодирования Шеннона-Фано
Метод архивации Шеннона-Фано C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
ValeryS
Модератор
6377 / 4843 / 442
Регистрация: 14.02.2011
Сообщений: 16,057
19.07.2011, 00:56     Двоичный вывод (алгоритм Шеннона Фано) #2
unsignet char
BYTE
один байт меньше не получится
Jupiter
Каратель
Эксперт C++
6543 / 3963 / 226
Регистрация: 26.03.2010
Сообщений: 9,273
Записей в блоге: 1
Завершенные тесты: 2
19.07.2011, 01:05     Двоичный вывод (алгоритм Шеннона Фано) #3
Цитата Сообщение от Rixard Посмотреть сообщение
А теперь вопрос, как из этого получить файл??
записывайте биты в строку, но лучше в вектор или динамический массив int-ов
ну или забейте на алгоритм и bitset вам в помощь
C++
1
2
3
4
5
6
7
8
9
#include <fstream>
#include <bitset>
 
int main ()
{
    std::ofstream file("1.txt");
    file << std::bitset<8>(10);
    return 0;
}
Rixard
0 / 0 / 0
Регистрация: 14.07.2011
Сообщений: 4
19.07.2011, 01:22  [ТС]     Двоичный вывод (алгоритм Шеннона Фано) #4
Цитата Сообщение от Maxwe11 Посмотреть сообщение
записывайте биты в строку, но лучше в вектор или динамический массив int-ов
ну или забейте на алгоритм и bitset вам в помощь
C++
1
2
3
4
5
6
7
8
9
#include <fstream>
#include <bitset>
 
int main ()
{
    std::ofstream file("1.txt");
    file << std::bitset<8>(10);
    return 0;
}
Ваш файл с одним числом "10" весит 8 байт
а мне нужно чтоб файл с одним числом 10 весил 4 бита.

Если я сделаю массив int-ов то боюсь будет то же самое.

Добавлено через 4 минуты
Цитата Сообщение от ValeryS Посмотреть сообщение
unsignet char
BYTE
один байт меньше не получится
http://compression.ru/download/artic...nnon-fano.html

вот здесь описан Алгоритм Шенно Фано. и там есть такой момент

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

длиной в 39 бит. Учитывая, что оргинал имел длину равную 136 бит, получаем коэффициент сжатия ~28% - не так уж и плохо."


Вот как они сделали такой вывод??У меня это весит 39 байт.
Jupiter
Каратель
Эксперт C++
6543 / 3963 / 226
Регистрация: 26.03.2010
Сообщений: 9,273
Записей в блоге: 1
Завершенные тесты: 2
19.07.2011, 01:30     Двоичный вывод (алгоритм Шеннона Фано) #5
Цитата Сообщение от Rixard Посмотреть сообщение
а мне нужно чтоб файл с одним числом 10 весил 4 бита.
4 бита он никак не будет весить, минимум 4 байта, пжлс, хозяин барин
C++
1
2
3
4
5
6
7
8
9
#include <fstream>
#include <bitset>
 
int main ()
{
    std::ofstream file("1.txt");
    file << std::bitset<4>(10);
    return 0;
}
Rixard
0 / 0 / 0
Регистрация: 14.07.2011
Сообщений: 4
19.07.2011, 01:42  [ТС]     Двоичный вывод (алгоритм Шеннона Фано) #6
Цитата Сообщение от Maxwe11 Посмотреть сообщение
4 бита он никак не будет весить, минимум 4 байта, пжлс, хозяин барин
Как тогда вообще возможно реализовать этот алгоритм??
grizlik78
Эксперт С++
 Аватар для grizlik78
1884 / 1416 / 102
Регистрация: 29.05.2011
Сообщений: 2,961
19.07.2011, 02:06     Двоичный вывод (алгоритм Шеннона Фано) #7
Цитата Сообщение от Rixard Посмотреть сообщение
в идеале 0 и 1 должны весить 1 бит, 2 и 3 два бита и т.д.
В дереве не может быть одновременно однобитного нуля и однобитной единицы. Их не удастся на приёме выделить из потока. Однобитным может быть только 1 символ.

Цитата Сообщение от Rixard Посмотреть сообщение
Как тогда вообще возможно реализовать этот алгоритм??
Очевидно упаковывая битовые последовательности в байты.
Rixard
0 / 0 / 0
Регистрация: 14.07.2011
Сообщений: 4
19.07.2011, 11:03  [ТС]     Двоичный вывод (алгоритм Шеннона Фано) #8
Цитата Сообщение от grizlik78 Посмотреть сообщение
В дереве не может быть одновременно однобитного нуля и однобитной единицы. Их не удастся на приёме выделить из потока. Однобитным может быть только 1 символ.


Очевидно упаковывая битовые последовательности в байты.


Да вы правы.Спасибо.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
27.12.2011, 17:12     Двоичный вывод (алгоритм Шеннона Фано)
Еще ссылки по теме:

C++ Алгоритм шеннона фано
Алгоритм Шеннона-Фано C++
Кодирование Шеннона-Фано C++

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

Или воспользуйтесь поиском по форуму:
OK
Сообщений: n/a
27.12.2011, 17:12     Двоичный вывод (алгоритм Шеннона Фано) #9
Доброго времени суток!Наткнулся на форуме на запись об алгоритме шенона-фано. У вас получилась его реализация?
Yandex
Объявления
27.12.2011, 17:12     Двоичный вывод (алгоритм Шеннона Фано)
Ответ Создать тему
Опции темы

Текущее время: 12:44. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru