Как написать простейший архиватор?

@[XandeR] · Регистрация: 18.03.2009

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

Необходимо написать программу -архиватор, степень сжатия неважна, лишь бы работало. Ничего интересного и понятного в интернете не нашел, на форуме тоже. Может у кого нибудь есть простой и понятный исходник архиватора, или подскажите что и где почитать, пжл.

@MikeSoft · 29.07.2010, 18:59

[XandeR], вам нужно смотреть в сторону Кодирования по Хаффману или Арифметического кодирования.

Информации по этим методам предостаточно (собственно, исходники тоже можно найти).

@radiohobbyt · 29.07.2010, 19:04

http://www.info-zip.org/Zip.html#Sources
итог гугления в течении 3 минут

@[XandeR] · 29.07.2010, 19:10 **[ТС]**

Сообщение от radiohobbyt

http://www.info-zip.org/Zip.html#Sources
итог гугления в течении 3 минут

хм, ничего тут не нашел

@NiTan · 29.07.2010, 19:28

[XandeR], вам нужно написать все алгоритмы сжатия самому или же нет? Просто для архивации есть множество готовых библиотек, таких как ZLib или ZipForge.

@[XandeR] · 29.07.2010, 19:41 **[ТС]**

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

@odip · 30.07.2010, 11:29

Ну если самому, тогда ищи описание алгоритма Хаффмана

@NiTan · 30.07.2010, 23:33

[XandeR], вот здесь есть исходник на C: Исходник алгоритма Хаффмана на C.
Также посмотрите вот здесь: Алгоритм Хаффмана или LWZ - сжатие

Добавлено через 2 минуты

Сообщение от XandeR

а вот сложные библиотеки и компоненты как раз мне не нужны, меня не интересует сильное или эффективное сжатие

Да там все просто работает. Устанавливаете компонент. Затем кидаете его на форму и пишите (просто пример - реальных функций не помню):

C++
1
2
3
Zip1->FileName="Test.zip"; //Создали архив
Zip1->Open(); //Открыли
Zip1->AddFile("FileName"); //Добавили файл

Что-то вроде этого.

@Black Fregat · 31.07.2010, 01:47

Давайте по порядку.

Во-первых. Исторически понятие "архивация" может означать 2 принципиально разные вещи:
1) Кодирование файла таким образом, чтобы он занимал меньше места (gzip)
2) Сохранение нескольких файлов (возможно, со структурой папок) в единый файл (tar)

Вам нужно реализовать оба этих функционала?

Во-вторых. Xаффман достаточно сложен для понимания и реализации. Есть более простые алгоритмы, тем более, если не требуется сильное сжатие. Вот, например, LZ77 с реализацией

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

@M128K145 · 31.07.2010, 12:49

[XandeR], знаете такую историю:

Проходила какая-то олимпиада по программированию. Задача была - написать архиватор, причём чем лучше сжимает, тем больше очков - но 0 очков, если нельзя распаковать. Выиграла команда, написавшая копирование файлов.

Это я к фразе

Сообщение от XandeR

степень сжатия неважна, лишь бы работало

Задумайтесь

@Black Fregat · 31.07.2010, 17:31

Не по теме:

Сообщение от M128K145

[XandeR], знаете такую историю:

А еще была история, как студент написал упаковщик, сжимающий любой файл в 2 байта. А на резонный вопрос преподавателя об обратном преобразовании ответил, что писать распаковщик задания не было..

@[XandeR] · 05.08.2010, 18:36 **[ТС]**

Сообщение от M128K145

[XandeR], знаете такую историю:

забавно

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

@Black Fregat · 05.08.2010, 18:48

Не по теме:

Сообщение от [XandeR]

Black Fregat за помощь спасибо а умничать не стоит.

Вот и помогай после этого людям..

@[XandeR] · 05.08.2010, 21:32 **[ТС]**

Алгоритм нашел.. разобрался в теории кода Хаффмана, но никак не могу понять почему мы на выходе имеем файл в 119 раз больше чем кодируемый...
алгоритм взять отсюда Исходник алгоритма Хаффмана на C
нет ну понять то я конечно могу, туда записывается туча информации, но зачем?

