Сжатие данных *

Как уместить словарь размером 250 КБ в 64 КБ ОЗУ с возможностью выполнения быстрого поиска? Для справки: даже современные методики сжатия наподобие gzip -9 не могут сжать этот файл до размера меньше 85 КБ.

В 1970-х Дуглас Макилрой столкнулся с этой непростой задачей при реализации проверки правописания для Unix в AT&T. Из-за ограничений компьютера PDP-11 весь словарь должен был умещаться всего в 64 КБ ОЗУ. Кажется, подобную задачу решить невозможно.

Вместо того, чтобы использовать стандартные методики сжатия, Дуглас воспользовался преимуществами свойств данных, разработав алгоритм сжатия, отличавшийся от теоретического минимума сжатия всего на 0,03 бита. И по сей день этот рекорд остаётся непревзойдённым.

История spell в Unix — это не только любопытный исторический факт. Это мастер-класс по проектированию в условиях жёстких ограничений: анализа первооснов задачи, применения математических наблюдений и проектирования изящных решений, работающих в условиях строгого дефицита ресурсов.

Привет! Меня зовут Михаил Мазанов, я отвечаю за технологический стек работы с медиаданными в Кинопоиске: от съёмок оригинальных проектов до доставки и просмотра видео на всех экранах. Для нашей пятой ежегодной конференции про стриминг PlayButton 2024 я готовил большой доклад про оптимизацию качества видео Кинопоиска, а для Хабра решил пересобрать его в виде статьи — для тех, кому текстовый формат предпочтительнее видео.

Кроме технических графиков, вас ждёт ещё и наглядная разница в работе алгоритмов сжатия на примере «Рика и Морти» и «Джона Уика».

Привет, Хабр! Меня зовут Александр Крестинин, я разработчик встроенного ПО в компании Whoosh. Мы в embedded-команде не только переливаем биты из одного регистра в другой, но и решаем разные бизнес-задачи. Иногда попадаются головоломки. 

Однажды мы подумали, что было бы здорово выводить на экраны самокатов анимации и изображения — показывать инструкции, как пользоваться сервисом, как начать и закончить поездку, и чтобы запускать DOOM.

Зачем?

1) Сделать комфортнее. Удобно видеть инструкции на большом и ярком экране перед глазами, а не нырять за ними в приложение на смартфоне. 

2) Сделать безопаснее. Пользователь меньше отвлекается на телефон, крепче держится за самокат и внимательнее смотрит на всё, что вокруг.

3) Почти у всех привычных устройств уже есть экраны, которые выводят пользователям видео и картинки, а почему бы не сделать то же самое на самокате?

Но тут возникает проблема. Микроконтроллер крайне ограничен в памяти и вычислительных ресурсах. Самая простая анимация занимает чрезмерно много места. А если внедрить в отрисовку алгоритмы сжатия, то вычислительная нагрузка увеличится и анимация будет сильно лагать.

Расскажу, как мы нашли решение этой задачи. Прошу под кат.

В этой статье я поделюсь своим опытом и еще некоторыми утилитами

Вообще меня побудило написать эту статью прохождение курса Базовый курс по CTF на онлайн платформе Stepik, он бесплатный и по окончании выдается сертификат (это не реклама, а совет).

Перейдем непосредственно к утилитам.

Я уже подготовил файл «нашпигованый» двумя стегоконтейнерами. Файл скриншота рабочего стола 1.jpg

Проверим его наличие на рабочем столе ls.

Сегодня я хотел бы познакомить читателей Хабра с цифровой стеганографией. В нынешнем примере мы создадим, протестируем, проанализируем и взломаем стегосистемы. Я использую операционную систему Kali GNU/Linux, но кому интересна тема на практике, тот может повторить все то же в любом другом дистрибутиве Линукс.
Но для начала совсем немного теории.

Среди методов анализа информации, в данной статье представлен анализ распределения плотности информации в битовом блоке данных. Данный метод может быть ориентиром при разработке методов сжатия информации, так как дает оценки как распределена плотность информации в зависимости от состава блока, который определяется количеством нулей и единиц, формирующих битовый блок данных.

Привет, меня зовут Рома. Я работаю в отделе спецпроектов KTS на позиции Python backend-разработчика. 

Однажды мне взбрело в голову написать собственную имплементацию алгоритма сжатия RLE. В этой статье рассказываю подробнее про RLE: что это за зверь такой, где используется, чем плох, чем хорош, и какие неожиданные сложности могут возникнуть при попытке имплементации.

▍ Ошибка

Самолёт поднялся на высоту трёх километров. Я вытащил свой ноутбук, надеясь воспользоваться Интернетом, а может, немного поработать, если станет совсем скучно.

Подключившись к Wi-Fi самолёта, я открыл браузер. Страница сетевого логина потребовала ввести данные кредитной карты. Я поискал карту, которая обнаружилась внутри паспорта. В процессе поисков я заметил, что страница логина предлагает бесплатно войти в мой аккаунт программы авиамиль, хотя я пока ни за что ещё не заплатил. Я решил, что это дыра в файрволле. Мне предстоял долгий путь из Лондона в Сан-Франциско, поэтому я решил её исследовать.

Я вошёл в свой аккаунт JetStreamers Diamond Altitude, перешёл на страницу своего профиля и увидел кнопку редактирования. Она выглядела обычно: отбрасываемая тень, скруглённые углы, ничего особенного. С её помощью можно было поменять имя, адрес и так далее.

Но внезапно я понял, что это необычная кнопка. Она мошенническим образом позволит мне получить полный доступ к Интернету через мой аккаунт программы авиамиль. Это будет медленно и невероятно тупо, но сработает.

