Русский
Русский
English
Авторизация
Ip-адрес
Восстановление пароля
Регистрация
Статистика
Реклама

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

Сжатие видео на пальцах как работают современные кодеки?

30.07.2020 00:17:36 | Автор: admin


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

Для большей наглядности начнем с цифр. Пускай видеозапись будет вестись непрерывно, в разрешении Full HD (сейчас это уже необходимый минимум, во всяком случае, если вы хотите полноценно использовать функции видеоаналитики) и в режиме реального времени (то есть, с фреймрейтом 25 кадров в секунду). Предположим также, что выбранное нами оборудование поддерживает аппаратное кодирование H.265. В этом случае при разных настройках качества изображения (высоком, среднем и низком) мы получим примерно следующие результаты.

Кодек

Интенсивность движения в кадре

Использование дискового пространства за сутки, ГБ

H.265 (Высокое качество)

Высокая

138

H.265 (Высокое качество)

Средняя

67

H.265 (Высокое качество)

Низкая

41

H.265 (Среднее качество)

Высокая

86

H.265 (Среднее качество)

Средняя

42

H.265 (Среднее качество)

Низкая

26

H.265 (Низкое качество)

Высокая

81

H.265 (Низкое качество)

Средняя

39

H.265 (Низкое качество)

Низкая

24

Но если бы сжатия видео не существовало в принципе, мы бы увидели совсем иные цифры. Попробуем разобраться, почему. Видеопоток представляет собой не что иное, как последовательность статичных картинок (кадров) в определенном разрешении. Технически каждый кадр является двумерным массивом, содержащим информацию об элементарных единицах (пикселях), формирующих изображение. В системе TrueColor для кодирования каждого пикселя требуется 3 байта. Таким образом, в приведенном примере мы бы получили битрейт:

19201080253/1048576 = ~148 Мб/с

Учитывая, что в сутках 86400 секунд, цифры выходят поистине астрономические:

14886400/1024=12487 ГБ

Итак, если бы мы записывали видео без сжатия в максимальном качестве при заданных условиях, то для хранения данных, полученных с одной единственной видеокамеры в течение суток нам бы потребовалось 12 терабайт дискового пространства. Но даже система безопасности квартиры или малого офиса предполагает наличие, как минимум, двух устройств видеофиксации, тогда как сам архив необходимо сохранять в течение нескольких недель или даже месяцев, если того требует законодательство. То есть, для обслуживания любого объекта, даже весьма скромных размеров, потребовался бы целый дата-центр!

К счастью, современные алгоритмы сжатия видео помогают существенно экономить дисковое пространство: так, использование кодека H.265 позволяет сократить объем видео в 90 (!) раз. Добиться столь впечатляющих результатов удалось благодаря целому стеку разнообразных технологий, которые давно и успешно применяются не только в сфере видеонаблюдения, но и в гражданском секторе: в системах аналогового и цифрового телевидения, в любительской и профессиональной съемке, и многих других ситуациях.

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

А вот со снижением детализации все оказывается уже совсем не так однозначно. Технически квантование (то есть, разбиение диапазона сигнала на некоторое число уровней с последующим их приведением к заданным значениям) работает великолепно: используя данный метод, размер видео можно многократно уменьшить. Но так мы можем упустить важные детали (например, номер проезжающего вдалеке автомобиля или черты лица злоумышленника): они окажутся смазаны и такая запись будет для нас бесполезной. Как же поступить в этой ситуации? Ответ прост, как и все гениальное: стоит взять за точку отсчета динамические объекты, как все тут же становится на свои места. Этот принцип успешно используется со времен появления кодека H.264 и отлично себя зарекомендовал, открыв ряд дополнительных возможностей для сжатия данных.

Это было предсказуемо: разбираемся, как H.264 сжимает видео


Вернемся к таблице, с которой мы начали. Как видите, помимо таких параметров, как разрешение, фреймрейт и качество картинки решающим фактором, определяющим конечный размер видео, оказывается уровень динамичности снимаемой сцены. Это объясняется особенностями работы современных видеокодеков вообще, и H.264 в частности: используемый в нем механизм предсказания кадров позволяет дополнительно сжимать видео, при этом практически не жертвуя качеством картинки. Давайте посмотрим, как это работает.

Кодек H.264 использует несколько типов кадров:

  • I-кадры (от английского Intra-coded frames, их также принято называть опорными или ключевыми) содержат информацию о статичных объектах, не меняющихся на протяжении длительного времени.
  • P-кадры (Predicted frames, предсказанные кадры, также именуемые разностными) несут в себе данные об участках сцены, претерпевших изменения по сравнению с предыдущим кадром, а также ссылки на соответствующие I-кадры.
  • B-кадры (Bi-predicted frames, или двунаправленные предсказанные кадры) в отличие от P-кадров, могут ссылаться на I-, P- и даже другие B-кадры, причем как на предыдущие, так и на последующие.

Что это означает? В кодеке H.264 построение видеоизображения идет следующим образом: камера делает опорный кадр (I-кадр) и уже на его основе (поэтому он и называется опорным) производит вычитание из кадра неподвижных частей изображения. Таким образом создается P-кадр. Затем из этого второго кадра вычитается третий и также создается P-кадр с изменениями. Так формируется серия разностных кадров, которые содержат только изменения между двумя последовательными кадрами. В результате мы получаем такую цепочку:

[НАЧАЛО СЪЕМКИ] I-P-P-P-P-P-P-P-P-P-P-P-P-P- ...

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

-P-P-P-P-P-P-P-I-P-P-P-P-P-P-P ...

Полное изображение формируется путем наложения P-кадров на опорный кадр. При этом появляется возможность независимой обработки фона и движущиеся объектов, что позволяет дополнительно сэкономить дисковое пространство без риска упустить важные детали (черты лиц, автомобильные номера и т. д.). В случае же с объектами, совершающими однообразные движения (например, вращающимися колесами машин) можно многократно использовать одни и те же разностные кадры.


Независимая обработка статических и динамических объектов позволяет сэкономить дисковое пространство

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


Кодек формирует кадры, предсказывая, куда будет двигаться объект

В свою очередь, использование двунаправленных предсказанных кадров позволяет в несколько раз сократить время доступа к каждому кадру в потоке, поскольку для его получения будет достаточно распаковать только три кадра: B, содержащий ссылки, а также I и P, на которые он ссылается. В данном случае цепочку кадров можно изобразить следующим образом.

[НАЧАЛО СЪЕМКИ] I-B-P-B-P-B-P-B-P-B-P-B-P-B-P-B-P-

Такой подход позволяет существенно повысить скорость быстрой перемотки с показом и упростить работу с видеоархивом.

В чем разница между H.264 и H.265?




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

Так, обновленная версия кодека стала использовать макроблоки дерева кодирования (Coding Tree Unit, CTU) переменного размера с разрешением до 6464 пикселей, тогда как ранее максимальный размер такого блока составлял лишь 1616 пикселей. Это позволило существенно повысить точность выделения динамических блоков, а также эффективность обработки кадров в разрешении 4K и выше.

Кроме того, H.265 обзавелся улучшенным deblocking filter фильтром, отвечающим за сглаживание границ блоков, необходимым для устранения артефактов по линии их стыковки. Наконец, улучшенный алгоритм прогнозирования вектора движения (Motion Vector Predictor, MVP) помог заметно снизить объем видео за счет радикального повышения точности предсказаний при кодировании движущихся объектов, чего удалось достичь за счет увеличения количества отслеживаемых направлений: если ранее учитывалось лишь 8 векторов, то теперь 36.

Помимо всего перечисленного выше, в H.265 была улучшена поддержка многопоточных вычислений: квадратные области, на которые разбивается каждый кадр при кодировании, теперь могут обрабатываться независимо одна от другой. Появилась и поддержка волновой параллельной обработки данных (Wavefront Parallelel Processing, WPP), что также способствует повышению производительности сжатия. При активации режима WPP обработка CTU осуществляется построчно, слева направо, однако кодирование каждой последующей строки может начаться еще до завершения предыдущей в том случае, если данных, полученных из ранее обработанных CTU, для этого достаточно. Кодирование различных строк CTU с временной задержкой со сдвигом, наряду с поддержкой расширенного набора инструкций AVX/AVX2 позволяет дополнительно повысить скорость обработки видеопотока в многоядерных и многопроцессорных системах.

Флэш-карты для видеонаблюдения: когда значение имеет не только размер


И вновь вернемся к табличке, с которой мы начали сегодняшний разговор. Давайте подсчитаем, сколько дискового пространства нам понадобится в том случае, если мы хотим хранить видеоархив за последние 30 дней при максимальном качестве видеозаписи:

13830/1024 = 4

По нынешним меркам 4 терабайта для винчестера индустриального класса практически ничто: современные жесткие диски для видеонаблюдения имеют емкость до 14 терабайт и могут похвастаться рабочим ресурсом до 360 ТБ в год при MTBF до 1.5 миллионов часов. Что же касается карт памяти, то здесь все оказывается не так однозначно.

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

Как видно из нашей таблицы, даже при низком качестве изображения и при условии минимальной активности в кадре, всего за сутки будет записано около 24 ГБ видео. А это значит, что 128-гигабайтная карточка будет полностью перезаписана менее чем за неделю. Если же нам требуется получать максимально качественную картинку, то все данные на таком носителе будут полностью обновляться раз в сутки! И это лишь при разрешении Full HD. А если нам понадобится картинка в 4K? В этом случае нагрузка вырастет практически в два раза (в заданных условиях видео в максимальном качестве потребует уже 250 ГБ).

При бытовом использовании подобное попросту невозможно, поэтому даже самая бюджетная карта памяти способна прослужить вам несколько лет к ряду без единого сбоя. А все благодаря алгоритмам выравнивания износа (wear leveling). Схематично их работу можно описать следующим образом. Пусть в нашем распоряжении есть новенькая флеш-карта, только что из магазина. Мы записали на нее несколько видеороликов, использовав 7 из 16 гигабайт. Через некоторое время мы удалили часть ненужных видео, освободив 3 гигабайта, и записали новые, объем которых составил 2 ГБ. Казалось бы, можно задействовать только что освободившееся место, однако механизм выравнивания износа выделит под новые данные ту часть памяти, которая ранее никогда не использовалась. Хотя современные контроллеры тасуют биты и байты куда более изощренно, общий принцип остается неизменным.



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

Нетрудно догадаться, что wear leveling перестает играть хоть сколько-нибудь значимую роль в том случае, если флэш-карта постоянно перезаписывается целиком: здесь на первый план уже выходит выносливость самих чипов. Наиболее объективным критерием оценки последней является максимальное количество циклов программирования/стирания (program/erase cycle), или, сокращенно, циклов P/E, которое способно выдержать флеш-память. Также достаточно точным и в данном случае наглядным (так как мы можем заранее рассчитать объемы перезаписи) показателем является коэффициент TBW (Terabytes Written). Если в технических характеристиках указан лишь один из перечисленных показателей, то вычислить другой не составит особого труда. Достаточно воспользоваться следующей формулой:

TBW = (Емкость Количество циклов P/E)/1000

Так, например, TBW флеш-карты емкостью 128 гигабайт, ресурс которой составляет 200 P/E, будет равен: (128 200)/1000 = 25,6 TBW.

Давайте считать дальше. Выносливость карт памяти потребительского уровня составляет 100300 P/E, и 300 это в самом лучшем случае. Опираясь на эти цифры, мы можем с достаточно высокой точностью оценить срок их службы. Воспользуемся формулой и заполним новую таблицу для карты памяти емкостью 128 ГБ. Возьмем за ориентир максимальное качество картинки в Full HD, то есть в сутки камера будет записывать 138 ГБ видео, как мы выяснили ранее.

Ресурс карты памяти, циклов P/E

TBW

Время наработки на отказ

100

12,8

3 месяца

200

25,6

6 месяцев

300

38,4

1 год

Хотите использовать карты на 64 ГБ или писать видео в 4K? Смело делите рассчитанные сроки на два: в среднем потребительские карты памяти придется менять раз в полгода, причем в каждой камере. То есть каждые 6 месяцев вам придется закупать новую партию флеш-карт, нести дополнительные расходы на сервисное обслуживание и, конечно же, подвергать опасности охраняемый объект, так как камеры придется выводить из эксплуатации на время замены.

Наконец, еще один момент, на который следует обратить пристальное внимание при выборе карты памяти, ее скоростные характеристики. В описании практически всех современных флеш-карт можно встретить запись вида: Производительность: до 100 МБ/с при чтении, до 90 МБ/с при записи; запись видео: C10, U1, V10. Здесь C10 и U1 означают не что иное, как класс скорости записи видео, причем если заглянуть в справочные материалы, то классам C10, U1 и V10 соответствует 10 МБ/с. Откуда разница в 9 раз и почему маркировка тройная? На самом деле все достаточно просто.

В рассмотренном примере 100 и 90 МБ/с это номинальная скорость, то есть максимально достижимая производительность карты в операциях последовательного чтения и записи при условии использования с совместимым оборудованием, которое само по себе обладает достаточной производительностью. А показатели C10, U1 и V1 (10 МБ/с) это минимальная устойчивая скорость передачи данных в наихудших условиях тестирования. Данный параметр необходимо учитывать при выборе карт для камер видеонаблюдения по той простой причине, что если он окажется ниже битрейта видеопотока, то это чревато появлением на записи графических артефактов и даже выпадением целых кадров. Очевидно, что в случае с охранными системами подобное недопустимо: любые дефекты картинки чреваты потерей критически важных данных например, улик, которые могли бы помочь при поимке злоумышленника.

Что же касается наличия сразу трех маркировок, то причины этого сугубо исторические. C10 относится к самой первой из созданных SD Card Association классификаций, которая была составлена еще в 2006 году, получив простое и незамысловатое название Speed Class. Появление классификации UHS Speed Class, на которую указывает маркировка U1, связано с созданием интерфейса Ultra High Speed, который сегодня используется в подавляющем большинстве флеш-карт. Наконец, последняя классификация, Video Speed Class (V1), была разработана SD Card Association в 2016-м в связи с распространением устройств, поддерживающих запись видео сверхвысоких разрешений (4K, 8K и 3D).

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

Speed Class

UHS Speed Class

Video Speed Class

Минимальная устойчивая скорость записи

Разрешение видео

C2

2 МБ/с

Запись видео стандартного разрешения (SD, 720 на 576 пикселей)

C4

4 МБ/с

Запись видео высокой четкости (HD), включая Full HD (от 720p до 1080p/1080i)

C6

V6

6 МБ/с

C10

U1

V10

10 МБ/с

Запись видео Full HD (1080p) с фреймрейтом 60кадров в секунду

U3

V30

30 МБ/с

Запись видео с разрешением до 4K и фреймрейтом 60/120 кадров в секунду


V60

60 МБ/с

Запись видеофайлов с разрешением 8K и фреймрейтом 60/120 кадров в секунду


V90

90 МБ/с

Следует учитывать, что приведенные в таблице соответствия актуальны для любительских, полупрофессиональных и профессиональных видеокамер. В отрасли видеонаблюдения, где запись в реальном времени ведется с максимальной частотой 25 кадров в секунду, а для сжатия видеопотока применяются высокоэффективные кодеки H.264 и H.265, задействующие кодирование с предсказанием, в подавляющем большинстве случаев будет достаточно карт памяти, соответствующих классу U1/V10, так как битрейт в таких условиях практически никогда не превышает порог в 10 МБ/с.

Карты памяти WD Purple microSD для систем видеонаблюдения




С учетом всех перечисленных особенностей компания Western Digital разработала специализированную серию карт памяти WD Purple microSD, которая на данный момент включает в себя две продуктовые линейки: WD Purple QD102 и WD Purple SC QD312 Extreme Endurance. В первую вошли четыре накопителя объемом от 32 до 512 ГБ, во вторую три модели, на 64, 128 и 256 ГБ. По сравнению с потребительскими решениями, WD Purple были специально адаптированы под современные цифровые системы видеонаблюдения за счет внедрения ряда важных усовершенствований.

