How to become an author
Search
Write a publication
Pull to refresh

Comments 45

Огромная работа…
Спасибо за исходники!
Total votes 1: ↑0 and ↓1 -1
Чёрт, кдпв чертовски правильная. А теги нет.
Total votes 4: ↑4 and ↓0 +4
Прикольно также что на тот патент уже в своих патентах ссылаются куча технологических гигатов (как то Microsoft, Apple, Citrix и тд).
Вот это годный пример переиспользования знаний.
This comment wasn’t rated yet 0

По мнению Патентов Гугла каждый день после сентября 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

Total votes 1: ↑1 and ↓0 +1
Шикарно!
Ощущение погружения в магию.
Всегда хотелось знать что там происходит за полосой прогресса.
Ещё интересней было бы это всё визуализировать для наглядности. Т.е. чтобы выводился лог действий, создаваемые таблицы, списки и т.д.
Чтобы заварить чайку, взять пару круассанов, поставить пару гигов на сжатие и вальяжно растянуться в кресле…
Total votes 3: ↑2 and ↓1 +1
В свое время архивировали 1 Мегабайт на 8088. 30 минут. 1 Мегабайт.
Total votes 1: ↑1 and ↓0 +1
Прочитал про некий «беспрефиксный» код и удивился.
Да, в оригинале «Such a code is called a prefix-free code, or sometimes just prefix code», но у нас всё же используется термин «префиксный код». Так сказать, always, а не sometimes.
Total votes 3: ↑3 and ↓0 +3
Один из лучших материалов, которые я когда либо читал на Хабре.
Total votes 9: ↑9 and ↓0 +9
UFO just landed and posted this here
Перевести хорошую статью — тоже труд.
Total votes 11: ↑11 and ↓0 +11
На оригинальную статью уходит очень много времени.
Total votes 3: ↑3 and ↓0 +3
UFO just landed and posted this here
Ну ведь прямо там пятым примечанием ссылка обратно на хабр, где описывается новейшая (улучшающая традиционную рекурсивную упаковку архива в архив) техника зип-бомб от 2019 года, использовано рекурсивное описание группы файлов друг через друга. Видимо, рекурсивное создание бесконечного потока данных разархиватором не поддерживается.
This comment wasn’t rated yet 0
Спасибо за хороший перевод! И оффлайн копию в комп сохранить на память :)
Total votes 1: ↑1 and ↓0 +1
Естественно заархивирую, сначала копию в ARJ, LHA, HA, RAR, 7Z, и конечно в ZIP :)
Total votes 2: ↑2 and ↓0 +2

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

Total votes 3: ↑3 and ↓0 +3

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


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

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

Total votes 1: ↑1 and ↓0 +1

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


  1. Верхняя граница меньше 0,5. Тогда пишем в выходной поток 0 и раздвигаем границы вдвое.
  2. Нижняя граница больше 0,5. Тогда пишем в выходной поток 1 и раздвигаем границы вдвое.
  3. Обе границы близки к 0,5. Тогда в выходной поток ничего писать не нужно, но для нескольких старших бит осталось всего два варианта: 011...1 или 100...0. Это можно запомнить и снова раздвинуть границы вдвое.
This comment wasn’t rated yet 0
Хотя файл архива .ZIP, хоть офисный документ, хоть какой-то свой кастомный формат, а в первых двух байтах файла записано «PK». В статье сказано, что Zip-файл не требует никакой сигнатуры или магического числа в начале файла, зачем тогда их пишут? Просто дань уважения Филу Катцу?
This comment wasn’t rated yet 0
А фиг его знает. Но для примера — упакованное расширение для Google Chrome представляет собой zip-файл с расширением .crx в начале!!! которого есть специальный заголовок, только после которого, относительно далеко от начала, можно найти заголовок PK самого zip. И если скормить этот файл WinRar'у то он не подавится, а признает в нем zip-архив. Подозреваю, что по заголовку и находит.
This comment wasn’t rated yet 0
Написано, что файл в целом не обязан иметь сигнатуру. А сигнатура «PK» 0x05 0x06 — это заголовок архивной записи. Собственно, это и используется для создания SFX-архивов: он начинается, как исполняемый файл, а где-то в конце к нему приклеены архивные записи.
This comment wasn’t rated yet 0
Жаль в заключении нет (или я не увидел) практическое сравнение перечисленных в статье методов сжатия. Технически подкованные специалисты конечно же поймут имеющиеся приемущества и недочеты, а вот люди вроде меня не совсем… но было очень познавательно.
Total votes 1: ↑1 and ↓0 +1
UFO just landed and posted this here

Теоретически, можно и короче — gcc.c.

Total votes 4: ↑4 and ↓0 +4

А можно и позакрученнее :-)


> dir A:
* pkunzip.arj
* arj.rar
* unrar.zip
Total votes 5: ↑5 and ↓0 +5

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

This comment wasn’t rated yet 0
ШОК! Реклама GitHub в виде ссылки на исходники в большинстве статей на Хабре
Вопрос к авторам: сколько заплатили?
This comment wasn’t rated yet 0
оффтоп
Уже и попетросянить нельзя?!
This comment wasn’t rated yet 0
Да если бы это петросянство было, в большинстве случаях такие комменты на серьезных щах оставляют. Хорошо если вы и правда попытались пошутить.
This comment wasn’t rated yet 0
Еще не все прочитал, но уже вопросы:
«Обратите внимание, что из-за возможного перекрытия мы не можем использовать memcpy или memmove.»
Не знаю про какой стандарт речь, и были ли в более ранних стандартах отличия, но C99 накладывает ограничение о недопустимости перекрытия только на memcpy. А memmove — можно использовать для пересекающихся регионов.
This comment wasn’t rated yet 0

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

This comment wasn’t rated yet 0
Согласен, причина в том что исходный блок изначально полностью отсутствует в памяти. memmove должен просто переместить блок вперед(для чего начнет копирование с конца, чтобы не испортить), а раз блока как такового еще нет, то нужный результат не будет достигнут. Поэтому и нужен свой алгоритм копирования. В итоге memcpy нельзя из-за ограничения по пересечению, что на мой взгляд сводится к тому что стандарт не регламентирует с какой стороны начнется копирование и какими частями, а memmove нельзя по описанной ранее причине.
This comment wasn’t rated yet 0
Компания обвинила его в нарушении торгового знака
Правильный перевод термина trade mark — «товарный знак».
This comment wasn’t rated yet 0
Sign up to leave a comment.

Your account

Sections

Information

Services

Support
© 2006–2024, Habr