Краткий обзор статьи https://www.researchgate.net/publication/6715625_Fast_and_Efficient_Compression_of_Floating-Point_Data
В масштабных научных вычислениях используются большие массивы чисел с плавающей точкой, которые хранятся в файловой системе. Чтобы организовать вычисления наилучшим образом, с максимальным использованием мощности процессоров, необходимо учитывать многие факторы, в том числе пропускную способность файловой системы. Если скорость чтения/записи данных ниже скорости, с которой эти данные генерируются, то процессоры будут простаивать. Один из подходов к решению этой проблемы - предварительное сжатие данных, и запись уже сжатых данных на диск. Собственно, один из алгоритмов сжатия предложен авторами статьи "Fast and Efficient Compression of Floating-Point Data"
Предложенный алгоритм обладает следующими свойствами:
- Сжатие происходит "на лету", без записи сырых данных на диск
- Сжатие происходит без потерь
- Алгоритм достигает сравнимых с лучшими (на момент публикации статьи - 2006 год) показателей скорости сжатия и коэффициента сжатия
- Алгоритм работает с форматами чисел разной точности
В основе алгоритма лежит идея энтропийного кодирования - подход, при котором множество символов разбивается на корзины, попадание в которые нового элемента приблизительно равновероятно.
Алгоритм работает с упорядоченными неким образом данными, в качестве примера авторы приводят трехмерный массив. Алгоритм проходит по массиву данных один раз и использует ранее встреченные значения для предсказания последующих. Авторы утверждают, что неважно, какой предсказатель используется, поскольку главное нововведение их алгоритма заключается в улучшении процесса энтропийного кодирования. В процессе работы алгоритма поддерживается интервал [l, l + r)
, в котором лежит очередной закодированный символ. Алгоритм устроен таким образом, что и кодер, и декодер могут определить, в какой момент интервал был перестроен, и на основе этого прочитать очередной символ.
В общих чертах алгоритм устроен следующим образом:
- Алгоритм читает очередное число и предсказывает его значение. Настоящее значение передается в предсказатель. Вызывается функция
encode(real, pred)
от настоящего и предсказанного значений. - В функции
encode()
значенияreal
иpred
преобразуются в беззнаковые целые числаr
иp
(их битовое представление в памяти) и вычисляется разностьd = r - p
и позиция наиболее значимого бита разностиk = MostSignificantBit(d)
. - Затем разность
d
кодируется следующим образом: сначала при помощи энтропийного кодирования кодируется числоg = s(k + 1)
, гдеs = sign(d)
:encode(zero + s(k + 1), model)
(структураmodel
хранит информацию о распределении, см 3.1). Используется предположение о неравномерном распределенииg
. Оставшиесяk
бит разности кодируются 'as is':encode(1 - (1 << k), k)
(см 3.2) 3.1. При выполнении энтропийного кодированияencode(unsigned, Model*)
периодически (авторы предлагают ра з в 1000 символов) обновляетсяmodel
, чтобы получить информацию о распределенииg
и каждый раз обновляется и затем нормализуется интервал[l, l + r)
3.2. При выполнении кодированияencode(unsigned, unsigned)
обновляется и затем нормализуется интервал[l, l + r)
- Интервал нормализуется таким образом, чтобы исключить переносы при сложении
l + r
. На этом этапе производится вывод сжатых данных.
Важно отметить, что интервал [l, l + r)
используется для вывода и числа s(k + 1)
, и остатка. Авторы утверждают, что именно это улучшение позволило достичь лучших показателей скорости и коэффициента сжатия.
В 5 секции авторы приводят результаты сравнительных запусков своего алгоритма и ранее известных алгоритмов сжатия на нескольких датасетах. Как видно из таблицы (Степа, вставь, пожалуйста картинки из статьи), новый алгоритм иногда демонстрирует наилучший коэффициент сжатия, а в других случаях - коэффициент сравнимый с наилучшими, но заметно превосходит эти алгоритмы в скорости. Новый алгоритм не является самым быстрым из рассмотренных, но заметно превосходит самый быстрый по коэффициенту сжатия. Алгоритм можно назвать компромиссным между скоростью и коэффициентом сжатия.
Подводя итог, можно сделать вывод, что автором удалось сконструировать алгоритм с заявленными ими свойствами. Сама статья получилась довольно короткой, но за счет этой краткости, она теряет в подробности изложения. Например, в статье не описан алгоритм расшифровки, видимо, авторами предполагается, что расшифровка очевидным образом получается из шифрования инверсией операций. Кроме этого, делается довольно сильное допущения насчет неравномерного распределения разности между реальным и предсказанным значениями, то есть эта разность должна быть предсказуема. В статье также нет математических выкладок и вообще доказательств эффективности алгоритма, кроме приведенного набора тестов. Судя, по всему, авторы и не преследовали цели математически обосновать свой алгоритм, а также предполагали, что читатель знаком с принципами энтропийного кодирования. Тем не менее, статья получила определенную известность, а предложенный алгоритм был имплементирован в пакете fpzip.