Главным преимуществом пурпурной серии является существенно больший по сравнению с бытовыми устройствами рабочий ресурс: карты линейки QD102 способны выдержать 1000 циклов программирования/стирания, тогда как QD312 уже 3000 циклов P/E, что позволяет многократно продлить срок их службы даже в режиме круглосуточной записи, и делает данные карточки идеально подходящими для эксплуатации на особо охраняемых объектах, где запись ведется в режиме 24/7. В свою очередь, соответствие классам скорости UHS Speed Class 1 и Video Speed Class 10 позволяет использовать карты WD Purple в камерах высокого разрешения, в том числе для записи в режиме реального времени.

Помимо этого, карты памяти WD Purple имеют и ряд других важных особенностей, о которых необходимо упомянуть:

  • влагостойкость (изделие способно выдержать погружение на глубину до 1 метра в пресную или соленую воду) и расширенный диапазон рабочих температур (от -25C до +85C) позволяют одинаково эффективно использовать карты WD Purple для оснащения как внутридомовых, так и уличных устройств видеофиксации независимо от погодных и климатических условий;
  • защита от воздействия статических магнитных полей с индукцией до 5000 Гс и устойчивость к сильной вибрации и ударам вплоть до 500 g полностью исключают вероятность утраты критически важных данных даже в случае повреждения видеокамеры;
  • функция удаленного мониторинга помогает оперативно отслеживать состояние каждой карты и эффективнее планировать проведение сервисных работ, а значит, дополнительно повысить надежность охранной инфраструктуры.

Для большей наглядности мы подготовили для вас сравнительную таблицу, в которой приведены основные характеристики карт памяти WD Purple.

Серия

WD Purple QD102

WD Purple QD312

Объем, ГБ

32

64

128

256

512

64

128

256

Форм-


фактор

microSDHC

microSDXC

Производи-тельность

До 100 МБ/с в операциях последовательного чтения,


до 65 МБ/с в операциях последовательной записи

Скоростной класс

U1/V10

Ресурс записи (P/E)

1000

3000

Ресурс записи (TBW)

32

64

128

256

512

192

384

768

Диапазон рабочих температур

От -25 C до 85 C

Гарантия

3 года
Подробнее..
Категории: Работа с видео , Хранение данных , Хранилища данных , Видеонаблюдение , Видео , Блог компании western digital , Wd , Сжатие данных , Видеонаблюдение через интернет , Карты памяти , Microsd , Wd purple , Карты памяти для видеонаблюдения , Карты памяти wd purple

Как Apple H.265 втихую продвигает

22.01.2021 20:15:37 | Автор: admin

Интро

Всем привет! Я являюсь пользователем техники всем известной Купертиновской компании Apple, думаю, как и многие из читателей Хабра. Я не ярый фанат яблока, просто меня устраивают устройства которые выпускает Apple. У меня в распоряжении несколько Iphone и планшет Ipad pro, так же не брезгую и устройствами на Android. Осенью 2020-го года у меня выдалось две недели отпуска. Чтобы не поддаваться осенней хандре (а она у меня бывает каждую осень), я решил махнуть в Питер и устроить себе мини путешествие дней на 5-7. Думаю погуляю, поснимаю видео и может сделаю мини ролик о путешествии.

ПетергофПетергоф

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

Суть

Сегодня я решил освободить свой icloud от отснятого из поездки и благополучно выгрузил себе на жесткий диск архив, через сервис https://www.icloud.com/photos/ и так же часть материалов до этого у меня была загружена на Google Drive. Объединил все это в одну папку и тут я увидел нечто странное.

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

Беру несколько файлов и выгружаю из через https://www.icloud.com/photos/.

Выгрузка через icloudВыгрузка через icloud

Те же файлы выгружаю через сам iphone на Google Drive

Те же файлы выгружаю через сам iphone на One Drive

Получается точно такая же картина. При выгрузке в любое облако через сам iphone 11 получаем один размер, при скачивании через icloud другой.

сравнение размера файловсравнение размера файлов

Размеры видео кадра одинаковые, а вес файла разный. Начал разбираться дальше.

Почему при попытке импорта этих видео в проект Adobe Premiere, одни импортируются нормально а другие нет?

Adobe importAdobe import

И тут я решил посмотреть инфо по кодекам, и получилось следующее.

Для файла загруженного через OneDrive

Для файла загруженного через Icloud

Для файла загруженного через google

Получается когда ты заливаешь видео файл на icloud, Apple перекодирует его в H.265, а не в H.264, как он хранится на самом девайсе.

Общение с Техподдержкой Apple

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

Информацию в лицензионном соглашении я тоже не нашел.

https://www.apple.com/ru/legal/sla/

Вывод

Если Вам как и мне нужно работать с видео в кодеке H.264, то нужно помнить что при скачивании видео из https://www.icloud.com/photos/ они будут в H.265. И придется заниматься их конвертацией.

Надеюсь, кому-то поможет информация которую я описал в посте. Буду рад услышать мнение сообщества на этот счет.

Подробнее..
Категории: Работа с видео , Apple , Сжатие данных , H.264 , H.265

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

30.10.2020 10:10:09 | Автор: admin


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

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

И если вы думаете, что обращения типа последнего мои любимые, то реакция ровно обратная (Боже, дай мне терпения!). Ибо по опыту в последнем случае люди наиболее настойчивые Кстати, это могут быть не только авторы, но и инвесторы, о которых ниже тоже будет.

Кому интересно, в чем же таки коварство алгоритмов, есть ли у нас таланты, и где же, наконец, деньги добро пожаловать под кат! (Талантливые авторы алгоритмов могут сразу переходить в раздел Про деньги).


Disclaimer 1: Любые совпадения в тексте с реальными лицами и фактами являются абсолютно случайными!
Disclaimer 2: Автор съел на этой теме несколько корейских невкусных собак, но так и не стал считать себя в ней истиной в последней инстанции!

Когда-то давно я имел неосторожность организовать команду из 4-х человек, и мы вместе написали книжку по алгоритмам сжатия, где много подходов разобрали. С тех пор идет довольно стабильный поток подобных писем. Настоящая жемчужина была этой весной. Пока люди страдали от ковида, человек написал очень прикольный текст про свой будущий архиватор. Зацените концовку (орфография во всех цитатах авторская):
И когда компрессор ******- будет создан Тогда Тогда
Да развергнутся Небеса.
И сойдёт на создателя сего творения Благодать, которая наполнит его Чашу богоугодным напитком,
Который опьянит его рассудок. И разольётся тепло по всей периферии, по всем жилам, согревая утомлённое от трудов, его бренное тело
И тогда сожмётся несжимаемый файл.
И тогда все скажут: О, чудо! И сильно удивятся, и начнут кричать: Ура! И начнут кидать вверх запонки, туфли, галстуки, лифчики
А потом выползет на пронизывающий свет брюзглявый скептик
Откроет один зашореный глаз, и пробубнит: Этого не может быть, так не бывает, у меня в книжке написано.
А скромный создатель ******, снисходительно улыбнётся. Зачем ему доказывать что-то, когда его Чаша наполнена, а Душа преисполнена
удовлетворённостью от выполненного дела

Боже, как поэтично! Особенно про несжимаемый файл, подброшенные лифчики и брюзглявого скептика, написавшего книжку! Волшебно! Я давно так не смеялся. Причем автор жег и дальше:
А для военных, это вообще находка. И сложно представить, сколько фильмов можно будет записать на одну флэшку. ТВ, интернет, телефон всё по двум проводам в дом. А оптоволокно будут использовать для новогодних гирлянд и магазинных вывесок. Мы живём в удивительное время, когда всё меняется. А России нужен технологический скачок.

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

О неправоте старика Шеннона


Писем таких много. Вот, например, человек теорему Шеннона поминает, но, похоже, не разбирался с ее доказательством:
Просмотрите pls не так бегло ;) Сравнение с Zip только для широкого круга читателей. Прямое сравнение с Арифметическим кодированием встречается в неск. местах. И да: я понимаю, что значит противоречит теореме Шеннона, именно это я и показываю НА ПРАКТИКЕ! Возможный по p*log(p) предел кодирования **** его превосходит! (в отдельных случаях)
Это не шутка.

Или вот:
И все бы хорошо, но **** действительно обеспечивает лучшее сжатие, т.е. поправить надо бы в консерватории Шеннона

А эти ребята даже стартап создали:
Мы создаём алгоритм сжатия данных, очень интересно было бы с вами пообщаться. [...] Мы начали разрабатывать алгоритм сжатия данных в конце 2017 года. ************ (второй сооснователь) придумал как сжимать любые данные в несколько раз. С технической точки зрения он лучше меня сможет объяснить, я занимаюсь продвижением.

Вежливо замечу, что если человек действительно напишет программу, которая ЛЮБЕ данные сожмет В НЕСКОЛЬКО РАЗ, то ему не нужен продвиженец, он может прямо сейчас начать хорошо зарабатывать. И я обязательно расскажу как.

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

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

Впрочем, для любого программиста совершенно очевидно, что в наш информационный век современный философский камень это сжатие несжимаемых данных. И неважно, что для чего-то там что-то доказано.
Г-голубчики, сказал Федор Симеонович озадаченно, разобравшись в почерках. Это же п-проблема Бен Б-бецалеля. К-калиостро же доказал, что она н-не имеет р-решения.
Мы сами знаем, что она не имеет решения, сказал Хунта, немедленно ощетиниваясь. Мы хотим знать, как ее решать.
К-как-то ты странно рассуждаешь, К-кристо К-как же искать решение, к-когда его нет? Б-бессмыслица какая-то
Извини, Теодор, но это ты очень странно рассуждаешь. Бессмыслица искать решение, если оно и так есть. Речь идет о том, как поступать с задачей, которая решения не имеет. Это глубоко принципиальный вопрос, который, как я вижу, тебе, прикладнику, к сожалению, не доступен. По-моему, я напрасно начал с тобой беседовать на эту тему.

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

Явление, которое проиллюстрировано выше цитатами из писем, это обычный эффект Даннинга-Крюгера, описанный в статье 1999 года, но хорошо известный со времен античности. Когда человек только начинает изучать любую область, ему кажется, что она очень проста и понятна, уверенность в своих знаниях растет очень быстро. Однако, чем выше самоуверенность в начале, тем глубже яма страданий потом из-за того, что реальность кардинально расходится с представлениями о ней. Причем попытки уберечь людей от глубоких страданий являются крайне неблагодарным занятием. Проверял несколько раз (мать-мать-мать, ладно, страдайте!!!).


Что можно сказать об опыте авторов таких писем? Когда смотришь присланный людьми PDF на тему сжатия несжимаемого, Яндекс дает просто неприличную рекламу (реальный скриншот аттача письма):


Справедливости ради люди часто прямо пишут:
Программирую на Delphi. Язык C, я плохо понимать.

Или так:
Так как мои познания в программировании ограничены, ищу соавтора программиста разбирающегося в алгоритмах сжатия информации

Или вот очень культурно:
Дмитрий, если у вас есть возможность помочь в данном вопросе, или заинтересуется кто-то из ваших знакомых прошу со мной связаться. Если окажется, что алгоритм неработоспособен, готов компенсировать затраты и потраченное время

Плохая новость заключается в том, что нужно будет разобраться не только как формально записывать алгоритм, но и для каких условий сформулирована та самая пресловутая теорема Шеннона, которую столь дружно превосходят начинающие авторы кодеров. Теория, мой друг, суха, но зеленеет жизни древо (Гете). И пока практика подтверждала теорию

Впрочем Ладно, расскажу! На самом деле сжимать уже сжатые данные, конечно, можно. (Что-о-о-о он несет??? возмущенно раздалось с мест!) Спокойно, господа! Рассказываю, как это делается на практике.

Когда-то я руководил разработкой проекта компании SoundGenetics с внутренним названием MP3Zip, позднее названным Sound Slimmer (сайт проекта, увы, более не поддерживается). Тогда удалось достичь сжатия MP3 в среднем в 1.2 раза на большой выборке MP3. Причем сжимался файл полностью без потерь, бит в бит. Идея была в том, что файл распаковывался до потока коэффициентов MDCT, которые далее паковались более эффективно (кому интересны детали, там было несколько патентов).

Причем если кто-то думает, что сильно сжать основная проблема, то он серьезно ошибается. Как показало вскрытие, огромный процент MP3 файлов, которые тогда ходили по людям, были битые. Особенно конец файла (наследие ранних p2p). И учесть корректно побитые файлы было не так просто. Т.е., если бы можно было починить файл, было бы достигнуто большее сжатие, но тогда каждый чайник проверил бы, увидел, что не бит в бит, и что есть силы закричал бы: Они обма-а-а-анывают! И был бы прав. Поэтому мы всячески извращались, стараясь минимально потерять сжатие, и максимально парсили битые куски (алгоритмически там не так все просто).

Также интересно, что если бы можно было зафиксировать распакованный файл (условно WAV), а не MP3, то для того же распакованного файла (бит в бит в WAV) можно было бы еще чуть увеличить сжатие. Но, увы, бизнес сказал: работаем только на уровне MP3. Так что эта часть осталась во внутренних разработках. Также по заказу известной японской компании была сильно переделана архитектура алгоритма (а теперь, ребята, делаем те же трюки, только стоя на канате!) и появилась возможность сжимать MP3 поток, т.е. работать по буферу, видя только небольшую часть файла. Это позволяло сжимать вещание. Аналогично, удалось примерно на 11% сжать AAC со всеми наворотами типа обработки битых и было показано, как аналогично дожимать JPEG и GIF (т.е. всю графику тогдашнего веба). В проекте работало 6 человек, и это было очень прикольно!

Так что сжимать сжатое можно! За это даже платят. Лично проверял!

Про деньги


А теперь про самое интересное (Да-да! Было явно обещано про деньги, раздалось с мест). Умные люди заранее спрашивают в письмах:
Существующие технологии сжатия графики будут развиваться. В частности, появятся новые преобразования [...]
Вопрос: как с минимальными усилиями извлечь некоторую финансовую выгоду в случае разработки более перспективных преобразований (которые на 20-30% лучше по быстродействию или по качеству сжатия)?

Мне нравятся такие письма. Перед тем как попусту растрачивать свой талант копать тему, человек грамотно интересуется, как с минимальными усилиями извлечь максимальную выгоду, когда (фигня вопрос!) удастся всех на 2030% обогнать.

Постараюсь ответить детально и по пунктам. Поехали!


Способ 0: Популярные неработающие подходы


Начну с нулевого во всех смыслах способа.

В письмах довольно регулярно всплывает тема заработка на патентах. Уж не буду цитатами сыпать, но предложения вместе сделать и запатентовать идут регулярно. Сожалею, но вынужден разочаровать, поскольку успешных кейсов, чтобы человек подал патент на алгоритм сжатия и разбогател, я не встречал. Можно реально заработать патентной экспертизой, это да, это реально. А вот продажей патента Обычно люди сильно недооценивают себестоимость жизненного цикла патента. А вопрос Почему ваш патент будет работать? вызывает реальный ступор. (А оно разве не само работает? Нет...) Поинтересуйтесь хотя бы, в каких юрисдикциях и как обеспечивают работу патента патентные тролли. Впрочем, это совершенно другая история.

Также частое желание сделать стартап и, конечно, продать его Google. Джим Коунси, директор подразделения Autodesk Developers Network (на потоке покупавший стартапы), несколько лет вел блог Dances with Elephants: How small companies can partner with large companies to accelerate their business growth. Его метафора танца со слонами довольно точно передает суть процесса. Безусловно, в блоге отражена точка зрения слона, поэтому скольких во время этих танцев раздавили даже не со зла, а просто не заметив, история умалчивает. Но, если вы мечтаете о продаже крупняку за много миллионов почитайте и трезво содрогнитесь.

