Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
Форум программистов > Алгоритмы > Алгоритм Сжатия данных |
Автор: Win MK 32 4.9.2002, 02:57 |
Я придумал как сжимать файлы в 2 раза! ![]() ![]() ![]() ![]() ![]() |
Автор: Vit 4.9.2002, 07:38 |
Сжатие в 8 раз? Это что шутка? или заявка на Нобелевскую премию? Или речь идёт об алгоритмах сжатия с потерей качества? Или сжимаются файлы определённой структуры? Если нет, то давай я тебе пришлю файл длинной 65536 байт ты мне его сожмёшь хотябы на 5% (не бойся, с чётностью проблем нет - эта длина делиться на 2, 4, 8, 16, 32, 64, 128, 256)? |
Автор: cardinal 4.9.2002, 21:00 |
Естж ше еше в 50 годач придуманнии одним математиком алгоритм. Я питалса в него врубитса, но там уш все оченж навороченно. Помоему "алгоритм хаммера" називаетса или как-то так. На нем и базируютса все .zip и .rar. |
Автор: Chingachguk 4.9.2002, 23:53 |
Допустим, файл состоит из 64 символов. Последовательно сжимая его вдвое, получаем: 64->32->16->8->4->2->1 байт. Неплохо ! Но над этим еще надо поработать: что это такое, зачем этот лишний байт ?! Надо довести алгоритм до ума, чтобы можно было сжимать до нуля ! А начет зипа, так у него ~ 8 различных методов, включая просто storing. |
Автор: Win MK 32 6.9.2002, 01:43 | ||||
Vit, идея есть, но...
1)Я забыл сказать, что это сжатие только текстовых файлов (А можно ли другие файлы (например - в двоичном виде) сжимать я не знаю) 2)Улучшить способ перебора и замены двух символов на один (не перебирать же все возможные по парам в ручную) 3)
Сardinal, скажи пожалуйста, что знаешь об "алгоритме хаммера". Chingachguk, Насчет последнего байта была шутка или можно сжимать файлы до размера < 1 байта? P.S. Может если алгоритм будет проработан, можно будет поместить статью "Новый архиватор на VB" в раздел "Совмесные проекты/Поиск партнеров"... |
Автор: Vit 6.9.2002, 02:23 |
Текстовые файлы сжимать в 8 раз конечно можно, в целом алгоритм сжатия текстового файла прост - подсчитываем частоты комбинаций букв, далее наиболее частые комбинации кодируем наименьшим числом бит, наиболее редкие - большим числом бит. Вообще можно создать для текстовых файлов очень мощный архиватор - 3 байта составляют 16 миллионов комбинаций, что значительно превышает число слов в любом языке, т.е. можно каждое слово кодировать 3х байтной комбинацией, что даст уровень упаковки в 3-4 раза, однако полученный файл будет архивироваться Хаммером минимум ещё в 2 раза. Если идти дальше этим путём, то просто надо ранжировать слова по встречаемости и наиболее частые слова кодировать меньшим количеством бит, более редкие - большим, это может дать очень большие степени упаковки, но к сожалению алгоритм будет работать только на текстовых файлах, что абсолютно не актуально - текстовые файлы и так хорошо пакуются и обычно небольших размеров - я еще не встречал надобность сильного сжатия текстовых файлов. Гораздо перспективнее разработка алгоритмов сжатия там где это действительно критично - например видео и звук |
Автор: cardinal 6.9.2002, 03:50 |
http://www.sources.ru/vb/vb_compress_huffman.shtml Господа, если хотите делать упаковщик по круче, то используйте этот алгоритм, я не думаю, что можно сделать лучше. Точнее сделать то все можно, но я сомневаюсь, что кто-то с форума пересилит математика, которого в институтах проходят ![]() P.S. только без обид. Я и сам в него не врубился полностью... |
Автор: cosmic 28.9.2002, 19:41 | ||
НЕЕЕЕЕЕЕЕЕЕЕ! надо добиться сжатия до отрицательного размера, чтобы место на ж.диске освобождалось :))))) |
Автор: FdX 1.10.2002, 00:30 | ||||
Алгоритм твой понятен. Если текстовый файл состоит только из букв латинского алфавита, пробелов, запятых и т.п., то на кодирование одного символа уйдет 5 битов (32=2^5 (или как там это пишется)). Если добавить ещще кирилицу, то уже 2 в шестой степени (6 битов). Если 2 в шестой, то сжатие будет всего 25%.
Реализуй сначала с четным кол-вом, а потом это добавим |
Автор: Win MK 32 1.10.2002, 02:48 | ||
С заменой двух символов на один проблям нет, но надо, чтобы это происходило автоматически(Нужен алгоритм).
А это возможно!?! ![]() ![]() |
Автор: FdX 2.10.2002, 23:24 | ||
Не понятно. Поясни |
Автор: Win MK 32 3.10.2002, 03:15 | ||
Я имею в виду то, что автоматически должно происходить следующее: 1)Перебирались по два все символы 2)И осуществлять замену не перебором Например:
А...например...циклом или еще как... |
Автор: FdX 3.10.2002, 23:02 |
Ну это не сложно. Можно и циклом. Ну а как распаковывать сжатый файл? |
Автор: Win MK 32 3.10.2002, 23:43 |
Наоборот. (Замена одного символа на один) |
Автор: neutrino 10.10.2002, 01:36 | ||||
Это простой перевод в другую систему счисления. Вот тебе и алгоритм. А тот алгоритм, что Вит предложил называется арифметическим кодированием. Он на самом деле лучше Хоффмана в этом случае. |
Автор: Indigo 8.1.2003, 19:28 |
А как вы будете сжимать в два раза![]() ![]() ![]() |
Автор: Vex 8.1.2003, 22:08 |
Я вот тоже придумал свой архиватор - сжимает любой файл до 5 байт. Сейчас работаю над разархиватором ![]() ![]() ![]() |