Регистрация | Последние сообщения | Персональный список | Поиск | Настройка конференции | Личные данные | Правила конференции | Список участников | Top 64 | Статистика раздела | faq | Что нового v.2.3 | Чат
Skunk Forum - Техника, Наука, Общество » Общекомпьютерный »
Программистам. Вопрос по архивации данных (страница 1)

Версия для печати (настроить)
Страницы: 1 2

Новая тема | Написать ответ

Подписаться

Автор Тема:   Программистам. Вопрос по архивации данных
ДиаМат
Member

Сообщений: 49
Откуда: Ленинград
Регистрация: Апрель 2002

написано 26 Июня 2002 23:22ИнфоПравкаОтветитьIP

Можно ли многократно использовать метод Хаффмана для архивации данных? Я имею ввиду, увеличиться ли степень сжатия (*.exe и др. файлов). Хочу написать архиватор, с помощью которого можно будет заархивировать 100 Мб на дискету 1,4 Мб . Чисто теоретически это возможно, но вот на практике я не могу представить сколько времени займёт архивация .
Также вопрос не программистам, ну жен ли такой архиватор (скорость такого архиватора может быть очень низкой, если файлы будут очень большие)?

Побочные вопросы, адресованные программистам C++:
1.При реализации алгоритма лучше использовать побайтное сжатие, т.е. 256 вариаций, или больше 1.5,2…байта? Что эффективней?
2.Часть программы реализующая сам алгоритм Хаффмана (ход по древу) написанный на С++, во сколько раз уменьшит скорость работы архивации нежели если написать его на ассемблере? Ассемблером не владею !!!
3.Что быстрее будет: архивация или распаковка? И во сколько быстрее?
4.Какой алгоритм можно использовать вместе с алгоритмом Хаффмана, чтобы увеличить степень сжатия: алгоритм Лемпеля-Зива-Велча, арифметическое кодирование, двухступенчатое кодирование (алгоритм Лемпеля-Зива)?
5.Кто ни будь знает как реализовать динамическое кодирование Хаффмана.

[Это сообщение изменил moderator-bf (изменение 03 Ноября 2010 13:27).]

Весельчак У
Moderator

Сообщений: 2336
Откуда: Санктъ-Питербурхъ
Регистрация: Декабрь 2000

написано 27 Июня 2002 01:58ИнфоПравкаОтветитьIP

Я не программист, по большей части, но могу сказать, что многократное использование сжатия только увеличит размер файла из-за вкладывания служебной информации. Как только избыточная информация будет удалена, дальнейшие усилия по сжатию не приведут к успеху. Более того, при неудачной реализации, можно получить коэффициент сжатия намного меньше оптимального, причём дальнейшее сжатие окажется невозможным. Можно, конечно, сжать и гигабайт до размера одной дискеты, но это ежели он будет состоять только из нулей (или только из единиц).
Для упаковки текста (про остальное не знаю) наиболее эффективен алгоритм, применённый в ACB.

P.S. А вообще, есть интересное доказательство, что нельзя упаковать любой файл. Некоторые файлы сжатию не поддаются.
Так что идея не пройдёт - не стоит морочить голову себе и другим.

[Это сообщение изменил элд (изменение 27 Июня 2002 16:58).]

Alex P.
Member

Сообщений: 1544
Откуда: SPb
Регистрация: Июнь 2001

написано 27 Июня 2002 08:45ИнфоПравкаОтветитьIP

ДиаМат
"Чисто теоретически это возможно"
Интересно, как? обычное сжатие основано примерно на том, что в исходном файле последовательность одинаковых символов может быть заменена на вставку одного символа служебной информации, обозначающего именно эти одинаковые последовательности. Отсюда следует, что коэффициент сжатия будет ограничен до некоторой величины, свыше которой время на дальнейшую паковку растет до бесконечности, и заархивировать помянутые 100 м на дискету не получится (если это, как сказал Весельчак У, не бессмысленная в необходимости последовательность нулей или единиц)

Elder
Member

Сообщений: 726
Регистрация: Июнь 2001

написано 27 Июня 2002 15:14ИнфоПравкаОтветитьIP

ДиаМат
разве это чем-то будет отличаться от просто многократного архивирования?

[Это сообщение изменил элд (изменение 27 Июня 2002 16:57).]

ДиаМат
Member

Сообщений: 50
Откуда: Ленинград
Регистрация: Апрель 2002

написано 27 Июня 2002 17:55ИнфоПравкаОтветитьIP