Способ 1: Сжимаем несжимаемое за славу и деньги (на новом месте работы)


Проще всего тем, кто реально может сжимать несжимаемое. Марк Нельсон, автор толстенного кирпича The Data Compression Book библии сжатия 90-х, еще в 2002 году объявил конкурс, позднее названный The Million Random Digit Challenge и продлевавшийся с уточнением правил не один раз. Смысл конкурса в том, что была взята хорошо подготовленная последовательность случайных чисел (большой файл):


Задача была создать архиватор для этого файла, который вместе с архивом был бы меньше по размеру, чем сжимаемый файл. Ибо, если ограничение на размер архиватора не ставить, задача, как вы понимаете, решается тривиально (Джентльмены верят на слово [что мы часть архива в архиватор не кладем] Тут-то мне карта и поперла!). Т.е. надо на другом чистом компе из двух файлов искомый несжимаемый распаковать, ибо история знала случаи, когда сжимающий ЛЮБОЙ файл архиватор просто клал часть файла в tmp директорию компа. И люди проверяли, и у них, вы не поверите, работало! Несжимаемые файлы успешно сжимались!!! На самом деле!!! И они коллегам срочно пересылали попробовать, и у них тоже о чудо! работало!!! Офигеть просто Если архиватор не находил в tmp нужный кусок архива, он просто вызывал деление на ноль и технично падал. А что вы хотели, его технология тогда была несовершенна и сохранять часть архива в облако еще не умела Но поклонение у пипла уже вызывала! Так сильна человеческая вера в чудо

В общем, уже много лет Марк Нельсон покупает торт и задувает все больше и больше свечей на день рождения The Million Random Digit Challenge (ведь его детищу уже стукнуло 18!), но воз и ныне там. Интересно, что к созданию исходного файла конкурса приложил руку тот самый физик Джон фон Нейман, который недвусмысленно высказывался, что:
Любой, кто рассматривает арифметические методы получения случайных чисел, безусловно грешник

Это, впрочем, не мешает и по сей день особо упорным товарищам со словами ваши теоремы не работают случайностей не бывает продолжать искать алгоритмические закономерности в несжимаемых данных. В 2012 на десятилетие конкурса Марк Нельсон расширил правила, позволив делать компрессор и декомпрессор любого размера, но работать оно должно для любого файла. И он герой, конечно. Ибо особо умных товарищей много, и там уже было сохранение данных в имени файла, переменных среды, буферах ядра и т.д. Т.е. обнаружить читера не так просто, как кажется. Несмотря на малый размер призового фонда конкурса всего 100 $, желающих поучаствовать достаточно, и, если вы победите, всемирная известность и выгодные контракты вам точно обеспечены!

Способ 2: Получаем под сжатие деньги инвестора


Вообще стартапы по теме сжатия возникают регулярно. Даже в сериале Кремниевая долина у главного героя, если помните, был стартап по сжатию (в т.ч. 3D видео, что характерно). Поверьте, это не случайность, а тонкий троллинг. Деньги под сжатие просят (и даже получают!) довольно часто.

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

Причем у меня с такими товарищами была масса характерных разговоров. Выходят на меня, как правило, через МГУ, и у них представление такое, что ученый должен млеть от самого факта общения с новым русским инвестором А я сам был и СЕО, и СТО и живу, хм не на зарплату. И очень любопытно посмотреть, как эти горе-инвесторы себя ведут. А ведут они себя своеобразно. Что-то веско пообещать и пропасть норма. И при этом забавное желание получить консультацию на халяву. Причем желательно разобраться вот прямо за один сеанс.

Господа! За получасовой сеанс вам все про ваш pet project расскажут экстрасенсы (с гарантией 100%, кстати). А если вам заливают в уши грамотно, то реально вникать надо. В общем, смотришь на этот мастер-класс по переговорам и так и хочется сказать: Господи! Жги! Люди! Берите инвестиции!. Ибо на чужом опыте эти инвесторы не учатся.

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

Короче, господа! Непуганых людей с деньгами в наших, да и чужих палестинах все еще явно хватает. Поэтому ищите и обрящете, стучите и откроется. Как минимум, сможете проверить свою идею. Чужим опытом получения инвестиций в русских реалиях, впрочем, тоже интересоваться рекомендую. Так, знаете, на всякий случай!

Способ 3: Конкурс на сжатие википедии


В 2006 профессор австралийского университета (ныне исследователь в Google DeepMind) и автор нескольких книжек (в том числе книги 2005 года по раннему ИИ и алгоритмической вероятности) Маркус Хаттер объявил приз в 50000 за лучшее сжатие 1 Gb текстов википедии. На самом деле это реклама, поскольку формула приза построена так, что более чем 10000 Маркус не рисковал. Но тем не менее за 11 лет конкурса 8747 призовых были выплачены! Вот, к примеру, призы за 2007 и 2018 коллеге и соавтору нашей книжки Александру Ратушняку (и это не все, о чем будет ниже):


Интересно, что в 2020 году конкурс получил новое название 500'000 Prize for Compressing Human Knowledge, а размер корпуса на сжатие увеличен до 10 Gb.

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

Способ 4: Специализированные конкурсы


Также существуют специализированные конкурсы. Например, в 2011 году был конкурс Sequence Squeeze Compression Competition на сжатие последовательности ДНК с призовым фондом 15000 $. Причем в результатах видно, что по сравнению с baseline удалось либо практически на порядок увеличить скорость сжатия при существенном уменьшении файла, либо при той же скорости практически в 3 раза увеличить сжатие. Это является основной мотивацией компаний для проведения таких конкурсов (например, в 3 раза уменьшить затраты на хранение данных):

В этом конкурсе победители публиковались в открытых исходных текстах, что улучшает карму призеров отсекает часть авторов.

Способ 5: Конкурс на 50000 евро + слава в подарок



И, наконец, прямо сейчас идет конкурс Global Data Compression Competition с прямым призовым фондом 50000 (т.е. вся сумма планируется к выплате после оглашения результатов). Как я понимаю, это самый крупный в истории конкурс по сжатию без потерь, если считать размер выплаты ко времени конкурса. В его организации принимают участие трое из четырех авторов той самой книжки.

В конкурсе 4 вида данных:
  • Тексты (дань традиции). Размер 1 Gb. Практический смысл сжатия текстов сегодня ограничен, но с новыми ML/DL NLP подходами там есть с чем развернуться и силушку показать.
  • Картинки. Размер 1 Gb. Тут понятно.
  • Количественно-качественные данные: исполняемые файлы с большим процентом числовых таблиц. Размер 1 Gb. Это, условно, кейс дистрибутивов, бэкапов и разнообразные случаи сжатия разнородных данных.
  • Блочное сжатие 1 Gb блоков по 32 Kb это кейс баз данных, block storage, сжатия файловых систем. Данные в этом кейсе неоднородные, чтобы также приблизиться к реальным условиям.

Для каждого вида данных есть 3 варианта ограничений по скорости для быстрых, средних и медленных (Иду на рекорд!) алгоритмов. Впрочем, многие алгоритмы можно адаптировать без переделки, и вы наверняка обращали внимание, что в тех же RAR или ZIP можно задавать силу сжатия, и чем сильнее, тем дольше жмет. Вот ровно про это речь.

Итого получается 12 номинаций, в каждой из которых призы за лучшие места. Можно и нужно точиться по времени и занимать первые места в нескольких номинациях (если у вас адски мощный DL препроцессинг текстовых данных, например).

Соревнование международное, и в нем уже участвуют авторы алгоритмов сжатия от профессоров университетов США до индийских программистов.

Важный момент никто не требует исходников. Это, безусловно, расширяет список участников, но Правильно, тут же появляются самые умные. Например, один из участников из гм Юго-Восточной Азии явственно парсит GitHub на предмет годных исходников, точит их под задание и засылает. Просто и со вкусом. При том, что вычислить такое поведение, пусть сложно, но реально.

Чтобы сразу понятно было. Финансирует конкурс Huawei. В этот момент должен раздаться хор непонятно чем недовольных. Поскольку когда такого спонсора нет, то призовой фонд, вспоминаем старика Нельсона, равен 100 $. Причем в его случае он мог и миллион долларов пообещать, но представляете, с какими изощренными способами спрятать куда-то кусок архива ему бы пришлось столкнуться! Он же не мазохист. И вообще у нас на compression.ru и ранее рейтинги кодеров проводились. И в других местах тоже. Но это, похоже, первое широкомасштабное соревнование на тему сжатия без потерь, проспонсированное компанией! Т.е. ни Google, ни Apple, ни Intel, ни Microsoft как-то не сподобились. При том что они от этого вполне выигрывают, в том числе реальные большие деньги на экономии трафика и хранении. А, чем выше призовой фонд, тем больше геморрой для нас, авторов книг организаторов соревнований. Ибо больше не только волн, но и пены. Хотя и больше шанс реально интересные результаты собрать, конечно.

Сейчас большие надежды возлагаются на Deep Learning, который, конечно, сметет все старые алгоритмы и в сжатии без потерь тоже. И тогда покажется смешным сжатие бит в бит MP3 и JPEG на 20%, и снизойдет на автора алгоритма благодать, и он улыбнется.

Короче, господа! Результаты, надеемся, будут очень интересные. И, если вы где-то будете в лидерах вас точно заметят и закидают предложениями о работе. Так что дерзайте! Планируем обязательно рассказать о том, что получилось в итоге.

Резюмируя тему, замечу, что наиболее частый путь успеха в общем-то похож на путь современного ML/DL поколения: прокачка Kaggle/хакатоны/конкурсы победы зарплата $100200K в год. Маркус Хаттер в DeepMind, как видим, получает столько, что конкурсы на полмиллиона евро лично спонсирует. В этом большой плюс соревнований и побед. Главное адекватно оценивать усилия, необходимые на качественную прокачку и быстро переходить от слов к делу (это самое сложное по опыту).

Про талант


И, наконец, последняя обещанная тема. Может показаться, что я как-то неровно дышу к нашим ярким талантам. Это не так. Просто мне ближе такое определение:

И к счастью, я знаю много замечательных талантливых (в рамках этого определения) соотечественников. Например, мы 17 лет проводим сравнения кодеков, в которых участвуют компании из разных стран. Так, до недавнего времени едва ли не половина общения шла на русском. Т.е. компания была западная, а видеокодеками в ней занимались люди родом из России, Украины, Белоруссии, из Прибалтики, наконец. Недавно, правда, стало очень много китайцев (как компаний, так и разработчиков), но это отдельная тема.

С обычным сжатием ситуация также очень показательна:
  • Если кто не знает, то автор RAR (WinRAR) фактически самого популярного коммерческого архиватора в мире талантливый челябинец Евгений Рошал.
  • Автор 7-zip крайне популярной бесплатной open-source программы сжатия и LZMA SDK Игорь Павлов.
  • Автор алгоритма PPMd (использованного и в RAR, и в 7-zip) и почти призер Hutter Prize Дмитрий Шкарин. Кстати, его же метод BMF сейчас в топе Global Data Compression Competition на сжатии изображений. При том что он придуман 1520 лет назад!
  • Автор PPMY, PPMd_sh, shar2 и многих алгоритмов рекомпрессии JPEG, MP3, AAC, Deflate (участник упоминавшегося проекта SoundSlimmer) харьковчанин Евгений Шелвин. Евгений контрибьютор большого количества компрессоров с открытым кодом и поддерживает, пожалуй, самый известный в мире форум по сжатию.
  • Александр Ратушняк, один из авторов той самой книги и соорганизатор конкурса Global Data Compression Competition, автор высокоэффективных компрессоров изображений, контрибьютор стандарта JPEG-XL, четыре раза получал Hutter Prize! Вообще таблица призеров Hutter Prize выглядит так, будто, несмотря на длительность конкурса, Саша не оставил другим авторам никаких шансов:



И список выше далеко не полный. Причем когда общаешься с этими замечательными людьми, понимаешь, что талант не главное. А главное терпеливо и настойчиво заниматься темой, которая тебе действительно нравится.

Закончить хотелось бы словами любимых Стругацких:
Сюда пришли люди, которым было приятнее быть друг с другом, чем порознь, которые терпеть не могли всякого рода воскресений, потому что в воскресенье им было скучно. Маги, Люди с большой буквы, и девизом их было Понедельник начинается в субботу они приняли рабочую гипотезу, что счастье в непрерывном познании неизвестного и смысл жизни в том же. Каждый человек маг в душе, но он становится магом только тогда, когда начинает меньше думать о себе и больше о других, когда работать ему становится интереснее, чем развлекаться в старинном смысле этого слова.

Дерзайте! Доводите ваши идеи до результата! И пусть ваша работа будет интереснее ваших развлечений!

Читайте также: Уличная магия сравнения кодеков. Раскрываем секреты текст о том, как мы много лет кодеки сравнивали и с какими эпичными случаями сталкивались.

Благодарности


Хотелось бы сердечно поблагодарить:
  • Лабораторию Компьютерной Графики и Мультимедиа ВМК МГУ им. М.В. Ломоносова за вклад в развитие сжатия медиа в России и не только,
  • моих соавторов по книге Методы сжатия данных, благодаря которым этот проект вообще стал возможным и нанес непоправимую пользу многим людям,
  • персонально Константина Кожемякова и Кирилла Малышева, которые сделали очень много для того, чтобы эта статья стала лучше,
  • и, наконец, огромное спасибо Дмитрию Коновальчуку, Максиму Смирнову, Анастасии Кирилловой, Андрею Москаленко, Егору Склярову, Никите Молотилову, Ивану Молодецких, Вячеславу Мещанинову, Михаилу Дремину, Александру Гущину и Николаю Сафонову за большое количество дельных замечаний и правок, сделавших этот текст намного лучше!
Подробнее..
Категории: Программирование , Научно-популярное , Алгоритмы , Статистика в it , Спортивное программирование , Соревнования , Сжатие данных , Алгоритмы сжатия , Теорема шеннона , Призы

Формату MP3 исполнилось 25 лет

29.07.2020 12:21:28 | Автор: admin


25 лет назад, в июле 1995 года, представители немецкого Института интегральных микросхем Фраунгофера (Fraunhofer-Institut fr Integrierte Schaltungen, сокращенно Fraunhofer IIS, FIIS) приняли важное решение: использовать расширение .mp3 для обозначения нового стандарта кодирования данных. Дату этого события и принято считать днем рождения MP3.

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

Когда горы были высокими, а компьютеры медленными



Источник: hackaday.com

На самом деле, 25 лет назад появилось именно расширение для файлов, закодированных по новому стандарту. А вот его разработка стартовала гораздо раньше.

В 1977 году молодой ученый Карлхайнц Бранденбург из института Эрлангена-Нюрнберга им. Фридриха-Александра ( Friedrich Alexander Universitt, или FAU) занялся поиском методов сжатия аудио. Через пять лет его научный руководитель попросил помочь запатентовать технологию передачи музыкальных данных через телефонные линии. Сейчас это звучит странно, но в патентном бюро им отказали, объяснив отказ невозможностью реализации технологии.



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

По рассказам самого Бранденбурга, он экспериментировал с одной и той же песней Tom's Diner Сюзанны Веги. Это была его любимая композиция, которая осталась таковой даже после прослушивания трека около 1000 раз. В итоге удалось найти приемлемый способ сжатия аудио, выбросив все то, что человеческое ухо просто не способно воспринять. Качество от этого страдает не сильно, а вот файл на выходе получается очень небольшим в сравнении с результатами других способов сжатия.


Путь к успеху



Источник: Википедия

В 1992 году технология MPEG Layer 3 все еще не была популярной. Тем не менее, ее подготовили к коммерческому использованию, она также стала стандартом ISO. На тот момент в ходу был MPEG Layer 2, который считали отличной технологией. Бизнес не рассматривал MP3 как перспективную альтернативу существующим решениям.

