Comments
Прикольно также что на тот патент уже в своих патентах ссылаются куча технологических гигатов (как то Microsoft, Apple, Citrix и тд).
Вот это годный пример переиспользования знаний.

По мнению Патентов Гугла каждый день после сентября 2011 для этого патента (lz77+hashing) является днем истечения его срока. Например, 2 июня 2019 http://web.archive.org/web/20190602195814/https://patents.google.com/patent/US5140321
2011-09-04 Anticipated expiration legal-status Critical
2019-06-02 Application status is Expired — Lifetime legal-status Critical
https://news.ycombinator.com/item?id=20182019 "Google patents always shows the current date for that line."
В общем случае патент действует около 20 лет от даты Application — https://en.wikipedia.org/wiki/Term_of_patent_in_the_United_States

Шикарно!
Ощущение погружения в магию.
Всегда хотелось знать что там происходит за полосой прогресса.
Ещё интересней было бы это всё визуализировать для наглядности. Т.е. чтобы выводился лог действий, создаваемые таблицы, списки и т.д.
Чтобы заварить чайку, взять пару круассанов, поставить пару гигов на сжатие и вальяжно растянуться в кресле…
В свое время архивировали 1 Мегабайт на 8088. 30 минут. 1 Мегабайт.
Прочитал про некий «беспрефиксный» код и удивился.
Да, в оригинале «Such a code is called a prefix-free code, or sometimes just prefix code», но у нас всё же используется термин «префиксный код». Так сказать, always, а не sometimes.
UFO landed and left these words here
Обратите внимание, что из-за возможного перекрытия мы не можем использовать memcpy или memmove.
memmove в отличии от memcpy как раз же и сделан, чтобы иметь возможность копировать перекрывающиеся участки, разве нет?
Вам это может показаться странным, но метод работает: после того, как скопированы байты первых трёх «-la», копирование продолжается уже с использованием недавно сгенерированных байтов.
случайно не именно этот ли чудесный механизм как раз и позволяет создавать zip-бомбы? :)
Ну ведь прямо там пятым примечанием ссылка обратно на хабр, где описывается новейшая (улучшающая традиционную рекурсивную упаковку архива в архив) техника зип-бомб от 2019 года, использовано рекурсивное описание группы файлов друг через друга. Видимо, рекурсивное создание бесконечного потока данных разархиватором не поддерживается.
Спасибо за хороший перевод! И оффлайн копию в комп сохранить на память :)
Естественно заархивирую, сначала копию в ARJ, LHA, HA, RAR, 7Z, и конечно в ZIP :)

Тему арифметического кодирования приподнять бы посильнее.
Вот где действительная магия: упаковка по динамическому словарю с нецелым количеством бит в символах в один проход и достижение теоретической энтропии!

Арифметическое кодирование описывается довольно просто:


  1. Начинаем с полуинтервала [0; 1)
  2. На каждом шаге текущий полуинтервал делим на подполуинтервалы.
    Длины будут соответствовать вероятности встретить соответствующую букву.
  3. Выбираем подполуинтервал, соответствующий текущей букве сжимаемого сообщения.
  4. Повторить для всех букв сообщения.
  5. Число из полученного полуинтервала и будет закодированным сообщением.

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

Я тоже в студенчестве реализовывал такой алгоритм, но для себя.
Если выделить отдельный класс "битовый поток", то туда уйдет большая часть сдвигов.
Оставшееся — это обработка границ полуинтервала. Там 2 тривиальных случая и один посложнее:


  1. Верхняя граница меньше 0,5. Тогда пишем в выходной поток 0 и раздвигаем границы вдвое.
  2. Нижняя граница больше 0,5. Тогда пишем в выходной поток 1 и раздвигаем границы вдвое.
  3. Обе границы близки к 0,5. Тогда в выходной поток ничего писать не нужно, но для нескольких старших бит осталось всего два варианта: 011...1 или 100...0. Это можно запомнить и снова раздвинуть границы вдвое.
Хотя файл архива .ZIP, хоть офисный документ, хоть какой-то свой кастомный формат, а в первых двух байтах файла записано «PK». В статье сказано, что Zip-файл не требует никакой сигнатуры или магического числа в начале файла, зачем тогда их пишут? Просто дань уважения Филу Катцу?
А фиг его знает. Но для примера — упакованное расширение для Google Chrome представляет собой zip-файл с расширением .crx в начале!!! которого есть специальный заголовок, только после которого, относительно далеко от начала, можно найти заголовок PK самого zip. И если скормить этот файл WinRar'у то он не подавится, а признает в нем zip-архив. Подозреваю, что по заголовку и находит.
Написано, что файл в целом не обязан иметь сигнатуру. А сигнатура «PK» 0x05 0x06 — это заголовок архивной записи. Собственно, это и используется для создания SFX-архивов: он начинается, как исполняемый файл, а где-то в конце к нему приклеены архивные записи.
Жаль в заключении нет (или я не увидел) практическое сравнение перечисленных в статье методов сжатия. Технически подкованные специалисты конечно же поймут имеющиеся приемущества и недочеты, а вот люди вроде меня не совсем… но было очень познавательно.

Вроде как и знал всё это, и deflate реализовывал из любопытства, а всё равно прочитал на одном дыхании.

ШОК! Реклама Flex Paste в блоге mail.ru на Хабре
Вопрос к автору: сколько заплатили?
ШОК! Реклама GitHub в виде ссылки на исходники в большинстве статей на Хабре
Вопрос к авторам: сколько заплатили?
Да если бы это петросянство было, в большинстве случаях такие комменты на серьезных щах оставляют. Хорошо если вы и правда попытались пошутить.
Еще не все прочитал, но уже вопросы:
«Обратите внимание, что из-за возможного перекрытия мы не можем использовать memcpy или memmove.»
Не знаю про какой стандарт речь, и были ли в более ранних стандартах отличия, но C99 накладывает ограничение о недопустимости перекрытия только на memcpy. А memmove — можно использовать для пересекающихся регионов.

Здесь, возможно, не совсем корректный перевод. Я так понял, суть в том, что, так как исходный и результирующий интервалы могут перекрываться, часть байт исходного интервала может быть банально неизвестна в начале копирования. К примеру, "ababa" может быть закодировано как "ab(3,2)", т.е. "отступить на 2 символа назад и скопировать 3 символа": третий копируемый символ будет отсутствовать на положенном месте, пока мы не скопируем первый.

Согласен, причина в том что исходный блок изначально полностью отсутствует в памяти. memmove должен просто переместить блок вперед(для чего начнет копирование с конца, чтобы не испортить), а раз блока как такового еще нет, то нужный результат не будет достигнут. Поэтому и нужен свой алгоритм копирования. В итоге memcpy нельзя из-за ограничения по пересечению, что на мой взгляд сводится к тому что стандарт не регламентирует с какой стороны начнется копирование и какими частями, а memmove нельзя по описанной ранее причине.
Компания обвинила его в нарушении торгового знака
Правильный перевод термина trade mark — «товарный знак».
Only those users with full accounts are able to leave comments. Log in, please.