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

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

03.10.2013, 16:55. Просмотров 3517. Ответов 31
Метки нет (Все метки)

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

Добавлено через 17 часов 27 минут
Извиняюсь тут "исходный алфавит без избытка" глупо звучит) наоборот получить исходный а из-него как то сделать без избытка новый
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
03.10.2013, 16:55
Ответы с готовыми решениями:

Равномерное распределение чисел в ряду
Здравствуйте. Имеется обычный ряд чисел. Необходимо равномерно и как можно максимально...

Равномерное распределение значений в массиве
Есть одномерный массив с целочисленными значениями. Пусть будет 1 и 0 (16 единиц и 14 нулей): ...

Равномерное распределение нагрузок по фазам
Дан некий набор однофазных нагрузок (токов). Необходимо распределить нагрузки по трем фазам, то...

Равномерное распределение чисел временного ряда
Здравствуйте. Есть временной ряд чисел. Дано количество классов N. Необходимо каждому члену...

31
3168 / 1927 / 312
Регистрация: 27.08.2010
Сообщений: 5,131
Записей в блоге: 1
03.10.2013, 20:05 2
Так называемое "сжатие" (термин абсолютно неверный, но устоявшийся) - это либо кодирование равномерных кодов неравномерными, либо неравномерных - равномерными, либо неравномерных - другими неравномерными. Все.

Если у вас второй вариант: неравномерных - равномерными, то это так называемые "словарные" алгоритмы. Составляете словарь фраз и выводите в выходной поток номер фразы в словаре. Смотреть, например, в сторону семейства LZ. (Всё о сжатии данных, изображений и видео).

P.S.

Что сжимать: текст/не текст - безразлично, разница только в возможном выигрыше. Текст, обычно, хорошо сжимается (в среднем, вчетверо) , бинарные данные после "сжатия" могут еще больше увеличиться в размере.
0
827 / 635 / 100
Регистрация: 20.08.2013
Сообщений: 2,524
03.10.2013, 23:32 3
Цитата Сообщение от gazlan Посмотреть сообщение
Что сжимать: текст/не текст - безразлично, разница только в возможном выигрыше.
Не совсем так. Кодирование текста не обязано быть полностью обратимым. Например, можно не различать заглавные и строчные буквы, объединять некоторые буквы в одну (как это принято в криптографии: i=j, и=й, е=ё, ь=ъ и т. д.). А для бинарных данных всё это неприемлимо.

Добавлено через 3 минуты
Ну кроме графики (jpg и подобное)...
0
3168 / 1927 / 312
Регистрация: 27.08.2010
Сообщений: 5,131
Записей в блоге: 1
04.10.2013, 00:22 4
Цитата Сообщение от Qwertiy Посмотреть сообщение
Кодирование текста не обязано быть полностью обратимым
Тогда это уже аннотирование, реферирование итп. Именно для текста, в отличие от графики, по умолчанию всегда предполагается Lossless-сжатие. А любое искажение трактуется как шум в канале связи.

Разумеется, если вы шлете SMS-ку без пробелов или с выброшенными гласными, это тоже сжатие, но вряд ли этот метод буден интересен TS.
0
827 / 635 / 100
Регистрация: 20.08.2013
Сообщений: 2,524
04.10.2013, 00:35 5
Цитата Сообщение от gazlan Посмотреть сообщение
Именно для текста, в отличие от графики, по умолчанию всегда предполагается Lossless-сжатие.
Если немного поменять на "для текста в криптографии по умолчанию всегда предполагается", то будет прямо-таки наоборот

Цитата Сообщение от gazlan Посмотреть сообщение
в отличие от графики
Графика - это не произвольные бинарные данные. А вот для произвольных 100% должно быть без потерь, а то вдруг exe так кодировать начнёшь
0
3168 / 1927 / 312
Регистрация: 27.08.2010
Сообщений: 5,131
Записей в блоге: 1
04.10.2013, 01:05 6
Цитата Сообщение от Qwertiy Посмотреть сообщение
Если немного поменять на "для текста в криптографии по умолчанию всегда предполагается", то будет прямо-таки наоборот
Наоборот не будет.