Для того, чтобы решить эту проблему и обратить внимание пользователей на новый стандарт, создатель MP3 с коллегами решил провести эксперимент по передаче аудиофайла по интернету. Технология передачи была разработана, и эксперимент прошел удачно. В опыте приняла участие компания Telos Systems из Кливленда.

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

После этого MP3 очень быстро стал востребованным форматом, поскольку он позволял интернет-сообществу передавать композиции по dial-up. Затем появился Napster, а вместе с ним так называемое цифровое пиратство. Музыканты стали распространять свои записи по сети, любители музыки беспрепятственно обменивались любой музыкой в любом объеме, сколько позволяла сеть. В 2001 году Стив Джобс представил iPod, который был способен хранить рекордные 1000 музыкальных композиций.

После музыкальная индустрия стала бороться со свободным обменом музыкой, что спровоцировало рост популярности стриминговых музыкальных сервисов. И все это стало возможным благодаря изобретению Карлхайнца Бранденбурга и его коллег.

Чем занимается Бранденбург сейчас?



Источник: brandenburg-labs.com

После 20 лет работы в своем институте Карлхайнц Бранденбург ушел на пенсию. Исследователь не забросил любимое дело, он продолжает работать со звуком, только направление сменил. Ученый основал компанию Brandenburg Labs и работает на созданием новой технологии PARty.

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

What would whip the llamas ass?



Источник: ianimal.ru

Да, а вы знаете, что Winamp сейчас доступен бесплатно? Если не знали, то теперь да. Наслаждайтесь.
Подробнее..
Категории: Звук , Блог компании selectel , История it , Стандарты , Сжатие данных , Mp3 , Исторя ит , Кодеки , Сжатие звука

Ещё один велосипед храним юникодные строки на 30-60 компактнее, чем UTF-8

02.10.2020 16:05:32 | Автор: admin


Если вы разработчик и перед вами стоит задача выбора кодировки, то почти всегда правильным решением будет Юникод. Конкретный способ представления зависит от контекста, но чаще всего тут тоже есть универсальный ответ UTF-8. Он хорош тем, что позволяет использовать все символы Юникода, не тратя слишком много байт в большинстве случаев. Правда, для языков, использующих не только латиницу, не слишком много это как минимум два байта на символ. Можно ли лучше, не возвращаясь к доисторическим кодировкам, ограничивающим нас всего 256 доступными символами?

Ниже предлагаю ознакомиться с моей попыткой дать ответ на этот вопрос и реализацию относительно простого алгоритма, позволяющего хранить строчки на большинстве языков мира, не добавляя той избыточности, которая есть в UTF-8.

Дисклеймер. Сразу сделаю несколько важных оговорок: описанное решение не предлагается как универсальная замена UTF-8, оно подходит только в узком списке случаев (о них ниже), и его ни в коем случае нельзя использовать для взаимодействия со сторонними API (которые о нём и знать не знают). Чаще всего для компактного хранения больших объемов текстовых данных подойдут алгоритмы сжатия общего назначения (например, deflate). Кроме того, уже в процессе создания своего решения я нашёл существующий стандарт в самом Юникоде, который решает ту же задачу он несколько сложнее (и нередко хуже), но всё-таки является принятым стандартом, а не собранным на коленке. О нём я тоже расскажу.

О Unicode и UTF-8


Для начала несколько слов о том, что вообще такое Unicode и UTF-8.

Как известно, раньше имели популярность 8-битные кодировки. С ними всё было просто: 256 символов можно занумеровать числами от 0 до 255, а числа от 0 до 255 очевидным образом представимы в виде одного байта. Если возвращаться к самым истокам, то кодировка ASCII и вовсе ограничивается 7 битами, поэтому самый старший бит в её байтовом представлении равен нулю, и большинство 8-битных кодировок с ней совместимы (они различаются только в верхней части, где старший бит единица).

Чем же от тех кодировок отличается Юникод и почему с ним связано сразу множество конкретных представлений UTF-8, UTF-16 (BE и LE), UTF-32? Разберёмся по порядку.

Основной стандарт Юникода описывает только соответствие между символами (а в некоторых случаях отдельными компонентами символов) и их номерами. И возможных номеров в этом стандарте очень много от 0x00 до 0x10FFFF (1 114 112 штук). Если бы мы хотели положить число в таком диапазоне в переменную, ни 1, ни 2 байт нам бы не хватило. А так как под работу с трехбайтовыми числами наши процессоры не очень заточены, мы были бы вынуждены использовать целых 4 байта на один символ! Это и есть UTF-32, но именно из-за этой расточительности этот формат не пользуется популярностью.

К счастью, символы внутри Юникода упорядочены не случайно. Всё их множество разделено на 17 плоскостей, каждая из которых содержит 65536 (0x10000) кодовых точек. Понятие кодовой точки тут это просто номер символа, присвоенный ему Юникодом. Но, как было сказано выше, в Юникоде занумерованы не только отдельные символы, но также их компоненты и служебные пометки (а иногда и вовсе номеру ничего не соответствует возможно, до поры до времени, но для нас это не так важно), поэтому корректнее всегда говорить именно про число самих номеров, а не символов. Однако далее для краткости я часто буду употреблять слово символ, подразумевая термин кодовая точка.

Плоскости Юникода. Как видно, большая часть (плоскости с 4 по 13) всё ещё не использована.
Плоскости Юникода. Как видно, большая часть (плоскости с 4 по 13) всё ещё не использована.

Что самое замечательное вся основная мякотка лежит в нулевой плоскости, она называется "Basic Multilingual Plane". Если строчка содержит текст на одном из современных языков (включая китайский), за пределы этой плоскости вы не выйдете. Но отсекать остальную часть Юникода тоже нельзя например, эмодзи в основном находятся в конце следующей по счёту плоскости, "Supplementary Multilingual Plane" (она простирается от 0x10000 до 0x1FFFF). Поэтому UTF-16 поступает так: все символы, попадающие в Basic Multilingual Plane, кодируются как есть, соответствующим им двухбайтовым числом. Однако часть чисел в этом диапазоне вообще не обозначают конкретные символы, а указывают на то, что следом за этой парой байт нужно рассмотреть ещё одну скомбинировав значения этих четырёх байт вместе, у нас получится число, охватывающее весь допустимый диапазон Юникода. Такое представление называется суррогатными парами возможно, вы о них слышали.

Таким образом, UTF-16 требует два или (в очень редких случаях) четыре байта на одну кодовую точку. Это лучше, чем постоянно использовать четыре байта, но латиница (и другие ASCII-символы) при таком кодировании расходует половину занимаемого места на нули. UTF-8 призван это поправить: ASCII в нём занимает, как раньше, всего один байт; коды от 0x80 до 0x7FF два байта; от 0x800 до 0x7FFF три, а от 0x8000 до 0x1FFFF четыре. С одной стороны, латинице стало хорошо: вернулась совместимость с ASCII, да и распределение более равномерно размазано от 1 до 4 байт. Но алфавиты, отличные от латинского, увы, никак не выигрывают по сравнению с UTF-16, а многие и вовсе теперь требуют трёх байт вместо двух диапазон, покрываемый двухбайтовой записью, сузился в 32 раза, с 0xFFFF до 0x7FF, и в него не попадает уже ни китайский, ни, к примеру, грузинский. Кириллице и ещё пяти алфавитам ура повезло, 2 байта на символ.

Почему так выходит? Давайте посмотрим, как UTF-8 представляет коды символов:

Непосредственно для представления чисел тут использованы биты, помеченные символом x. Видно, что в двухбайтовой записи таких бит лишь 11 (из 16). Ведущие биты тут несут только служебную функцию. В случае с четырёхбайтовой записью и вовсе под номер кодовой точки отведён 21 бит из 32 казалось бы, тут хватило бы и трёх байт (которые дают суммарно 24 бита), но служебные маркеры съедают слишком много.

Плохо ли это? На самом деле, не очень. С одной стороны если мы сильно заботимся о занимаемом пространстве, у нас есть алгоритмы сжатия, которые легко устранят всю лишнюю энтропию и избыточность. С другой целью Юникода было дать максимально универсальное кодирование. Например, закодированную в UTF-8 строчку мы можем доверить коду, который раньше работал только с ASCII, и не бояться, что он там увидит символ из ASCII-диапазона, которого там на самом деле нет (ведь в UTF-8 все байты, начинающиеся с нулевого бита это именно ASCII и есть). А если мы захотим вдруг отрезать маленький хвост от большой строки, не декодируя её с самого начала (или восстановить часть информации после повреждённого участка) нам несложно найти то смещение, где начинается какой-то символ (достаточно пропустить байты, имеющие битовый префикс 10).

Зачем же тогда выдумывать что-то новое?


В то же время, изредка бывают ситуации, когда алгоритмы сжатия вроде deflate плохоприменимы, а добиться компактного хранения строк хочется. Лично я столкнулся с такой задачей, размышляя о построении сжатого префиксного дерева для большого словаря, включающего слова на произвольных языках. С одной стороны каждое слово очень короткое, поэтому сжимать его будет неэффективно. С другой реализация дерева, которую я рассматривал, была рассчитана на то, что каждый байт хранимой строки порождал отдельную вершину дерева, так что минимизировать их количество было очень полезно. В моей библиотеке Az.js (как и в pymorphy2, на котором она основана) подобная проблема решается просто строки, упакованные в DAWG-словарь, хранятся там в старой доброй CP1251. Но, как нетрудно понять, это хорошо работает только для ограниченного алфавита строчку на китайском в такой словарь уже не сложить.

Отдельно отмечу ещё один неприятный нюанс, который возникает при использовании UTF-8 в такой структуре данных. На картинке выше видно, что при записи символа в виде двух байт, биты, относящиеся к его номеру, не идут подряд, а разорваны парой бит 10 посередине: 110xxxxx 10xxxxxx. Из-за этого, когда в коде символа переполняются младшие 6 бит второго байта (т.е. происходит переход 10111111 10000000), то меняется и первый байт тоже. Получается, что буква п обозначается байтами 0xD00xBF, а следующая за ней р уже 0xD10x80. В префиксном дереве это приводит к расщеплению родительской вершины на две одной для префикса 0xD0, и другой для 0xD1 (хотя вся кириллица могла бы кодироваться только вторым байтом).

Что у меня получилось


Столкнувшись с этой задачей я решил поупражняться в играх с битами, а заодно чуть лучше познакомиться со структурой Юникода в целом. Результатом стал формат кодирования UTF-C (C от compact), который тратит не более 3 байт на одну кодовую точку, а очень часто позволяет тратить лишь один лишний байт на всю кодируемую строчку. Это приводит к тому, что на многих не-ASCII алфавитах такое кодирование оказывается на 30-60% компактнее UTF-8.

Я оформил примеры реализации алгоритмов кодирования и декодирования в виде библиотек на JavaScript и Go, вы можете свободно использовать их в своём коде. Но я всё же подчеркну, что в некотором смысле этот формат остаётся велосипедом, и я не рекомендую его использовать без осознания того, зачем он вам нужен. Это всё-таки больше эксперимент, чем серьёзное улучшение UTF-8. Тем не менее, код там написан аккуратно, лаконично, с большим числом комментариев и покрытием тестами.

Результат выполнения тестов и сравнение с UTF-8
Результат выполнения тестов и сравнение с UTF-8

Ещё я сделал демо-страничку, где можно оценить работу алгоритма, а далее я расскажу подробнее о его принципах и процессе разработки.

Устраняем избыточные биты


За основу я взял, конечно, UTF-8. Первое и самое очевидное, что в нём можно поменять уменьшить число служебных бит в каждом байте. Например, первый байт в UTF-8 всегда начинается либо с 0, либо с 11 а префикс 10 есть только у следующих байт. Заменим префикс 11 на 1, а у следующих байт уберём префиксы совсем. Что получится?

0xxxxxxx 1 байт
10xxxxxx xxxxxxxx 2 байта
110xxxxx xxxxxxxx xxxxxxxx 3 байта

Стоп, а где же четырёхбайтовая запись? А она стала не нужна при записи тремя байтами у нас теперь доступен 21 бит и этого с запасом хватает на все числа до 0x10FFFF.

Чем мы пожертвовали тут? Самое главное обнаружением границ символов из произвольного места буфера. Мы не можем ткнуть в произвольный байт и от него найти начало следующего символа. Это ограничение нашего формата, но на практике необходимость в таком встаёт нечасто. Обычно мы способны пробежать буфер с самого начала (особенно когда речь идёт о коротких строках).

Ситуация с покрытием языков 2 байтами тоже стала лучше: теперь двухбайтовый формат даёт диапазон в 14 бит, а это коды до 0x3FFF. Китайцам не везёт (их иероглифы в основном лежат в диапазоне от 0x4E00 до 0x9FFF), но вот грузинам и многим другим народам стало повеселее их языки тоже укладываются в 2 байта на символ.

Вводим состояние энкодера


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

Как было сказано выше, Юникод поделён на плоскости по 65536 кодов каждая. Но это не очень полезное деление (как уже сказано, чаще всего мы находимся в нулевой плоскости). Более интересным является деление на блоки. Эти диапазоны уже не имеют фиксированной длины, и несут больше смысла как правило, каждый объединяет символы одного алфавита.

Блок, содержащий символы бенгальского алфавита. К сожалению, по историческим причинам, это пример не очень плотной упаковки 96 символов хаотично раскиданы по 128 кодовым точкам блока.
Блок, содержащий символы бенгальского алфавита. К сожалению, по историческим причинам, это пример не очень плотной упаковки 96 символов хаотично раскиданы по 128 кодовым точкам блока.

Начала блоков и их размеры всегда кратны 16 сделано это просто для удобства. Кроме того, многие блоки начинаются и заканчиваются на значениях, кратных 128 или даже 256 например, основная кириллица занимает 256 байт от 0x0400 до 0x04FF. Это довольно удобно: если мы один раз сохраним префикс 0x04, то дальше любой кириллический символ можно записывать одним байтом. Правда, так мы потеряем возможность вернуться к ASCII (и к любым другим символам вообще). Поэтому делаем так:

  1. Два байта 10yyyyyy yxxxxxxx не только обозначают символ с номером yyyyyy yxxxxxxx, но и меняют текущий алфавит на yyyyyy y0000000 (т.е. запоминаем все биты, кроме младших 7 бит);
  2. Один байт 0xxxxxxx это символ текущего алфавита. Его нужно просто сложить с тем смещением, которое мы запомнили на шаге 1. Пока алфавит мы не меняли, смещение равно нулю, так что совместимость с ASCII мы сохранили.

Аналогично для кодов, требующих 3 байт:

  1. Три байта 110yyyyy yxxxxxxx xxxxxxxx обозначают символ с номером yyyyyy yxxxxxxx xxxxxxxx, меняют текущий алфавит на yyyyyy y0000000 00000000 (запомнили всё, кроме младших 15 бит), и ставят флажок, что мы теперь в длинном режиме (при смене алфавита обратно на двухбайтовый этот флажок мы сбросим);
  2. Два байта 0xxxxxxx xxxxxxxx в длинном режиме это символ текущего алфавита. Аналогично, мы складываем его со смещением из шага 1. Вся разница только в том, что теперь мы читаем по два байта (потому что мы переключились в такой режим).

Звучит неплохо: теперь пока нам нужно кодировать символы из одного и того же 7-битного диапазона Юникода, мы тратим 1 лишний байт в начале и всего по байту на каждый символ.

Работа одной из ранних версий. Уже нередко обходит UTF-8, но ещё есть что улучшать.
Работа одной из ранних версий. Уже нередко обходит UTF-8, но ещё есть что улучшать.

