Сжатие 21 буквенно-цифрового символа в 16 байтов

Получается (18*7+10)=136 бит, или 17 байт. Вы написали trade_num является буквенно-цифровым? Если это означает обычный набор символов [a-zA-Z0-9_], то у вас будет только 6 бит на символ, что потребует (18*6+10)=118 бит = 15 байт.

Предполагая, что 8 бит = 1 байт

Или, если подойти с другой стороны: У вас есть 128 бит для хранения, вам нужно ~10 бит для части номера, поэтому для торгового_номера остается 118. 18 символов означают 118/18=6.555 бит на символ, это означает, что у вас есть место только для кодирования 26.555 = 94 различных символов **если только в trade_num нет скрытой структуры, которую мы могли бы использовать, чтобы сэкономить больше бит.

Это то, что должно работать, если вам нужны только символы из allowedchars , а там не более 94 символов. Это python, но он написан без использования причудливых ярлыков, чтобы вам было проще перевести его на язык назначения. Однако предполагается, что переменная number может содержать целые числа до 2 ** 128 - в C ++ вы должны использовать какой-то класс больших чисел.

allowedchars=' !"#$%&\'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\]^_`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

Вы можете сделать это в ~~ 15 байтах (14 байтов и 6 бит).

Для каждого символа из trace_num_ вы можете сохранить 1 бит, если хотите сохранить ascii в 7 битах.

• Тогда у вас есть 2 байта свободных и 2 бит, у вас должно быть 5.

Позвольте получить числовую информацию, каждый символ может быть одним из десяти значений (от 0 до 9). Затем у вас должно быть 4 бита для сохранения этого символа, для сохранения числа у вас должен быть 1 байт и 4 бита, тогда вы сохраняете половину этого.

• Теперь у вас есть 3 свободных байта и 6 бит, у вас должно быть 5.

Если вы хотите использовать только qwertyuioplkjhgfdsazxcvbnmQWERTYUIOPLKJHGFDSAZXCVBNM1234567890 [] Вы можете сохранить каждый символ в 6 битах. Затем у вас есть следующие 2 байта и 2 бита.

• Теперь у вас осталось 6 байтов, и ваша строка может сохраниться в 15 байтах + nulltermination = 16 байт.

А если вы сохраните ваше число целым числом по 10 байт. Вы можете уместить это в 14 байтов и 6 бит.

Ключевые вопросы:

Похоже, в вашем сообщении есть некоторое противоречие, является ли торговый номер 16 или 18 символами. Вам нужно это прояснить. Вы говорите, что общая сумма равна 21, состоящему из 16 + 3. : - (

Вы говорите, что символы торгового номера находятся в диапазоне 0x00-0x7f.Могут ли они действительно быть любым символом в этом диапазоне, включая табуляцию, новую строку, Ctrl-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 или C ++? Разве в C ++ нет какого-то класса больших чисел? Извините, я давно не занимался C ++. В противном случае мы могли бы легко создать небольшую библиотеку для реализации огромного.

Если он может содержать только буквы, то у вас есть менее 64 вариантов для каждого символа (26 в верхнем регистре, 26 в нижнем регистре, оставляя вам 12 для пробела, терминатора, подчеркивания и т. Д.). С 6 битами на символ вы должны получить 15 символов. Предполагая, что вы не поддерживаете специальные символы.

Используйте первые 10 битов для 3-символьной числовой строки (кодируйте биты так, как будто они представляют собой число, а затем при декодировании дополняйте нулями при необходимости).

Хорошо, остается 118 бит и 16 буквенно-цифровых символов для хранения.

От 0x00 до 0x7F (если вы имеете в виду включительно) содержит 128 возможных символов для представления. Это означает, что каждый символ может быть идентифицирован комбинацией 7 бит. Придумайте индекс, отображающий каждое число, которое эти 7 бит могут представлять фактическому персонажу. Чтобы представить таким образом 16 ваших «буквенно-цифровых» символов, вам понадобится всего 112 бит.

Теперь у нас есть 122 бита (или 15,25 байта), представляющие наши данные. Добавьте пасхальное яйцо, чтобы заполнить оставшиеся неиспользуемые биты, и у вас есть массив из 16 символов.

Между пробелом (0x20) и тильдой (0x7e) находится 95 символов. (94 в других ответах страдают от ошибки off-by-1).

Следовательно, количество различных идентификаторов составляет 95 ¹⁸ × 1000 = 3,97 × 10 ³⁸ .

Но эта сжатая структура может содержать только (2 ⁸ ) ¹⁶ = 3,40 × 10 ³⁸ различных значений.

Следовательно, невозможно представить все идентификаторы этой структурой, кроме случаев:

• 1 неиспользованный символ в ≥15 цифрах trade_num_ , или
• В 1 ≥14 неиспользуемых символов цифра trade_num_ , или
• Есть только ≤856 брокеров, или
• Вы используете PDP-10 с 9-битным символом .