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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 33, средняя оценка - 4.94
Rixard
0 / 0 / 0
Регистрация: 14.07.2011
Сообщений: 4
#1

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

19.07.2011, 00:53. Просмотров 4179. Ответов 8
Метки нет (Все метки)

Здравствуйте!

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

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

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

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

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

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

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

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

и т.д.

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

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

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

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

Во общем надеюсь я смог описать проблему, и буду надеяться что вы мне поможете.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
ValeryS
Модератор
6508 / 4974 / 459
Регистрация: 14.02.2011
Сообщений: 16,476
19.07.2011, 00:56     Двоичный вывод (алгоритм Шеннона Фано) #2
unsignet char
BYTE
один байт меньше не получится
Jupiter
Каратель
Эксперт С++
6549 / 3969 / 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
Каратель
Эксперт С++
6549 / 3969 / 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
Эксперт С++
1903 / 1435 / 109
Регистрация: 29.05.2011
Сообщений: 2,989
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++
Реализовать алгоритм Шеннона-Фано C++
Метод Шеннона-Фано и контейнер Map C++

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

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

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