Что стало хуже? Во-первых, у нас появилось состояние, а именно смещение текущего алфавита и флажок длинного режима. Это нас дополнительно ограничивает: теперь одни и те же символы могут быть закодированы по-разному в разных контекстах. Поиск подстрок, например, придётся делать уже с учётом этого, а не просто сравнивая байты. Во-вторых, как только мы сменили алфавит, стало плохо с кодированием ASCII-символов (а это не только латиница, но и базовая пунктуация, включая пробелы) они требуют повторной смены алфавита в 0, то есть снова лишнего байта (а потом ещё одного, чтобы вернуться к нашему основному).

Один алфавит хорошо, два лучше


Попробуем чуть-чуть поменять наши битовые префиксы, втиснув к трём вышеописанным ещё один:

0xxxxxxx 1 байт в обычном режиме, 2 в длинном
11xxxxxx 1 байт
100xxxxx xxxxxxxx 2 байта
101xxxxx xxxxxxxx xxxxxxxx 3 байта



Теперь в двухбайтовой записи на один доступный бит стало меньше помещаются кодовые точки вплоть до 0x1FFF, а не 0x3FFF. Впрочем, всё ещё ощутимо больше, чем в двухбайтовых кодах UTF-8, большая часть распространённых языков всё ещё влезает, самая заметная потеря выпала хирагана и катакана, японцы в печали.

Что же за новый код 11xxxxxx? Это небольшой загашник размером в 64 символа, он дополняет наш основной алфавит, поэтому я назвал его вспомогательным (auxiliary) алфавитом. Когда мы переключаем текущий алфавит, то кусок старого алфавита становится вспомогательным. Например, переключились с ASCII на кириллицу в загашнике теперь 64 символа, содержащих латиницу, цифры, пробел и запятую (самые частые вставки в не-ASCII текстах). Переключились обратно на ASCII и вспомогательным алфавитом станет основная часть кириллицы.

Благодаря доступу к двум алфавитам, мы можем справиться с большим количеством текстов, имея минимальные затраты на переключение алфавитов (пунктуация чаще всего будет приводить к возврату в ASCII, но после этого многие не-ASCII символы мы будем доставать уже из дополнительного алфавита, без повторного переключения).

Бонус: обозначив допалфавит префиксом 11xxxxxx и выбрав его начальное смещение равным 0xC0, у нас получается частичная совместимость с CP1252. Иными словами, многие (но не все) западноевропейские тексты, закодированные в CP1252, будут выглядеть так же и в UTF-C.

Тут, правда, возникает трудность: как из основного алфавита получить вспомогательный? Можно оставить то же самое смещение, но увы тут структура Юникода уже играет против нас. Очень часто основная часть алфавита находится не в начале блока (например, русская заглавная А имеет код 0x0410, хотя кириллический блок начинается с 0x0400). Таким образом, взяв в загашник первые 64 символа, мы, возможно, утратим доступ к хвостовой части алфавита.

Для устранения этой проблемы я вручную прошёлся по некоторым блокам, соответствующим различным языкам, и указал для них смещение вспомогательного алфавита внутри основного. Латиницу, в порядке исключения, вообще переупорядочил наподобие base64.




Финальные штрихи


Давайте напоследок подумаем, где мы ещё можем что-то доработать.

Заметим, что формат 101xxxxx xxxxxxxx xxxxxxxx позволяет закодировать числа вплоть до 0x1FFFFF, а Юникод заканчивается раньше, на 0x10FFFF. Иными словами, последняя кодовая точка будет представлена как 10110000 11111111 11111111. Стало быть, мы можем сказать, что если первый байт имеет вид 1011xxxx (где xxxx больше 0), то он обозначает что-то ещё. Например, можно добавить туда ещё 15 символов, постоянно доступные для кодирования одним байтом, но я решил поступить по-другому.

Посмотрим на те блоки Юникода, которые требуют трёх байт сейчас. В основном, как уже было сказано, это китайские иероглифы но с ними трудно что-то сделать, их 21 тысяча. Но ещё туда улетела хирагана с катаканой а их уже не так много, меньше двухсот. И, раз уж мы вспомнили про японцев там же лежат эмодзи (на самом деле они много где раскиданы в Юникоде, но основные блоки в диапазоне 0x1F300 0x1FBFF). Если подумать о том, что сейчас существуют эмодзи, которые собираются из сразу нескольких кодовых точек (например, эмодзи состоит аж из 7 кодов!), то становится совсем жалко тратить на каждую по три байта (73 = 21 байт ради одного значка, кошмар же).

Поэтому выбираем несколько избранных диапазонов, соответствующих эмодзи, хирагане и катакане, перенумеровываем их в один непрерывный список и кодируем в виде двух байт вместо трёх:

1011xxxx xxxxxxxx

Отлично: вышеупомянутый эмодзи , состоящий из 7 кодовых точек, в UTF-8 занимает 25 байт, а мы уместили его в 14 (ровно по два байта на каждую кодовую точку). Кстати, Хабр отказался его переваривать (как в старом, так и в новом редакторе), так что пришлось вставить его картинкой.

Попробуем исправить ещё одну проблему. Как мы помним, основной алфавит это по сути старшие 6 бит, которые мы держим в уме, и приклеиваем к коду каждого очередного декодируемого символа. В случае с китайскими иероглифами, которые находятся в блоке 0x4E00 0x9FFF, это либо бит 0, либо 1. Это не очень удобно: нам нужно будет постоянно переключать алфавит между этими двумя значениями (т.е. тратить по три байта). Но заметим, что в длинном режиме из самого кода мы можем вычесть число символов, которое мы кодируем с помощью короткого режима (после всех вышеописанных хитростей это 10240) тогда диапазон иероглифов сместится к 0x2600 0x77FF, и в этом случае на всём этом диапазоне старшие 6 бит (из 21) будут равны 0. Таким образом, последовательности иероглифов будут использовать по два байта на иероглиф (что оптимально для такого большого диапазона), не вызывая переключений алфавита.

Альтернативные решения: SCSU, BOCU-1


Знатоки Unicode, ещё только прочитав название статьи, скорее всего, поспешат напомнить, что непосредственно среди стандартов Юникода есть Standard Compression Scheme for Unicode (SCSU), который описывает способ кодирования, весьма сходный с описанным в статье.

Признаюсь честно: о его существовании я узнал только уже глубоко погрузившись в написание своего решения. Знай о нём с самого начала, я, вероятно, попробовал бы написать его реализацию вместо придумывания собственного подхода.

Что занятно, SCSU использует идеи, очень похожие на те, к которым я пришёл самостоятельно (вместо понятия алфавитов там используются окна, и их доступно больше, чем у меня). В то же время, у этого формата тоже есть минусы: он чуть ближе к алгоритмам сжатия, нежели кодирования. В частности, стандарт даёт множество способов представления, но не говорит, как выбрать из них оптимальный для этого энкодер должен применять какие-то эвристики. Таким образом, SCSU-энкодер, дающий хорошую упаковку, будет сложнее и более громоздок, чем мой алгоритм.

Для сравнения я перенёс относительно простую реализацию SCSU на JavaScript по объему кода она оказалась сравнима с моим UTF-C, но в ряде случаев показала результат на десятки процентов хуже (иногда она может и превосходить его, но ненамного). Например, тексты на иврите и греческом UTF-C закодировал аж на 60% лучше, чем SCSU (вероятно, из-за их компактных алфавитов).

Отдельно добавлю, что кроме SCSU существует также другой способ компактного представления Юникода BOCU-1, но он ставит целью совместимость с MIME (что мне не требовалось), и использует несколько иной подход к кодированию. Его эффективность я не оценивал, но мне кажется, что она вряд ли будет выше, чем SCSU.

Возможные доработки


Приведённый мной алгоритм не универсален by design (в этом, наверное, мои цели сильнее всего расходятся с целями консорциума Unicode). Я уже упомянул, что он разрабатывался преимущественно под одну задачу (хранение мультиязычного словаря в префиксном дереве), и некоторые его особенности могут плохо подходить для других задач. Но тот факт, что он не является стандартом, может быть и плюсом вы можете легко доработать его под свои нужды.

Например, очевидным образом можно избавиться от наличия состояния, сделать кодирование stateless просто не обновлять переменные offs, auxOffs и is21Bit в энкодере и декодере. В таком случае не получится эффективно упаковывать последовательности символов одного алфавита, зато будет гарантия, что один и тот же символ всегда кодируется одними и теми же байтами, независимо от контекста.

Кроме того, можно заточить кодировщик под конкретный язык, поменяв состояние по умолчанию например, ориентируясь на русские тексты, выставить в начале энкодера и декодера offs = 0x0400 и auxOffs = 0. В особенности это имеет смысл именно в случае stateless режима. В целом это будет похоже на использование старой восьмибитной кодировки, только не лишает возможности вставлять символы из всего Юникода по необходимости.

Ещё один недостаток, упомянутый ранее в объемном тексте, закодированном в UTF-C, нет быстрого способа найти границу символа, ближайшего к произвольному байту. Отрезав от закодированного буфера последние, скажем, 100 байт, вы рискуете получить мусор, с которым ничего не сделать. На хранение многогигабайтных логов кодировка и не рассчитана, но в целом это можно поправить. Байт 0xBF никогда не должен встречаться в качестве первого байта (но может быть вторым или третьим). Поэтому при кодировании можно вставлять последовательность 0xBF 0xBF 0xBF каждые, скажем, 10 Кб тогда при необходимости найти границу будет достаточно просканировать выбранный кусок до тех пор, пока не найдётся подобный маркер. Вслед за последним 0xBF гарантированно будет начало символа. (При декодировании эту последовательность из трёх байт, конечно, нужно будет игнорировать.)

Подводя итог


Если вы дочитали досюда поздравляю! Надеюсь, вы, как и я, узнали что-то новое (или освежили в памяти старое) об устройстве Юникода.

Демонтрационная страница. На примере иврита видны преимущества как перед UTF-8, так и перед SCSU.
Демонтрационная страница. На примере иврита видны преимущества как перед UTF-8, так и перед SCSU.

Не стоит рассматривать вышеописанные изыскания как посягательство на стандарты. Однако я в целом доволен результатами своих наработок, поэтому рад ими поделиться: например, JS-библиотека в минифицированном виде весит всего 1710 байт (и не имеет зависимостей, конечно). Как я упоминал выше, с её работой можно ознакомиться на демо-страничке (там же есть набор текстов, на которых её можно посравнивать с UTF-8 и SCSU).

Напоследок ещё раз напомню, что закодированная с помощью UTF-C строка не обеспечивает ASCII transparency в ней могут находиться байты, соответствующие ASCII-символам. Попросту говоря использовать её можно только внутренне, в противном случае вы рискуете получить непредвиденные уязвимости.
Подробнее..
Категории: Алгоритмы , Хранение данных , Сжатие данных , Unicode , Юникод , Utf-8 , Scsu , Кодировки , Utf-c

Перевод Использование ИИ для сверхсжатия изображений

20.10.2020 16:06:30 | Автор: admin

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


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

Что такое сжатие изображений и какое оно бывает?


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

Как известно, существует два типа сжатия изображений: без потерь и с потерями. Как следует из названий, при сжатии без потерь можно получить данные исходного изображения, а при сжатии с потерями некоторые данные теряются во время сжатия. например, JPG это алгоритмы с потерями [прим. перев. в основном, не будем также забывать о JPEG без потерь], а PNG алгоритм без потерь.


Сравнение сжатия без потерь и с потерями

Обратите внимание, что на изображении справа много блочных артефактов. Это потерянная информация. Соседние пиксели похожих цветов сжимаются как одна область для экономии места, но при этом теряется информация о фактических пикселях. Конечно, алгоритмы, применяемые в кодеках JPEG, PNG и т.д., намного сложнее, но это хороший интуитивный пример сжатия с потерями. Сжатие без потерь это хорошо, но сжатые без потерь файлы занимают много места на диске. Есть более эффективные способы сжатия изображений без потери большого количества информации, но они довольно медленные, и многие применяют итеративные подходы. Это означает, что их нельзя запускать параллельно на нескольких ядрах центрального или графического процессора. Такое ограничение делает их совершенно непрактичными в повседневном использовании.

Ввод сверточной нейронной сети


Если что-то нужно вычислить и вычисления могут быть приближёнными, добавьте нейронную сеть. Авторы использовали довольно стандартную сверточную нейронную сеть для улучшения сжатия изображений. Представленный метод не только работает наравне с лучшими решениями (если не лучше), он также может использовать параллельные вычисления, что приводит к резкому увеличению скорости. Причина в том, что сверточные нейронные сети (CNN) очень хороши в извлечении пространственной информации из изображений, которые затем представляются в форме компактнее (например, сохраняются только важные биты изображения). Авторы хотели использовать эту возможность CNN, чтобы лучше представлять изображения.

Архитектура


Авторы предложили двойную сеть. Первая сеть принимает на вход изображение и генерирует компактное представление (ComCNN). Выходные данные этой сети затем обрабатываются стандартным кодеком (например, JPEG). После обработки кодеком изображение передается во вторую сеть, которая исправляет изображение из кодека в попытке вернуть исходное изображение. Авторы назвали эту сеть реконструирующей CNN (RecCNN). Подобно GAN обе сети обучаются итеративно.


ComCNN Компактное представление передается стандартному кодеку


RecCNN. Выходные данные ComCNN масштабируются с увеличением и передаются в RecCNN, которая попытается изучить остаток

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


Сквозной фреймворк сжатия изображений. Co(.) представляет собой алгоритм сжатия изображений. Авторы применяли JPEG, JPEG2000 и BPG

Что такое остаток?


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

Функции потерь


Две функции потерь используются потому, что у нас две нейронные сети. Первая из них, ComCNN, помечена как L1 и определяется так:


Функция потерь для ComCNN

Объяснение


Это уравнение может показаться сложным, но на самом деле это стандартная (среднеквадратичная ошибка) MSE. || означает норму вектора, который они заключают.


Уравнение 1.1

Cr обозначает выходные данные ComCNN. обозначает обучаемость параметров ComCNN, XK это входное изображение


Уравнение 1.2

Re() означает RecCNN. Это уравнение просто передает значение уравнения 1.1 В RecCNN. обозначает обучаемые параметры RecCNN (шляпка сверху означает, что параметры фиксированы).

Интуитивное определение


Уравнение 1.0 заставит ComCNN изменить свои веса таким образом, чтобы после воссоздания с помощью RecCNN окончательное изображение выглядело как можно более похожим на входное изображение. Вторая функция потерь RecCNN определяется так:


Уравнение 2.0

Объяснение


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


Уравнение 2.1

Co() означает вывод кодека, x со шляпкой сверху означает вывод ComCNN. 2 это обучаемые параметры RecCNN, res() представляет собой просто остаточный вывод RecCNN. Стоит отметить, что RecCNN обучается на разнице между Co() и входным изображением, но не на входном изображении.

Интуитивное определение


Уравнение 2.0 заставит RecCNN изменить свои веса так, чтобы выходные данные выглядели как можно более похожими на входное изображение.

Схема обучения


Модели обучаются итеративно, подобно GAN. Веса первой модели фиксируются, пока веса второй модели обновляются, затем веса второй модели фиксируются, пока первая модель обучается.

Тесты


Авторы сравнили свой метод с существующими методами, включая простые кодеки. Их метод работает лучше других, сохраняя при этом высокую скорость на соответствующем оборудовании. Кроме того, авторы попытались использовать только одну из двух сетей и отметили падение производительности.


Сравнение индекса структурного сходства (SSIM). Высокие значения указывают на лучшее сходство с оригиналом. Жирным шрифтом выделен результат работы авторов

Заключение


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

Изучать нейронные сети стало проще, ведь специально для хабравчан мы сделали промокод HABR, дающий дополнительную скидку 10% к скидке указанной на баннере.

image



Eще курсы


Рекомендуемые статьи


Подробнее..
Категории: Алгоритмы , Математика , Лайфхаки для гиков , Искусственный интеллект , Блог компании skillfactory , Нейронные сети , Ии , Сжатие данных , Skillfactory , Сжатие изображений

