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

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

Место для хранения карты ограничено (обычно максимум 8 КБ, если вы не платите глупые цены за очень смарт-карты), поэтому мне нужно максимально сжать данные.

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

  • Дата/время - в формате yyMMddhhmmssfff
  • Серийный номер устройства - 17 цифр
  • Сумма - в пенни, максимум 999,99 фунтов стерлингов, поэтому пять цифр.

Представление этого в виде строки цифр дает 37 цифр на транзакцию.

Я пытался использовать алгоритмы в System.IO.Compression (следуя коду в этой записи в блоге и сопутствующему репозиторию GitHub, не включенному сюда, поскольку это стандартное использование классов).

Это дало довольно впечатляющие результаты: сокращение примерно на 72% при использовании оптимального алгоритма Gzip.

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

  • год - здесь не так много ограничений
  • месяц - может быть только 1-12
  • день - может быть только 1-31
  • час - может быть только 0-23
  • минуты и секунды - может быть только 0-59
  • миллисекунды - без ограничений

Любой комментарий о том, помогут ли эти ограничения помочь мне улучшить это сжатие. Спасибо

См. stackoverflow.com/questions/283299/…

Chronicle 25.01.2023 20:08

Почему вы используете двузначные годы? Разве вы не помните все вещи Y2K? Или все ваши сделки относятся к 20 веку? Давно

Robot Head 25.01.2023 20:15

Обычно вам действительно требуется БОЛЬШЕ места для хранения при сжатии небольших строк, и я, безусловно, считаю 37 цифр маленькой строкой. Вы действительно уверены, что получаете что-то от сжатия? В моих быстрых тестах как gzip, так и LZ4 я вижу значительное увеличение (~ 25%) используемых байтов, а не уменьшение

David L 25.01.2023 20:20

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

David L 25.01.2023 20:27

Рассматривали ли вы возможность использования битов для представления частей? т.е. месяц можно закодировать 3 битами, день 4, год - 1 байтом и т.д.?

Guru Stron 25.01.2023 21:21

Ответ на ваш вопрос - да. Например, если вы знаете самую раннюю дату/время, вы можете использовать смещение от нее. С 15 цифрами с точностью до 1/1000 секунды вы можете покрыть 31 688 лет — при условии, что вы можете сократить этот диапазон до 1000 лет, вы можете сохранить две цифры, а 100 лет — три цифры, но, поскольку вы также знаете, что все поля просто 0-9, вы можете преобразовать 37-значное число в двоичное и использовать 16 байт.

NetMage 25.01.2023 21:38

В качестве альтернативы вы можете отобразить каждый компонент в битовое поле и также получить 17 байтов.

NetMage 25.01.2023 21:50

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

Avrohom Yisroel 26.01.2023 00:13

@RobotHead Это новый проект, поэтому самая ранняя дата транзакции будет при каждом запуске. 2 цифры для года дают нам почти 77 лет, к тому времени все технологии, используемые здесь, будут сильно устаревшими. Это совсем не похоже на ошибку 2000 года, поскольку мы будем контролировать весь код, поэтому даже если (ха-ха) что-то из этого все еще существует, мы сможем обновить его заранее.

Avrohom Yisroel 26.01.2023 00:16

Я немного пошутил!

Robot Head 26.01.2023 15:48

@RobotHead Извините, сейчас не всегда могу сказать!

