Рубрика «алгоритмы сжатия»

Как развитие алгоритмов сжатия остановилось 20 лет назад, или о новом конкурсе на 200 тысяч евро - 1

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

Пост набрал 206 «плюсов», вышел на 2 место топа недели и вызвал оживленную дискуссию, в которой мне больше всего понравился комментарий: «Коммерческого интереса эффективность по сжатию алгоритмов сжатия без потерь сегодня не представляет, в силу отсутствия принципиально более эффективных алгоритмов. Деньги сегодня — в сжатии аудио-видео. И там и алгоритмы другие. Тема сжатия без потерь удобна именно лёгкостью верификации алгоритма, и не слегка устарела. Лет на 20.» 

Поскольку я сам уже 20 лет в области сжатия видео, с ее бурным развитием мне спорить сложно. А вот что сжатие без потерь развиваться перестало… Хотя логика тут понятна каждому. Я до сих пор пользуюсь ZIP, все мои друзья пользуются ZIP с 1989 года — значит, ничего нового не появляется. Так ведь? Похоже рассуждают сторонники плоской земли. ))) Я не видел, знакомые не видели, и даже некоторые авторитеты утверждают, значит, это так! 

О том, как Intel просили меня не прекращать читать курс по сжатию, ибо людей нет новые алгоритмы делать, я в прошлый раз писал. Но тут и Huawei в ту же дуду дует! Вместо того, чтобы раздать призы и должности победителям, а затем успокоиться, поскольку развитие давно встало, эти эксцентричные люди посчитали конкурс крайне успешным и запустили новый с призовым фондом 200 тысяч EUR.

Развивались ли алгоритмы сжатия без потерь в последние 20 лет? Чем закончился прошлый конкурс и на сколько опередили baseline? Сколько денег получили русские таланты, а сколько зарубежные? И есть ли вообще жизнь на Марсе в сжатии без потерь? 

Кому интересно — добро пожаловать под кат! Читать полностью »

О талантах, деньгах и алгоритмах сжатия данных - 1

Алгоритмы сжатия — это очень коварная тема, привлекающая многих новичков. Это правда! Часто человеку кажется, что его осенила божественная идея, как сильно сжать данные. Любые, кстати! Без потерь! Рекурсивно! А поскольку данные — это хранение информации и передача, то если хотя бы на единицы процентов результат улучшить — это миллиарды долларов (смотрим экономию всех провайдеров на передаче и хранении, всех дата-центров компаний, всех домашних пользователей, перемножаем… аж дух захватывает)! И люди пишут письма:

«Обращаюсь к вам, как «создателю и демиургу проекта ;) compression». Мной придуман алгоритм, основанный на простом рассуждении – если файл условно несжимаемый, есть вероятность что, часть файла имеет избыточность и файл можно сжать частично. …» 

«Обращаюсь к Вам, как к одному из главных специалистов в области сжатия информации. Предлагаю Вам ознакомиться с изобретением в области сжатия информации. [...] По мнению автора, основным достоинством данного «Способа кодирования информации» является способность одинаково хорошо сжимать без потери качества информацию любого типа (видео, аудио, текст, архив и т.д.). Помимо этого «Способ» позволяет проводить процесс кодирования (сжатия) повторно....» 

Бывает даже так:

«Мне, для начала, нужно 30–60 минут общения с Вами по Скайпу.
Вопрос: каково Ваше вознаграждение и куда его отправить?» 

И если вы думаете, что обращения типа последнего — мои любимые, то реакция ровно обратная («Боже, дай мне терпения!»). Ибо по опыту в последнем случае люди наиболее настойчивые… Кстати, это могут быть не только авторы, но и инвесторы, о которых ниже тоже будет. 
О талантах, деньгах и алгоритмах сжатия данных - 2
Кому интересно, в чем же таки коварство алгоритмов, есть ли у нас таланты, и где же, наконец, деньги — добро пожаловать под кат! (Талантливые авторы алгоритмов могут сразу переходить в раздел «Про деньги»).
Читать полностью »

Сравнение компиляторов для разработки на микроконтроллерах с ядром ARM Cortex-M - 1
В этой статье протестируем 3-и компилятора для микроконтроллеров Kinetis с ядром ARM Cortex-M4.
Запустим тесты CoreMark, Whetstone, Dhrystone.
Исследуем алгоритмы сжатия с минимальным потреблением ОЗУ и выясним как влияют на их быстродействие разные компиляторы.
И даже попытаемся узнать насколько отстает Kinetis по быстродействию от Intel Core I7.


Предыдущие статьи о разработке на микроконтроллерах Kinetis:

Читать полностью »

Мы с моим научным руководителем готовим небольшую монографию по обработке изображений. Решил представить на суд хабрасообщества главу, посвящённую алгоритмам сжатия изображений. Так как в рамках одного поста целую главу уместить тяжело, решил разбить её на три поста:
1. Методы сжатия данных;
2. Сжатие изображений без потерь;
3. Сжатие изображений с потерями.
Ниже вы можете ознакомиться с первым постом серии.
Читать полностью »

От переводчика:
Основная цель перевода это попытка помочь тем программистам кто пишет статические распаковщики исполняемых файлов. Другими словами эта информация нацелена на практикующих reverse-engineer-ов. Под статичеческим распаковщиком понимаю программу которая поданный на вход упакованный или запротекченный исполняемый файл анализирует и создает на выходе файл, как будто бы тот создан каким-либо компилятором. Особенностью такого типа распаковщиков в том что он работает исключительно на знании структуры защиты или упаковки файла, т.е. без применения «сброса дампа», «востановления импорта» и др. типов «читерства».

При изучении упакованных файлов к примеру с помощью UPX, RlPack и др. часто встречаешься с кодом где делаются некоторые магические действиями с маш. инструкциями переходов байты 0xE8, 0xE9 и др. Этой магией является «фильтрация» и она направлена на улучшение степени сжатия исполняемого файла.

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

Ниже следует первод небольшого но крайне полезного текстового файла "%UPX_SOURCE%docfilter.txt". В этом пути под UPX_SOURCE подразумевается файловый путь до исходных кодов к UPX версии 3.91. Все что описано про UPX также применимо и к другим упаковщикам.

Читать полностью »


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js