Кодирование для чайников, ч.1

01.01.2021 18:11:05 | Автор: admin

Не являясь специалистом в обозначенной области я, тем не менее, прочитал много специализированной литературы для знакомства с предметом и прорываясь через тернии к звёздам набил, на начальных этапах, немало шишек. При всём изобилии информации мне не удалось найти простые статьи о кодировании как таковом, вне рамок специальной литературы (так сказать без формул и с картинками).

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

0. Начало

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

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

Мимика, жесты, речь, сигналы разного уровня - табличка с надписью, знак на дороге, светофоры, и для современного мира - штрих- и бар-коды, URL, хэш-тэги.

Давайте рассмотрим некоторые более подробно.

1.1 Речь, мимика, жесты

Удивительно, но всё это - коды. С помощью них мы передаём информацию о своих действиях, ощущениях, эмоциях. Самое важное, чтобы коды были понятны всем. Например, родившись в густых лесах у Амазонки и не видя современного городского человека, можно столкнуться с проблемой непонимания кода - улыбка, как демонстрация зубов, будет воспринята как угроза, а не как выражение радости.

Следуя определению, что же происходит когда мы говорим? Мысль - как форма, удобная для непосредственного использования, преобразуется в речь - форму удобную для передачи. И, смотрите, так как у звука есть ограничение как на скорость, так и на дальность передачи, то, например, жест, в какой-то ситуации, может быть выбран для передачи той же информации, но на большее расстояние. Но мы всё еще будем ограничены дальностью остроты нашего зрения и тогда человек начинает придумывать другие способы передачи и преобразования информации, например огонь или дым.

1.2 Чередующиеся сигналы

Индеец пингуетИндеец пингует

В примитивном виде кодирование чередующимися сигналами используется человечеством очень давно. В предыдущем разделе мы сказали про дым и огонь. Если между наблюдателем и источником огня ставить и убирать препятствие, то наблюдателю будет казаться, что он видит чередующиеся сигналы "включено/выключено". Меняя частоту таких включений мы можем выработать последовательность кодов, которая будет однозначно трактоваться принимающей стороной.

Наряду с сигнальными флажками на морских и речных судах, при появлении радио начали использовать код Морзе. И при всей кажущейся бинарности (представление кода двумя значениями), так как используются сигналы точка и тире, на самом деле это тернаный код, так как для разделения отдельных кодов-символов требуется пауза в передаче кода. То есть код Морзе кроме "точка-тире", что нам даёт букву "A" может звучать и так - "точка-пауза-тире" и тогда это уже две буквы "ET".

1.3 Контекст

Когда мы пользуемся компьютером, мы понимаем, что информация бывает разной - звук, видео, текст. Но в чем основные различия? И до того, как начать информацию кодировать, чтобы, например, передавать её по каналам связи, нужно понять, что из себя представляет информация в каждом конкретном случае, то есть обратить внимание на содержание. Звук - череда дискретных значений о звуковом сигнале, видео - череда кадров изображений, текст - череда символов текста. Если мы не будем учитывать контекст, а, например, будем использовать азбуку Морзе для передачи всех трёх видов информации, то если для текста такой способ может оказаться приемлемым, то для звука и видео время, затраченное на передачу например 1 секунды информации, может оказаться слишком долгим - час или даже пара недель.

2. Кодирование текста

От общего описания кодирования перейдём к практической части. Из условностей вы за константу примем то, что будем кодировать данные для персонального компьютера где за единицу информации приняты - бит и байт. Бит, как атом информации, а байт - как условный блок размером в 8 бит.

Текст в компьютере является частью 256 символов, для каждого отводится один байт и в качестве кода могут быть использованы значения от 0 до 255. Так как данные в ПК представлены в двоичной системе счисления, то один байт в значении ноль равен записи 00000000, а 255 как 11111111. Чтение такого представления числа происходит справа налево, то есть один будет записано как 00000001.

Итак, символов английского алфавита 26 для верхнего и 26 для нижнего регистра, 10 цифр. Так же есть знаки препинания и другие символы, но для экспериментов мы будем использовать только прописные буквы (верхний регистр) и пробел.

Тестовая фраза "ЕХАЛ ГРЕКА ЧЕРЕЗ РЕКУ ВИДИТ ГРЕКА В РЕЧКЕ РАК СУНУЛ ГРЕКА РУКУ В РЕКУ РАК ЗА РУКУ ГРЕКУ ЦАП".

2.1 Блочное кодирование

Информация в ПК уже представлена в виде блоков по 8 бит, но мы, зная контекст, попробуем представить её в виде блоков меньшего размера. Для этого нам нужно собрать информацию о представленных символах и, на будущее, сразу подсчитаем частоту использования каждого символа:

Символ

Количество

ПРОБЕЛ

18

Р

12

К

11

Е

11

У

9

А

8

Г

4

В

3

Ч

2

Л

2

И

2

З

2

Д

1

Х

1

С

1

Т

1

Ц

1

Н

1

П

1

Всего нами использовано 19 символов (включая пробел). Для хранения в памяти ПК будет затрачено 18+12+11+11+9+8+4+3+2+2+2+2+1+1+1+1+1+1+1=91 байт (91*8=728 бит).

Эти значения мы берём как константы и пробуем изменить подход к хранению блоков. Для этого мы замечаем, что из 256 кодов для символов мы используем только 19. Чтобы узнать - сколько нужно бит для хранения 19 значений мы должны посчитать LOG2(19)=4.25, так как дробное значение бита мы использовать не можем, то мы должны округлить до 5, что нам даёт максимально 32 разных значения (если бы мы захотели использовать 4 бита, то это дало бы лишь 16 значений и мы не смогли бы закодировать всю строку).

Нетрудно посчитать, что у нас получится 91*5=455 бит, то есть зная контекст и изменив способ хранения мы смогли уменьшить использование памяти ПК на 37.5%.

К сожалению такое представление информации не позволит его однозначно декодировать без хранения информации о символах и новых кодах, а добавление нового словаря увеличит размер данных. Поэтому подобные способы кодирования проявляют себя на бОльших объемах данных.

Кроме того, для хранения 19 значений мы использовали количество бит для 32 значений, это снижает эффективность кодирования.

2.2 Коды переменной длины

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

Символ

Количество

Переменный код, бит

ПРОБЕЛ

18

0

Р

12

1

К

11

00

Е

11

01

У

9

10

А

8

11

Г

4

000

В

3

001

Ч

2

010

Л

2

011

И

2

100

З

2

101

Д

1

110

Х

1

111

С

1

0000

Т

1

0001

Ц

1

0010

Н

1

0011

П

1

0100

Для подсчёта длины закодированного сообщения мы должны сложить все произведения количества символов на длины кодов в битах и тогда получим 179 бит.

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

2.3 Префиксные блочные коды

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

Составим третью таблицу всё для той же строки:

Символ

Количество

Префиксный код с переменными блоками, бит

ПРОБЕЛ

18

0000

Р

12

0001

К

11

0010

Е

11

0011

У

9

0100

А

8

0101

Г

4

0110

В

3

0111

Ч

2

10001

Л

2

10010

И

2

10011

З

2

10100

Д

1

10101

Х

1

10110

С

1

10111

Т

1

11000

Ц

1

11001

Н

1

11010

П

1

11011

Особенность новых кодов в том, что первый бит мы используем для указания размера следующего за ним блока, где 0 - бок три бита, 1 - блок четыре бита. Нетрудно посчитать, что такой подход закодирует нашу строку в 379 бит. Ранее при блочном кодировании у нас получился результат в 455 бит.

Можно развить этот подход и префикс увеличить до 2 бит, что позволит нам создать 4 группы блоков:

Символ

Количество

Префиксный код с переменными блоками, бит

ПРОБЕЛ

18

000

Р

12

001

К

11

0100

Е

11

0101

У

9

0110

А

8

0111

Г

4

10000

В

3

10001

Ч

2

10010

Л

2

10011

И

2

10100

З

2

10101

Д

1

10110

Х

1

10111

С

1

11000

Т

1

11001

Ц

1

11010

Н

1

11011

П

1

11100

Где 00 - блок в 1 бит, 01 - 2 бита, 10 и 11 - 3 бита. Подсчитываем размер строки - 356 бит.

В итоге за три модификации одного способа мы регулярно уменьшаем размер строки, от 455 до 379, а затем до 356 бит.

2.4 Код Хаффмана

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

Такой код гарантирует, что для каждого символа есть только одна уникальная последовательность значений битов. При этом частым символам будут назначены короткие коды.

Символ

Количество

Код

ПРОБЕЛ

18

00

Р

12

101

К

11

100

Е

11

011

У

9

010

А

8

1111

Г

4

11011

В

3

11001

Ч

2

111011

Л

2

111010

И

2

111001

З

2

111000

Д

1

1101011

Х

1

1101010

С

1

1101001

Т

1

1101000

Ц

1

1100011

Н

1

1100010

П

1

110000

Считаем результат - 328 бит.

Заметьте, хоть мы и стали использовать коды в 6 и 7 бит, но их слишком мало, чтобы повлиять на исход.

2.5.1 Строки и подстроки

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

Напомню нашу строку: "ЕХАЛ ГРЕКА ЧЕРЕЗ РЕКУ ВИДИТ ГРЕКА В РЕЧКЕ РАК СУНУЛ ГРЕКА РУКУ В РЕКУ РАК ЗА РУКУ ГРЕКУ ЦАП".

Составим таблицу повторов слов:

Слово

Количество

ПРОБЕЛ

18

ГРЕКА

3

В

2

РАК

2

РЕКУ

2

РУКУ

2

ВИДИТ

1

ГРЕКУ

1

ЕХАЛ

1

ЗА

1

РЕЧКЕ

1

СУНУЛ

1

ЦАП

1

ЧЕРЕЗ

1

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

Сначала формируем словарь:

Слово

Количество

Индекс

ГРЕКА

3

0

В

2

1

РАК

2

2

РЕКУ

2

3

РУКУ

2

4

ВИДИТ

1

5

ГРЕКУ

1

6

ЕХАЛ

1

7

ЗА

1

8

РЕЧКЕ

1

9

СУНУЛ

1

10

ЦАП

1

11

ЧЕРЕЗ

1

12

Таким образом наша строка кодируется в последовательность:

7, 0, 12, 3, 5, 0, 1, 9, 2, 10, 0, 4, 1, 3, 2, 8, 4, 6, 11

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

Индексы записываем в виде блоков по 4 бита (так можно представить индексы от 0 до 15), таких цепочек у нас будет две, одна для закодированного сообщения, а вторая для соответствия индексу и слову. Сами слова будем кодировать кодами Хаффмана, только нам еще придется задать разделитесь записей в словаре, можно, например, указывать длину слова блоком, самое длинное слово у нас в 5 символов, для этого хватит 3 бита, но так же мы можем использовать код пробела, который состоит из двух бит - так и поступим. В итоге мы получаем схему хранения словаря:

Индекс / биты

Слово / биты

Конец слова / биты

0 / 4

ГРЕКА / 18

ПРОБЕЛ / 2

1 / 4

В / 5

ПРОБЕЛ / 2

2 / 4

РАК / 10

ПРОБЕЛ / 2

3 / 4

РЕКУ / 12

ПРОБЕЛ / 2

4 / 4

РУКУ / 12

ПРОБЕЛ / 2

5 / 4

ВИДИТ / 31

ПРОБЕЛ / 2

6 / 4

ГРЕКУ / 17

ПРОБЕЛ / 2

7 / 4

ЕХАЛ / 20

ПРОБЕЛ / 2

8 / 4

ЗА / 10

ПРОБЕЛ / 2

9 / 4

РЕЧКЕ / 18

ПРОБЕЛ / 2

10 / 4

СУНУЛ / 26

ПРОБЕЛ / 2

11 / 4

ЦАП / 17

ПРОБЕЛ / 2

12 / 4

ЧЕРЕЗ / 21

ПРОБЕЛ / 2

7

0

12

3

5

0

1

9

2

10

0

4

1

3

2

8

4

6

11

и само сообщение по 4 бита на код.

Считаем всё вместе и получаем 371 бит. При этом само сообщение у нас было закодировано в 19*4=76 бит. Но нам всё еще требуется сохранять соответствие кода Хаффмана и символа, как и во всех предыдущих случаях.

Послесловие

Надеюсь статья позволит составить общее впечатление о кодировании и покажет, что это не только военный-шифровальщик или сложный алгоритм для математических гениев.

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

Подробнее..
Категории: Алгоритмы , Занимательные задачки , Сжатие данных , Кодирование , Huffman , Биты. двоичная система

Что такое HDR10? Разбор

05.02.2021 14:16:53 | Автор: admin
70% информации о мире человек получает через зрение. Фактически глаза наш главный орган чувств.Но можем ли мы доверять нашему зрению?

Давайте взглянем на картинку. Вроде ничего необычного. Но что если я вам скажу, что ячейки A и B совершенного одного цвета.





На самом деле мы не всегда можем отличить светлое от темного. Далеко за примерами ходить не надо: помните сине-черное / бело-золотое платье или появившиеся чуть позже кроссовки?





И все современные экраны пользуются этой особенностью человеческого зрения. Вместо настоящего света и тени нам показывают их имитацию. Мы настолько к этому привыкли, что даже не представляем что может быть как-то иначе. Но на самом деле может. Благодаря технологии HDR, которая намного сложнее и интереснее, чем вы думаете.Поэтому сегодня мы поговорим, что такое настоящее HDR-видео, поговорим про стандарты и сравним HDR10 и HDR10+ на самом продвинутом QLED телевизоре!



На самом деле первое, что надо знать про HDR: это не просто штука, которая правильно хранит видео. Чтобы увидеть HDR-контент нам нужно две составляющие: сам контент, и правильный экран, который его поддерживает. Поэтому смотреть мы сегодня будем на QLED-телевизоре Samsung.

6 стопов SDR


Ежедневно наши глаза сталкиваются с экстремальными перепадами яркости. Поэтому человеческое зрение в ходе эволюции научилось видеть достаточно широкий динамический диапазон (ДД), то есть разницу улавливать разницу между разными уровнями яркости. Фотографы и киноделы знают, что ДД измеряется в ступенях экспозиции или стопах (f-stop).

Так сколько стопов видит человеческий глаз? Скажу так по разному.

Если завязать вам глаза, вывести в незнакомое место и резко снять повязку, то в эту секунду вы увидите 14 стопов экспозиции. Это не мало. Вот камера, на которую я снимаю ролики, видит только 12 стопов. И это ничто по сравнению с человеческим зрением, потому что оно умеет адаптироваться.

Спустя пару секунд, когда ваши глаза привыкнут к яркости и обследуют пространство вокруг, настройки зрения подкрутятся и вы увидите потрясающую игру света и тени из 30 стопов экспозиции!





Ух! Красота! Но когда мы смотрим видео на ТВ или на экране смартфона, нам остаётся довольствоваться только 6 стопами экспозиции, потому как видео со стандартным динамическим диапазоном или SDR больше не поддерживает.

Яркость


Почему так мало? Вопрос исторический и связан он с двумя этапами.

Стандарты современного SDR видео зародились еще в середине 20-го века, когда появилось цветное телевидение. Тогда существовали только ЭЛТ телевизоры, и они были очень тусклые. Максимальная яркость была 100 нит или кандел на квадратный метр. Кстати, кандела это свеча. Поэтому 100 кандел на квадратный метр буквально означает уровень яркости 100 свечей, расположенных на площади в 1 метр. Но если вам не нравится измерять яркость в свечах, вместо кандел на квадратный метр можно просто говорить ниты. Кстати в нашем телевизоре Samsung Q950T 4000 нит.

Так вот, это ограничение яркости было заложено в стандарт SDR. Поэтому современные телевизоры показывая SDR-контент по сути игнорируют потрясающую адаптивность человеческого зрения подсовывают нам тусклую и плоскую картинку. И это несмотря на то, что с тех пор техника сильно продвинулись вперед.

