У нас есть карты лояльности (подобные кредитным/дебетовым картам, но обрабатываемые с помощью нашего специального кода, в отличие от тех, которые обрабатываются при взаимодействии с банками). Нам нужно хранить данные о транзакциях на картах, так как многие транзакции будут совершаться с использованием автономных устройств и загружаться только при следующем касании карты на онлайн-терминале.
Место для хранения карты ограничено (обычно максимум 8 КБ, если вы не платите глупые цены за очень смарт-карты), поэтому мне нужно максимально сжать данные.
Наши данные о транзакциях состоят из трех частей, каждая из которых состоит только из цифр (т.е. без буквенных или специальных символов)...
yyMMddhhmmssfff
Представление этого в виде строки цифр дает 37 цифр на транзакцию.
Я пытался использовать алгоритмы в System.IO.Compression
(следуя коду в этой записи в блоге и сопутствующему репозиторию GitHub, не включенному сюда, поскольку это стандартное использование классов).
Это дало довольно впечатляющие результаты: сокращение примерно на 72% при использовании оптимального алгоритма Gzip.
Однако мне было интересно, можно ли это улучшить, учитывая, что мы кое-что знаем о форме данных транзакции. Например, часть данных даты/времени разбивается следующим образом...
Любой комментарий о том, помогут ли эти ограничения помочь мне улучшить это сжатие. Спасибо
Почему вы используете двузначные годы? Разве вы не помните все вещи Y2K? Или все ваши сделки относятся к 20 веку? Давно
Обычно вам действительно требуется БОЛЬШЕ места для хранения при сжатии небольших строк, и я, безусловно, считаю 37 цифр маленькой строкой. Вы действительно уверены, что получаете что-то от сжатия? В моих быстрых тестах как gzip, так и LZ4 я вижу значительное увеличение (~ 25%) используемых байтов, а не уменьшение
Не говоря уже о том, что при 37 байтах на транзакцию и при условии, что вы используете только половину хранилища карты, вы все равно можете хранить ~ 110 транзакций. Сколько именно транзакций вы собираетесь хранить в автономном режиме? Похоже, вы должны сначала установить это, а затем работать в обратном направлении, чтобы определить свои требования.
Рассматривали ли вы возможность использования битов для представления частей? т.е. месяц можно закодировать 3 битами, день 4, год - 1 байтом и т.д.?
Ответ на ваш вопрос - да. Например, если вы знаете самую раннюю дату/время, вы можете использовать смещение от нее. С 15 цифрами с точностью до 1/1000 секунды вы можете покрыть 31 688 лет — при условии, что вы можете сократить этот диапазон до 1000 лет, вы можете сохранить две цифры, а 100 лет — три цифры, но, поскольку вы также знаете, что все поля просто 0-9, вы можете преобразовать 37-значное число в двоичное и использовать 16 байт.
В качестве альтернативы вы можете отобразить каждый компонент в битовое поле и также получить 17 байтов.
@Chronicle Да, я видел это (наряду со многими другими здесь), но в этом вопросе конкретно упоминалось, что многие целые числа были в последовательности, и у меня сложилось впечатление, что это был важный фактор в сжатии. В моем случае такого нет
@RobotHead Это новый проект, поэтому самая ранняя дата транзакции будет при каждом запуске. 2 цифры для года дают нам почти 77 лет, к тому времени все технологии, используемые здесь, будут сильно устаревшими. Это совсем не похоже на ошибку 2000 года, поскольку мы будем контролировать весь код, поэтому даже если (ха-ха) что-то из этого все еще существует, мы сможем обновить его заранее.
Я немного пошутил!
@RobotHead Извините, сейчас не всегда могу сказать!
Вместо того, чтобы пытаться сжимать текстовую версию данных, рассмотрите свои данные и сохраните их в более эффективном формате.
Дата может храниться в секундах с момента времени 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
. Мы что-то здесь упускаем, потому что если это всегда ноль, это избыточно
Ах, только что прочитал и увидел комментарий Керка. Объясняет ли это ведущий ноль? Если это так, не могли бы вы обновить свой код, чтобы отразить это.
На самом деле, мне только что пришло в голову, что для нашего варианта использования нам нужно время только с точностью до 1/10 секунды, нам на самом деле не нужны миллисекунды. Это позволит нам еще больше уменьшить хранилище. Я все еще не совсем понимаю математику, которую вы использовали для расчета количества байтов, поэтому, пожалуйста, потерпите меня, если это глупый вопрос.
(пауза для размышления) ...и это заставило меня понять, почему начальный байт равен нулю! Просто прочитайте ответ Керка, и между вами двумя я думаю, что теперь понимаю. Означает ли это, что я могу использовать ваш код как есть и просто отбросить первый байт?
@ Аврохом Исроэль: если дата и время должны быть с точностью до 1/10
секунды, мы можем втиснуть данные в 14
байт (112
бит)
Решение №1 (старое, 16 байт):
Вы можете сохранить две цифры (байта), используя указанные ограничения:
month+day
в dayOfYear
(000-365
) (для согласованности предположим, что в феврале всегда 29 дней);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;)
С такими ответами вы быстро получите репутацию! Довольно удивительно для нового участника. Голосуй и от меня
См. stackoverflow.com/questions/283299/…