Avrohom Yisroel 26.01.2023 16:07
Стоит ли изучать PHP в 2023-2024 годах?
Стоит ли изучать PHP в 2023-2024 годах?
Привет всем, сегодня я хочу высказать свои соображения по поводу вопроса, который я уже много раз получал в своем сообществе: "Стоит ли изучать PHP в...
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
В JavaScript одним из самых запутанных понятий является поведение ключевого слова "this" в стрелочной и обычной функциях.
Приемы CSS-макетирования - floats и Flexbox
Приемы CSS-макетирования - floats и Flexbox
Здравствуйте, друзья-студенты! Готовы совершенствовать свои навыки веб-дизайна? Сегодня в нашем путешествии мы рассмотрим приемы CSS-верстки - в...
Тестирование функциональных ngrx-эффектов в Angular 16 с помощью Jest
В системе управления состояниями ngrx, совместимой с Angular 16, появились функциональные эффекты. Это здорово и делает код определенно легче для...
Концепция локализации и ее применение в приложениях React ⚡️
Концепция локализации и ее применение в приложениях React ⚡️
Локализация - это процесс адаптации приложения к различным языкам и культурным требованиям. Это позволяет пользователям получить опыт, соответствующий...
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
4
11
130
3
Перейти к ответу Данный вопрос помечен как решенный

Ответы 3

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

Дата может храниться в секундах с момента времени EPOCH (EDIT) объекта DateTime, который должен занимать 8 байтов (длинный без знака).

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

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

Это дает вам общий размер 8 + 8 + 4 = 20 байт.

Ответ принят как подходящий

Мы можем сжать данные в 118 бит (или 15 байт). Пока все хорошо, у нас есть диапазоны:

  • Дата и время: от 1 Jan 2000 0:0:0.000 до 1 Jan 2100 0:0:0.000, что составляет 3_155_760_000_000 миллисекунд.
  • Серийный номер: 1_000_000_000_000_000_000 возможные номера
  • Сумма: 1_000_00 в копейках

Итого имеем:

double dt = (new DateTime(2100, 1, 1) - new DateTime(2000, 1, 1)).TotalMilliseconds;
double sn = 1_000_000_000_000_000_000L;
double amount = 1_000_00;

Console.Write(Math.Log2(dt * sn * amount));

Результат 117,925470... бит, 118 бит, так как мы не можем использовать бит частично

Обновлено: Сжать и распаковать процедуру:

private static byte[] MyCompress(DateTime date, long serial, decimal amount) {
  BigInteger ms = (long)(date - new DateTime(2000, 1, 1)).TotalMilliseconds;

  BigInteger value = 
    ms * 1_000_000_000_000_000_000L * 1_000_00 +
    (BigInteger)serial * 1_000_00 +
    (BigInteger)(amount * 100);

  byte[] result = new byte[15];

  for (int i = result.Length - 1; i >= 0; --i, value /= 256) 
    result[i] = (byte)(value % 256);

  return result;
}

private static (DateTime date, long serial, decimal amount) MyDecomress(byte[] data) {
  BigInteger value = data.Aggregate(BigInteger.Zero, (s, a) => s * 256 + a);

  BigInteger amount = value % 1_000_00;
  BigInteger serial = (value / 1_000_00) % 1_000_000_000_000_000_000L;
  BigInteger dt = value / 1_000_00 / 1_000_000_000_000_000_000L;

  return (
    new DateTime(2000, 1, 1).AddMilliseconds((double)dt),
    (long)serial,
    (decimal)amount / 100M
  );
}

Демо:

var data = MyCompress(new DateTime(2023, 1, 25, 21, 06, 45), 12345, 345.87m);

Console.WriteLine(string.Join(" ", data.Select(b => b.ToString("X2"))));

var back = MyDecomress(data);

Console.Write(back);

Выход:

00 0E 05 4C 23 D7 34 A8 BD E8 F7 CC 3D 95 80 BB
(25.01.2023 21:06:45, 12345, 345.87)

Скрипка

Обновлено: если мы можем хранить дату и время до 1/10 секунды (не до миллисекунды), мы можем использовать только 14 байтов:

private static byte[] MyCompress(DateTime date, long serial, decimal amount) {
  BigInteger ms = (long)(date - new DateTime(2000, 1, 1)).TotalMilliseconds / 100;

  BigInteger value = 
    ms * 1_000_000_000_000_000_000L * 1_000_00 +
    (BigInteger)serial * 1_000_00 +
    (BigInteger)(amount * 100);

  byte[] result = new byte[14];

  for (int i = result.Length - 1; i >= 0; --i, value /= 256) 
    result[i] = (byte)(value % 256);

  return result;
}

