April 13th, 2021

lenin

Об одном самонадеянном комментарии

Трюк из предыдущего поста базируется на том, что программа 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-х годов были от силы порядка сотен килобайт (потому что емкости дисков были порядка единиц мегабайт), вот и в программе написано



На самом же деле это наглое враньё, и рассуждение выше с "действительно" - заблуждение. В молодости у меня не потребовалось много времени, чтобы, познакомившись с программой pack, вызвать эту диагностику с помощью файла гораздо меньшей длины, чем 16 Мб. Попробуйте и вы.

Автор первоначальной программы - T.G. Szymanski (тот, который вторая S в LZSS). Вот же ж ведь позорник.

This entry was originally posted at https://spamsink.dreamwidth.org/1209677.html. Please comment there using OpenID.
lenin

Придумал способ делать спойлеры

...не зависящие от движка и не требующие стилей, джаваскрипта и подобного.
Вот такой:

Считаю, что придумал, потому что ни у кого раньше такой не видел.

This entry was originally posted at https://spamsink.dreamwidth.org/1209863.html. Please comment there using OpenID.
lenin

Я вам один капитализационный вопрос задам, только вы не обижайтесь

Если в США чёрный полицейский застрелит ку-клукс-клановца, или кто там сейчас вместо них, напишут ли в прессе про него the black police officer who fatally shot a White man?

This entry was originally posted at https://spamsink.dreamwidth.org/1210277.html. Please comment there using OpenID.