Весельчак У
Я не программист, по большей части, но могу сказать, что многократное использование сжатия только увеличит размер файла из-за вкладывания служебной информации. Как только избыточная информация будет удалена, дальнейшие усилия по сжатию не приведут к успеху.
Представь себе следующею картину, при архивации по алгоритму Хаффмана, древо (т.е. служебная информация – СИ) занимает максимум 514 байт (это при однобайтном кодирование). При первой архивации создаётся древо, первые 2 байта СИ показывает количество зарезервированного под древо место, т.е. после указанного байта начинается область данных (ОД). При последующей архивации СИ (предыдущего) переносится в ОД и архивируется как обыкновенный не заархивированный файл, т.е. СИ не разрастается, а для количества архиваций файла можно использовать счётчик, который не займёт более 2-х байтов. Подводя итоги скажу: при каждой последующей архивации файл уже заархивированный (не единожды), представляет для архиватора всего лишь новый набор двоичного кода.

Можно, конечно, сжать и гигабайт до размера одной дискеты, но это ежели он будет состоять только из нулей (или только из единиц).
Существует самый простой алгоритм СЖАТИЯ СПОСОБОМ КОДИРОВАНИЯ СЕРИЙ (RLE). Он используется для кодирования растровых изображений (BMP, PCX, TIF, GIF), т.к. последние содержат достаточно много длинных серий повторяющихся последовательностей байтов.
Для *.exe и других не растровых изображений, очень хорошо подходит именно алгоритм Хаффмана.

Для упаковки текста (про остальное не знаю) ******** эффективен алгоритм, применённый в ACB.
Может ты про алгоритм Хаффмана и говоришь?

P.S. А вообще, есть интересное доказательство, что нельзя упаковать любой файл. Некоторые файлы сжатию не поддаются.
Да, существует такая ситуация когда максимальное количество комбинаций (битов) в байте, т.е. 256, при том что все комбинации равны по количеству повторений в файле (очень редкая ситуация). Для этого всего лишь надо увеличить архивируемый область от одного, к примеру, к двум байтам – это при кодирование Хаффмана. Или взять да использовать другой метод, к примеру двухступенчатое кодирование, а при последующих архивациях использовать снова алгоритм Хаффмана.
Нельзя заархивировать - только однобайтные или двух байтные файлы, но НЕТ смысла их архивировать

Alex P.
См. мой ответ Весельчак У.

Всем
Отвечайте (советуйте) – конструктивно!!!

Elder
А ты многократно когда-нибудь архивировал?

Elder
Member

Сообщений: 727
Регистрация: Июнь 2001

написано 27 Июня 2002 22:35ИнфоПравкаОтветитьIP

ДиаМат, ближе к делу.

Reason
Добрый, но ленивый

Сообщений: 49
Откуда: Русь [святая]
Регистрация: Март 2002

написано 27 Июня 2002 23:26ИнфоПравкаОтветитьIP

ДиаМат
Честно говоря мне не верится, что такое возможно на самом деле. Хотя про алгоритм Хаффмана я не слышал, если только мельком читал в компьютерре, но если по твоим словам да, то пиши архиватор, много народу порадуется =) Сколько тогда фильмов можно будет записать на винчестер 40 Гб? ))
Я, как программист любитель, представляю любую архивацию, как тут уже говорили: "обычное сжатие основано примерно на том, что в исходном файле последовательность одинаковых символов может быть заменена на вставку одного символа служебной информации, обозначающего именно эти одинаковые последовательности."
И как сто мег в 1,5 ужмешь.. Где-нибудь есть русская документация по методу Хаффмана, был бы не прочь почитать..

Весельчак У
Moderator

Сообщений: 2346
Откуда: Санктъ-Питербурхъ
Регистрация: Декабрь 2000

написано 28 Июня 2002 01:36ИнфоПравкаОтветитьIP

