2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Эта тема закрыта, вы не можете редактировать и оставлять сообщения в ней. На страницу Пред.  1, 2, 3, 4, 5
 
 Re: Архивация - предела нет...
Сообщение28.03.2012, 23:41 


26/03/12
2
Спасибо за отклик! 8-)
Я один из тех, что пытались изобрести способ бесконечного сжатия информации. Обьемы информации постоянно растут и это было бы просто панацеей. Я продолжаю эксперименты по сжатию информации в надежде изобрести новый эффективный способ сжатия информации. Я провел просто масу экспериментов и, на мой взгляд, получил доказательства возможности алгоритма вечного сжатия.
Я переоткрыл заново алгоритм Хаффмана в перевернутом и прямом его использовании, алгоритм Лемпеля-Зива. (Арифметическое кодирование я рассматривал "через Google" я думал, что он круче чем эти два, но пришел к выводу, что он не сжимает сильнее моего гибрида из двоих первих, а иногда и хуже, а голову то сломать можно и я его закинул...) Я был просто потрясен узнав, что не я один пришел к таким же выводам и изобретениям, а так же Гибридные алгоритмы... На самом деле между всеми алгоритмами есть тесная взаимосвязь и можно сказать, что алгоритм Хаффмана и Лемпеля-Зива ОДНО И ТО ЖЕ. Рассмотрим два примера (это при том, что комбинации выстроены по колличеству повторений первая наиболее часто повторяема и т.д.).
Хаффман:
00 - 1
01 - 01
10 - 001
11 - 000
Лемпель-Зив:
000 - 00
001 - 010
010 - 011
011 - 100
100 - 101
101 -110
110 - 1110
111 - 1111
И в первом и во втором примере "слизан" верх на один бит (первая комбинация) и "утежелен" на 2 бита низ (две нижние комбинации). Схожесть видно правда? Лемпел-Зив можно еще "слизать" верх на 1 бит но тогда "приростет" низ на 2 бита. И вот, я для себя открил, что выигрыш в одном месте дает проигрыш в двух. Если удасться преодолеть этот порог (в одноместе выигрывать и в одном проигрывать), то тогда и будет катастрофическое сжатие, но увы... :-( Для сжимаемости колличество первых комбинаций должно превышать суму двух последних (или двух первых и четырех последних в Лемпель-Зива, идею можно развивать в зависимости от длинны сжимаемого слова).
Я проводил еще один эксперимент брал все возможные 20битные слова и пробовал на сжимаемость. Я заметил, что РОВНО ПОЛОВИНА поддается сжатию, возможно, это и не доказывает возможность бесконечного сжатия? Разве? Тогда другой пример. Я точно знаю, что есть прямая связь между сжимаемостью и разнице в колличестве единиц и нулей в сжимаемых данных, если их будет примерно одинаковое колличество данные не сожмуться (хотя и не всегда например 01 10 10 01 сожмется в два раза, но такого идеала в природе нет) к чему я веду? Возьмем RAR архив (максимально сжатый) - в нем будет почти равное колличество нулей и единиц (разница будет в несколько процентов) сколько можно построить слов используя равное колличество нулей и единиц? А если отбросить сжимемые комбинации (например та же 01 10 10 01 или 01 01 01 01 00 10 11 или еще какую-то)? А если еще взять до внимания то, что сжатая в RAR инфа не сожмется сжимай мы ее словами хоть 2, хоть 3 ... хоть 10битов длинной, колличество слов (длинною в архив) еще сузилась. Так сколько комбинаций этого слова может быть из всех возможных? А я скажу - приблизительно четверть из всех возможных! Подумайте! Вы еще не верите в возможность такого алгоритма?
Согласен - бред идея сжать в несколько бит фильм... Только что бы построить алгоритм и рабочую программу нужен комп такой мощьностью, что ее и представить себе невозможно. :-(
Идея в том чем больше файл тем сильнее можно ужать его...
А для меньших мощьностей то же вышло бы создать такой алгоритм если бы удавалось зжимать небольшой дисбаланс слов например двубитных:
00 - 2шт
01 - 1шт
10 - 1шт
11 - 1шт
Сжать не меньше чем на 1 бит, в независимости от порядка слов... На мой взгляд это невозможно...

 Профиль  
                  
 
 Re: Архивация - предела нет...
Сообщение29.03.2012, 10:25 
Заслуженный участник
Аватара пользователя


11/03/08
9496
Москва
Посмотрите "арифметическое кодирование". Там вопрос использования "небольшого дисбаланса" решён (разумеется, последовательность в 2 бита он не сожмёт, а вот миллион букв из Вашего алфавита с заданными Вами вероятностями сожмёт, пусть и не столь сильно).
А вообще - есть очень простая теорема, из которой следует, что создать универсально-сжимающий алгоритм нельзя не потому, что нет у нас СуперКомпьютера, а потому, что $2^N>2^N-1$

 Профиль  
                  
 
 Re: Архивация - предела нет...
Сообщение29.03.2012, 13:52 
Супермодератор
Аватара пользователя


29/07/05
8248
Москва
 !  Просто тему забыли закрыть вовремя. Был бы в CS раздел "Пургаторий" - отправилось бы туда. Но пока его нет, так что тема просто закрывается


-- Чт мар 29, 2012 15:08:22 --

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

По этой теме все, обсуждение закончено.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Эта тема закрыта, вы не можете редактировать и оставлять сообщения в ней.  [ Сообщений: 63 ]  На страницу Пред.  1, 2, 3, 4, 5

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group