Об алгоритмах сжатия

 

Zeus

Динамик

Не поверю, пока не увижу ;) Особенно в то, что для любых файлов годится.

Вот есть у нас файл без избыточности, т.е. информацию из него уже не выкинешь. Значит, они собираются уменьшить ее количество в 100 раз, переложив, соответственно, остальное на распаковщик. А поскольку файл произвольный, этот распаковщик должен знать все способы размещения информации, то есть попросту предусматривать в себе все возможные файлы :) Тогда сам распаковщик будет просто громадного размера (или бесконечного) :p

Кстати, на Нобелевку в любом случае не потянет: математикам она не полагается :p
И животноводство!  
+
-
edit
 

varban

администратор
★★★
В подтверждение приведу рассказ известного в прежние времена журналиста Николая Семенова. Началась история на заре перестройки, когда тогдашнее "прозападное" правительство страны во время одного из вояжей захватило молодых предпринимателей перенимать опыт капиталистического управления. Среди них был руководитель успешного многопрофильного кооператива (Платов, если кто помнит те времена и имена), который на всех фуршетах пил исключительно водку, а на скучных демонстрациях организации управления производством, посмеиваясь, говорил, что его ребята безо всяких этих менеджеров, планов, графиков и отчетов и почище вещи сделать могут, особенно в интеллектуальной области.

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

Следующая поездка долго не случалась, "прозападное" правительство ушло в отставку, а новое, напротив, не учиться, а учить других желало. Платов, воспользовавшись случаем, вызвался на очередной выставке показать достижения русской мысли. Отряхнув пыль с подарка, он всучил его Леве, своему ведущему программисту, дав "техническое задание": сделать то, не знаю что, но чтобы все отпали.

Нашим хакерам к таким заданиям было не привыкать. Они не могли сказать, когда и что будет готово, - да Платов и не спрашивал: ребята его никогда не подводили. Взял Лева двоих помощников, прошлись они пару раз по подарку дизассемблером и после нескольких бессонных ночей в дымном полуподвале вспомнили несколько недокументированных особенностей DOS, на самом низком уровне команд процессора, используя нестандартным образом любой бит каждого регистра, вставили несколько затычек и привезли не успевшего проспаться Леву с дискетой в последний момент прямо к трапу самолета с правительственной делегацией.

"Возвращение" подарка было обставлено с большой помпой. Прародители утилиты, правда, долго не могли понять, что же в ней изменилось (интерфейс-то тот же самый остался), но когда Лева записал фидошную конференцию в несколько сотен мегабайт на одну дискету, их удивлению не было преела. Оказалось к тому же, что программа размером на два байта меньше стала. Более того, при замене оригинальных процедур на новые удалось сэкономить несколько байт, в которых теперь гордо красовались имена хакеров.
- И твое имя тут есть? - спросили Леву.
- Никак нет, - отвечает Лева, - моего одного и нет. Мой модуль настолько маленький, что на нем мое имя не поместится. Зато я его сделал одной левой, и он самое популярное в Фидо слово из трех букв всего в один бит кодирует, за счет этого и такая фантастическая компрессия выходит!
В общем, триумф был небывалый. Вот только потом, при тестировании, выяснилось, что с англоязычными (особенно литературными) текстами коэффициент сжатия не такой уж фантастический, а бинарные файлы новая утилита не только не сжимает, а даже и увеличивает. Так что новых заказов, на которые Платов рассчитывал, получить не удалось.
 
+
-
edit
 

varban

администратор
★★★
Тем не менее, мастерство Левы оценили и пригласили на стажировку в известную компанию. На одной вечеринке авторы исходной программы поинтересовались, где он теорию кодирования изучал.

Лева им отвечает:
- Наша наука простая: в курилке поболтаешь, а что не найдешь - по Фидо спросить можно.
Они говорят:
- Это жалко, лучше бы вы теорему Ш-К почитали, которая теоретический предел кодирования устанавливает. Тогда вы могли бы сообразить, что наша утилита всего на 1% до этого предела не дотягивает, а при уменьшении ее размера хоть на один байт ближе 5% к пределу не подойти.
Лева спорить не стал, хотя и не поверил. А в скорости стажировка закончилась, Лева по пути на родину пытался на спор перепить одного англичанина, что кончилось плохо для обоих. Но англичанина вылечили, а Лева с тех пор из-за постоянных запоев стал профнепригоден. Когда он входит в запой, то вспоминает самый большой секрет, который со стажировки вез, и умоляет собутыльников:
- Скажите Платову, что буржуины программы, прежде чем тиражировать, у программистов отбирают и тестировщикам отдают: пусть и у нас тестировать станут, а то, храни Бог, в них блохи заведутся!

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

//

Самый мягкий - Журнал "Компьютерра"

Кто не верит, что наш софт - "самый мягкий", пусть обратится через редакцию "Компьютерры" в любую российскую программистскую компанию. Там вам покажут россыпи самородков - золотой фонд России, ее интеллектуальный капитал.

// www.computerra.ru
 
 

Tima

втянувшийся
Для некоторых типов файлов вполне верится.Например если в файле
есть много цепочек:1111111(7-1),0000000(0-7),дальше можно организовать неограниченный уровень вложений.Да я полностью согласен что словарь получится довольно большой.
 
+
-
edit
 

=KRoN=
Balancer

администратор
★★★★☆

Сжатие в 100 раз без потерь?




Компания ZeoSync заявляет, что ее математики вплотную подобрались к алгоритму сжатия цифровой информации, который позволит сократить исходный размер в 100 раз _без потерь_. "Вплотную подобралась" - это означает, что команда ученых успешно опробовала алгоритм на небольшом файле. Файл содержал случайный набор символов (т.е. избыточности по определению вроде как уже не должно быть!).

Если на больших объемах алгоритм покажет себя успешно, то он потянет на Нобелевскую, надо полагать. Потому как горизонты открываются просто фантастические. HiTech индустрия получит огромный толчок вперед. Во-первых, интернет - станет возможным видео на низких скоростях, MP3 и иже с ним можно будет забыть. Правда, с одной оговоркой - если скорость _распаковки_ будет приемлимой.
На сайте о новых горизонтах в теории сжатия информации было заявлено 7 января 2002. Принцип сжатия, описаный на сайте, достаточно туманен, непонятно, почему бы не разбивать большие файлы на куски поменьше и с ними оперировать, раз уж все работает на малых объемах... Вопросов много. На сайте обещают (если все будет хорошо) коммерческую версию утаптывателя к 2003 году.

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

Посмотрим.

[small]// [html_a href=http://cooler.it/cl140102.html target=_blank]http://cooler.it/cl140102.html
[/small]
// ссылку прислал Alex
 
+
-
edit
 
TEvg>Не верю.

Про поиск базиса для данной системы векторов слышали когда-нибудь? Мой знакомый многопроходной компрессией на подобной математике занимается.

Про утаптывание в сотню раз не знаю, врать не буду.
 

в начало страницы | новое
 
Поиск
Настройки
Твиттер сайта
Статистика
Рейтинг@Mail.ru