ДиаМат, хватит прикалываться.
Сам-то не пробовал многократно архивировать? Очень поучительное занятие. Мне только один раз в жизни удалось выиграть на этом деле, когда я запаковал сначала ZIP'ом, а потом RAR'ом (а может тогда RAR'а ещё не было?). Это было году так в 1998..1999, а файл был pCAD'овский, т.е., по существу, текстовый.
Возвращаясь к доказательству невозможности упаковки любого файла (помнил бы где прочитал, привёл бы ссылку): пусть есть несколько разных файлов размера 20000 байт, количеством 10000 штук. Мы упаковываем их и получаем из каждого архив размером 7000 байт. Вопрос: как можно обратно распаковать все файлы, ежели 300 из этих архивов полностью совпадают с другими?

Может ты про алгоритм Хаффмана и говоришь?
Я повторяю: хватит прикалываться.

цитата:
ACB-compression can be
classified as a variety of the DMC approach.

цитата:
DMC - Dynamic Markov Coding

цитата:
PPM, or context modelling, is based on theoretical work conducted from 1986-95 (T.C.Bell, J.G.Cleary, I.H.Witten, W.J.Teahan, A.Moffat ....). Software realization came about in the early nineties (HA, X1, ....).
DMC - Several DMC, or Dynamic Markov Coding, are known, in particular, Ross Williams'DHPC algorithm, as well as the DMC algorithm of Cormack & Horspool, which uses many heuristics methods (as well as PPM).

Это из описания на ACB.

ДиаМат
Member

Сообщений: 51
Откуда: Ленинград
Регистрация: Апрель 2002

написано 28 Июня 2002 17:37ИнфоПравкаОтветитьIP

Reason
Я, как программист любитель, представляю любую архивацию, как тут уже говорили: "обычное сжатие основано примерно на том, что в исходном файле последовательность одинаковых символов может быть заменена на вставку одного символа служебной информации, обозначающего именно эти одинаковые последовательности."
Что Вы все к этой последовательности символов прицепились, алгоритм Хаффмана, основывается не на подмене последовательности символов, а на подмене самого символа, т.е. символ с самым большим количеством повторений заменяется на 2 бита и т.д.

как сто мег в 1,5 ужмешь.. Где-нибудь есть русская документация по методу Хаффмана, был бы не прочь почитать..
В общем для начинающих, не обладающих базовыми знаниями ссылка
Существует несколько модификаций алгоритма Хаффмана!

Весельчак У
пусть есть несколько разных файлов размера 20000 байт, количеством 10000 штук. Мы упаковываем их и получаем из каждого архив размером 7000 байт. Вопрос: как можно обратно распаковать все файлы, ежели 300 из этих архивов полностью совпадают с другими?
Не понял вопроса!!!

Если ты говоришь, что для архивации текстов хорошо использовать ABC, то почему его не используют для архивации *.exe, ведь каждый байт можно представить как 256 символов?

Elder
Member

Сообщений: 729
Регистрация: Июнь 2001

написано 28 Июня 2002 18:17ИнфоПравкаОтветитьIP

с помощью которого можно будет заархивировать 100 Мб на дискету 1,4 Мб
а почему не 0.14Mb? 0.014Mb? 0.0014Mb? 0.00014Mb? Почему не 1 байт, в конце-то концов? Как я понимаю, предела нет вообще, вопрос только во времени ("Чисто теоретически это возможно, но вот на практике я не могу представить сколько времени займёт архивация")?

Ru
Member

Сообщений: 1358
Откуда: Санкт-Петербург
Регистрация: Декабрь 2000

написано 28 Июня 2002 18:19ИнфоПравкаОтветитьIP

Вообще-то это флейм все. Расслабься ДиаМат, не сожмешь ты любой файл со 100 мег до 1.4.

ps: Комми как всегда разводят народ.

ДиаМат
Member

Сообщений: 52
Откуда: Ленинград
Регистрация: Апрель 2002

написано 28 Июня 2002 23:20ИнфоПравкаОтветитьIP

Ru
не сожмешь ты любой файл со 100 мег до 1.4.
А где ты у меня прочитал, что любой?

Elder
Member

Сообщений: 731
Регистрация: Июнь 2001

написано 28 Июня 2002 23:59ИнфоПравкаОтветитьIP

ДиаМат
Вы проигнорировали мой вопрос относительно магнитофона

Весельчак У
Moderator

Сообщений: 2350
Откуда: Санктъ-Питербурхъ
Регистрация: Декабрь 2000

написано 29 Июня 2002 02:35ИнфоПравкаОтветитьIP

ДиаМат
т.е. символ с самым большим количеством повторений заменяется на 2 бита и т.д.
А ежели символы все будут одинаково повторяемы? Или повторов не будет?

Не понял вопроса!!!
Иначе говоря, архивы будут совпадать у разных исходных файлов, поэтому восстановить исходную информацию не удастся.

то почему его не используют для архивации *.exe
По видимому, из-за особенностей алгоритма. Тебе переслать этот архиватор с описанием? Сам попробуй разобраться, ежели английский хорошо знаешь, а то мне это будет слишком долго делать.

Николай_С
Junior Member

Сообщений: 17
Откуда: Москва
Регистрация: Май 2002

написано 29 Июня 2002 10:39ИнфоПравкаОтветитьIP

При кодировании методом Хоффмана, максимальный эффект
в случае,когда из 256 кодов,какая-то часть преобладает.
После архивации,файл будет представлять из себа набор кодов,частота повторения которых,будет примерно одинакова.
Существует еще такое понятие - количество информации.
Каждый файл содержит в себе информацию.
Если файл в 100 Мб хранит в себе 70 Мб информации (остальные 30 Мб - избыточность), то как ни изголяйся,а файл размером меньше 70 Мб не получить.
Это примерно как закон сохранения энергии.

ДиаМат
Member

Сообщений: 53
Откуда: Ленинград
Регистрация: Апрель 2002

написано 29 Июня 2002 13:57ИнфоПравкаОтветитьIP

Весельчак У
А ежели символы все будут одинаково повторяемы?
Я таких файлов не видел! А если и появился такой файл, можно применить несколько алгоритмов:
1) Уменьшить область архивации, т.е. к примеру разбить файл на две части (виртуально конечно), и заархивировать их отдельно. Шанс что при разделении файла, снова кол-во повторений будет одинаково, очень мал но если и это произойдёт то надо взять разделить файл не на две, а на три части и т.д. СИ не намного возрастёт.
2) Производить кодировку не одного байта, а например 2-х, правда СИ может разрастись при этом от 0,6 до ~4 Кб.
3) Подумать, да ещё что-нибудь придумать

