Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > Алгоритмы > Алгоритм Сжатия данных


Автор: Win MK 32 4.9.2002, 02:57
Я придумал как сжимать файлы в 2 раза! :colgate Надо заменять каждые два символа одним. И таким образом можно сжимать одно и то же в 2, 4, 8 и тд. раз!:colgate  Но!  :hmmm Иногда файл состоит из нечетного количества символов (Например, после первого сжатия). В этом вся проблема! :sneaky2  у кого-нибудь есть предложения как усовершенствовать  этот метод сжатия данных!?  :bored

Автор: 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)
Цитата
давай я тебе пришлю файл длинной 65536 байт
Это конкретны пример. Надо решить проблему с тем, чтобы сжимались и файлы с нечетным количеством символов.

С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
Цитата(Chingachguk @ 04.9.2002, 16:53)
Допустим, файл состоит из 64 символов. Последовательно сжимая его вдвое, получаем: 64->32->16->8->4->2->1 байт. Неплохо ! Но над этим еще надо поработать: что это такое, зачем этот лишний байт ?! Надо довести алгоритм до ума, чтобы можно было сжимать до нуля !

НЕЕЕЕЕЕЕЕЕЕЕ!
надо добиться сжатия до отрицательного размера, чтобы место на ж.диске освобождалось :)))))

Автор: FdX 1.10.2002, 00:30
Цитата
Я придумал как сжимать файлы в 2 раза! :colgate Надо заменять каждые два символа одним.

Алгоритм твой понятен. Если текстовый файл состоит только из букв латинского алфавита, пробелов, запятых и т.п., то на кодирование одного символа уйдет 5 битов (32=2^5 (или как там это пишется)). Если добавить ещще кирилицу, то уже 2 в шестой степени (6 битов). Если 2 в шестой, то сжатие будет всего 25%.
Цитата
Иногда файл состоит из нечетного количества символов

Реализуй сначала с четным кол-вом, а потом это добавим

Автор: Win MK 32 1.10.2002, 02:48
С заменой двух символов на один проблям нет, но надо, чтобы это происходило автоматически(Нужен алгоритм).
Цитата
надо добиться сжатия до отрицательного размера, чтобы место на ж.диске освобождалось :)))))

А это возможно!?!  :butbut  :D

Автор: FdX 2.10.2002, 23:24
Цитата
надо, чтобы это происходило автоматически

Не понятно. Поясни

Автор: Win MK 32 3.10.2002, 03:15
Я имею в виду то, что автоматически должно происходить следующее:
1)Перебирались по два все символы
2)И осуществлять замену не перебором
Например:
Код
ЕСЛИ два_символа = "01" ТО   Вставить_в_тест "2"
ИНАЧЕ ЕСЛИ два_символа = "hd" ТО   Вставить_в_тест "w"
ИНАЧЕ ЕСЛИ два_символа = "?;" ТО   Вставить_в_тест "№"
...
и тд.

А...например...циклом или еще как...

Автор: FdX 3.10.2002, 23:02
Ну это не сложно. Можно и циклом.
Ну а как распаковывать сжатый файл?

Автор: Win MK 32 3.10.2002, 23:43
Наоборот. (Замена одного символа на один)

Автор: neutrino 10.10.2002, 01:36
Цитата(Win @ 02.10.2002, 17:15)
Я имею в виду то, что автоматически должно происходить следующее:
1)Перебирались по два все символы
2)И осуществлять замену не перебором
Например:
Код
ЕСЛИ два_символа = "01" ТО   Вставить_в_тест "2"
ИНАЧЕ ЕСЛИ два_символа = "hd" ТО   Вставить_в_тест "w"
ИНАЧЕ ЕСЛИ два_символа = "?;" ТО   Вставить_в_тест "№"
...
и тд.

А...например...циклом или еще как...

Это простой перевод в другую систему счисления. Вот тебе и алгоритм.
А тот алгоритм, что Вит предложил называется арифметическим кодированием. Он на самом деле лучше Хоффмана в этом случае.


Автор: Indigo 8.1.2003, 19:28
А как вы будете сжимать в два раза??? Суммой??? А как слагаемые будете узнавать???

Автор: Vex 8.1.2003, 22:08
Я вот тоже придумал свой архиватор - сжимает любой файл до 5 байт.

Сейчас работаю над разархиватором :D :D :D

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)