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

Равномерное кодирование - C++

Восстановить пароль Регистрация
 
faustmangos
3 / 3 / 0
Регистрация: 02.10.2013
Сообщений: 34
02.10.2013, 21:08     Равномерное кодирование #1
Скажу коротко, есть задание : программа должна сжимать файлы текстовые и бинарные с помощью равномерного кодирования. И если с исходным алфавитом текстового файла все еще как то ясно, то что делать с бинарным, как производить разбивку битов , что бы получить исходный алфавит без избытка и чтобы кодирование вышло эффективным?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
02.10.2013, 21:08     Равномерное кодирование
Посмотрите здесь:

C++ Кодирование, C++
C++ Кодирование
Кодирование файла C++
Кодирование и декодирование C++
C++ Равномерное дополнение строки пробелами
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
tony_pershin
16 / 16 / 1
Регистрация: 05.03.2013
Сообщений: 36
02.10.2013, 21:16     Равномерное кодирование #2
Бинарные данные чаще всего кодируют, используя base64: http://ru.wikipedia.org/wiki/Base64. Легко и быстро реализуется.
faustmangos
3 / 3 / 0
Регистрация: 02.10.2013
Сообщений: 34
02.10.2013, 21:29  [ТС]     Равномерное кодирование #3
Не , эта штука не подойдет она применяется в транспортных целях и не сжимает файл
tony_pershin
16 / 16 / 1
Регистрация: 05.03.2013
Сообщений: 36
02.10.2013, 21:53     Равномерное кодирование #4
Справедливо, пропустил слово "сжимать", когда читал. А чем обыкновенный run-length encoding не устраивает? Блоки по 8 бит, например. Можно поэкспериментировать на dll-ках всяких
faustmangos
3 / 3 / 0
Регистрация: 02.10.2013
Сообщений: 34
02.10.2013, 22:36  [ТС]     Равномерное кодирование #5
Почитал про RLE спасибо за инфу, но вот вопрос как раз заключался в том какой размер блоков брать что бы эффективность кодирования была высокая, тоесть ты считаешь что 8 всегда?

Добавлено через 24 минуты
Да и впринципе это уже не очень то и на равномерное кодирование похоже, т.к. у равномерного кодирования есть своя теоритическая основа , т.е. есть алфавит A есть B и они там связаны по элементно а тут получается алфавит B будет дополнением к A, т.е. тупо в B хранятся элементы А + их число повторов, тогда например в кодовой таблице будет соотв. 10000001 -> 10000001[закодировать число повторов] и поменятеся алгоритм раскодировки который не соотв. теории равномерного кодирования, где идет тупо замена, а тут мне придется работать побитово доставая вначале первые 8 битов а потом доставая биты повторений
тема интересная, но боюсь препод не примет такой способ
tony_pershin
16 / 16 / 1
Регистрация: 05.03.2013
Сообщений: 36
03.10.2013, 13:15     Равномерное кодирование #6
Вообще сжимать бинарные данные равномерным кодированием странновато. Ну да ладно.
Как мне кажется, задача не сильно отличается от текстовой. В текстовой тебе известен размер элемента алфавита (8 бит). Я бы попробовал такой же размер элемента для бинарного файла, составил бы множество уникальных элементов, содержащихся в бинаре, и посмотрел бы какой получается выигрыш. Общего алфавита, ты, очевидно не получишь (если мощность полученного множества равна 2^8, то ты ничего не выигрываешь). И это логично, ведь ты пытаешься задать однозначное отображение одного множества в другое, ниже энтропии тебе не опуститься. Так что возможен только такой динамический путь. Вообще это интересный вопрос. Мне кажется, что по этой причине постановка задачи некорректна, но возможно я и не прав. Было бы интересно услышать какие-нибудь контраргументы.
faustmangos
3 / 3 / 0
Регистрация: 02.10.2013
Сообщений: 34
03.10.2013, 17:08  [ТС]     Равномерное кодирование #7
Да да да. В голове вертится, что-то подобное о чем ты написал, но в задании четко написано, что программа должна именно "сжимать". Вот наткнулся на теорию http://femto.com.ua/articles/part_1/1668.html оптимального равномерного кодирования(заголовок там чуть ниже по статье), "общие черты" более-менее понятны, но может ты больше поймешь, там написано что можно сжимать аж до 80% (хоть и специфичные файлы наподобие массивов данных в банках и тд.).

Добавлено через 3 минуты
И еще я перечитал тему вопроса извиняюсь тут "исходный алфавит без избытка" глупо звучит) наоборот получить исходный а из-него как то сделать без избытка новый