Многие коллеги просили меня выполнить ревью их пул-реквестов, потому что я оставлял комментарии типа «опоздало на две недели» или «мешает развёртыванию критического обновления». Но мои идеи тоже важны, поэтому я надел наушники и включил музыку для концентрации. Я забыл зарядить наушники, поэтому Limp Bizkit начал проигрываться через динамики ноутбука. К счастью, никто из пассажиров не был против, так что мы кайфовали вместе.

Прежде чем получить доступ ко всему Интернету через аккаунт программы авиамиль, мне нужно было написать несколько прототипов. Сначала я думал, что напишу их на Go, но потом понял, что если напишу их на Python, то смогу назвать получившийся инструмент PySkyWiFi. Разумеется, я выбрал второй вариант.

Для наилучшего восприятия выделим основные пункты изложенного материала:

1.    Для чего необходимо сжатие информации и увеличение плотности записи.
2.    Проблемы в покорение хаоса, нерешенные математиками и ими же созданные.
3.    Простое решение проблемы сжатия абсолютно любого бинарного кода.
4.    Пути и методы дальнейшего развития сжатия бинарного кода.

Сегодня я кратко расскажу вам как включить дедупликацию данных в клиентских ОС - Windows 10 и Windows 11, добавив функционал из Windows Server, причем не какие-то сторонние бинарники, а оригинальные, подписанные файлы Microsoft, которые к тому же будут обновляться через Windows Update.

В этой статье не будет описания дедупликации данных, - разве что совсем кратко что это такое, и не будет сравнения решений разных вендоров. Я дам ниже ссылки на достойные, на мой взгляд, статьи других авторов и готов буду отвечать на вопросы, если их зададут ниже в виде комментария или в ПМ.

Начать знакомство рекомендую с базовой теории Введение в дедупликацию данных / Хабр (habr.com) от компании Veeam, затем почитать о том, что такое дедупликация Microsoft - Обзор и настройка средств дедупликации в Windows Server 2012 / Хабр (habr.com) - статья моего бывшего коллеги по Microsoft Георгия говорит о том, как настраивается дедупликация NTFS в Windows Server 2012. В последующих изданиях Windows Server 2012R2, 2016, 2019, 2022 и 2025 функционал развивался, появилась поддержка ReFS, стало возможно (неочевидным способом) дедуплицировать системный том, расширились компоненты управления, - но для конечного пользователя все остается там же. Установили одним кликом, включили для диска, забыли. В заключение подготовительной информации - тем кого действительно интересует кроссплатформенные решения и их сравнения, предложу ознакомиться со статьей Илии Карина - Dedup Windows vs Linux, MS снова “удивит”? / Хабр (habr.com) - его не должны заподозрить в рекламе Microsoft, его сравнение подходов, и результат меня самого удивил. У меня на такую большую исследовательскую работу сил и возможностей нет, - почитайте. И имейте в виду, что если вы используете последний Windows 11, то и компоненты дедупликации в нем будут последние, от Windows Server 2025, то есть с еще более впечатляющим результатом.

« Надо будет мне собраться с яйцами, добить исследование и выдать на-гора статью о сжатии жпегом в 3D (то есть не квадрат 8х8, а куб 8х8х8). Там получился (не у меня первого, но у меня тоже получился, кек) неплохой видеокодек, в котором корреляция «между кадрами» не требует отдельно никакие области движений, смещений (и так далее) высчитывать — они там получаются нативно, «просто потому, что». И жмёт он — держите меня семеро.

Я это рассматривал как расширение (внезапно) стандарта GIF — новый тип кадра для анимации, в котором вместо одного кадра лежат сразу 8. Все остальные опции, типа заголовка с длительностью — оставляем стандартные анигифовские. Ну, и пара новых служебных форматов чанка потребуется — таблицы Хаффмана и квантования сами себя не загрузят.

А главную проблему, связанную с тем, что количество умножений там не квадратичное, а кубичное, я разрешил очень просто, без всяких группировок «бабочкой» и как там вообще обычно это до меня пытались делать: поскольку 95% величин квантуются в ноль (а иначе зачем бы было вообще такое сжатие, как не ради его эффективности?), я просто в 95% случаев перехожу в continue; :-)

И всё у меня в реалтайме на одном ядре сразу стало летать… ларчик просто откр оптимизировался :-D »

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

На данную тему была написана не одна сотня статей, но во всех, что видел, для построения двоичного дерева поиска использовались структуры по типу приоритетной очереди, хотя достаточно отсортировать массив частот в порядке убывания и отбрасывать последние две буквы с самыми маленькими частотами из алфавита, объединяя их в новую "псевдо-букву", но можно даже обойтись без постройки бинарного дерева поиска, чтобы сжать данные. В этой статье хотел представить реализацию данного алгоритма на языке C++.

Думаю все кто так или иначе интересовался сжатием информации или каким-то другим способом кодирования данных - слышали о кодах переменной длины. Я расскажу про свою реализацию этого велосипеда.

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

Внимание! В статье много картинок.

Всем привет, меня зовут Пётр, я инженер компании Nixys. На современных проектах используется огромное разнообразие баз данных: реляционные, ключ-значение, документоориентированные. Особое место среди них занимают колоночные базы данных, ярким представителем которых является ClickHouse. Это мощный инструмент, который способен обрабатывать миллиарды строк в секунду при минимальном времени ответа. Однако, для максимальной эффективности ClickHouse необходимо понимать ряд фундаментальных моментов для того, чтобы использовать его по назначению. В этой серии статей мы разберем особенности работы ClickHouse, которые помогут в выжимании максимума из этой базы. И сегодня начнём с фундаментальных теоретических моментов, чтобы составить максимально полное общее впечатление, которое поможет нам в дальнейшем.