Или повторов не будет?
А я не встречал таких дегенератов (это я не про тебя конечно), которые пытались заархивировать файл меньше 256 байт

Тебе переслать этот архиватор с описанием? Сам попробуй разобраться, ежели английский хорошо знаешь, а то мне это будет слишком долго делать.
Если этот мега архиватор не занимает много места, шли!
И ещё, а там описания алгоритма архивации есть? А то дизассемблером, пол года его пережёвывать неохота.

Николай_С
При кодировании методом Хоффмана, максимальный эффект в случае, когда из 256 кодов ,какая-то часть преобладает.
Во-первых: не Хоффмана, а Хаффман.
Во-вторых: почти всегда “какая-то часть преобладает”! Если не преобладает смотри мой ответ Весельчак У в этом посте.

После архивации, файл будет представлять из себя набор кодов, частота повторения которых, будет примерно одинакова.
Не обязательно!!! Как правило, снова образуется двоичный файл с преобладанием …

Существует еще такое понятие - количество информации.
Да, существует.
Кол-во информации – мера информации, сообщаемой появлением события определённой вероятности; мера оценки информации, содержащейся в сообщении.

Каждый файл содержит в себе информацию.
Конечно!

Если файл в 100 Мб хранит в себе 70 Мб информации (остальные 30 Мб - избыточность), то как ни изгаляйся, а файл размером меньше 70 Мб не получить.
Это примерно как закон сохранения энергии.

Не согласен. Аналогии с законом сохранения энергии неуместны.
Разъясни, пожалуйста как ты понимаешь понятие информации.

Elder
Ты о чём?

Весельчак У
Moderator

Сообщений: 2357
Откуда: Санктъ-Питербурхъ
Регистрация: Декабрь 2000

написано 30 Июня 2002 00:52ИнфоПравкаОтветитьIP

ДиаМат
Выслал - 45 кбайт.

P.S. Для особо упёртых - файлы формата Rocket e-Book (*.rb) практически не сжимаются ни одним архиватором.

:spy:
unregistered
написано 30 Июня 2002 02:41  ПравкаОтветитьIP

ДиаМат
Не согласен. Аналогии с законом сохранения энергии неуместны.

Kaк так? Прямая аналогия со вторым законом термодинамики. Информация - это "минус" энтропия, а энтропия, однако, возрастает. Будем спорить?

Еще... существует теоретический предел на сжатие информации при определенных условиях. Соответственно, что работает для одного типа данных никогда не сработает для другого. Т.е. универсального сжатия быть не может, потому что его не может быть никогда.

А вообще, хватит прикалываться, тоже мне псевдонауку развели
Все читаем первоисточники. Дать ссылочки?

Elder
Member

Сообщений: 733
Регистрация: Июнь 2001

написано 30 Июня 2002 12:36ИнфоПравкаОтветитьIP

Весельчак У
файлы формата Rocket e-Book (*.rb) практически не сжимаются ни одним архиватором.
и что?

Весельчак У
Moderator

Сообщений: 2361
Откуда: Санктъ-Питербурхъ
Регистрация: Декабрь 2000

написано 01 Июля 2002 00:04ИнфоПравкаОтветитьIP

Elder
А то, что это тоже архив (схожий с PDF), и многократного сжатия не получается.
А что, ты - особо упёртый?

Elder
Member

Сообщений: 734
Регистрация: Июнь 2001

написано 01 Июля 2002 22:36ИнфоПравкаОтветитьIP

Весельчак У
я просто не понял, что ты этим хотел подчеркнуть. Автор, вроде, уже сказал , что жать любые файлы не намерен (тем более, надо полагать, архивы)...

Ваш ответ:

Коды форума
Смайлики


Ник:    Пароль       
Отключить смайлики
Страницы: 1 2

Все время MSK

Склеить | Разбить | Закрыть | Переместить | Удалить

Новая тема | Написать ответ
Последние сообщения         
Перейти к:

Свяжитесь с нами | skunksworks.net

Copyright © skunksworks.net, 2000-2018

Разработка и техническая поддержка: skunksworks.net


Рейтинг@Mail.ru Яндекс.Метрика