private static (DateTime date, long serial, decimal amount) MyDecomress(byte[] data) {
  BigInteger value = data.Aggregate(BigInteger.Zero, (s, a) => s * 256 + a);

  BigInteger amount = value % 1_000_00;
  BigInteger serial = (value / 1_000_00) % 1_000_000_000_000_000_000L;
  BigInteger dt = value / 1_000_00 / 1_000_000_000_000_000_000L;

  return (
    new DateTime(2000, 1, 1).AddMilliseconds((double)dt * 100),
    (long)serial,
    (decimal)amount / 100M
  );
}

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

Avrohom Yisroel 26.01.2023 19:08

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

Avrohom Yisroel 26.01.2023 19:12

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

Avrohom Yisroel 26.01.2023 19:16

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

Avrohom Yisroel 26.01.2023 19:21

@ Аврохом Исроэль: если дата и время должны быть с точностью до 1/10 секунды, мы можем втиснуть данные в 14 байт (112 бит)

Dmitry Bychenko 26.01.2023 19:27

Решение №1 (старое, 16 байт):

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

  1. Объедините month+day в dayOfYear (000-365) (для согласованности предположим, что в феврале всегда 29 дней);
  2. Объедините hours+minutes+seconds в timeInSeconds (00000-86399).

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

После этого вы можете преобразовать число в строке из base 10 в base 256. Таким образом вы получаете 16 байт вместо 37. Никакого математического доказательства, только практический результат в коде по ссылке (вывод внизу страницы). https://ideone.com/SMKb6S

Полученные результаты:

initial: 39 999912312359599999999999999999999999999
base10: 37 9999365863999999999999999999999999999
base256: 16 [7, 133, 206, 204, 233, 237, 90, 213, 156, 154, 224, 34, 63, 255, 255, 255]
base62: 21 EC5zRr0FV71hggqe73b0J

И после этого вы можете попробовать некоторые методы сжатия. Однако, как отмечено в комментариях, это может не работать с небольшим объемом данных.

Решение №2 (15 байт):

На самом деле, вы можете получить 15 байт. Дмитрий Быченко в своем ответе использовал микросекунды вместо миллисекунд (у меня недостаточно репутации, чтобы указать это в комментарии). Зафиксированный. Итак, 128 years будет 4_047_667_200_000 milliseconds (или что-то в этом роде).

Все данные умещаются в 15 байт, а некоторые биты вообще остаются свободными. Вы можете использовать их, например, для увеличения максимальной суммы. Вот расчеты на Python: https://ideone.com/37Bie3

Полученные результаты:

Target bytes: 15 (120 bits)
Years: 64
  Total bits: 120
  Max amount: £41943.04 (22 bits, 5 free bits used)
Years: 128
  Total bits: 120
  Max amount: £20971.52 (21 bits, 4 free bits used)
Years: 256
  Total bits: 120
  Max amount: £10485.76 (20 bits, 3 free bits used)
Years: 512
  Total bits: 120
  Max amount: £5242.88 (19 bits, 2 free bits used)
Years: 1024
  Total bits: 120
  Max amount: £2621.44 (18 bits, 1 free bits used)
Years: 2048
  Total bits: 120
  Max amount: £1310.72 (17 bits, 0 free bits used)

Редактировать: отформатировать решение №1, добавить решение №2.

Спасибо! Плохо, вы абсолютно правы насчет микросекунд; мы можем сэкономить еще 1 байт. Надеюсь, вы быстро наберете достаточно репутации, чтобы комментировать, позвольте мне начать добавлять +1;)

Dmitry Bychenko 26.01.2023 14:40

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

Avrohom Yisroel 26.01.2023 19:14

Другие вопросы по теме