Комментарии 45
Монументальный труд, спасибо!
Спасибо за исходники!
Внезапно, пошёл по ссылкам. Сегодня день, когда истёк патент на ARJ (запахло молодостью?)
2020-03-03
Application status is Expired — Lifetime
Вот это годный пример переиспользования знаний.
По мнению Патентов Гугла каждый день после сентября 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
Ощущение погружения в магию.
Всегда хотелось знать что там происходит за полосой прогресса.
Ещё интересней было бы это всё визуализировать для наглядности. Т.е. чтобы выводился лог действий, создаваемые таблицы, списки и т.д.
Чтобы заварить чайку, взять пару круассанов, поставить пару гигов на сжатие и вальяжно растянуться в кресле…
Да, в оригинале «Such a code is called a prefix-free code, or sometimes just prefix code», но у нас всё же используется термин «префиксный код». Так сказать, always, а не sometimes.
Тему арифметического кодирования приподнять бы посильнее.
Вот где действительная магия: упаковка по динамическому словарю с нецелым количеством бит в символах в один проход и достижение теоретической энтропии!
Арифметическое кодирование описывается довольно просто:
- Начинаем с полуинтервала [0; 1)
- На каждом шаге текущий полуинтервал делим на подполуинтервалы.
Длины будут соответствовать вероятности встретить соответствующую букву. - Выбираем подполуинтервал, соответствующий текущей букве сжимаемого сообщения.
- Повторить для всех букв сообщения.
- Число из полученного полуинтервала и будет закодированным сообщением.
В бытность свою студентом я реализовал этот алгоритм на чистом ассемблере в качестве курсовой работы. Ваше описание, равно как почти все встречающиеся в Сети, при воплощении в код теряют свою кажущуюся простоту и приобретают элементы «черной магии» в постоянных битовых сдвигах для наполнения очередного байта выходного потока.
Я тоже в студенчестве реализовывал такой алгоритм, но для себя.
Если выделить отдельный класс "битовый поток", то туда уйдет большая часть сдвигов.
Оставшееся — это обработка границ полуинтервала. Там 2 тривиальных случая и один посложнее:
- Верхняя граница меньше 0,5. Тогда пишем в выходной поток 0 и раздвигаем границы вдвое.
- Нижняя граница больше 0,5. Тогда пишем в выходной поток 1 и раздвигаем границы вдвое.
- Обе границы близки к 0,5. Тогда в выходной поток ничего писать не нужно, но для нескольких старших бит осталось всего два варианта: 011...1 или 100...0. Это можно запомнить и снова раздвинуть границы вдвое.
Вроде как и знал всё это, и deflate реализовывал из любопытства, а всё равно прочитал на одном дыхании.
Вопрос к автору: сколько заплатили?
«Обратите внимание, что из-за возможного перекрытия мы не можем использовать memcpy или memmove.»
Не знаю про какой стандарт речь, и были ли в более ранних стандартах отличия, но C99 накладывает ограничение о недопустимости перекрытия только на memcpy. А memmove — можно использовать для пересекающихся регионов.
Здесь, возможно, не совсем корректный перевод. Я так понял, суть в том, что, так как исходный и результирующий интервалы могут перекрываться, часть байт исходного интервала может быть банально неизвестна в начале копирования. К примеру, "ababa" может быть закодировано как "ab(3,2)", т.е. "отступить на 2 символа назад и скопировать 3 символа": третий копируемый символ будет отсутствовать на положенном месте, пока мы не скопируем первый.
Компания обвинила его в нарушении торгового знакаПравильный перевод термина trade mark — «товарный знак».
Спасибо! Очень понравилось!
Zip-файлы: история, объяснение и реализация