Добавлено через 13 минут
"Предположим, что множество всех последовательностей длиной n из сообщений источника разбита на два подмножества. Первое из них образовано всеми теми последовательностями (блоками длиной n), которые сопоставлены с кодовыми словами взаимно однозначно. Это подмножество называется множеством однозначно кодируемых и декодируемых блоков. Второе подмножество образовано всеми остальными блоками, каждому из которых сопоставляется одно и тоже кодовое слово. (Можно сопоставлять и различные кодовые слова. Это не существенно. Существенно лишь, что эти кодовые слова использованы для представления однозначно кодируемых и декодируемых блоков. В дальнейшем мы будем употреблять более короткое выражение – однозначно (неоднозначно) кодируемые блоки.) Последнее подмножество называется множеством неоднозначно кодируемых и декодируемых блоков. Все кодовые слова имеют одинаковую длину m, которая определяется числом M кодовых слов: m – наименьшее целое, удовлетворяющее неравенству Dm ≥M, где D – объем кодового алфавита. При кодировании последовательность сообщений на выходе источника разбирается на блоки длиной n, каждому блоку кодер сопоставляет соответствующее кодовое слово.

Описанный метод кодирования дискретного источника мы будем называть равномерным кодированием
."


Вот еще тоже самое, что я кинул тебе в статье, надо как-то с этим разобраться
tony_pershin
16 / 16 / 1
Регистрация: 05.03.2013
Сообщений: 36
03.10.2013, 17:34     Равномерное кодирование #8
Идея ясна, она отличается от того, что я выше написал всего лишь двумя моментами. Во-первых, предполагается, что p != q. Как следствие, получается этот "рабочий" словарь. И как следствие, второй момент -- неоднозначность. Т.е. все слова, не входящие в рабочий словарь, они ставят в соответствие одному (!) кодовому слову. Ты же говоришь об общем подходе. Общий -- значит p == q, а значит рабочий словарь равен кодовому.
Такого сжатия в БД достигают за счет того, что они хорошо знают этот рабочий словарь. Представь, что у тебя есть таблица типа key-> value, в которой так получается, что value принимают всего пару значений типа 287453, 234870 и 294852. Сразу становится очевидно, за счет чего происходит сжатие). Об общем алгоритме здесь речи не идет.
faustmangos
3 / 3 / 0
Регистрация: 02.10.2013
Сообщений: 34
03.10.2013, 18:08  [ТС]     Равномерное кодирование #9
Так это по-идее и есть общий подход, смотри мне написано в задании "с помощью равномерного кодирования", а тут в определении написано Описанный метод кодирования дискретного источника мы будем называть равномерным кодированием.

Добавлено через 15 минут
ты хочешь сказать если я возьму например слова по 8 бит, и сделаю то, что здесь написано то моему файлу крындздец прийдет? Из-за того , что я не знаю как он устроен и , что можно сжимать так, а что нет?
tony_pershin
16 / 16 / 1
Регистрация: 05.03.2013
Сообщений: 36
03.10.2013, 18:23     Равномерное кодирование #10
Это общий подход, но не общий алгоритм. Тут просто объяснено, что теоретически, при p != q и большом количестве слов, вероятность появления одних слов сильно выше, чем других. Так давайте только их и кодировать! Вот и весь подход. Он логичен, ведь действительно, если p(1) = p = 0.75, p(0) = q = 0.25, то вероятность, что появится слово 0000 0000 равна 1/100000 (если p = q = 0.5, то 1/256, почувствуй разницу), так какой смысл его кодировать, если она вероятнее всего не появится?

Ты можешь это использовать, если это удовлетворяет условию. Однако это кодирование неоднозначно!
faustmangos
3 / 3 / 0
Регистрация: 02.10.2013
Сообщений: 34
03.10.2013, 19:14  [ТС]     Равномерное кодирование #11
Я понял суть, Спасибо.
Может еще к преподу подойду спрошу.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
03.10.2013, 19:16     Равномерное кодирование
Еще ссылки по теме:

Задача на равномерное распределение дам и господ, ошибка сегментации C++
C++ Кодирование Хаффмана
Кодирование Хаффмана C++

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

Или воспользуйтесь поиском по форуму:
tony_pershin
16 / 16 / 1
Регистрация: 05.03.2013
Сообщений: 36
03.10.2013, 19:16     Равномерное кодирование #12
Это в первую очередь надо бы сделать). Если не затруднит, напиши потом, к какому решению пришел.
Yandex
Объявления
03.10.2013, 19:16     Равномерное кодирование
Ответ Создать тему
Опции темы

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