Предыскажения текста, использование сленга, кличек, сокращений, вязаные руны и монокондил, язык индейцев навахо, номенклаторы, омофоны и прочие приемы обфускации - все это замечательно, но сами криптографические протоколы требуют восстановления данных бит-в-бит.

И то, о чем вы пишете, очевидно, не имеет никакого отношения к исходному вопросу о сжатии.
0
3 / 3 / 0
Регистрация: 02.10.2013
Сообщений: 34
11.10.2013, 21:29  [ТС] 7
gazlan, Прочитал про LZ но там вроде наоборот равномерного неравномерным, т.е. есть слова по 8 бит, составялем строки и пихаем в таблицу, но там при декодировании некоторые индексы будут декодироваться большим кол-вом байтов чем другие индексы

Добавлено через 34 секунды
Тоесть вы хотите сказать что сжимать равномерный равномерным глупо?
0
3168 / 1927 / 312
Регистрация: 27.08.2010
Сообщений: 5,131
Записей в блоге: 1
11.10.2013, 23:27 8
Цитата Сообщение от faustmangos Посмотреть сообщение
сжимать равномерный равномерным глупо?
Невозможно (с точностью, до переобозначения).

Например, преобразование из кодировки DOS-866 в Win-1251 - это замена одного равномерного кода другим

1. Сжатие равномерных кодов неравномерными (Huffman coding)
Код
A -> 0
B -> 1
C -> 10
D -> 110
2. Сжатие неравномерных кодов равномерными (Tunstall coding)
Код
A    -> 00
AB   -> 01
ABC  -> 10
ABCD -> 11
3. Сжатие равномерных кодов равномерными (Mapping)
Код
A -> a
B -> b
C -> c
D -> d
0
827 / 635 / 100
Регистрация: 20.08.2013
Сообщений: 2,524
12.10.2013, 00:00 9
Цитата Сообщение от gazlan Посмотреть сообщение
Сжатие равномерных кодов равномерными
Код
QWE -> a
ASD -> b
ZXC -> c
0
3168 / 1927 / 312
Регистрация: 27.08.2010
Сообщений: 5,131
Записей в блоге: 1
12.10.2013, 00:24 10
Еще раз, медленно:

Цитата Сообщение от gazlan Посмотреть сообщение
Невозможно (с точностью, до переобозначения).
0
827 / 635 / 100
Регистрация: 20.08.2013
Сообщений: 2,524
12.10.2013, 00:50 11
gazlan, во-первых, любое кодирование - это переобозначение. А во-вторых, ничего что это переобозначение уменьшает размер в 3 раза?
0
3168 / 1927 / 312
Регистрация: 27.08.2010
Сообщений: 5,131
Записей в блоге: 1
12.10.2013, 01:34 12
С тем же успехом, можете "увеличить" их размер в три раза. Любому из этих вариантов будет соответствовать один и тот же эквивалентный набор равномерных кодов. Например: ASCII <-> Unicode.

"Сжатие" возможно только в том случае, когда набор допустимых состояний системы меньше числа всех ее состояний (имеются запрещенные состояния - т.н. "избыточность").

Исключая запрешенные состояния (перенумерация = кодирование), систему можно вложить (упаковать) в пространство меньшей размерности.

Наименование же этих состояний - "QWE" или "a" или "AbRaCaDaBrA" или еще как либо - никакого значения не имеет.

