LINUX.ORG.RU
Форум — Talks  

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


0

0
Есть идея что на алгоритме поиска хэш коллизий можно сделать архиватор с неоднозначной распаковкой. это даже не архивация с потерями, а вообще не понять что. зато сжимает очень круто.

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

или если есть кусочек данных. например можно восстанавливать торренты где полного источника нет.

но, конечно, в идеале из торрент файла получать то на что он ссылается. условие что данные не шум может оказаться достаточным для восстановления.

эх, где мой мегакластер для экспериментов.

★★★
← [анабиоз][qt]Блацкович может выходить в интернет
[озвучиватель девайсов 2] Тот самый маунтманагер →
  1 2 →
Ответ на: комментарий от vasaka
короче вопрос в том сколько будет коллизий для того же фильма, удовлетворяющих условию что человек это воспримет за фильм?
vasaka ★★★
() автор топика
Ответ на: комментарий от vasaka
>если добавить к фильму текстовое описание сюжета - то может одна?

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

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

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

Davidov ★★★★
()
Ответ на: комментарий от melkor217
>Не припомню его трудов, имеющих отношение к вопросу.

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

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

Macil ★★★★★
()
Ответ на: комментарий от Davidov
блин, врубился.

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

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

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

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

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

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

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

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

Alsvartr ★★★★★
()
Ответ на: комментарий от Alsvartr
та ладно, всего-лишь экспоненциальные. это почти то же самое с практической точки зрения, но все же не бесконечность.
vasaka ★★★
() автор топика
тред-индикатор ЛОРа "кто прогуливал дискретную математику"
your_bunny
()
> но. на некоторых данных разархивирование может стать однозначным. например если добавить условие что нужно на выходе получить корректный mp3 файл.

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

guest065234
()
Ответ на: комментарий от DNA_Seq
Нет. В eMule хеши используются для адресации, а не для восстановления по ним исходных данных.
Zenom ★★★
()
http://forum.ixbt.com/topic.cgi?id=40:515

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

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

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

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

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

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

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

Ты описал то ли перелемпелзива, то ли недохаффмена.
shimon ★★★★★
()
Ответ на: комментарий от ftor
да знаю я что тупиковый.

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

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

vasaka ★★★
() автор топика
Ответ на: комментарий от Deleted
> Можно показать, что почти у всех строк колмогоровская сложность очень большая. И лишь у горстки строк она низкая.

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

n01r ★★
()
Ответ на: комментарий от Macil
> Ну как бы его труды по теории информации к вопросу имеют прямое отношение.

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

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

melkor217 ★★★★★
()
Ответ на: комментарий от shimon
> Ты описал то ли перелемпелзива, то ли недохаффмена.

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

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

melkor217 ★★★★★
()
раз уж с хэшами облом, то вот еще идея из разряда миллиард обезьян. перебирать проги размера n генерящие данные размера m. пока не найдешь подходящую.
vasaka ★★★
() автор топика
Ответ на: комментарий от vasaka
при этом тут уже может помочь что-нибудь вроде генетических алгоритмов. если нужно делать сжатие с потерями, то есть шанс на эффективность.
vasaka ★★★
() автор топика
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.
  1 2 →
← [анабиоз][qt]Блацкович может выходить в интернет
Talks
[озвучиватель девайсов 2] Тот самый маунтманагер →