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

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

Войти
Регистрация
Восстановить пароль
 
faustmangos
3 / 3 / 0
Регистрация: 02.10.2013
Сообщений: 34
#1

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

02.10.2013, 21:08. Просмотров 970. Ответов 11
Метки нет (Все метки)

Скажу коротко, есть задание : программа должна сжимать файлы текстовые и бинарные с помощью равномерного кодирования. И если с исходным алфавитом текстового файла все еще как то ясно, то что делать с бинарным, как производить разбивку битов , что бы получить исходный алфавит без избытка и чтобы кодирование вышло эффективным?
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
02.10.2013, 21:08
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Равномерное кодирование (C++):

Равномерное кодирование - C++
Задача такова: Программа должна запускаться с командной строки с темя параметрами: имя входного файла, имя выходного файла и режим работы...

Равномерное дополнение строки пробелами - C++
Всем доброго времени суток.Имеется задача: Дан текст из нескольких строк. Написать функцию, равномерно дополняющую строку пробелами до...

Заполнить массив случайными, равномерное распределёнными числами - C++
Всем привет. Нужно заполнить массив из, ну например, 100 чисел, числами в интервале от 1 до 1000. Причём распределение должно быть...

Задача на равномерное распределение дам и господ, ошибка сегментации - C++
Дана задача: КИНОТЕАТР. X мальчиков и Y девочек пошли в кинотеатр и купили билеты на подряд идущие места в одном ряду. Требуется...

Кодирование, C++ - C++
Закодировать каждую букву произвольного символьного массива равномерным кодом.

Кодирование - C++
В какой тип данных можно записывать по одному биту 0 или 1, чтобы потом можно было считать целиком последовательность. Например, 010 или 1.

11
tony_pershin
16 / 16 / 1
Регистрация: 05.03.2013
Сообщений: 36
02.10.2013, 21:16 #2
Бинарные данные чаще всего кодируют, используя base64: http://ru.wikipedia.org/wiki/Base64. Легко и быстро реализуется.
0
faustmangos
3 / 3 / 0
Регистрация: 02.10.2013
Сообщений: 34
02.10.2013, 21:29  [ТС] #3
Не , эта штука не подойдет она применяется в транспортных целях и не сжимает файл
0
tony_pershin
16 / 16 / 1
Регистрация: 05.03.2013
Сообщений: 36
02.10.2013, 21:53 #4
Справедливо, пропустил слово "сжимать", когда читал. А чем обыкновенный run-length encoding не устраивает? Блоки по 8 бит, например. Можно поэкспериментировать на dll-ках всяких
0
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 битов а потом доставая биты повторений
тема интересная, но боюсь препод не примет такой способ
0
tony_pershin
16 / 16 / 1
Регистрация: 05.03.2013
Сообщений: 36
03.10.2013, 13:15 #6
Вообще сжимать бинарные данные равномерным кодированием странновато. Ну да ладно.
Как мне кажется, задача не сильно отличается от текстовой. В текстовой тебе известен размер элемента алфавита (8 бит). Я бы попробовал такой же размер элемента для бинарного файла, составил бы множество уникальных элементов, содержащихся в бинаре, и посмотрел бы какой получается выигрыш. Общего алфавита, ты, очевидно не получишь (если мощность полученного множества равна 2^8, то ты ничего не выигрываешь). И это логично, ведь ты пытаешься задать однозначное отображение одного множества в другое, ниже энтропии тебе не опуститься. Так что возможен только такой динамический путь. Вообще это интересный вопрос. Мне кажется, что по этой причине постановка задачи некорректна, но возможно я и не прав. Было бы интересно услышать какие-нибудь контраргументы.
0
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, каждому блоку кодер сопоставляет соответствующее кодовое слово.

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


Вот еще тоже самое, что я кинул тебе в статье, надо как-то с этим разобраться
0
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. Сразу становится очевидно, за счет чего происходит сжатие). Об общем алгоритме здесь речи не идет.
1
faustmangos
3 / 3 / 0
Регистрация: 02.10.2013
Сообщений: 34
03.10.2013, 18:08  [ТС] #9
Так это по-идее и есть общий подход, смотри мне написано в задании "с помощью равномерного кодирования", а тут в определении написано Описанный метод кодирования дискретного источника мы будем называть равномерным кодированием.

Добавлено через 15 минут
ты хочешь сказать если я возьму например слова по 8 бит, и сделаю то, что здесь написано то моему файлу крындздец прийдет? Из-за того , что я не знаю как он устроен и , что можно сжимать так, а что нет?
0
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, почувствуй разницу), так какой смысл его кодировать, если она вероятнее всего не появится?

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

Арифметическое кодирование на С++ - C++
Здравствуйте. Такая проблема: нужно реализовать алгоритм арифметического кодирования и декодирования. Кодирование у меня получилось. Но...

Кодирование файла - C++
Задача написать часть полиморфного вируса для курсовой. Т.е нужно подать нашей программе на вход файл она должна зашифровать его по...

Кодирование Хаффмана - C++
Есть дерево Хаффана, с помощью функции, приведенной ниже прохожусь по дереву и "выписываю" 0 и 1, получившиеся коды символов записываю в...

Кодирование Хаффмана - C++
Добрый вечер. Я за эту неделю малость зафлудил форум наверно. Прошу прощения за это. Просто уже не знаю, куда ещё обратиться со всем...


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

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

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