Привет, Хабр!

Сегодня мы рассмотрим хорошие библиотеки для реализации алгоритмов сжатия данных на ЯП Rust. Сжатие данных позволяет уменьшать объемы данных без потери качества или с минимальными потерями. Различают две основные категории методов сжатия: с потерями и без потерь.

Алгоритмы сжатия без потерь

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

• Текстовых данных и коде;

• Архивациях, когда нужно сжать множество файлов без потери информации;

• Некоторых форматах изображений, таких как PNG, где важно сохранение деталей и прозрачности.

Хорошие примеры таких алгоритмов - Алгоритм Хаффмана и Алгоритм Лемпеля-Зива-Велча.

Алгоритмы сжатия с потерями

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

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

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

Один из примеров таких алгоритмов - DCT.

Так вот, кратко поговорили про основы, а теперь перейдем к библиотекам. И первая библиотека - zstd.

zstd

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

Основные функции:

encoder и decoder классы позволяют сжимать и распаковывать данные соответственно. encoder принимает данные для сжатия и выводит результат, тогда как decoder читает сжатые данные и восстанавливает их.

stream: модуль для работы со стримами данных, который включает в себя функции copy_encode и copy_decode для работы со стандартными потоками ввода-вывода Rust.

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

encode_all и decode_all: функции для сжатия и декомпрессии полных данных в памяти.

compression_level_range: функция, которая возвращает допустимый диапазон уровней сжатия.

Библиотека async-compression интегрирует zstd с асинхронными потоками Rust, что позволяет использовать сжатие и декомпрессию данных в асинхронных приложениях.

DEFAULT_COMPRESSION_LEVEL: константа, определяющая уровень сжатия по умолчанию.

Примеры использования

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

use std::io;
use zstd::stream::{read::Decoder, write::Encoder};

// сжатие данных
fn compress(data: &[u8], level: i32) -> io::Result<Vec<u8>> {
    let mut encoder = Encoder::new(Vec::new(), level)?;
    io::copy(&mut &data[..], &mut encoder)?;
    let compressed = encoder.finish()?;
    Ok(compressed)
}

// декомпрессия данных
fn decompress(data: &[u8]) -> io::Result<Vec<u8>> {
    let mut decoder = Decoder::new(&data[..])?;
    let mut decompressed = Vec::new();
    io::copy(&mut decoder, &mut decompressed)?;
    Ok(decompressed)
}

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

use async_compression::stream::{ZstdDecoder, ZstdEncoder};
use tokio::io::{self, AsyncReadExt, AsyncWriteExt};

async fn compress_async(input: &[u8], level: i32) -> io::Result<Vec<u8>> {
    let reader = io::Cursor::new(input);
    let stream = ZstdEncoder::with_quality(reader, level);
    let mut writer = Vec::new();
    let mut stream = io::BufReader::new(stream);

    while let Some(bytes) = stream.fill_buf().await? {
        writer.write_all(bytes)?;
        stream.consume(bytes.len());
    }
    Ok(writer)
}

async fn decompress_async(input: &[u8]) -> io::Result<Vec<u8>> {
    let reader = io::Cursor::new(input);
    let stream = ZstdDecoder::new(reader);
    let mut writer = Vec::new();
    let mut stream = io::BufReader::new(stream);

    while let Some(bytes) = stream.fill_buf().await? {
        writer.write_all(bytes)?;
        stream.consume(bytes.len());
    }
    Ok(writer)
}

Можно настраивать уровень сжатия с помощью передачи параметра уровня сжатия в конструктор Encoder. Уровни могут варьироваться от 1 (самое быстрое сжатие, наименьшая степень сжатия) до 22 (самая высокая степень сжатия, самое медленное сжатие).

flate2

flate2 может быть настроена для работы с различными бэкендами, включая miniz_oxide и zlib-ng.

Основные функции:

1. Модули для работы с потоками данных:

   • read: модуль для работы с потоками данных, которые можно читать.

   • write: предназначен для записи и сжатия данных. Включает классы, которые оборачивают стандартные типы вывода и позволяют сжимать данные при записи.

   • bufread: содержит функции для работы с буферизированными чтениями