Одной из особенностей технологии QLED является высокая пиковая яркость. Это самые яркие ТВ на рынке, они даже ярче OLED.

Современные QLED-телевизоры способны выдавать целых 4000 нит яркости, что в 40 раз больше, чем заложено в стандарт SDR. Потрясающе показывай, что хочешь. Но по-прежнему 99% контента, который мы видим это SDR, поэтому смотря YouTube на своём потрясающем AMOLED-дисплее, вы фактически смотрите эмуляцию кинескопа из гостиной времен разгара холодной войны. Такие дела.

Глубина цвета


Второе ограничение тоже происходит из глубокой древности 1990-х.

Тогда появился революционный стандарт цифровое телевидение высокой четкости HDTV, частью которого стала глубина цвета 8 бит.Это значит, что у каждого из базовых цветов красного, зеленого и синего может быть только 256 значений. Возводим 2 в 8-ю степень получается 256 это и есть 8 бит..

Итого на три канала, всего 16 777 216 миллионов оттенков.



Кажется, что это много. Но человек видит куда больше цветов. И все эти некрасивые ступенчатые переходы, которые часто можно заметить на видео и фотографиях и конечно в YouTube, спасибо его фирменному кодеку это как раз ограничения 8 бит.



Но самое интересное, что эти два ограничения: 6 стопов экспозиции и 8 бит на канал, не позволяли SD-видео сымитировать главную особенность человеческого зрения его нелинейность! Поэтому поговорим про восприятие яркости.

Восприятие яркости


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



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



Но в отличие от SDR HDR видео кодируется с глубиной цвета, как минимум 10 бит. А это 1024 значения на канал и итоговые более миллиарда оттенков (1024 x 1024 x 1024 = 1 073 741 824)





А предельная яркость изображения в HDR видео стартует от 1000 нит и может достигать 10000 нит. Это в 100 раз ярче SDR!

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



Метаданные


Итак, мы с вами выяснили, что возможности HDR сильно превосходят SDR, и HDR показывает куда более страшную и всю из себя контрастную картинку, но! Какая разница, какой там у тебя формат видео, SDR или HDR, если качество изображения всё равно зависит от экрана, на котором ты смотришь. На некоторых экранах SDR выглядит так насыщенно и контрастно, что HDR даже и не снилось.Всё так!

Все дисплеи отличаются. Они по-разному откалиброваны, в них разный уровень яркости и прочие параметры.

Но HDR-видео в отличие от SDR не просто выводит изображение на экран, но еще и умеет сообщать телевизору, как именно нужно его показывать! Делается это при помощи так называемых метаданных.



Они бывают двух видов.

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

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

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

HDR10 и HDR10+


Самый распространённый формат с поддержкой статический метаданных это HDR10.Более того это самый распространенный HDR формат в принципе. Если видите наклейку HDR на телевизоре знайте: он поддерживает HDR10. Это его плюс.

Но поддержка только статических метаданных не позволяют назвать его настоящим HDR.Поэтому компания Samsung, совместно с 20th Century Fox и Panasonic решили исправить это недоразумение и добавили к HDR10 поддержку динамических метаданных, назвав новый стандарт HDR10+.



Получился он царский 10 бит, 4000 нит, более миллиарда оттенков.Но видна ли разница между HDR10 и 10+ на практике.

У нас есть QLED телевизор Samsung Q950T, который как раз поддерживает оба формата. Поэтому сравнение будет максимально корректным. Мы запустили кино, которые смастерили в HDR10 и HDR10+. И знаете, что я действительно увидел разницу.На этом телевизоре и HDR10 выглядит круто, а HDR10+ вообще разрывает шаблон. И дело не только в стандарте HDR10+.

Adaptive Picture




Дело в том, что HDR-контент существенно более придирчив к качеству дисплея, чем SDR. Например, яркость в HDR-видео указывается не в относительных значениях, то есть в процентах, а в абсолютных в нитах.Поэтому, хочешь не хочешь, но если в метаданных указано, что этот конкретный участок изображения должен светить 1000 нит нужно, чтобы телевизор сумел выдать такую яркость. Иначе, это уже будет не HDR.

А если, вдруг, вы смотрите видео днём, в ярко освещенной комнате, то нужно еще компенсировать окружающее освещение.Большинство устройств не справляются с этой задачей. Но, у QLED телевизоров Samsung, в этом плане есть, огромное преимущество.

Во-первых, в них используется технология Adaptive Picture, которая подстраивает яркость и контрастность изображения в зависимости от окружающего освещения.

Во-вторых, как я уже говорил, запас яркости в QLED 4000 нит. А этого с головой хватит для компенсации практически любого внешнего освещения.

В отличие от OLED-телевизоров, которые могут выдавать необходимый уровень контраста только при плотно зашторенных шторах.

Другие технологии




Естественно, это не единственная крутая технология внутри данного телевизора. Здесь установлен мощный нейропроцессор Quantum 8K, который в реальном времени умеет апскейлить 4K-контент до 8К. Причём он не просто повышает четкость изображения, он распознаёт разного типа текстуры и дополнительно их прорабатывает.Еще тут сверхширокие углы обзора, прекрасный объемный звук, который кстати тоже адаптируется под уровень шума в помещении в реальном времени. И масса других технологии, эксклюзивных для QLED-телевизоров Samsung.

Но главная технология сегодняшнего вечера HDR10+ и, что прекрасно это не эксклюзив.



HDR10+ это открытый и бесплатный стандарт, как и обычный HDR10. Всё это дает ему огромное преимущество перед, по сути, таким же, но платным Dolby Vision.Поэтому HDR10+ есть не только в телевизорах и смартфонах Samsung его поддерживают практически все производители телевизоров, смартфонов, камер, ну и, конечно, в этом формате снимаются и делаются фильмы. А значит у HDR10+ есть все шансы стать настоящим народным стандартом HDR, которым вы сможете насладиться на всех экранах страны, как больших, так и малых.
Подробнее..
Категории: Алгоритмы , Разбор , Электроника для начинающих , Матрицы , Мониторы и тв , Контент , Блог компании droider.ru , Дисплей , Сжатие данных , Телевизоры , Тв , Телевидение , Dolby , Dolby vision , Hdr , Hdr10 , Hdr 10+ , Экран , Тв-матрицы , Hdr-контент , Hdr-видео

Windows 95 на двух флоппиках

04.11.2020 18:10:50 | Автор: admin
В этом году мы отпраздновали четверть века с Windows 95. Её минимальная установка занимала 30 МБ; народные умельцы ужимали её до 5 МБ после удаления всех лишних файлов и сжатия UPX-ом оставшихся. А как насчёт двух флоппиков по 1.44 МБ, вместе с загрузчиком?



Общий подход я уже описывал в комментариях: создаётся RAMDRIVE, и на него разворачивается двухтомный SFX-архив. Но есть много тонкостей:

  1. Как видно на видео выше, распакованная папка Windows у меня занимает 6.2 МБ. Я взял за основу список файлов Micro95, и дополнительно удалил файлы, оказавшиеся необязательными например, шрифты и драйвер dosnet.vxd. Кроме того, vmm32.vxd я распаковал, и удалил бывшие внутри него необязательные драйвера.

    Можно было уменьшить Windows ещё сильнее, пересобрав vmm32.vxd после удаления необязательных драйверов (освобождается почти мегабайт, но сжимается такой vmm32.vxd хуже, чем распакованные VXD), заменив оболочку на классический Диспетчер программ (освобождается целый мегабайт за счёт explorer.exe и shell32.dll), и/или отказавшись от поддержки командной строки (освобождается 155 КБ за счёт pifmgr.dll, vgafull.3gr, winoa386.mod); но я решил, что без этих компонентов Windows 95 становится полностью бесполезной.

    Со всем этим, на втором флоппике у меня оставались ещё 247 свободных КБ, так что я смог добавить к минимальному набору файлов ещё Блокнот и три аплета Панели управления; даже и с ними один килобайт на флоппике остался незанятым :-)

    Fun fact: среди оставшихся файлов поровну (по 19) 16-битных NE и 32-битных PE, подтверждая байку о том, что Windows 95 была 32-битной ровно наполовину.
  2. Проект Micro95 публиковал минимальное содержимое system.ini, win.ini, и реестра. К ним я тоже подошёл творчески: в system.ini на самом деле достаточно двух строк 
    [386Enh]mouse=*vmouse
    Существование win.ini необязательно; а с предложенным ими вариантом реестра перестают работать ярлыки, Корзина и Панель управления, так что реестр я урезал менее агрессивно.
  3. Для сжатия Windows лучше всего подошёл WinAce: уровень сжатия у него почти такой же, как у WinRAR, но SFX-модуль для DOS меньше на 32 КБ, и его можно уменьшить ещё на килобайт, пережав UPX-ом c ключом --ultra-brute. Ещё 31 КБ удалось выиграть, сжав UPX-ом драйвера himem.sys, ramdrive.sys, ifshlp.sys
  4. Для того, чтобы работали ярлыки (в т.ч. Перезагрузка в режиме MS-DOS), при распаковке Windows должны воссоздаваться длинные имена файлов (LFN). SFX-модули делают это при помощи LFN API, который доступен в MS-DOS 7+ только после загрузки графической среды Windows. Я нашёл опенсорсный драйвер DOSLFN, заброшенный в 2012; к сожалению, под версией DOS, родной для Windows 95, он не работал из-за бага: наличие в DOS поддержки FAT32 определялось некорректно, так что в Windows 95 он думал, что поддержка есть, пытался ей пользоваться, и терпел неудачу. (В DOS 6.x и более старых, а также в Windows 95 OSR2 и более новых, драйвер работал корректно.) Для того, чтобы исправить этот баг, достаточно было закомментировать в исходнике две строчки: 
    ;== 6. Determine the presence of the FAT32 API == movax,7302h;extended get DPB movdl,0;current drive movcx,3fh;length of buffer movdi,ofs truename_buf;buffer stc;for pre-DOS7 int21h jnc@@ext; On Win95 4.00.950, it always fails with AX=1; cmpax,7300h;did it fail because there's no such call?; jne@@ext;no, it didn't like the drive
    Раз мне всё равно пришлось перекомпилировать DOSLFN, я заодно расставил по всему коду условную компиляцию, чтобы получить возможность уменьшить файл в полтора раза, отключив ненужные мне возможности переключение языков сообщений, поддержку Unicode, и поддержку CD-ROM. Пропатченный исходник я положил на tyomitch.github.io/doslfn.asm; все мои изменения можно увидеть на github.com/tyomitch/tyomitch.github.io/commit/ad8a2

Поскольку Windows 95 в 2018 была передана в общественное достояние, то я не нарушаю ничьи авторские права, публикуя образы двух моих флоппиков:
Подробнее..
Категории: Системное администрирование , Разработка под windows , История it , Assembler , Сжатие данных , Windows 95 , Micro95 , Vmm32 , Ramdrive , Winace , Doslfn

Почтовая система Mailion как нам удалось создать эффективное объектное хранилище для электронной почты

11.12.2020 16:14:18 | Автор: admin

Недавно на Хабре вышли две статьи про новую корпоративную почтовую систему Mailion от МойОфис (1, 2) уникальную российскую разработку, которая отличается беспрецедентными возможностями масштабирования и способна работать в системах с более чем 1 миллионом пользователей.

Несложно подсчитать, что для обслуживания такого числа пользователей потребуется колоссальный объем дискового пространства вплоть до десятков петабайт. При этом почтовая система должна уметь быстро обрабатывать эту информацию и надежно хранить её. Сегодня мы объясним общие принципы организации хранения данных внутри почтовой системы Mailion и расскажем, к каким оптимизациям мы прибегли, чтобы значительно снизить количество операций ввода/вывода и сократить требования к инфраструктуре.

Хабр, привет! Меня зовут Виталий Исаев, я занимаюсь разработкой объектного хранилища почтовой системы Mailion. Этой статьёй мы открываем цикл публикаций, посвящённых архитектуре нашего хранилища, его масштабированию, отказоустойчивости и устройству его внутренних подсистем.

Немного истории

Структура электронного письма формировалась в течение последних пятидесяти лет. Этапы её развития зафиксированы несколькими стандартами. Первое электронное письмо было отправлено между компьютерами системы ARPANET ещё в 1971 г. Но разработчикам стандартов потребовалось ещё 11 лет на разработку RFC 822, который стал прообразом современного представления электронной почты. В нём был описан общий коммуникационный фреймворк текстовых сообщений. В это время электронное письмо рассматривалось просто как набор текстовых строк, а передача структурированных данных (изображений, видео, звука) не подразумевалась и никак не регламентировалась.

Примерно в середине 1990-х родилась концепция специальных расширений MIME (RFC 2045, RFC 2046, RFC 2047), которые позволили включать в состав электронного письма бинарные форматы данных в закодированном виде.

В 2001 году новый стандарт RFC 2822 отменил некоторые устаревшие положения RFC 822, и ввёл понятие частей сообщения message parts, или, проще говоря, "партов". А благодаря MIME появилась возможность создавать multipart-письма, которые могли бы состоять из множества частей различных типов. Наиболее актуальным стандартом электронной почты является RFC 5322, он был разработан в 2008 году.

Структура электронного письма

На сегодняшний день типичное почтовое сообщение состоит из заголовка и "партов". В заголовке в структурированном виде хранятся метаданные, такие как идентификатор письма, электронные адреса отправителя и получателя, дата отправки и другие служебные поля. К "партам", которые составляют само тело письма, относятся основной и альтернативный текст, изображения, прикреплённые файлы. Объём заголовочной части письма редко превышает 1 килобайт текста, тогда как размер тела письма ограничен лишь лимитами почтовой системы и может достигать десятков и даже сотен мегабайт.

Когда письма поступают в Mailion по любому из транспортных каналов (SMTP, IMAP, API), они не сохраняются как единое целое, а разбиваются на составные части. В Mailion мы извлекаем информацию о структуре письма и некоторые другие служебные данные, и затем сохраняем их в хранилище метаинформации. "Парты" писем, которые составляют основной объем данных, направляются в объектное хранилище.

Рис. 1. Разбиение электронного письма на фрагменты и сохранение по частям в хранилище метаданных и объектном хранилище.

Поток данных, который проходит через почтовую систему, отличается следующими важными особенностями:

  • Письма часто пишутся и ещё чаще читаются. Работа пользователей с почтовой системой порождает огромное количество операций ввода-вывода в хранилище.

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

  • Многие письма частично совпадают по содержимому. Например, в длинной цепочке писем могут встречаться взаимные цитирования. Это порождает совпадающие фрагменты текста. Пересылка писем со вложениями приводит к дублированию вложенных файлов. Кроме того, всеми сотрудниками одной компании используется в подписи идентичная картинка с логотипом. В корпоративной среде помимо этих совпадений бывают и другие, которые создаются информационными системами предприятия, например, шаблонными письмами с ответами календаря или системы управления задачами.

  • В корпоративной среде часто встречаются полные дубликаты писем. Это связано как с широким применением рассылок (например, отправка новостей компании всем сотрудникам), так и с практикой использования копий и скрытых копий. Наконец, у каждого письма всегда есть минимум две копии для отправителя и получателя, и в случае внутрикорпоративной переписки обе копии хранятся в одной и той же почтовой системе.

Дедупликация

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

Пример расчета ресурсов системы хранения

Представьте, что вам необходимо выполнить массовую рассылку письма по компании с 1000 сотрудников. В подписи отправителя письма находится картинка с логотипом компании, её размер составляет 256 Кб. Давайте оценим затраты ресурсов на чтение рассылки всеми сотрудниками компаниями.