Никакое переобозначение не приводит к "сжатию", если нет запрещенных состояний, исключаемых при перенумерации. (Схемы в #8 даны только для иллюстрации).

В вашем примере, никакого исключения состяний не произойдет, следовательно, невозможно и сжатие.

Посмотрите здесь базовые понятия: "Сжатие" данных.
0
827 / 635 / 100
Регистрация: 20.08.2013
Сообщений: 2,524
12.10.2013, 02:44 13
Цитата Сообщение от gazlan Посмотреть сообщение
"Сжатие" возможно только в том случае, когда набор допустимых состояний системы меньше числа всех ее состояний (имеются запрещенные состояния - т.н. "избыточность").
Да, именно так.

Цитата Сообщение от gazlan Посмотреть сообщение
В вашем примере, никакого исключения состяний не произойдет, следовательно, невозможно и сжатие.
Не филосовствуй.
Было 3 байта на допустимое состояние, стал 1 байт. А можно сделать 2 бита. Именно это и есть сжатие. А не уменьшение числа состояний системы.
А если я начну рассматривать исходную систему как 256^3 состояний, из которых допустимы только 3, то по твоему же критерию, сжатие есть.
0
3168 / 1927 / 312
Регистрация: 27.08.2010
Сообщений: 5,131
Записей в блоге: 1
12.10.2013, 03:24 14
Я вижу, для вас это трудный материал.

Для оценки возможного сжатия важны только два числа: Общее количество состояний и количество запрещенных состояний.

На пальцах:

Пусть имеется 100-квартирный дом, полностью заселенный жильцами.

1. Андреев ... 50. Матвеев ... 100. Яковлев

Если теперь переименовать жильцов в

1. АА ... 50. ММ ... 100. ЯЯ

то в три раза больше места не станет.

А вот если, например, все четные квартиры запрещены к заселению, то можно перенумеровать всех жильцов от 1 до 50 и переселить в дом вдвое меньшего размера.

Аналогично, если имеется 256 символов ASCII (8 bits) и 256 символов Unicode32 (32 bits), то для указания любого символа из заданного набора необходимо ровно LOG2(256) = 8 bits.

А вот если запрещены все четные символы алфавита, то 7 bits уже достаточно - независимо от битовой ширины
самого символа.


Повторю еще раз, для лучшего запоминания:

Важны только два числа: Общее количество состояний и количество запрещенных состояний.
0
827 / 635 / 100
Регистрация: 20.08.2013
Сообщений: 2,524
12.10.2013, 03:41 15
Цитата Сообщение от gazlan Посмотреть сообщение
Важны только два числа: Общее количество состояний и количество запрещенных состояний.
Ещё раз:
Цитата Сообщение от Qwertiy Посмотреть сообщение
рассматривать исходную систему как 256^3 состояний, из которых допустимы только 3, то по твоему же критерию, сжатие есть.
0
3168 / 1927 / 312
Регистрация: 27.08.2010
Сообщений: 5,131
Записей в блоге: 1
12.10.2013, 08:04 16
Цитата Сообщение от Qwertiy Посмотреть сообщение
как 256^3 состояний
Я смотрю, вы в трех буквах заблудились. FAQ почитайте.
Ну, или просто задумайтесь, о невозможности вечного двигателя и законах сохранения.

При сжатии без потерь, число состояний - это инвариант преобразования.

Например, если трехлитровую банку пива разделить на троих приятелей, то в каждом окажется всего по одному литру, но в сумме это все равно будет три - инвариант.

Запись QWE -> a, ASD -> b, ZXC -> c именно и означает, что у вас есть ровно ТРИ состояния {s0,s1,s2}, которые преобразованием T отображаются из алфавита {QWE,ASD,ZXC} на алфавит {a,b,c}.

А, неизвестно откуда, взявшееся 256 (или, подставьте сюда любое другое число по вкусу) - плод вашего воображения.

Пример: если взять три тома "Война и мир", то сами эти тома можно - без потерь - переименовать как {1, 2, 3}.
А вот записать содержание одного тома одной цифрой, без потерь уже никак не получится.

И я настоятельно советую вам не только почитать хоть что-нибудь по теме сжатия данных без потерь, но и "с карандашом в руках" проделать выкладки в каком-нибудь простом примере (типа Huffman-сжатия слова ABRACADABRA), чтобы усвоить, что такое алфавит, преобразование, биективность, инвариант и другие базовые понятия.
0
3 / 3 / 0
Регистрация: 02.10.2013
Сообщений: 34
13.10.2013, 20:24  [ТС] 17
gazlan, это "сжатие" равномерным равномерного правильно? -> "Еще один достаточно простой способ сжатия информации можно назвать ограничением информационного алфавита. Сразу же отметим, что на практике такой алгоритм не реализован, но изложение данного метода поможет лучше понять метод кодов переменной длины.
В дальнейшем под информационным алфавитом мы будем подразумевать набор символов, используемый для кодирования информационной последовательности. К примеру, пусть имеется некоторое текстовое сообщение. Для кодировки каждой буквы этого сообщения используется ASCII-таблица, состоящая из 256 символов. При этом под кодирование каждого символа отводится ровно 8 бит (1 байт). В данном случае информационный алфавит — это все 256 символов кодировочной ASCII-таблицы.
Понятно, что в исходном текстовом сообщении могут применяться не все 256 символов ASCII-таблицы. К примеру, если речь идет о текстовом сообщении на русском языке, в котором нет цифр, то достаточно 64 символов (33 строчные и 31 заглавная буквы). Если добавить к этому знаки препинания, знаки абзаца и перехода на новую строку, станет понятно, что число символов не превысит 100. В этом случае можно использовать не 8-, а 7-битное кодирование символов, что позволяет получить таблицу из 128 символов. То есть мы как бы ограничиваем информационный алфавит, за счет чего можно уменьшить разрядность каждого колируемого символа. Можно пойти дальше — точно определить количество применяемых символов в текстовом сообщении. Если, к примеру, выяснится, что в сообщении задействуются всего 30 символов (включая символы перехода на новую строку), то можно использовать 5-битную кодировочную таблицу, содержащую 32 символа, и тогда степень сжатия текстового сообщения станет еще большей. Действительно, если в исходном сообщении применяется 8-битное кодирование символов, а в сжатом — 5-битное, то коэффициент сжатия будет 8/5.
Несмотря на кажущуюся простоту метода ограничения алфавита, на практике он не используется. Дело в том, что описанный метод не позволяет корректно декодировать исходное сообщение без передачи дополнительной информации. Действительно, не зная кодировочных таблиц, применяемых для сжатия информации, декодировать ее невозможно. То есть вместе с закодированной информационной последовательностью необходимо передавать и кодировочные таблицы. Понятно, что в этом случае выигрыш от использования ограниченного алфавита сводится к нулю.
У метода ограниченного алфавита есть и другие недостатки. Если исходное информационное сообщение содержит большое количество разнообразных символов, то понизить разрядность представления символов алфавита не удастся и данный способ просто не сработает. Предположим, к примеру, что в исходном информационном сообщении содержится 129 символов из 256-символьного алфавита. Воспользоваться 7-битным кодированием символов в данном случае не удастся, поскольку 7 бит позволят закодировать только 128 символов. Поэтому для 129 символов придется обратиться к тому же 8-битному кодированию, как и в исходном 256-символьном алфавите.
"
0
3168 / 1927 / 312
Регистрация: 27.08.2010
Сообщений: 5,131
Записей в блоге: 1
13.10.2013, 22:01 18
Изложение предельно невнятное, но мысль уловить можно.

Краткий ответ: все неверно.

1. Используется повсеместно. MIME64, например. Или архиватор ARJ. Или еще 100500 примеров.
2. Это НЕ сжатие

Развернутый ответ:

Второй пункт требует пояснений.

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

Например, к единице можно приписать спереди сколько угодно незначащих нулей: 1, 01, 001 ... итд. Так вот, преобразование 000...0001 --> 1 (отбрасывание незначащих нулей) сжатием не является, мы остаемся в той же самой кодовой системе.

Например, независимо от размера диагонали вашего монитора и выбранного шрифта, это сообщение будет все тем же самым - НЕ сжатым и НЕ расширенным.

Сжатие без потерь (как частный случай трансформации) - это переход от одной минимальной системы кодов к другой минимальной системе кодов.

Причем, подчеркну еще раз, не сжатие - следствие перекодирования, а перекодирование - (побочный) эффект сжатия.

Иными словами, если у вас есть минимальная система кодов в которой различимы N состояний, и K из них никогда не используются (запрещены), то можно, ничего не теряя, перейти к системе кодов с меньшим числом состояний (N - K).

Этот переход и является сжатием. А замена кодов первой системы на коды второй системы (переименование) - следствие сжатия, а не его причина.

Например, с учетом буквы "Ё", пробела, перевода строки, цифр и знаков препинания, кириллический алфавит больше чем 2^5 = 32, но все еще меньше, чем 2^6 = 64 (без учета регистра).

Используя равномерный код, невозможно записать текст в таком алфавите менее, чем 6 битами. Таким образом, полная кодовая система (минимальная) будет содержать 2^6 = 64 кодов.

Запишете вы их как 01, 02, ... 64 или как 00001, 00002, ... 00064, не имеет значения - это все та же самая система, все тех же 64 кодовых слов.

При этом, хотя сама система кодов минимальна, некоторые состояния все еще останутся неиспользованными (суммарное количество цифр и знаков препинания меньше 31). Можно найти систему кодов по другому основанию (не 2), где число неиспользуемых состояний будет меньше (в идеале - 0). Тогда, при переходе к этой новой системе мы получим сжатие (и, как побочный эффект, перекодирование) .

В том же примере, который приведен у вас просто выполняется "нормализация", т.е. переход к минимальной системе кодов.

При этом о возможности сжатия текста, на самом деле, ничего нельзя сказать, без знания самого текста. Если, например, в тексте использованы все символы алфавита с равной кратностью, то в этом алфавите текст несжимаем.
0
3 / 3 / 0
Регистрация: 02.10.2013
Сообщений: 34
13.10.2013, 23:41  [ТС] 19
gazlan, что тогда скажешь насчёт этого http://femto.com.ua/articles/part_1/1668.html (подзаголовок оптимальное равномерное кодирование)
0
3168 / 1927 / 312
Регистрация: 27.08.2010
Сообщений: 5,131
Записей в блоге: 1
14.10.2013, 00:25 20
Стандартный текст из учебника. Почти в любом курсе по теме вы найдете нечто похожее.
Только какое отношение это имеет к сжатию?

Я даже поискал по ключевому слову, нашел на странице всего одну фразу:

Кодирование источника приобретает новое значение в связи с необходимостью "сжатия" информационных массивов данных в базах и банках данных. Массивы организационной, экономич., измерит. информации имеют столь большую избыточность, что допускают сжатие, доходящее до 80-85%. Развитые системы управления базами данных (СУБД) имеют спец. программы (утилиты) анализа, сжатия и восстановления текста, работающие на принципах, изложенных выше.

Ну, так этот пункт у нас разногласий не вызывает.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
14.10.2013, 00:25

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

Кодирование данных
Добрый день, не могу разобраться с МНР (машина с натуральными регистрами) и в инэте очень мало...

Арифметическое кодирование
Сразу скажу что тема для меня не новая, 25 лет назад читал про это и даже что-то с преподом...

Помехоустойчивое кодирование.
Помогите ответить на вопросы: Может ли код длиной 4 исправлять двухкратные ошибки? Сколько...

Арифметическое кодирование в vp8
Всем привет, возник такой вопрос. В формате vp8 используется арифметическое кодирование. Имеется...


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

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

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