Дан поток чисел типа double, в котором соседние элементы различаются мантиссой не более чем на байт. Или могут различаться больше, но очень редко. Примером такого потока могут быть данные котировок с биржи. И стоит задача — как можно лучше сжать такой поток. У меня появилась идея — в double храним только опорные элементы (первый и те, которые отличаются от соседних больше чем на байт), а всю остальную информацию записываем в виде разницы. Соответственно, восстановление заключается в последовательном прибавлении разницы к опорным элементам.
Вопрос: по каким ключевым словам можно найти больше информации? Перед неализацией хочу убедиться, что такой алгоритм не будет проигрыватьв gzip.
Здравствуйте, cppguard, Вы писали:
C>Дан поток чисел типа double, в котором соседние элементы различаются мантиссой не более чем на байт. Или могут различаться больше, но очень редко. Примером такого потока могут быть данные котировок с биржи. И стоит задача — как можно лучше сжать такой поток.
Сейчас есть простые алгоритмы, основанные на XOR-е бинарных представлений двух соседних значений и последующим сжатием результата. Гуглить по float sequence XOR compression. Есть более сложные алгоритмы на других принципах, в том числе с потерей точности. Для них нужно гуглить без слова XOR. Выбирай на вкус )
Здравствуйте, cppguard, Вы писали:
C>в double храним только опорные элементы (первый и те, которые отличаются от соседних больше чем на байт), а всю остальную информацию записываем в виде разницы. Соответственно, восстановление заключается в последовательном прибавлении разницы к опорным элементам.
Есть еще двухбайтовый флоат. Его точности может хватить для разницы с опорным элементом.
Здравствуйте, cppguard, Вы писали:
C>Дан поток чисел типа double, в котором соседние элементы различаются мантиссой не более чем на байт. Или могут различаться больше, но очень редко. Примером такого потока могут быть данные котировок с биржи. И стоит задача — как можно лучше сжать такой поток. У меня появилась идея — в double храним только опорные элементы (первый и те, которые отличаются от соседних больше чем на байт), а всю остальную информацию записываем в виде разницы. Соответственно, восстановление заключается в последовательном прибавлении разницы к опорным элементам.
Можно сжимать мантиссы и экспоненты раздельно. И, конечно, сжимать дельты.
Здравствуйте, cppguard, Вы писали:
C>Дан поток чисел типа double, в котором соседние элементы различаются мантиссой не более чем на байт. Или могут различаться больше, но очень редко. Примером такого потока могут быть данные котировок с биржи. И стоит задача — как можно лучше сжать такой поток. У меня появилась идея...
C>Вопрос: по каким ключевым словам можно найти больше информации? Перед неализацией хочу убедиться, что такой алгоритм не будет проигрыватьв gzip.
Честно говоря не знаю. Современный интернет -- помойка. Ищите и обращете. Например, compression.ru в разделе "статьи" и далее по ссылкам.
gzip и статистическое кодирование -- это разные подходы. Сравнивать в лоб бесмысленно.
Одно часто дополняет другое (внутри того же gzip, но там так кодируются не сами данные, а ссылки на повторяющиеся данные).
Есть смысл попробовать комбинацию обоих методов (но,конечно, не в виде готового gzip -- так не сработает).
Дельта-кодирование -- это лишь первый шаг. Нет смысла кодировать специальным образом только отдельные записи,
проще всегда хранить разности. Но сами разности, разной величины, встречаются с разной частотой. И их (разности)
тоже можно закодировать по-разному: MTF, код Голомба (Райса), арифметическое кодирование наконец (range coder им. Д. Субботина).
Идея в том, чтоб представить разность меньшим количеством битов, переменным и не обязательно целым вообще.
Дальше больше. Не обязательно кодировать разность между предыдущим и следующим элементом. В общем случае
можно кодировать разность между предсказанным и фактическим значением. Где значения пресказываются (экстраполируются)
на основе серии предыдущих значений (или даже серий разностей). В простейшем случае "предсказателем" может быть фильтр
низких частот (попросту среднее последних нескольких значений).
Это всё статистические методы. Все же виды LZ (читай ZIP) они про поиск последовательностей повторяющихся значений
(конкретно байтов, но не обязательно). Таких последовательностей в в биржевых данных, или в результах измерений,
может и не оказаться. Все виды LZ хорошо работают для сжатия текстов, например. Где есть повторяющиеся слова, фразы
или хотя бы слоги.
Для биржевых котировок или физических данных я бы больше думал, как описано выше, о разностном кодировании
между экстраполированнойи фактической величиной. Вопрос как сделать прогноз следующей величины с минимальной
ошибкой (эта часть работает и в кодере, и в декодере). Кстати примером такого алгоритма для записи звука является
ADPCM -- может имеет смысл взять на вооружение.
Здравствуйте, cppguard, Вы писали:
C>Дан поток чисел типа double, в котором соседние элементы различаются мантиссой не более чем на байт. Или могут различаться больше, но очень редко. Примером такого потока могут быть данные котировок с биржи. И стоит задача — как можно лучше сжать такой поток. У меня появилась идея — в double храним только опорные элементы (первый и те, которые отличаются от соседних больше чем на байт), а всю остальную информацию записываем в виде разницы. Соответственно, восстановление заключается в последовательном прибавлении разницы к опорным элементам.
C>Вопрос: по каким ключевым словам можно найти больше информации? Перед неализацией хочу убедиться, что такой алгоритм не будет проигрыватьв gzip.
Какая задача?
Точно нужно ли сжатие без потерь или допускается с потерями?
Для всяких измерений можно посмотреть к примеру Swinging Door .
Здравствуйте, swame, Вы писали:
S>Какая задача? S>Точно нужно ли сжатие без потерь или допускается с потерями? S>Для всяких измерений можно посмотреть к примеру Swinging Door .
Задача — сжимать историю котировок криптовалют, 100байт/с * 300 валютных пар (и это число растёт), и всё это нужно хранить несколько лет и ещё передавать по сети. Так что с потерями нельзя, а алгоритм интересный, спасибо.
C>Дан поток чисел типа double, в котором соседние элементы различаются мантиссой не более чем на байт. Или могут различаться больше, но очень редко. Примером такого потока могут быть данные котировок с биржи.
Именно для данных биржы стоит рассмотреть использовать шаг цены и диапазон цены на сессию.
Здравствуйте, AtCrossroads, Вы писали:
AC>Ну, типа, хранить целое кол-во шагов цены AC>1. от минимальной/максимальной на сессию; AC>2. от предыдущего тика или чего-то.
Идея интересная, но её тяжело обобщить. Допустим, храним мы TSLA, и тут сплит произошёл. Или биток упал, у шаг цены изменился с 1e-10 на 1e-11. Вобщем, работать может и будет, но для отдельно взятого тикера, а мне нужен универсальный алгоритм.
Здравствуйте, cppguard, Вы писали:
C>Дан поток чисел типа double, в котором соседние элементы различаются мантиссой не более чем на байт. Или могут различаться больше, но очень редко. Примером такого потока могут быть данные котировок с биржи. И стоит задача — как можно лучше сжать такой поток. У меня появилась идея — в double храним только опорные элементы (первый и те, которые отличаются от соседних больше чем на байт), а всю остальную информацию записываем в виде разницы. Соответственно, восстановление заключается в последовательном прибавлении разницы к опорным элементам.
C>Вопрос: по каким ключевым словам можно найти больше информации? Перед неализацией хочу убедиться, что такой алгоритм не будет проигрыватьв gzip.
Решал похожую задачу, но для координат, самый эффективней способ оказался найти минимальный шаг, метр, миллиметр, нанометр и т.д, что бы можно было посадить на целочисленную сетку, а дальше уже богатый выбор различных алгоритмов разностного кодирования.
В случае, когда не было возможности выбрать сетку то решали через нахождение целочисленной дроби для числа double, условно говоря 1.333333333 это 4/3
