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

@faustmangos · Регистрация: 02.10.2013

Студворк — интернет-сервис помощи студентам

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

@tony_pershin · 02.10.2013, 21:16

Бинарные данные чаще всего кодируют, используя base64: http://ru.wikipedia.org/wiki/Base64. Легко и быстро реализуется.

@faustmangos · 02.10.2013, 21:29 **[ТС]**

Не , эта штука не подойдет она применяется в транспортных целях и не сжимает файл

@tony_pershin · 02.10.2013, 21:53

Справедливо, пропустил слово "сжимать", когда читал. А чем обыкновенный run-length encoding не устраивает? Блоки по 8 бит, например. Можно поэкспериментировать на dll-ках всяких

@faustmangos · 02.10.2013, 22:36 **[ТС]**

Почитал про RLE спасибо за инфу, но вот вопрос как раз заключался в том какой размер блоков брать что бы эффективность кодирования была высокая, тоесть ты считаешь что 8 всегда?

Добавлено через 24 минуты
Да и впринципе это уже не очень то и на равномерное кодирование похоже, т.к. у равномерного кодирования есть своя теоритическая основа , т.е. есть алфавит A есть B и они там связаны по элементно а тут получается алфавит B будет дополнением к A, т.е. тупо в B хранятся элементы А + их число повторов, тогда например в кодовой таблице будет соотв. 10000001 -> 10000001[закодировать число повторов] и поменятеся алгоритм раскодировки который не соотв. теории равномерного кодирования, где идет тупо замена, а тут мне придется работать побитово доставая вначале первые 8 битов а потом доставая биты повторений
тема интересная, но боюсь препод не примет такой способ

@tony_pershin · 03.10.2013, 13:15

Вообще сжимать бинарные данные равномерным кодированием странновато. Ну да ладно.
Как мне кажется, задача не сильно отличается от текстовой. В текстовой тебе известен размер элемента алфавита (8 бит). Я бы попробовал такой же размер элемента для бинарного файла, составил бы множество уникальных элементов, содержащихся в бинаре, и посмотрел бы какой получается выигрыш. Общего алфавита, ты, очевидно не получишь (если мощность полученного множества равна 2^8, то ты ничего не выигрываешь). И это логично, ведь ты пытаешься задать однозначное отображение одного множества в другое, ниже энтропии тебе не опуститься. Так что возможен только такой динамический путь. Вообще это интересный вопрос. Мне кажется, что по этой причине постановка задачи некорректна, но возможно я и не прав. Было бы интересно услышать какие-нибудь контраргументы.

@faustmangos · 03.10.2013, 17:08 **[ТС]**

Да да да. В голове вертится, что-то подобное о чем ты написал, но в задании четко написано, что программа должна именно "сжимать". Вот наткнулся на теорию http://femto.com.ua/articles/part_1/1668.html оптимального равномерного кодирования(заголовок там чуть ниже по статье), "общие черты" более-менее понятны, но может ты больше поймешь, там написано что можно сжимать аж до 80% (хоть и специфичные файлы наподобие массивов данных в банках и тд.).

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

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

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

Вот еще тоже самое, что я кинул тебе в статье, надо как-то с этим разобраться

@tony_pershin · 03.10.2013, 17:34

Идея ясна, она отличается от того, что я выше написал всего лишь двумя моментами. Во-первых, предполагается, что p != q. Как следствие, получается этот "рабочий" словарь. И как следствие, второй момент -- неоднозначность. Т.е. все слова, не входящие в рабочий словарь, они ставят в соответствие одному (!) кодовому слову. Ты же говоришь об общем подходе. Общий -- значит p == q, а значит рабочий словарь равен кодовому.
Такого сжатия в БД достигают за счет того, что они хорошо знают этот рабочий словарь. Представь, что у тебя есть таблица типа key-> value, в которой так получается, что value принимают всего пару значений типа 287453, 234870 и 294852. Сразу становится очевидно, за счет чего происходит сжатие). Об общем алгоритме здесь речи не идет.

