Сжатие 21 буквенно-цифровых символов в 16 байт
Я пытаюсь взять 21 байт данных, которые однозначно идентифицируют сделку и хранят ее в массиве размером 16 байт char. У меня возникают проблемы с правильным алгоритмом для этого.
Торговый идентификатор, который я пытаюсь сжать, состоит из двух полей:
- 18 буквенно-цифровых символов
состоящий из символов ASCII
0x20 - 0x7E, включительно. (32-126)
- 3-значная цифровая строка "000" до "999"
Итак, класс С++, который будет охватывать эти данные, выглядит следующим образом:
class ID
{
public:
char trade_num_[18];
char broker_[3];
};
Эти данные необходимо сохранить в структуре данных 16- char, которая выглядит следующим образом:
class Compressed
{
public:
char sku_[16];
};
Я попытался воспользоваться тем, что, поскольку символы в trade_num_ равны 0-127, в каждом символе был один неиспользуемый бит. Аналогично, 999 в двоичном формате - 1111100111, что составляет всего 10 бит - на 6 бит меньше 2-байтового слова. Но когда я выясняю, насколько я могу сжать это, самое маленькое, что я могу сделать, это 17 байт; один байт слишком большой.
Любые идеи?
Кстати, trade_num_ является неправильным. Он может содержать буквы и другие символы. Вот что говорит спецификация.
EDIT: Извините за путаницу. Поле trade_num_ действительно 18 байт, а не 16. После того, как я опубликовал эту тему, мое интернет-соединение умерло, и я не мог вернуться к этой теме только сейчас.
EDIT2: Я думаю, что безопасно делать предположения о наборе данных. В поле trade_num_ мы можем предположить, что непечатаемые символы ASCII 0-31 не будут присутствовать. Также не будут ASCII-коды 127 или 126 (~). Все остальные могут присутствовать, включая буквы верхнего и нижнего регистра, цифры и пунктуации. Это дает в общей сложности 94 символа в наборе, в котором trade_num_ будет состоять из кодов ASCII с 32 по 125 включительно.
Ответы
Ответ 1
Если у вас есть 18 символов в диапазоне 0 - 127 и число в диапазоне 0 - 999 и максимально компактное, это потребует 17 байт.
>>> math.log(128**18 * 1000, 256)
16.995723035582763
Возможно, вы сможете воспользоваться тем фактом, что некоторые символы, скорее всего, не используются. В частности, маловероятно, что есть символы ниже значения 32, а 127 также, вероятно, не используются. Если вы можете найти еще один неиспользуемый символ, чтобы вы могли сначала преобразовать символы в базу 94, а затем как можно ближе упаковать их в байты.
>>> math.log(94**18 * 1000, 256)
15.993547951857446
Это просто вписывается в 16 байтов!
Пример кода
Вот пример кода, написанного на Python (но написанного в очень императивном стиле, так что его легко понять программисты, не являющиеся программистами на Python). Я предполагаю, что во вкладке нет тильд (~). Если есть, вы должны заменить их другим символом перед кодировкой строки.
def encodeChar(c):
return ord(c) - 32
def encode(s, n):
t = 0
for c in s:
t = t * 94 + encodeChar(c)
t = t * 1000 + n
r = []
for i in range(16):
r.append(int(t % 256))
t /= 256
return r
print encode(' ', 0) # smallest possible value
print encode('abcdefghijklmnopqr', 123)
print encode('}}}}}}}}}}}}}}}}}}', 999) # largest possible value
Вывод:
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[ 59, 118, 192, 166, 108, 50, 131, 135, 174, 93, 87, 215, 177, 56, 170, 172]
[255, 255, 159, 243, 182, 100, 36, 102, 214, 109, 171, 77, 211, 183, 0, 247]
Этот алгоритм использует способность Python обрабатывать очень большие числа. Чтобы преобразовать этот код в С++, вы можете использовать большую целочисленную библиотеку.
Разумеется, вам понадобится эквивалентная функция декодирования, принцип будет одинаков - операции выполняются в обратном порядке.
Ответ 2
Это делает (18 * 7 + 10) = 136 бит или 17 байтов. Вы написали trade_num буквенно-цифровой? Если это означает обычный набор символов [a-zA-Z0-9_], тогда у вас будет всего 6 бит на символ, для чего требуется (18 * 6 + 10) = 118 бит = 15 байтов.
Предполагая, что 8 бит = 1 байт
Или, исходя из другого направления: у вас есть 128 бит для хранения, вам нужно ~ 10 бит для части номера, поэтому для trade_num осталось 118. 18 символов означают 118/18 = 6,555 бит на символы, это означает, что вы можете иметь только пространство для кодирования 2 6.555 = 94 разных символа **, если не существует скрытой структуры в trade_num, которую мы могли бы использовать для сохранить больше бит.
Ответ 3
Это то, что должно работать, предполагая, что вам нужны только символы из allowedchars, и там должно быть не более 94 символов. Это python, но написано, пытаясь не использовать причудливые ярлыки - чтобы вы могли легче перевести его на ваш язык назначения. Однако предполагается, что переменная number может содержать целые числа до 2 ** 128 - на С++ вы должны использовать какой-то класс больших чисел.
allowedchars=' !"#$%&\'()*+,-./0123456789:;<=>[email protected][\\]^_`abcdefghijklmnopqrstuvwxyz{|}'
alphabase = len(allowedchars)
def compress(code):
alphanumeric = code[0:18]
number = int(code[18:21])
for character in alphanumeric:
# find returns index of character on the allowedchars list
number = alphabase*number + allowedchars.find(character)
compressed = ''
for i in xrange(16):
compressed += chr(number % 256)
number = number/256
return compressed
def decompress(compressed):
number = 0
for byte in reversed(compressed):
number = 256*number + ord(byte)
alphanumeric = ''
for i in xrange(18):
alphanumeric = allowedchars[number % alphabase] + alphanumeric
number = number/alphabase
# make a string padded with zeros
number = '%03d' % number
return alphanumeric + number
Ответ 4
Вы можете сделать это в ~ ~ 15 байт (14 байтов и 6 бит).
Для каждого символа из trace_num_ вы можете сохранить 1 бит, если хотите сохранить ascii в 7 бит.
- Тогда у вас есть 2 байта бесплатно и 2
бит, у вас должно быть 5.
Позвольте получить информацию о числе, каждый char может быть одним из десяти значений (от 0 до 9).
Затем вы должны иметь 4 бита для сохранения этого символа, чтобы сохранить номер, который должен иметь 1 байт и 4 бита, тогда вы сохраните половину этого.
- Теперь у вас есть 3 байта бесплатно и 6 бит,
у вас должно быть 5.
Если вы хотите использовать только qwertyuioplkjhgfdsazxcvbnmQWERTYUIOPLKJHGFDSAZXCVBNM1234567890[]
Вы можете сохранить каждый char в 6 бит. Затем у вас есть следующие 2 байта и 2 бита.
- Теперь у вас осталось 6 байт, а ваша строка может сэкономить 15 байт +
nulltermination = 16bytes.
И если вы сохраните свой номер в integer на 10 байт. Вы можете поместить это в 14 байтов и 6 бит.
Ответ 5
Ключевые вопросы:
Кажется, в вашем сообщении есть какое-то противоречие, является ли торговый номер 16 или 18 символов. Вам нужно это очистить. Вы говорите, что сумма составляет 21, состоящую из 16 + 3.: - (
Вы говорите, что числовых символов num находится в диапазоне 0x00-0x7f. Могут ли они действительно быть персонажем в этом диапазоне, включая вкладку, новую строку, control-C и т.д.? Или они ограничены печатными буквами или, может быть, даже буквенно-цифровыми?
Должны ли выходные 16 байтов быть печатными символами, или это в основном двоичное число?
ИЗМЕНИТЬ, после обновления исходного сообщения:
В этом случае, если вывод может быть любым символом в наборе символов, это возможно. Если это могут быть только печатные символы, это не так.
Демонстрация математической возможности достаточно проста. Существует 94 возможных значения для каждого из 18 символов и 10 возможных значений для каждого из 3. Общее количество возможных комбинаций = 94 ^ 18 * 10 ^ 3 ~ = 3.28E35. Для этого требуется 128 бит. 2 ^ 127 ~ = 1,70e38, что слишком мало, а 2 ^ 128 ~ = 3,40e38, что достаточно велико. 128 бит - 16 байт, поэтому он будет едва соответствовать, если мы сможем использовать все возможные комбинации бит.
Учитывая жесткую подгонку, я думаю, что самый практичный способ генерировать значение - это думать о нем как о двойном длинном числе, а затем запускать вход через алгоритм для генерации уникального целого для каждого возможного ввода.
Концептуально, тогда предположим, что у нас есть тип данных "огромный целочисленный", длина которого составляет 16 байтов. Алгоритм будет примерно таким:
huge out;
for (int p=0;p<18;++p)
{
out=out*94+tradenum[p]-32;
}
for (int p=0;p<3;++p)
{
out=out*10+broker[p]-'0';
}
// Convert output to char[16]
unsigned char[16] out16;
for (int p=15;p>=0;--p)
{
out16[p]=huge&0xff;
huge=huge>>8;
}
return out16;
Конечно, у нас нет "огромного" типа данных в C. Используете ли вы чистый C или С++? Разве нет какого-то большого класса чисел в С++? К сожалению, я еще не сделал С++. Если нет, мы могли бы легко создать небольшую библиотеку для реализации огромного.
Ответ 6
Между пространством (0x20) и тильдой (0x7e) присутствуют символы 95. (94 в других ответах страдают от ошибки "один за другим" ).
Следовательно, число различных идентификаторов 95 18 & times; 1000 = 3.97 & times; 10 38.
Но эта сжатая структура может удерживать (2 8) 16= 3.40 и times; 10 38 различные значения.
Поэтому невозможно представить все идентификаторы этой структурой, если:
- Существует 1 неиспользуемый символ в ≥15 цифр
trade_num_ или
- Есть ≥14 неиспользуемых символов в 1 цифре
trade_num_ или
- Есть только ≤856 брокеров, или
- Вы используете PDP-10 с 9-бит
char.
Ответ 7
Если он может содержать только буквы, то у вас есть менее 64 возможностей на каждый персонаж (26 верхний регистр, 26 нижний регистр, оставляя вам 12 для пробела, терминатор, подчеркивание и т.д.). С 6 бит на символ вы должны попасть туда - в 15 символов. Предполагая, что вы не поддерживаете специальные символы.
Ответ 8
Используйте первые 10 бит для 3-значной числовой строки (закодируйте биты, как они представляют число, а затем поместите нуль при необходимости при декодировании).
Хорошо, это оставляет вам 118 бит и 16 буквенно-цифровых символов для хранения.
0x00 до 0x7F (если вы имеете в виду включительно) содержит 128 возможных символов для представления. Это означает, что каждый символ может быть идентифицирован комбинацией из 7 бит. Придумайте индекс, отображающий каждый номер, который 7 битов могут представлять действительный символ. Чтобы представить 16 ваших буквенно-цифровых символов таким образом, вам нужно всего 112 бит.
Теперь у нас есть 122 бита (или 15.25 байт), представляющие наши данные. Добавьте пасхальное яйцо, чтобы заполнить оставшиеся неиспользуемые биты, и у вас есть 16-символьный массив.
