мегаархиватор.

короче вопрос в том сколько будет коллизий для того же фильма, удовлетворяющих условию что человек это воспримет за фильм?

если добавить к фильму текстовое описание сюжета - то может одна?

>если добавить к фильму текстовое описание сюжета - то может одна?

Чуть более чем дохрена.

Если сказать: длина фильма - 732311123 байт и текстовое описание, достаточно ли тебе этого будет для восстановления? Нет. Хеш длиной в 100 кб сокращает пространство поиска всего лишь на 100кб, вот и считай (коллизии распределены равномерно).

Вот тебе ещё повод для размышление: в знаках числа пи содержатся все возможные числовые последовательности. Можно ли сделать на основе этого архиватор?

>Не припомню его трудов, имеющих отношение к вопросу.

Ну как бы его труды по теории информации к вопросу имеют прямое отношение.

И вообще, тогда хеша нужно два.

блин, врубился.

>Хеш длиной в 100 кб сокращает пространство поиска всего лишь на 100кб

вот это я из виду как-то упустил.

действительно фигню выдумал.

хорошо, оперируем блоками размером n. для каждого блока храним хэш размером h и сигнатуру размером s. в таком случае количество коллизий c = 2^n / 2^(h+s) (1)

нам требуется c = 1

из 1 очевидно, что для этого должно выполняться условие n - (h + s) = 0, а значит h + s = n. сжатия не получается.

>думаю есть шансы что с увеличением мощностей начнут применять метод "миллион обезьян много миллиардов лет печатали" для генерации контента.

Для генерации чего-либо сложнее "hello, world" понадобятся бесконечные мощности.

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

Выдыхай.

ты только что изобрел eMule

тред-индикатор ЛОРа "кто прогуливал дискретную математику"

> но. на некоторых данных разархивирование может стать однозначным. например если добавить условие что нужно на выходе получить корректный mp3 файл.

Только если данные в файле умещаются в длину md5 хеша, иначе перед тобой будет множество коллизий c заголовками mp3 файлов.

Нет. В eMule хеши используются для адресации, а не для восстановления по ним исходных данных.

http://www.linux.org.ru/jump-message.jsp?msgid=1675302&cid=1676278

http://forum.ixbt.com/topic.cgi?id=40:515

Особо рекомендуется к прочтению первый же пост IronPeter'а:
> Господа. Хотите я докажу теорему, что сжатие в принципе невозможно?

> Дано: алфавит из N букв. Наборов строк длины K ровно N^K штук. Теперь мы хотим переписать (закодировать) эти строки на том же языке, используя строки длины <K. Таких строк меньше или равно, чем N^{K-1}. Нельзя однозначно отобразить множество из большего числа элементов на множество их меньшего числа элементов. Можно показать, что если наша операция сжимает хоть одну строку, то оно "разжимает" какую-то другую строку. Сжатие в принципе невозможно!

> Возможно оно лишь в том случае, ежели мы сжимаем строки с разумным строением. Есть такое понятие - колмогоровская сложность строки. Грубо говоря, это длина минимальной программы на формальном языке (скажем, на C), которая печатает данную строку. У строки, состоящей из первого миллиарда знаков pi после запятой, колмогоровская сложность копеечная. Между тем эта строка _может__быть_ (я не берусь доказать, что она такова) чрезвычайно плохой с вероятностной точки зрения (стандартная энтропия большая).
> Можно показать, что почти у всех строк колмогоровская сложность очень большая. И лишь у горстки строк она низкая. Так что у строки, снятой с генератора белого шума, колмогоровская сложность относительно заданного формального языка будет почти наверняка большой, то есть такую строку нельзя сжать.

Только читать надо со включенным мозгом, иначе эффект может быть непредсказуемым =).

смысл...

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

Разумный архиватор готов. Вот только воспользоваться им смог бы, пожалуй, только боженька, которого, как _МЫ ВСЕ ЗНАЕМ_, не.

> Пример простого сжатия: сначала выделяем самые часто встречаемые и длинные слова (в данном файле или вообще). Допустим, таблица генерируется из файла и хранится вместе с архивом. А затем архивируем: переходим к более мощному алфавиту, допустим, двухбайтовому.

Ты описал то ли перелемпелзива, то ли недохаффмена.

Тотальный перебор - эот тупиковый путь. Надеюсь, ты это поймешь

да знаю я что тупиковый.

да только вот не всегда. иногда метод работает. некоторые группы, например так классифицировали.

или, вот, комп в шашки так научили играть.

> Можно показать, что почти у всех строк колмогоровская сложность очень большая. И лишь у горстки строк она низкая.

одно дело _почти всех строк_, другое _почти всех используемых строк_, которые как раз, походу, и представляют эту горстку...

> Ну как бы его труды по теории информации к вопросу имеют прямое отношение.

По теории информации? Гм, а почему труды Черча, Тьюринга, Фон Неймана, Кнута, Дейкстры, [...] по теории информации не имеют прямого отношения к вопросу?

Если у Шеннона всё-таки есть что-то, связанное с хеш-таблицами и сжатием данных -- кидайте, местные аналитики будут рады.

> Ты описал то ли перелемпелзива, то ли недохаффмена.

Именно поэтому я и не стал называть то, что получилось))

Просто на ходу придумывалось что-нибудь работающее лучше этих хешей, чтобы быстро описать на словах.

раз уж с хэшами облом, то вот еще идея из разряда миллиард обезьян. перебирать проги размера n генерящие данные размера m. пока не найдешь подходящую.

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