@faustmangos · 03.10.2013, 18:08 **[ТС]**

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

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

@tony_pershin · 03.10.2013, 18:23

Это общий подход, но не общий алгоритм. Тут просто объяснено, что теоретически, при p != q и большом количестве слов, вероятность появления одних слов сильно выше, чем других. Так давайте только их и кодировать! Вот и весь подход. Он логичен, ведь действительно, если p(1) = p = 0.75, p(0) = q = 0.25, то вероятность, что появится слово 0000 0000 равна 1/100000 (если p = q = 0.5, то 1/256, почувствуй разницу), так какой смысл его кодировать, если она вероятнее всего не появится?

Ты можешь это использовать, если это удовлетворяет условию. Однако это кодирование неоднозначно!

@faustmangos · 03.10.2013, 19:14 **[ТС]**

Я понял суть, Спасибо.
Может еще к преподу подойду спрошу.

@tony_pershin · 03.10.2013, 19:16

Это в первую очередь надо бы сделать). Если не затруднит, напиши потом, к какому решению пришел.

Новые блоги и статьи Все статьи Все блоги /
PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Access VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 16.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .

@faustmangos 3 / 3 / 0 Регистрация: 02.10.2013 Сообщений: 34

	Равномерное кодирование 02.10.2013, 21:08. Показов 1985. Ответов 11 Метки нет (Все метки) Скажу коротко, есть задание : программа должна сжимать файлы текстовые и бинарные с помощью равномерного кодирования. И если с исходным алфавитом текстового файла все еще как то ясно, то что делать с бинарным, как производить разбивку битов , что бы получить исходный алфавит без избытка и чтобы кодирование вышло эффективным? 0

@tony_pershin 17 / 17 / 7 Регистрация: 05.03.2013 Сообщений: 36
	02.10.2013, 21:16
	Бинарные данные чаще всего кодируют, используя base64: http://ru.wikipedia.org/wiki/Base64. Легко и быстро реализуется. 0

@faustmangos 3 / 3 / 0 Регистрация: 02.10.2013 Сообщений: 34
	02.10.2013, 21:29 [ТС]
	Не , эта штука не подойдет она применяется в транспортных целях и не сжимает файл 0

@tony_pershin 17 / 17 / 7 Регистрация: 05.03.2013 Сообщений: 36
	02.10.2013, 21:53
	Справедливо, пропустил слово "сжимать", когда читал. А чем обыкновенный run-length encoding не устраивает? Блоки по 8 бит, например. Можно поэкспериментировать на dll-ках всяких 0

@faustmangos 3 / 3 / 0 Регистрация: 02.10.2013 Сообщений: 34
	02.10.2013, 22:36 [ТС]
	Почитал про RLE спасибо за инфу, но вот вопрос как раз заключался в том какой размер блоков брать что бы эффективность кодирования была высокая, тоесть ты считаешь что 8 всегда? Добавлено через 24 минуты Да и впринципе это уже не очень то и на равномерное кодирование похоже, т.к. у равномерного кодирования есть своя теоритическая основа , т.е. есть алфавит A есть B и они там связаны по элементно а тут получается алфавит B будет дополнением к A, т.е. тупо в B хранятся элементы А + их число повторов, тогда например в кодовой таблице будет соотв. 10000001 -> 10000001[закодировать число повторов] и поменятеся алгоритм раскодировки который не соотв. теории равномерного кодирования, где идет тупо замена, а тут мне придется работать побитово доставая вначале первые 8 битов а потом доставая биты повторений тема интересная, но боюсь препод не примет такой способ 0

