Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.83/6: Рейтинг темы: голосов - 6, средняя оценка - 4.83
3 / 3 / 0
Регистрация: 02.10.2013
Сообщений: 34
1

Равномерное кодирование

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

Скажу коротко, есть задание : программа должна сжимать файлы текстовые и бинарные с помощью равномерного кодирования. И если с исходным алфавитом текстового файла все еще как то ясно, то что делать с бинарным, как производить разбивку битов , что бы получить исходный алфавит без избытка и чтобы кодирование вышло эффективным?
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
02.10.2013, 21:08
Ответы с готовыми решениями:

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

Равномерное распределение
Имеется склад с N контейнеров (N всегда чётное число). Для равномерной погрузки контейнеров на Q...

Равномерное распределение
Дано N контейнеров весом a1,a2,a3..an. Нужно распределить эти контейнеры между Q транспортными...

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

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

Добавлено через 15 минут
ты хочешь сказать если я возьму например слова по 8 бит, и сделаю то, что здесь написано то моему файлу крындздец прийдет? Из-за того , что я не знаю как он устроен и , что можно сжимать так, а что нет?
0
17 / 17 / 7
Регистрация: 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
3 / 3 / 0
Регистрация: 02.10.2013
Сообщений: 34
03.10.2013, 19:14  [ТС] 11
Я понял суть, Спасибо.
Может еще к преподу подойду спрошу.
0
17 / 17 / 7
Регистрация: 05.03.2013
Сообщений: 36
03.10.2013, 19:16 12
Это в первую очередь надо бы сделать). Если не затруднит, напиши потом, к какому решению пришел.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
03.10.2013, 19:16

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

OpenQL равномерное визуальное распределение температуры
Пишу карту температуры с помощью OpenGL и столкнулся с такой проблемой: илюзия переходов между...

Рекурсия: равномерное размещение вершин дерева на экране
Всем привет! С праздниками! Возникли проблемы с следующей задачкой. С чего начать? Может...

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

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


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

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

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