Оптимальное LZ-кодирование

[GriV]

2lvd> внимательней почитай, там из общей теории следуют парочка интересных выводов, интересных для тебя в том числе. Поиск оптимальных команд языка LZ* - вообще задача экспертной системы и для файлов разного контента (текст, медиа, код) эта задача по разному решаться будет (т.е. давать разный результат, тот же пример привёл Caro вообще-то). Пример с тем же LC - его команды в общем то очень неплохо подобраны для сжатия картинок, однако сильно сомнительно что при помощи LC можно будет эффективно текст или код сжимать - у него управляющие коды под другое заточены.
А потому универсальной последовательности нет, именно это и следует из отсылки, которая была до математика и воздушного шара.
Если ты хочешь сделать чтото совсем мегауниверсальное, сделай, скажем, штук 256 наборов управляющих команд - каждая из которых будет подбираться под сжимаемый файл - и в конце у тебя будет неизменно блестящий результат - для распаковщика дискретного всё равно весь набор команд (256 таблиц) известен, а для распаковщика интегрированного с архивом так вообще тем более - он изначально будет заточен под заданную комбинацию.

Немного пофантазировав (то что было чуть выше это банальные реалии
:-D) можно сообразить такое: файл сжимаемый разбивается на блоки по несколько килобайт каждый из которых сжимается по оптимальной таблице - итого будет уже не просто блестящий - а просто отличный результат, непревзойдённый в принципе.

Немножко оффтопа - тут один товарищ тоже упаковщик писал... который все файлы в 32 байта сжимал (-; я так за него радовался, жалко он рабочий алгоритм - рабочий код - не показал... (-%

[lvd]

2lvd> внимательней почитай, там из общей теории следуют парочка интересных выводов, интересных для тебя в том числе. Поиск оптимальных команд языка LZ* - вообще задача экспертной системы и для файлов разного контента (текст, медиа, код) эта задача по разному решаться будет (т.е. давать разный результат, тот же пример привёл Caro вообще-то). Пример с тем же LC - его команды в общем то очень неплохо подобраны для сжатия картинок, однако сильно сомнительно что при помощи LC можно будет эффективно текст или код сжимать - у него управляющие коды под другое заточены.
А потому универсальной последовательности нет, именно это и следует из отсылки, которая была до математика и воздушного шара.
Если ты хочешь сделать чтото совсем мегауниверсальное, сделай, скажем, штук 256 наборов управляющих команд - каждая из которых будет подбираться под сжимаемый файл - и в конце у тебя будет неизменно блестящий результат - для распаковщика дискретного всё равно весь набор команд (256 таблиц) известен, а для распаковщика интегрированного с архивом так вообще тем более - он изначально будет заточен под заданную комбинацию.

Эээ. Я хочу (хотел) лишь под существующий распаковщик паковать наиболее оптимально. Вот и всё. Это получилось. Переписывать распаковщик в мои планы не входило. Вот.

Немножко оффтопа - тут один товарищ тоже упаковщик писал... который все файлы в 32 байта сжимал (-; я так за него радовался, жалко он рабочий алгоритм - рабочий код - не показал... (-%

Гы. Легко доказать, что такое невозможно. =)

[SMT]

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

(если кто эту историю не слышал, могу запостить алгоритм)

[lvd]

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

(если кто эту историю не слышал, могу запостить алгоритм)

Запости. Такого быть не может в принципе.

[caro]

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

(если кто эту историю не слышал, могу запостить алгоритм)

Если я правильно помню он использовал имя файла, как дополнительную память.

[lvd]

Если я правильно помню он использовал имя файла, как дополнительную память.

Ха-ха, ну и правильно, что зажали, ибо читер подлый! =)

[Hrumer]

2caro: Да,похоже я слышал эту историю.. Кое-кто ыявлял определенный символ, который точно встречается в файле, и по нему разбивал файл на несколько. Сам символ, естественно в выходные файлы не записывался. Имена файлов, видимо, использовались для того, чтобы можно было правильно склеить эти файлы...

[lvd]

2caro: Да,похоже я слышал эту историю.. Кое-кто ыявлял определенный символ, который точно встречается в файле, и по нему разбивал файл на несколько. Сам символ, естественно в выходные файлы не записывался. Имена файлов, видимо, использовались для того, чтобы можно было правильно склеить эти файлы...

Не только имена, но и длины файлов - помечали места вставления символа, т.е. были дополнительными битами информации.

[SMT]

всё верно, был файл 1.txt с содержимым "Hello", стал 1-48.txt с содержимым "ello", потом стал 1-48-65.txt с "llo", и т.п...

[SMT]

Ха-ха, ну и правильно, что зажали, ибо читер подлый! =)

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