@tony_pershin 17 / 17 / 7 Регистрация: 05.03.2013 Сообщений: 36
	03.10.2013, 13:15
	Вообще сжимать бинарные данные равномерным кодированием странновато. Ну да ладно. Как мне кажется, задача не сильно отличается от текстовой. В текстовой тебе известен размер элемента алфавита (8 бит). Я бы попробовал такой же размер элемента для бинарного файла, составил бы множество уникальных элементов, содержащихся в бинаре, и посмотрел бы какой получается выигрыш. Общего алфавита, ты, очевидно не получишь (если мощность полученного множества равна 2^8, то ты ничего не выигрываешь). И это логично, ведь ты пытаешься задать однозначное отображение одного множества в другое, ниже энтропии тебе не опуститься. Так что возможен только такой динамический путь. Вообще это интересный вопрос. Мне кажется, что по этой причине постановка задачи некорректна, но возможно я и не прав. Было бы интересно услышать какие-нибудь контраргументы. 0

@faustmangos 3 / 3 / 0 Регистрация: 02.10.2013 Сообщений: 34
	03.10.2013, 17:08 [ТС]
	Да да да. В голове вертится, что-то подобное о чем ты написал, но в задании четко написано, что программа должна именно "сжимать". Вот наткнулся на теорию http://femto.com.ua/articles/part_1/1668.html оптимального равномерного кодирования(заголовок там чуть ниже по статье), "общие черты" более-менее понятны, но может ты больше поймешь, там написано что можно сжимать аж до 80% (хоть и специфичные файлы наподобие массивов данных в банках и тд.). Добавлено через 3 минуты И еще я перечитал тему вопроса извиняюсь тут "исходный алфавит без избытка" глупо звучит) наоборот получить исходный а из-него как то сделать без избытка новый Добавлено через 13 минут "Предположим, что множество всех последовательностей длиной n из сообщений источника разбита на два подмножества. Первое из них образовано всеми теми последовательностями (блоками длиной n), которые сопоставлены с кодовыми словами взаимно однозначно. Это подмножество называется множеством однозначно кодируемых и декодируемых блоков. Второе подмножество образовано всеми остальными блоками, каждому из которых сопоставляется одно и тоже кодовое слово. (Можно сопоставлять и различные кодовые слова. Это не существенно. Существенно лишь, что эти кодовые слова использованы для представления однозначно кодируемых и декодируемых блоков. В дальнейшем мы будем употреблять более короткое выражение – однозначно (неоднозначно) кодируемые блоки.) Последнее подмножество называется множеством неоднозначно кодируемых и декодируемых блоков. Все кодовые слова имеют одинаковую длину m, которая определяется числом M кодовых слов: m – наименьшее целое, удовлетворяющее неравенству Dm ≥M, где D – объем кодового алфавита. При кодировании последовательность сообщений на выходе источника разбирается на блоки длиной n, каждому блоку кодер сопоставляет соответствующее кодовое слово. Описанный метод кодирования дискретного источника мы будем называть равномерным кодированием." Вот еще тоже самое, что я кинул тебе в статье, надо как-то с этим разобраться 0

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

@faustmangos 3 / 3 / 0 Регистрация: 02.10.2013 Сообщений: 34
	03.10.2013, 18:08 [ТС]
	Так это по-идее и есть общий подход, смотри мне написано в задании "с помощью равномерного кодирования", а тут в определении написано Описанный метод кодирования дискретного источника мы будем называть равномерным кодированием. Добавлено через 15 минут ты хочешь сказать если я возьму например слова по 8 бит, и сделаю то, что здесь написано то моему файлу крындздец прийдет? Из-за того , что я не знаю как он устроен и , что можно сжимать так, а что нет? 0

@tony_pershin 17 / 17 / 7 Регистрация: 05.03.2013 Сообщений: 36
	03.10.2013, 18:23
	Это общий подход, но не общий алгоритм. Тут просто объяснено, что теоретически, при 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 [ТС]
	Я понял суть, Спасибо. Может еще к преподу подойду спрошу. 0

@tony_pershin 17 / 17 / 7 Регистрация: 05.03.2013 Сообщений: 36
	03.10.2013, 19:16
	Это в первую очередь надо бы сделать). Если не затруднит, напиши потом, к какому решению пришел. 0