Добавлено через 1 час 59 минут
и ещё возник вопрос( почему в двоичный файл хоть убей нельзя записать 1 бит информации?

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
void __fastcall TForm1::Button1Click(TObject *Sender)
{
 
TFileStream *out = new TFileStream("info", fmCreate); // создаем файл
if( out != NULL ) {
  AnsiString text = Memo1->Text; // исходная строка
  int size = text.Length();
  bool t=true;
 
  out->WriteBuffer(&t,  sizeof(t));
delete out;
}
 
}

записывает 1 байт, а зачем один байт под 1 бит выделять не понимаю!

@Demihalf · 05.08.2010, 23:24

[XandeR],

Байт в современных x86-совместимых компьютерах — это минимально адресуемый набор фиксированного числа битов.

Википедия

@[XandeR] · 06.08.2010, 16:19 **[ТС]**

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

@MikeSoft · 06.08.2010, 16:36

[XandeR], рассуждения неверны.

Расскажу вам принцип кодирования по Хаффману (простого, не адаптивного).

1. Собираем статистику появления символов в заданном тексте/файле.
2. В полученной последовательности символа с его частотой встречаемости выбираем два минимальных элемента, частоту их встречаемости слаживаем и объединяем в "новый элемент" (тем самым начинается построение дерева).
3. Для "родителей" нового объекта устанавливаем "0" и "1" соответственно.
4. Повторяем пункт 2 до тех пор, пока в последовательности не останется один элемент. Соответственно, при каждом проходе не забываем устанавливать "0" и "1".
5. Получаем последовательность бит, которыми будут закодированы символы. Для этого проходим дерево от нового (единственного) элемента к исходной последовательности.
6. Последовательность бит будет такой, что максимально повторяющийся элемент будет кодироваться минимальным количеством бит.
7. Делаем проход по тексту, заменяя символы на полученные биты, дополняем биты до байт (следующим набором бит) и записываем символ в новый файл. Последовательность из восьми бит даст один байт, который должен быть преобразован в символ.

Может теперь вы сможете увидеть, откуда берётся выигрыш в объёме.

@[XandeR] · 06.08.2010, 17:25 **[ТС]**

да, вижу,
но код приведенный здесь Исходник алгоритма Хаффмана на C работает неправильно, он выводит нам последовательность бит, это правильно в текстовый файл а в бинарный он выводит какую то ерунду которая занимает в 130 раз больше чем сам исходный файл. Мне достаточно того текстового файла, но ведь в него ещё надо вложить какую то информацию для раскодировки, да и вобще в алгоритме нет раскодировки..

@MikeSoft · 06.08.2010, 17:40

[XandeR], мозможно, алгоритм неверный ...

Для интереса проверил... Взял файл в 50 кб.
Хаффман (не адаптивный) ужал его до 38 кб.
Арифметический метод (адаптивный) ужал до 34 кб.
WinRar ужал до 26 кб.

@Black Fregat · 06.08.2010, 17:52

Сообщение от Black Fregat

Xаффман достаточно сложен для понимания и реализации. Есть более простые алгоритмы, тем более, если не требуется сильное сжатие. Вот, например, LZ77 с реализацией

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

Конечно, если Хаффман так зацепил - разбирайтесь.

Новые блоги и статьи Все статьи Все блоги /
[Owen Logic] Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ФедосеевПавел 14.03.2026 Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ВВЕДЕНИЕ Выполняя задание на управление насосной группой заполнения резервуара,. . .	делаю науч статью по влиянию грибов на сукцессию anaschu 13.03.2026 прикрепляю статью	SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++ 8Observer8 10.03.2026 Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:	Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE 8Observer8 10.03.2026 Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .
Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки Neotwalker 08.03.2026 Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .	Модульная разработка через nuget packages DevAlt 07.03.2026 Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .	Модульный подход на примере F# DevAlt 06.03.2026 В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .	Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование 8Observer8 05.03.2026 Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .

@[XandeR] 31 / 31 / 3 Регистрация: 18.03.2009 Сообщений: 381 Записей в блоге: 2

	Как написать простейший архиватор? 29.07.2010, 18:54. Показов 54365. Ответов 45 Метки нет (Все метки) Необходимо написать программу -архиватор, степень сжатия неважна, лишь бы работало. Ничего интересного и понятного в интернете не нашел, на форуме тоже. Может у кого нибудь есть простой и понятный исходник архиватора, или подскажите что и где почитать, пжл. 0

@MikeSoft 3957 / 1812 / 184 Регистрация: 21.11.2009 Сообщений: 2,540
	29.07.2010, 18:59
	[XandeR], вам нужно смотреть в сторону Кодирования по Хаффману или Арифметического кодирования. Информации по этим методам предостаточно (собственно, исходники тоже можно найти). 1

@radiohobbyt 192 / 190 / 15 Регистрация: 27.01.2009 Сообщений: 548
	29.07.2010, 19:04
	http://www.info-zip.org/Zip.html#Sources итог гугления в течении 3 минут 0

@NiTan Покинул форум 3189 / 1368 / 109 Регистрация: 29.01.2010 Сообщений: 2,887
	29.07.2010, 19:28
	[XandeR], вам нужно написать все алгоритмы сжатия самому или же нет? Просто для архивации есть множество готовых библиотек, таких как ZLib или ZipForge. 2

@[XandeR] 31 / 31 / 3 Регистрация: 18.03.2009 Сообщений: 381 Записей в блоге: 2
	29.07.2010, 19:41 [ТС]
	да, желательно самому, в худшем случае найти несложный пример, а вот сложные библиотеки и компоненты как раз мне не нужны, меня не интересует сильное или эффективное сжатие 0

@odip 7176 / 3234 / 82 Регистрация: 17.06.2009 Сообщений: 14,164
	30.07.2010, 11:29
	Ну если самому, тогда ищи описание алгоритма Хаффмана 0

@Black Fregat Фрилансер 3709 / 2083 / 567 Регистрация: 31.05.2009 Сообщений: 6,683
	31.07.2010, 01:47
	Давайте по порядку. Во-первых. Исторически понятие "архивация" может означать 2 принципиально разные вещи: 1) Кодирование файла таким образом, чтобы он занимал меньше места (gzip) 2) Сохранение нескольких файлов (возможно, со структурой папок) в единый файл (tar) Вам нужно реализовать оба этих функционала? Во-вторых. Xаффман достаточно сложен для понимания и реализации. Есть более простые алгоритмы, тем более, если не требуется сильное сжатие. Вот, например, LZ77 с реализацией Во-третьих. Главное, что непонятно - всё это можно найти в Гугле за несколько секунд. Поэтому не совсем понятно, какой именно помощи Вы ждете. Может быть, Вам на самом деле следует переместиться во фриланс? 0