2. Типы для сжатия и декомпрессии:

   • GzEncoder и GzDecoder: классы для работы с форматом gzip. GzEncoder используется для сжатия данных, GzDecoder — для их декомпрессии.

   • DeflateEncoder и DeflateDecoder: предназначены для работы с форматом DEFLATE.

   • ZlibEncoder и ZlibDecoder: используются для сжатия и декомпрессии в формате zlib.

3. Функции и утилиты:

   • compress и decompress: функции для сжатия и декомпрессии блоков данных. Можно очень быстро сжимать или распаковывать данные без надобности управлять потоками.

   • Compression: структура, которая предоставляет различные уровни сжатия, от быстрого и менее эффективного до медленного, но более эффективного.

Примеры использования

Сжатие данных с использованием DEFLATE

use flate2::write::DeflateEncoder;
use flate2::Compression;
use std::io::prelude::*;

let data = b"Пример данных для сжатия";
let mut encoder = DeflateEncoder::new(Vec::new(), Compression::default());
encoder.write_all(data).unwrap();
let compressed_data = encoder.finish().unwrap();

Декомпрессия данных DEFLATE

use flate2::read::DeflateDecoder;
use std::io::prelude::*;

let mut decoder = DeflateDecoder::new(&compressed_data[..]);
let mut decompressed_data = Vec::new();
decoder.read_to_end(&mut decompressed_data).unwrap();

Юзаем gzip для сжатия

use flate2::write::GzEncoder;
use flate2::Compression;
use std::io::prelude::*;

let mut encoder = GzEncoder::new(Vec::new(), Compression::fast());
encoder.write_all(b"Пример данных для сжатия с использованием gzip").unwrap();
let gzip_compressed_data = encoder.finish().unwrap();

Декомпрессия данных gzip

use flate2::read::GzDecoder;
use std::io::{self, Read};

let mut decoder = GzDecoder::new(&gzip_compressed_data[..]);
let mut decompressed_data = String::new();
decoder.read_to_string(&mut decompressed_data).unwrap();

Можно выбрать бэкенд сжатия в зависимости от потребностей:

• miniz_oxide: полностью на Rust, хорошо подходит для сценариев, требующих совместимости и безопасности памяти.

• zlib-ng: высокопроизводительная либа, которая может использоваться для супер производительности:

flate2 = { version = "1.0.17", features = ["zlib-ng"] }

brotli

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

Основные функции библиотеки:

CompressorReader и CompressorWriter: обертки для потокового сжатия данных. CompressorReader обрабатывает данные на чтение, а CompressorWriter — на запись.

Decompressor: для декомпрессии данных, поддерживает как потоковое чтение, так и потоковую запись.

encode и decode: функции для сжатия и декомпрессии блоков данных в памяти.

BrotliEncoderParams: структура для настройки параметров сжатия, включая уровень сжатия и размер окна.

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

BrotliCompress и BrotliDecompress: функции для сжатия и декомпрессии данных, использующие потоки io::Read и io::Write.

Примеры использования

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

use brotli::CompressorWriter;
use std::io::Write;

let mut output = Vec::new();
{
    let mut writer = CompressorWriter::new(&mut output, 4096, 11, 22);
    writer.write_all(b"Пример данных для сжатия").unwrap();
}

Декомпрессия данных

use brotli::Decompressor;
use std::io::Read;

let mut decompressor = Decompressor::new(&output[..]);
let mut result = String::new();
decompressor.read_to_string(&mut result).unwrap();

snap

Snap не стремится к максимальному сжатию, а ориентирован больше на скорость.

Основные функции:

FrameEncoder и FrameDecoder - потоковое сжатие и декомпрессия соответственно.

compress и decompress для сжатия и декомпрессии данных соответственно.

compress_into и decompress_into позволяют сжимать и распаковывать данные непосредственно в пользовательский буфер.

compress_raw и decompress_raw предназначены для работы с данными без использования формата "framed"

