Об одном самонадеянном комментарии
Трюк из предыдущего поста базируется на том, что программа zcat (gunzip), кроме своего собственного формата .gz, умеет разжимать еще и устаревшие форматы compress (.Z), который был основным и самым популярным до распространения gzip, а также предшествоваший ему формат pack (.z).
Этот формат pack был довольно прост. До 1977-78 годов, когда профессор אברהם למפל (родившийся в 1936 году, как и положено еврейскому математику, во Львове) и профессор יעקב זיו (родившийся в 1931 году, сабра), да будут они оба здоровы, изобрели семейство алгоритмов LZ, всё искусство сжатия текстов, отличных от длинных повторов одинаковых символов, недалеко ушло от кода Морзе: чего много - обозначаем более короткой последовательностью нулей и единиц вместо точек и тире, чего мало - обозначаем более длинной. В алгоритмические детали (префиксные коды, отличия кодировки Хаффмена от Шеннона-Фано) вдаваться не будем.
Благодаря тому, что создателю программы была поставлена задача сжимать только файлы (а не потоки байтов), сжиматель работает в два прохода - сначала собирает статистику по символам и строит таблицу, а потом читает файл ещё раз и выдаёт его сжатый вид. Из-за этого в начале сжатого файла есть таблица соответствия символов кодам, в которой можно устроить почти произвольную перетасовку символов, в частности ROT13.
А теперь по существу темы поста. Для простоты и скорости выполнения программы максимальная длина кода была ограничена 24 битами, чтобы при побайтной записи в сжатый файл или чтении из него в 32-битном слове гарантированно помещался как минимум один код независимо от положения кода по отношению к границам байтов (можно бы и 25, в принципе, ну да ладно). Эффективный алгоритм построения кодов с ограничением длины тогда еще не придумали, поэтому решили, что на практике такого соотношения частот символов, которое могло бы привести к кодам длиной более 24, не встретится. Действительно™, чтобы у символа был код длиной 1 бит, его частота должна быть порядка 50%, длиной 2 бита - порядка 25%, и т.п. Итого, чтобы длина кода была больше 24, частота символа должна быть меньше 1/224, а это может быть, только если символ встречается реже, чем 1 раз на 16 Мб.
Типичные длины файлов, которые могло бы захотеться сжимать этим алоритмом, в конце 70-х годов были от силы порядка сотен килобайт (потому что емкости дисков были порядка единиц мегабайт), вот и в программе написано
if (maxlev > 24) { /* can't occur unless insize.l.lng >= 2**24 */ printf (": Huffman tree has too many levels"); return(0); }
На самом же деле это наглое враньё, и рассуждение выше с "действительно" - заблуждение. В молодости у меня не потребовалось много времени, чтобы, познакомившись с программой pack, вызвать эту диагностику с помощью файла гораздо меньшей длины, чем 16 Мб. Попробуйте и вы.
Автор первоначальной программы - T.G. Szymanski (тот, который вторая S в LZSS). Вот же ж ведь позорник.
This entry was originally posted at https://spamsink.dreamwidth.org/1209677.html. Please comment there using OpenID.
Этот формат pack был довольно прост. До 1977-78 годов, когда профессор אברהם למפל (родившийся в 1936 году, как и положено еврейскому математику, во Львове) и профессор יעקב זיו (родившийся в 1931 году, сабра), да будут они оба здоровы, изобрели семейство алгоритмов LZ, всё искусство сжатия текстов, отличных от длинных повторов одинаковых символов, недалеко ушло от кода Морзе: чего много - обозначаем более короткой последовательностью нулей и единиц вместо точек и тире, чего мало - обозначаем более длинной. В алгоритмические детали (префиксные коды, отличия кодировки Хаффмена от Шеннона-Фано) вдаваться не будем.
Благодаря тому, что создателю программы была поставлена задача сжимать только файлы (а не потоки байтов), сжиматель работает в два прохода - сначала собирает статистику по символам и строит таблицу, а потом читает файл ещё раз и выдаёт его сжатый вид. Из-за этого в начале сжатого файла есть таблица соответствия символов кодам, в которой можно устроить почти произвольную перетасовку символов, в частности ROT13.
А теперь по существу темы поста. Для простоты и скорости выполнения программы максимальная длина кода была ограничена 24 битами, чтобы при побайтной записи в сжатый файл или чтении из него в 32-битном слове гарантированно помещался как минимум один код независимо от положения кода по отношению к границам байтов (можно бы и 25, в принципе, ну да ладно). Эффективный алгоритм построения кодов с ограничением длины тогда еще не придумали, поэтому решили, что на практике такого соотношения частот символов, которое могло бы привести к кодам длиной более 24, не встретится. Действительно™, чтобы у символа был код длиной 1 бит, его частота должна быть порядка 50%, длиной 2 бита - порядка 25%, и т.п. Итого, чтобы длина кода была больше 24, частота символа должна быть меньше 1/224, а это может быть, только если символ встречается реже, чем 1 раз на 16 Мб.
Типичные длины файлов, которые могло бы захотеться сжимать этим алоритмом, в конце 70-х годов были от силы порядка сотен килобайт (потому что емкости дисков были порядка единиц мегабайт), вот и в программе написано
if (maxlev > 24) { /* can't occur unless insize.l.lng >= 2**24 */ printf (": Huffman tree has too many levels"); return(0); }
На самом же деле это наглое враньё, и рассуждение выше с "действительно" - заблуждение. В молодости у меня не потребовалось много времени, чтобы, познакомившись с программой pack, вызвать эту диагностику с помощью файла гораздо меньшей длины, чем 16 Мб. Попробуйте и вы.
Автор первоначальной программы - T.G. Szymanski (тот, который вторая S в LZSS). Вот же ж ведь позорник.
This entry was originally posted at https://spamsink.dreamwidth.org/1209677.html. Please comment there using OpenID.