Сжатие в больших данных: типы и техники

\

Введение

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

\

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

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

\ Существует множество причин для сжатия данных. Наиболее распространенная и интуитивная причина - экономия места для хранения. Другие причины являются результатом уменьшения данных. Преимущества работы с меньшими данными включают:

1. Более быстрое время передачи данных: Сжатые данные меньше по размеру и требуют меньше времени для передачи от источника к месту назначения.
2. Снижение потребления пропускной способности: Эта причина тесно связана с преимуществом более быстрой передачи данных. Сжатые данные используют меньше пропускной способности сети, тем самым увеличивая пропускную способность и уменьшая задержку.
3. Улучшенная производительность для цифровых систем, которые сильно зависят от данных: Это очевидно в системах, которые полагаются на обработку данных. Эти системы используют сжатие для улучшения производительности систем путем уменьшения объема данных, которые необходимо обработать. Обратите внимание, что это может быть специфично для системы и будет зависеть от использования соответствующей техники сжатия. Техники сжатия будут обсуждаться позже в этой статье.
4. Экономическая эффективность: Облачные сервисы взимают плату за хранение данных. Используя меньше хранилища, вводится экономия затрат, особенно в системах больших данных.

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

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

\

Типы сжатия

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

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

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

\ С другой стороны, сжатие без потерь обратимо, что означает, что при сжатии все данные сохраняются и полностью восстанавливаются во время распаковки. Это подразумевает, что сжатие без потерь подходит для текстовых файлов, и в мире хранилищ данных и лейкхаусов это будет единственный соответствующий тип для использования. Некоторые форматы аудиофайлов (FLAC и ALAC) и графических файлов (GIF, PNG и т.д.) хорошо работают с этим типом сжатия.

Выбор метода

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

Техники сжатия

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

Техники сжатия без потерь

Три распространенные техники без потерь - это кодирование длин серий (RLE), кодирование Хаффмана и техника Лемпеля-Зива-Велча.

\ Кодирование длин серий: RLE основано на кодировании данных таким образом, что оно заменяет последовательности повторяющихся данных одним фрагментом данных и подсчетом этого фрагмента данных. Оно эффективно для длинных серий повторяющихся данных. Кроме того, наборы данных, которые имеют измерения (поля), отсортированные от низкого уровня до высокого уровня кардинальности, выигрывают от RLE.

\ Например, возьмем простую строку вроде AAAAABBCDDD. RLE сжимает данные, чтобы они стали A(5)B(2)C(1)D(3). Чтобы быть более практичным, возьмите таблицу на изображении ниже.

\ Рисунок 1 - до RLE. Важно отметить, что уровень кардинальности увеличивается по полям слева направо

Рисунок 2 - После RLE

Поскольку RLE зависит от серий повторяющихся полей, и во втором примере кардинальности и порядка сортировки данных, запись Mouse в столбце элементов не может быть сжата до просто Mouse (3), потому что предыдущий столбец разделяет все значения на IT, Mouse и HR, Mouse. Определенные форматы файлов совместимы с RLE, такие как форматы растровых файлов, как TIFF, BMP и т.д. Файлы Parquet также поддерживают RLE, что делает его очень полезным в современных лейкхаусах данных, использующих объектное хранилище, такое как S3 или GCS.

\ Кодирование Хаффмана: Оно основано на статистическом моделировании, которое назначает коды переменной длины значениям в исходных данных на основе частоты их появления в исходных данных. Представление этого моделирования можно назвать деревом Хаффмана, которое похоже на двоичное дерево. Затем это дерево используется для создания кода Хаффмана для каждого значения в исходных данных. Алгоритм приоритизирует кодирование наиболее частых значений в наименьшем возможном количестве битов.

\ Давайте возьмем те же данные, использованные в примере RLE AAAAABBCDDD. Соответствующее дерево Хаффмана выглядит так.

\ Дерево Хаффмана

Из дерева мы видим, что буква A представлена 0, аналогично D представлена 10. По сравнению с буквами B: 111 и C:110, мы наблюдаем, что A и D представлены меньшим количеством битов. Это потому, что они имеют более высокую частоту; следовательно, алгоритм Хаффмана по дизайну представляет их меньшим количеством битов. Результирующие сжатые данные становятся 00000111111110101010.

\ Кодирование Хаффмана использует правило префикса, которое гласит, что код, представляющий символ, не должен присутствовать в префиксе любого другого кода. Например, допустимый код Хаффмана не может иметь буквы c и d, представленные с использованием C: 00 и D: 000, потому что представление C является префиксом D.

\ Чтобы увидеть это в действии, в Computer Science Field Guide есть Генератор деревьев Хаффмана, с которым вы можете поиграть.