compress_raw_into и decompress_raw_into также позволяют работать непосредственно с буферами, минимизируя некоторые расходы

Примеры использования

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

extern crate snap;

use snap::{write::FrameEncoder, read::FrameDecoder};
use std::io::{Cursor, Read, Write};

let data = b"Example data that needs to be compressed";
let mut encoder = FrameEncoder::new(Vec::new());
encoder.write_all(data).unwrap();
let compressed = encoder.into_inner().unwrap();

Декомпрессия данных

let compressed_data = compressed;
let mut decoder = FrameDecoder::new(Cursor::new(compressed_data));
let mut decompressed = Vec::new();
decoder.read_to_end(&mut decompressed).unwrap();

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

lz4-compression

lz4-compression использует алгоритм LZ4. Алгоритм отличается тем, что предлагает очень высокую скорость сжатия, достигающую более 500 МБ/с на одном ядре и декомпрессии до нескольких ГБ/с

Примеры использования

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

use lz4::EncoderBuilder;
use std::io::Write;

let mut encoder = EncoderBuilder::new().level(4).build(Vec::new()).unwrap();
encoder.write_all(b"Пример данных для сжатия").unwrap();
let (compressed, result) = encoder.finish();
result.unwrap();

Декомпрессия данных

use lz4::Decoder;
use std::io::Read;

let mut decoder = Decoder::new(&compressed[..]).unwrap();
let mut decompressed = Vec::new();
decoder.read_to_end(&mut decompressed).unwrap();

Стриминговое сжатие и декомпрессия

use lz4::EncoderBuilder;
use lz4::Decoder;
use std::io::{self, Read, Write, BufReader, BufWriter};

// подготовка стримингового сжатия
let input_stream = io::Cursor::new(b"Data stream that needs to be compressed in real-time");
let output_stream = Vec::new();
let mut encoder = EncoderBuilder::new().level(4).build(output_stream).unwrap();
let mut buffered_encoder = BufWriter::new(encoder);

// сжатие данных в стриме
io::copy(&mut BufReader::new(input_stream), &mut buffered_encoder).unwrap();
let (compressed_stream, result) = buffered_encoder.into_inner().unwrap().finish();
result.unwrap();

// подготовка стриминговой декомпрессии
let input_compressed_stream = io::Cursor::new(compressed_stream);
let mut decoder = Decoder::new(input_compressed_stream).unwrap();
let mut decompressed_stream = Vec::new();

// декомпрессия данных из стрима
decoder.read_to_end(&mut decompressed_stream).unwrap();

Существуют различные уровни сжатия, от базового быстрого сжатия до высокого сжатия, которое требует больше времени на CPU, но обеспечивает лучшее сжатие. Например, стандартный уровень сжатия LZ4 может достигать скорости сжатия до 780 МБ/с и скорости декомпрессии до 4970 МБ/с, в то время как LZ4_HC на максимальном уровне увеличивает качество сжатия, снижая скорость сжатия до 41 МБ/с, при этом скорость декомпрессии остаётся сопоставимой.

Напоследок попробуем реализовать сжатие на чистом RUST

Реализуем простой алгоритм сжатия Run-Length Encoding.

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

use std::char;
use std::fmt::Write;

fn rle_encode(input: &str) -> String {
    let mut encoded = String::new();
    let mut chars = input.chars();
    let mut current_char = chars.next();

    while let Some(c) = current_char {
        let mut count = 1;

        while let Some(next) = chars.next() {
            if next == c {
                count += 1;
            } else {
                break;
            }
        }

        // записываем символ и его количество в результат
        write!(&mut encoded, "{}{}", c, count).unwrap();
        current_char = chars.next();
    }

    encoded
}

/// юзаем
fn main() {
    let input_string = "aaaabbbccddddde";
    let compressed = rle_encode(&input_string);
    println!("Original: {}", input_string);
    println!("Compressed: {}", compressed);
}

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

write!: макрос используется для записи символа и его количества в строку encoded.

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

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

А какие библиотеки для сжатия данных в Rust знаете вы? Делитесь в комментариях!

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