|
78 / 3 / 2
Регистрация: 03.10.2015
Сообщений: 26
|
||||||
Алгоритм Хаффмана, кодировка битов11.12.2016, 12:12. Показов 4857. Ответов 34
Метки нет (Все метки)
Здравствуйте! Есть ДЗ по информатике - создать программу на Pascal ABCnet, которая сжимает файл по алгоритму Хаффмана.
Я сначала написал программу хотя бы создания дерева и словаря, чтобы была основа, и думал, что с битами разберусь позже. Дело в том, что нам вообще ничего не рассказывали про саму кодировку, и если на Си я нашел очень много информации по тому, как можно менять биты внутри байтового символа, например, то на Паскале я так и не нашел решения.. В общем, ниже представлена программа, которая кодирует ТЕКСТОВЫЙ файл по алгоритму Хаффмана (текстовый или нет - не важно, это я, скорее всего, поменяю), и она заменяет один байт символа на пять-шесть байт последовательностей цифр D А нужно, чтобы эти цифры вгонялись в биты. Плюс преподаватель рассказывал, что обратная программа (разархиватор) идет по коду, находит префиксный код и прекращает чтение, переключается на следующий "байт" как бы, а найденный заменяет числом. Но я не представляю, как можно сделать так, чтобы читались БИТЫ, и если находится последовательность БИТ из 4 штук, то все это прекращалось. Пожалуйста, просветите невежду! Буду очень благодарен, если хотя бы расскажете, как мне это сделать (я не прошу именно менять что-то в программе). Просто на основе моих замен объяснить, как то же самое запихнуть внутрь байта. Я знаю лишь shr и shl, но не смог придумать применения этому( Еще самое обидное, что дедлайн передвинули на 10 дней ближе, и теперь вообще все плохо..
0
|
||||||
| 11.12.2016, 12:12 | |
|
Ответы с готовыми решениями:
34
Записать дерево Хаффмана в виде последовательности битов кодировка Хаффмана Кодировка Хаффмана |
|
78 / 3 / 2
Регистрация: 03.10.2015
Сообщений: 26
|
||||||
| 12.12.2016, 18:01 [ТС] | ||||||
|
Хорошо, большое спасибо! Вечером попробую воплотить мечту в реальность.
Добавлено через 7 часов 59 минут Извините, а существует более адекватный способ закодировать байты, нежели представленный мной в коде первой программы? Несколько людей высказали свое недовольство таким методом, а что-то поправить не могу сообразить (+ переделать на байтовый лад). Я решил сделать
0
|
||||||
|
Модератор
|
|
| 12.12.2016, 20:01 | |
|
Pascal code = array[0..255] of cif; Можно, конечно так Декодирование префиксным кодом В любом случае, код каждого символа имеет собственную длину. Значит под хранение кода каждого символа нужно выделить 1 байт под хранение длины, несколько байт (2-3) под хранение самого кода. Сделайте, как сможете. Потом будете оптимизировать внутренние структуры.
0
|
|
|
78 / 3 / 2
Регистрация: 03.10.2015
Сообщений: 26
|
||||||
| 12.12.2016, 21:36 [ТС] | ||||||
|
Не могли бы Вы помочь последний раз? Я куда больше путаюсь, когда пытаюсь найти немногочисленную информацию сам, чем от Ваших рук. Прошу прощения...
Вот только со старой программой по строкам я четко мог ориентироваться и складывать нужные кол-ва повторений и символы, то тут я опять наступаю на неверные кнопки и все ломаю. Могу ли я попросить Вас помочь с кодом составления кодов символов? Если потребуется, попробовал бы как-то отблагодарить... Неделя перед сессией ужасно выносит мозг (я не давлю на жалость, ни в коем случае).
0
|
||||||
|
Модератор
|
||||||
| 12.12.2016, 22:05 | ||||||
|
Оставьте со строками - не ломайте себя.
Добавлено через 1 минуту Мне трудно ориентироваться в чужеродном синтаксисе PABC.NET. А вы его вовсю применяете. Добавлено через 1 минуту Что вы хотите от этих строк? Я не пойму синтаксис...
0
|
||||||
|
78 / 3 / 2
Регистрация: 03.10.2015
Сообщений: 26
|
|
| 12.12.2016, 22:06 [ТС] | |
|
Через строки я читал именно строки и работал с ними, но тут же мы уже читали байты и заносили в массивы различные байты. Плюс ваш предложенный вариант занесения битов в самом начале действует с чарами или байтами (опять же).. Все работает, осталось лишь связать части кодированием..
0
|
|
|
Модератор
|
|
| 12.12.2016, 22:07 | |
|
code - это таблица кодов Хаффмана?
А в этих строках вы хотите удлинить код для конкретного символа? Поступайте, как со строками: 1. Один байт - длина кода 2. Последовательность бит или байт или символов в строке - это сам код.
0
|
|
|
78 / 3 / 2
Регистрация: 03.10.2015
Сообщений: 26
|
|
| 12.12.2016, 22:15 [ТС] | |
|
А если Вам написать так, как видите Вы и как удобно Вам, не ломая голову моим кривым кодом? Я серьезно чувствую себя отсталым.
Добавлено через 6 минут Все равно не могу провести параллели(
0
|
|
|
Модератор
|
|
| 12.12.2016, 22:25 | |
|
Сдавать - не мне, а вам.
Сделайте код на строках, чтобы он совпадал с каким нибудь эталонным (файл из 1 строки). А я под ваш тип code подстроюсь.
0
|
|
|
78 / 3 / 2
Регистрация: 03.10.2015
Сообщений: 26
|
|||||||||||
| 12.12.2016, 23:29 [ТС] | |||||||||||
|
Код на строках есть изначально. Я понимаю, что сдавать мне, но я могу и написать какую-то дичь, к которой не подстроишься, а забот больше вам (вроде как).
Лучше уж научиться чему-то правильному, нежели копаться в своем мусоре. Если будет сегодня-завтра возможность - я был бы очень признателен (я не отказываюсь от своих слов). Я уже понял свою ошибку в плане амбиций, но нужно выжить здесь и вынести урок. Поэтому сердечно прошу помощи..
0
|
|||||||||||
|
Модератор
|
|
| 12.12.2016, 23:58 | |
|
Завтра подумаю.
Посмотрите ссылки. Мне кажется, что у вас не совсем корректно. Даже с примером на Pascal. http://algolist.manual.ru/comp... uffman.php https://habrahabr.ru/post/144200/
0
|
|
|
78 / 3 / 2
Регистрация: 03.10.2015
Сообщений: 26
|
|
| 13.12.2016, 13:28 [ТС] | |
|
Я читал обе этим темы. Код с habrahabr'а я не вижу, а из первой ссылки он ооочень уж тяжел и нагружен. Плюс мне необходимо создать программу без подключенных модулей, и в итоге для меня тот ад становится вообще невероятным. Поэтому пришлось импровизировать, хоть и, извиняюсь, не очень вышло.
По алгоритму Хаффмана после сортировки (не важно, по возрастанию или по убыванию, но логичнее по возрастанию, чтобы удобнее было брать редкие) мы объединяем элементы массива байтов в одно целое, и то же самое должны сделать с вхождениями этих байтов, после чего вновь произвести сортировку и продолжить это действо. Вот я и заикался о том, чтобы сделать одинаковые индексы для кол-ва вхождений и самих байтов. И особенно тяжелой сейчас для меня является создание самого кода. На деле-то понятно, когда мы идем по нарисованному дереву, но вот как это объяснить дереву (к тому же если дерево будет постоянно различаться).. В итоге я пришел к выводу, что погряз в этом достаточно серьезно, а дедлайн жесток. ![]() Добавлено через 5 часов 36 минут Все оказалось куда хуже. Мы сегодня прошли указатели (как бы прошли, но только теория). Задание сдавать в пятницу, и препод мне сказал, что кодирование по дереву Хаффмана делается только по указателям) Сказать, что я выпал в осадок.. В общем, весело. Если вам информация про указатели поможет, буду рад... Ибо в них уж точно беда, когда я узнал о них лишь сегодня.
0
|
|
|
Модератор
|
|
| 13.12.2016, 15:30 | |
|
Правильно говорят - не торопись делать, много исправлять придётся.
Как вариант: "Чем круче джип, тем дальше за трактором идти"
0
|
|
|
78 / 3 / 2
Регистрация: 03.10.2015
Сообщений: 26
|
||
| 13.12.2016, 23:57 [ТС] | ||
|
И ведь верно. Вы сможете попробовать помочь?
Добавлено через 6 минут Оказалось, что преподаватель рассматривал задания с нормальными коэффициентами для тех, кто и без курса в вузе умеет много чего прогать. А я оказался тем дурачком, который просто идет по курсу. Добавлено через 7 часов 52 минуты
0
|
||
|
Модератор
|
|
| 14.12.2016, 01:04 | |
|
Изучайте структуры на основе указателей - сначала списки, затем деревья.
Я не смогу выделить время для полноценного написания программы. Начальник меня спросит - "твоя трудовая где лежит?" Подкорректировать - да, пожалуйста. На это время меньше уходит. Если уж всё равно не успеете - берите с algolist.
0
|
|
|
78 / 3 / 2
Регистрация: 03.10.2015
Сообщений: 26
|
|
| 14.12.2016, 12:49 [ТС] | |
|
Еще раз здравствуйте!
Большое спасибо Вам за удаленное время и помощь. Я соединил в одно предложенные Вами решения и свои варианты, сделав рабочую программу, сжимаюзую любойкилобайтный файл в два раза. Для кдов использовал свой кривой алгоритм, но все остальное - Ваша заслуга, в особенности код по сабжу в сообщении 2. Огромное вам спасибо!
0
|
|
| 14.12.2016, 12:49 | |
|
Кодировка Хаффмана и энтропия Алгоритм Хаффмана Алгоритм Хаффмана
Алгоритм Хаффмана Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |
|
Новые блоги и статьи
|
|||
|
Транслитерация текста с кириллицы на латиницу (вариант №5)
Maks 17.11.2026
Дабы оставить позади все споры о том, какая буква каким образом должна транслитерироваться на латиницу - решил таки доработать данное решение и довести его до мало-мальски логического завершения. . . .
|
Просмотровщик HLP и конвертер в CHM
Argus19 16.11.2026
Просмотровщик HLP и конвертер в CHM
Давно хотел переделать справку Microsoft® Win32® Programmer's Reference, чтобы иметь её под рукой.
Но использовать несколько программ не удобно. Искал другие. . .
|
BitTorrent (версия 7.11 English) и Меню Настройки
russiannick 15.11.2026
Пункты, отвечающие за отключение обновлений в BitTorrent версии 7. 11 (английской)
Options
Preferences
General
Language
|
Транслитерация текста с кириллицы на латиницу (вариант №4)
Maks 15.11.2026
Что-то я перемудрил с предыдущими версиями, в этот раз сделал всё проще, обратившись к функции "СтрокаЛатиницей" из типового общего модуля "СтроковыеФункцииКлиент".
В данной функции нет апострофов,. . .
|
|
BitTorrent (версия 4.3.9) и Меню Настройки
russiannick 15.11.2026
В меню Настройки можно отключить автоматическое обновление программы.
Карта этого меню приложена ниже.
Нужный пункт выделен красным.
Сервис
Настройки
Поведение
|
Транслитерация текста с кириллицы на латиницу (вариант №3)
Maks 15.11.2026
Обновленная версия предыдущей обработки.
Изменения коснулись букв: Ъ, Ы, Ь, Э, отображения которых зависят от положения реквизита "Транслитерация имён".
Изменено отображение буквы Й.
Добавлена. . .
|
Транслитерация текста с кириллицы на латиницу (вариант №2)
Maks 13.11.2026
Обновленная версия ранее созданной обработки.
Добавлено:
- Проверка исходного текста на кириллицу, через обращение к стандартной функции "ТолькоКириллицаВСтроке" из общего модуля. . .
|
Часы с термометром и праздничным календарем
yariko 12.11.2026
Сегодня мы рассмотрим как можно сделать отличные многофункциональные часы.
Итак, поставим конкретную задачу: разработать часы с календарем, двумя термодатчиками, выводом поздравительных сообщений. . .
|