Имя (желательно полное):

E-Mail:

URL:

Город:

Страна:

Вежливый и подробный комментарий:
(Форматируйте его, пожалуйста, как почту - короткими строками
Еnter в конце строки, пустая строка между параграфами).
> > Мне кажется ни один компрессор не пытается обнаружить структуру файла, обычно архив это словарь и перекодированный по новому словарю файл. Грамматики там нет. Искать грамматику если даже возможно то это наверняка дорогое удовольствие, поэтому ширпотребные архиваторы этого не делают. > В естественных языках грамматику выделить не так-то и просто. Вот классический пример: "Глокая куздра штеко будланула бокра и кудрячит бокренка". Очевидно, что не зная _смысла_ фразы, осуществить грамматический разбор будет затруднительно. Будем учить архиваторы пониманию смысла речи? > Простейший грамматический разбор можно построить на базе словаря, но мне почему-то кажется, что выигрыш от LIPT-подобного преобразования в таком случае будет выше, чем от грамматического разбора. > > Простая академическая задача, всего два слова - "максимальное сжатие". Затраты памяти или машинного времени просто не принимаются во внимание. Тогда что? > Анализировать задачу ;) > > Я понимаю что теоретически архиваторы вообще не возможны, но случилось так что мы живем в реальном мире и имеем относительно узкий класс файлов, поэтому архиваторы и существуют. Но что если мы не знаем этот класс? Т.е. речь идет об универсальном методе сжатия, в смысле моделей источника. > Не будет и сжатия. Доказательство несуществования алгоритмов, позволяющих сжать произвольный файл (т.к. класс, к которому принадлежит файл нам неизвестен, мы не можем сделать никаких выводов о его структуре) в этом форуме приводилось. Также легко доказать, что если нам известен класс файлов, которые предстоит сжимать, то сжатия можно добиться всегда. > > Вот есть 256 возможных файлов длиной 8 бит. Отправитель выбрал из них 32 штуки, и передает нам. Мы знаем что файлы длиной в 8 бит, мы даже получили уже штук десять, но мы еще не задумывались о том правиле которым этот человек руководствовался отбирая файлы. Как в общем случае сделать предположение какие 32 файла выбрал отправитель? > В общем случае -- никак. Пусть мы уже получили байты > 2, 187, 4, 14, 6, 111, 8, 208, 10, 9 > Тогда возможны такие варианты: > 1) Это случайный выбор, и все закономерности -- игра ГСЧ > 2) Это некая последовательность A(n) = > F(n, A(n-1),... A(0)) > 3) На четных позициях стоят четные числа начиная с 2, на нечетных -- > а) случайные числа > б) A(2*n) = F(2*n, A(2*n-2), ... A(1)) > в) на позициях с номером 4*n+1 стоят случайные нечетные числа, 4*n+3 -- случайные четные > ... > 4) ... > ... > Доказать, что какое-нибудь из этих утверждений верно не представляется возможным. Опровергнуть же некоторые из них можно. Утверждения 1) и 2) принципиально невозможно опровергнуть. > Любая последовательность чисел может быть получена при помощи ГСЧ, и для любой последовательности чисел можно подобрать рекуррентную зависимость. > Более того, для любой конечной последовательности чисел можно подобрать бесконечное количество рекуррентных зависимостей. > В том слчае, если у нас нет дополнительной информации об источнике, какие-либо предположения относительно характера этой последовательности сделать невозможно.

Пожалуйста, заполните все поля.
И не нажимайте по два раза на кнопку! Дождитесь ответа сервера.