В классических почтовых системах mbox-формата, в которых копии писем разных пользователей хранятся в разных файлах, данная операция будет порождать поток произвольных чтений (random read) с диска. Стандартные HDD в этом режиме работы выдают производительность около 100 IOPS. При размере блока в 4 Кб чтение картинки в худшем случае, когда блоки файла при записи не были размещены последовательно, потребует 64 операции чтения. Следовательно, для чтения всех писем с картинками будет необходимо выполнить 64000 операции (64 операции * 1000 пользователей). Для того, чтобы обработать данную операцию за 1 секунду, потребуется 640 HDD одновременно. Если же в системе присутствует только один накопитель, то он будет работать со 100% утилизацией более 10 минут.

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

Накладные расходы дедупликации

Безусловно, дедупликация не бесплатна и сильно усложняет процесс записи и чтения, налагает дополнительные расходы на CPU и RAM. Однако иммутабельность данных частично компенсирует этот рост сложности. Благодаря неизменности писем, можно не поддерживать операцию записи по смещению (при необходимости его можно реализовать по принципу copy-on-write) и сохранять интерфейс хранилища максимально простым. На данный момент он состоит из записи, чтения, удаления данных и ещё пары вспомогательных методов.

Известные решения с дедупликацией

На момент старта проекта Mailion ни в одном из известных нам объектных хранилищ с открытым кодом подобные оптимизации не были реализованы. Например, в Minio отказались от реализации дедупликации ещё в 2017 г. Попытки доработки других готовых решений, таких, как Elliptics, Riak или Swift, при очевидных и значительных трудозатратах также не гарантировали успеха. ZFS в течение долгих лет не поддерживалась в Linux и по причине лицензионных разногласий официально не может поставляться в дистрибутивах, отличных от Oracle, да и к производительности дедупликации в этой файловой системе есть вопросы.

В Ceph дедупликация появилась в 2019 г., но Ceph имеет репутацию сложного для эксплуатации хранилища с большим количеством историй неуспеха. Многим известны истории отказа Ceph в Росреестре и DigitalOcean и даже потеря бизнеса компанией DataMouse. В багтрекере Ceph можно найти большое количество тикетов с зависаниями, сегфолтами и другими ошибками. Причем некоторые баги, даже в статусе Immediate, могут не устраняться по полгода и больше. Это наводит на мысли о том, что Ceph дорог не только с точки зрения эксплуатации, но и с точки зрения разработки: ресурсы разработчиков будут уходить на стабилизацию самого Ceph, а не на разработку собственного продукта.

Что такое DOS и как это работает

Мы убедились в отсутствии подходящих для наших задач продуктов с открытым исходным кодом, и решили разработать собственное хранилище с поддержкой дедупликации в самом ядре системы. Мы вдохновились программной статьей аналитиков из компании Storage Switzerland, в которой кратко описываются принципы проектирования современных программно-ориентированных хранилищ, и решили назвать наш продукт Dispersed Object Store (DOS). Код DOS написан на языках Go (95%), C и C++ (5%).

Модель данных и метаданных

Иерархия сущностей DOS включает в себя четыре уровня:

  • документы;

  • версии документов;

  • чанки (chunks);

  • сегменты.

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

Каждый документ со стороны публичного API адресуется идентификатором, который состоит из пространства имён (namespace) и собственно ключа (key). В рамках одного пространства имён все ключи являются уникальными. Непосредственно в хранилище из внешнего идентификатора и с помощью криптографической хеш-функции генерируется внутренний ключ (storekey), который обладает свойством глобальной уникальности. Во внутренних API все документы адресуются уже через storekey.

В DOS применяется стриминговая запись. В рамках обработки одного запроса на запись поток данных, который поступает на сервер, частично буферизуется в оперативной памяти и только по накоплению определенного объёма сохраняется в персистентном хранилище. Полной буферизации крупных файлов не происходит никогда, поскольку это привело бы к чрезмерным расходам RAM. Частичная буферизация данных (но не только она) предопределяет в модели данных DOS появление чанков крупных байтовых последовательностей. Каждая версия документа может состоять из одного или нескольких чанков.

Чанки, в свою очередь, с помощью специальных алгоритмов разделяются на сегменты более короткие байтовые последовательности. Они выступают в роли элементарных единиц хранения в DOS. У сегментов тоже есть свои идентификаторы, ими являются хеши от их содержимого. В каком-то смысле, внутренним адресом данных в DOS являются сами данные (эта идея не нова и используется, например, в P2P-файловом хранилище IPFS).

Все документы, версии, чанки и сегменты в совокупности формируют внутренние метаданные DOS. Для персистентного хранения метаданных (документов и сегментов) вводятся индексы. В качестве хранилища индексов используется широко известная встраиваемая key-value база данных RocksDB. Индексы с метаданными должны размещаться на быстрых SSD дисках.

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

Рис. 2. Иерархия внутренних сущностей DOS.

Дедупликация в DOS

В нашей системе дедупликация реализована на двух разных уровнях: на уровне сегментов (блочная дедупликация); на уровне версий документов.

Каждый из этих подходов имеет свои плюсы и минусы. Дедупликация на уровне сегментов достигается за счёт совместного использования одних и тех же сегментов различными версиями документов. Каждый сегмент поддерживает внутри себя счётчик ссылок (reference counter) со стороны версий документов. В момент записи новой версии документа поток входящих данных разбивается на сегменты. Для каждого из них по индексу выполняется проверка существования. Если подобный сегмент встречается впервые, то выполняется его запись в бэкенд. Если же сегмент уже сохранялся ранее, то он просто получает новую ссылку со стороны только что созданной версии документа. Тем самым обеспечивается хранение каждого сегмента в единственном экземпляре.

Этот способ дедупликации работает постоянно и позволяет обнаруживать совпадения между разными версиями документов, которые могут отличаться по размеру, времени создания, типу данных и другим параметрам. Он вносит значительный вклад в оптимизацию дискового пространства и операций ввода-вывода. Популярные сегменты, постоянно использующиеся при обработках запроса на чтение, почти наверняка окажутся в кешах.

Однако есть и минусы: существенные накладные расходы на поддержание счётчиков ссылок. Например, одна ссылка потребует от 8 до 40 байт, поэтому для очень популярных сегментов с сотнями тысяч ссылок такие счётчики могут достигать размера в несколько десятков мегабайт. Индекс сегментов раздувается, тяжёлые сегменты становятся слишком большими для пересылки по сети, в результате начинает возрастать время отклика. Для решения этой проблемы приходится вводить сложную систему шардирования счётчика ссылок.

В результате хеширования содержимого сегмента создается идентификатор, обладающий свойством глобальной уникальности. Коллизии идентификаторов сегментов неизбежно приведут к повреждению данных, поэтому для хеширования используется криптографическая функция BLAKE3. Она вносит весомый вклад в потребление CPU при обработке запроса на запись. В случае, если клиент готов ради экономии CPU пожертвовать глобальной уникальностью (например, для короткоживущих данных в небольших инсталляциях хранилища), он может выбрать более быстрые хеш-функции, не обладающие свойством криптографической стойкости.

Второй способ дедупликации несёт значительно меньше накладных расходов, но требует более глубокого вовлечения клиента. Внутрь версии документа встроена очень компактная структура счётчика копий (copy counter). Клиенту DOS предоставляются методы для проверки наличия версии документа и модификации её счётчика копий. Если бизнес-логика клиента позволяет выявить ранее записанную версию, то её повторная запись сводится лишь к дешёвой операции инкремента счётчика копий. В почтовой системе именно так реализовано сохранение партов письма: клиент использует хеш от содержимого парта для построения идентификатора документа, проверяет наличие документа с таким идентификатором и при его наличии просто увеличивает счётчик копий нужной версии на единицу. Иммутабельность данных версии документа даёт гарантию того, что все накопленные инкременты счётчика копий версии относились к одним и тем же данным.

Дедупликация на уровне версий документов фактически обеспечивает ещё один (очень экономичный) вариант записи, при котором оптимизируется не только дисковое пространство и операции ввода-вывода, но ещё и CPU и RAM, а также снижается нагрузка на сеть за счёт облегчения запросов.

Рис. 3. Два уровня дедупликации данных в DOS.

Отказоустойчивость

Если сегмент существует в единственном экземпляре, то что произойдёт в случае его потери? Если диск, на котором хранится популярный сегмент выйдет из строя, будет ли это означать невозможность чтения всех ссылающихся на него версий?

Для борьбы с этой проблемой в хранилищах самых разных классов (компакт-диски, RAID-массивы, промышленные СХД) традиционно используются коды коррекции ошибок. Наибольшую популярность получили коды Рида-Соломона (Подробнее в статьях на Хабре: 1, 2, 3).

В DOS во время записи чанк разбивается на заданное количество сегментов равного размера (data segments, d). С помощью кодирования Рида-Соломона из сегментов данных генерируются избыточные сегменты (parity segments, p). При потере любые p из d + p сегментов могут быть восстановлены из имеющихся d с помощью обратной операции. Таким образом, отказоустойчивость приобретается путём дополнительных расходов дискового пространства. Конкретные значения параметров определяются на этапах внедрения и эксплуатации системы. Исходя из потребностей в отказоустойчивости инсталляции, пользователи могут выбирать между стоимостью хранения и возможностью восстановления (часто встречаются комбинации d + p = 2 + 1 и d + p = 5 + 2).

Для гарантии восстановления каждого чанка DOS размещает все входящие в его состав сегменты на бэкенды, которые находятся на независимых HDD. Таким образом, при выходе из строя одного диска не произойдет повреждение сразу нескольких сегментов одного чанка.

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

Конечно, коды Рида-Соломона могут спасти далеко не всегда. Поэтому в DOS имплементирован ещё один способ восстановления данных: при запросе на инкремент счётчика копий клиент может получить ответ о том, что версия была повреждена и что надо заново записать точно такую же. В этом случае вновь записанная версия восстановит старые поврежденные.

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

Конвейерная обработка данных

Во время обработки запроса на запись DOS буферизует первые несколько килобайт из входящего потока и отправляет их в библиотеку сигнатурного анализа файлов. Оттуда хранилище получает вычисленный MIME-тип данных. В контексте DOS все возможные MIME-типы подразделяются на группы форматов. Для каждой из групп в DOS организован отдельный конвейер преобразований (pipeline) и разные оптимизации.

Текстовые данные хорошо сжимаются. Для некоторых текстов с помощью алгоритмов ZSTD, Snappy, Brotli удаётся добиться более чем двукратного сжатия. Это существенная экономия дискового пространства и операций ввода-вывода, и она стоит дополнительных затрат CPU на компрессию и декомпрессию.

Для текстовых данных также можно повысить вероятность обнаружения дубликатов с помощью алгоритма content-defined chunking (CDC). Сущность алгоритма заключается в вычислении хеша Рабина в небольшом окне, скользящем по входящему потоку данных. В позициях, на которых вычисленный хеш принимает определённое значение, ставится граница между чанками. В результате поток разбивается на небольшие чанки разных размеров, однако при этом повышается вероятность обнаружения аналогичных чанков в других версиях с частично совпадающим содержимым.

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

Рис. 4. Различия в конвейерной обработке бинарных и текстовых данных в DOS.

Таким образом, конвейер для бинарных данных настроен на повышение пропускной способности сервера и на снижение времени отклика. А конвейер текстовых данных оптимизирует уровень потребления дискового пространства и IOPS ценой повышенного потребления CPU. Насколько же эффективны эти оптимизации?

Производительность конвейерной обработки данных

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

Параметры эксперимента

В систему сохраняется 10000 писем. Письма состоят только из текста и не включают в себя какие-либо бинарные объекты. Медианный размер письма около 500 Кб. При этом 70% писем имеют 50% совпадающих данных, остальные полностью уникальны. Полностью эквивалентные письма отсутствуют, поскольку они дедуплицировались бы на уровне счётчиков копий и сильно завысили бы итоговый результат. Настройки кодирования Рида-Соломона d + p = 2 + 1, избыточность данных составляет 50%.

Результат эксперимента

При прохождении через текстовый конвейер объем данных изменяется следующим образом: Входящий поток разделяется на чанки и компрессируется со средним коэффициентом сжатия 2.3. Затем кодирование Рида-Соломона увеличивает количество данных в 1.5 раза. Дедупликация cегментов (блочная дедупликация) снижает полученный с учётом избыточности объем данных в 1.17 раза.

Итоговое отношение записанных данных к хранимым данным составляет 2.3 * 1.17 / 1.5 = 1.79. При этом в нашей модели количество метаданных составляет 0.2% от количества данных, однако этот показатель очень вариативен и сильно зависит как от настроек конвейера, так и от характера и количества самих данных.

Удаление данных

В условиях совместного владения сегментами удаление версии документа становится нетривиальной операцией. Её нужно проводить очень аккуратно, чтобы, с одной стороны, не удалить данные, которые ещё кому-то нужны, а с другой не допустить утечек дискового пространства. Связи между всеми сущностями в DOS можно представить в виде большого ациклического ориентированного графа, в котором начальными вершинами являются документы, а конечными вершинами - сегменты. Также есть и промежуточный уровень версий документов. Для каждой из сущностей действуют свои правила удаления: Документ удаляется, если не содержит версий. Версия документа удаляется, если её счетчик копий равен нулю либо истекло время её жизни (TTL). Сегмент удаляется, если не имеет ссылок со стороны версий документов.

Клиент напрямую работает лишь с версиями документов; доступный клиенту метод удаления позволяет декрементировать счётчик копий у конкретной версии. Далее в действие приходят два асинхронных сборщика мусора (GC), один из которых проходит по индексу документов, а другой по индексу сегментов. GC документов удаляет версии с обнулённым счётчиком копий или истекшим TTL, собирает пустые документы и очищает счётчики ссылок сегментов от идентификаторов удаляемых версий. GC сегментов удаляет сегменты с пустыми счётчиками ссылок. Оба GC запускаются в фоновом режиме в периоды, свободные от пользовательской нагрузки.

Рис. 5. Иллюстрация работы сборщиков мусора (1 - граф связей в исходном состоянии; 2 - клиент декрементирует до нуля счётчик копий у одной из версий; 3 - GC документов удаляет версию и владеющий ей документ, GC сегментов удаляет сегмент без ссылок; 4 - граф связей в итоговом состоянии).

Заключение

Хранение больших объёмов электронной почты - крайне непростая и ресурсоёмкая задача. Однако производительность и экономическую эффективность почтовой системы можно значительно увеличить, если реализовать дедупликацию и компрессию электронных писем. Если вам близка эта тема, и вы тоже хотите создавать уникальные российские программные продукты, то приходите на работу в МойОфис. Прямо сейчас нашей команде требуется разработчик бэкенда откликайтесь, возможно, это именно вы.

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

Подробнее..
Категории: Nosql , Электронная почта , Хранение данных , Хранилища данных , Отказоустойчивость , Блог компании мойофис , Коды избыточности , Сжатие данных , Сборка мусора , Объектное хранилище , Дедупликация , Компрессия данных , Rocksdb , Целостность данных

Категории

Последние комментарии

  • Имя: Макс
    24.08.2022 | 11:28
    Я разраб в IT компании, работаю на арбитражную команду. Мы работаем с приламы и сайтами, при работе замечаются постоянные баны и лаги. Пацаны посоветовали сервис по анализу исходного кода,https://app Подробнее..
  • Имя: 9055410337
    20.08.2022 | 17:41
    поможем пишите в телеграм Подробнее..
  • Имя: sabbat
    17.08.2022 | 20:42
    Охренеть.. это просто шикарная статья, феноменально круто. Большое спасибо за разбор! Надеюсь как-нибудь с тобой связаться для обсуждений чего-либо) Подробнее..
  • Имя: Мария
    09.08.2022 | 14:44
    Добрый день. Если обладаете такой информацией, то подскажите, пожалуйста, где можно найти много-много материала по Yggdrasil и его уязвимостях для написания диплома? Благодарю. Подробнее..
© 2006-2024, personeltest.ru