\ Кодирование Лемпеля-Зива-Велча: Оно было создано Абрахамом Лемпелем, Якобом Зивом и Терри Велчем в 1984 году и названо в честь создателей, очевидно 😅. Подобно RLE и кодированию Хаффмана, LZW хорошо работает с данными, которые содержат много повторяющихся данных. Алгоритм LZW основан на словаре и создает словарь, содержащий пары ключ-значение часто встречающихся паттернов в исходных данных. Такой словарь также можно назвать таблицей кодов. Используя иллюстрацию для объяснения того, как работает эта техника, возьмем наши исходные данные, представленные ABBABABABA. При прохождении через алгоритм с использованием конфигурации A-Z в качестве возможных значений, результирующая таблица кодов выглядит следующим образом:

\ Таблица кодов LZW

Из приведенной выше таблицы кодов есть пара ключ-значение для всех букв A-Z и пары ключ-значение для паттернов, таких как AB, BB, BA и ABA. Имея более короткое представление этих паттернов, алгоритм LZW может сжимать исходные данные, кодируя их в меньшее количество битов. Следовательно, используя таблицу кодов, сгенерированную из этого ввода, сжатая версия будет 0 1 1 26 29 28. Важно заметить пробелы в сжатых данных. Можно думать о них как о конце символа, чтобы декодер не интерпретировал 1,0 как 10, поскольку они означают разные вещи.

\ LZW обычно универсален и широко используется сегодня. Он интегрирован во многие операционные системы на базе Unix/Linux за командой оболочки compress. Кроме того, распространенные форматы файлов, совместимые с LZW, - это GIF, TIFF и PDF. Другие применения сжатия LZW можно увидеть в области обработки естественного языка, как обсуждается в этой статье о токенизации в NLP.

\ RLE, кодирование Хаффмана и кодирование LZW - это только распространенные примеры. Техники сжатия без потерь выходят за рамки этих трех (3), описанных выше. Другие техники включают DEFLATE, которая использует комбинацию кодирования Хаффмана и LZW - в частности, LZ77.

Техники сжатия с потерями

В этом разделе мы рассмотрим два типа сжатия с потерями. Напомним, что сжатие с потерями вводит потерю в исходные данные, что означает, что не все данные сохраняются.

\ Дискретное косинусное преобразование (DCT): Этот метод сжатия используется в основном в аудио-, графических и видеофайлах и также обычно называется блочным сжатием. Он использует математическую функцию - косинусную функцию, как следует из названия - для преобразования блоков исходных данных в частоты. Блоки данных обычно представляют собой матрицу 8x8, 4x4 и так далее, в таком порядке величины.

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

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

\ DCT широко используется в различных областях сегодня, не только в сжатии, но и в обработке сигналов. Распространенные форматы файлов, совместимые с DCT, - это JPEG (изображения), MP3 (аудио) и MPEG (видео). Кроме того, DCT может достигать высоких коэффициентов сжатия, что делает его подходящим для цифровых систем с большим количеством изображений, таких как веб-страницы в Интернете.

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

\ Примеры фракталов

Фрактальное сжатие было введено Майклом Барнсли в 1980-х годах. Общая идея с использованием изображения заключается в том, что если изображение содержит несколько частей, которые выглядят одинаково, зачем хранить их дважды? Для этого фрактальное сжатие делает следующее:

• Разделяет изображение на неперекрывающиеся блоки, известные как блоки диапазона. Это могут быть блоки диапазона 8x8, 16x16 пикселей и т.д.
• Оно сканирует изображение на предмет самоповторяющихся паттернов (фрактальных паттернов). Используя блоки диапазона, алгоритм находит большие разделы изображения, которые похожи на эти блоки диапазона. Эти большие разделы называются доменными блоками.
• Затем к доменному блоку применяется функция преобразования для аппроксимации блоков диапазона. Эти функции преобразования являются математическими функциями, такими как масштабирование, перемещение, поворот и т.д. Их также можно назвать преобразованиями. Эти преобразования называются фрактальными кодами в отношении фрактального сжатия.
• Затем данные кодируются в эти функции преобразования. Вместо хранения попиксельных данных хранятся преобразования. Эти преобразования - это правила, которые описывают, как восстановить изображение из доменных блоков.

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

\ Существуют другие техники сжатия с потерями, такие как дискретное вейвлет-преобразование, квантование. Эти техники обычно используются в изображениях, аудио- и видеофайлах и подходят для определенных типов или форматов файлов - JPEG, MP3 - для каждого типа файлов.

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

Коротко

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

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

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

Дополнительные ресурсы

Видео: Основы озера данных - кодирование RLE с Parquet на практике

Статья: Обзор техник сжатия данных

Статья: Техники сжатия без потерь

Краткое введение в сжатие данных Дэвида Саломона

Статья: Исследование различных техник сжатия данных

Блог: Сжатие в открытых форматах файлов

Статья: Открытые форматы файлов

Статья: Сжатие в базах данных

Сжатие с потерями для геномных данных (РНК)

\