@[XandeR] 31 / 31 / 3 Регистрация: 18.03.2009 Сообщений: 381 Записей в блоге: 2
	06.08.2010, 16:19 [ТС]
	ладно, это понятно, но каким образом я смогу заархивировать текст если текстовый символ занимает 1 байт и цифра 1 или 0 тоже занимает 1 байт а после кодировки по хаффману цифр получается больше чем символов в исходном тексте, и в итоге мы получаем файл размером больше а не меньше.. 0

@MikeSoft 3957 / 1812 / 184 Регистрация: 21.11.2009 Сообщений: 2,540
	06.08.2010, 16:36
	Сообщение было отмечено как решение Решение [XandeR], рассуждения неверны. Расскажу вам принцип кодирования по Хаффману (простого, не адаптивного). 1. Собираем статистику появления символов в заданном тексте/файле. 2. В полученной последовательности символа с его частотой встречаемости выбираем два минимальных элемента, частоту их встречаемости слаживаем и объединяем в "новый элемент" (тем самым начинается построение дерева). 3. Для "родителей" нового объекта устанавливаем "0" и "1" соответственно. 4. Повторяем пункт 2 до тех пор, пока в последовательности не останется один элемент. Соответственно, при каждом проходе не забываем устанавливать "0" и "1". 5. Получаем последовательность бит, которыми будут закодированы символы. Для этого проходим дерево от нового (единственного) элемента к исходной последовательности. 6. Последовательность бит будет такой, что максимально повторяющийся элемент будет кодироваться минимальным количеством бит. 7. Делаем проход по тексту, заменяя символы на полученные биты, дополняем биты до байт (следующим набором бит) и записываем символ в новый файл. Последовательность из восьми бит даст один байт, который должен быть преобразован в символ. Может теперь вы сможете увидеть, откуда берётся выигрыш в объёме. 3

@[XandeR] 31 / 31 / 3 Регистрация: 18.03.2009 Сообщений: 381 Записей в блоге: 2
	06.08.2010, 17:25 [ТС]
	да, вижу, но код приведенный здесь Исходник алгоритма Хаффмана на C работает неправильно, он выводит нам последовательность бит, это правильно в текстовый файл а в бинарный он выводит какую то ерунду которая занимает в 130 раз больше чем сам исходный файл. Мне достаточно того текстового файла, но ведь в него ещё надо вложить какую то информацию для раскодировки, да и вобще в алгоритме нет раскодировки.. 0

@MikeSoft 3957 / 1812 / 184 Регистрация: 21.11.2009 Сообщений: 2,540
	06.08.2010, 17:40
	[XandeR], мозможно, алгоритм неверный ... Для интереса проверил... Взял файл в 50 кб. Хаффман (не адаптивный) ужал его до 38 кб. Арифметический метод (адаптивный) ужал до 34 кб. WinRar ужал до 26 кб. 0

Как написать простейший архиватор?

Решение