Как кодировать 8-байтовый блок, используя только цифры (цифры)?

Question

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

Answer 1

Ответ на вопрос эффективности будет зависеть от lot от типичного диапазона значений в 8-байтовых блоках. Рассмотрим Unicode UTF-8 и UTF-16. UTF-8 очень эффективен для кодирования текстов, написанных в основном на западных сценариях, поскольку большинство символов в этих сценариях находятся в диапазоне от 0x00 до 0x7F, которые UTF-8 может хранить в одном байте. Но это не очень эффективно для кодирования текстов, написанных в основном на восточных языках; UTF-16 или UTF-32 - лучший выбор.

Если вы прочитали различных UTF , они могут вдохновить на решение. По сути, они работают, выполняя такие вещи, как прямое кодирование множества значений в байте, но затем наличие флага (я думаю, это старший бит в случае первого байта UTF-8), указывающего, что байт не рассказывает всю историю, и следующий байт (или два, или три, или четыре) является / требуется. Отправной точкой является байт для UTF-8, слово для UTF-16, но концепции похожи.

Теперь вы работаете с резко меньшим диапазоном значений (0-9, а не 0-255), и, очевидно, я не рекомендую пытаться напрямую использовать UTF, только концепцию. Например, скажем, большинство ваших значений (напрямую или с некоторым массажем) меньше 9000, довольно мало меньше 9000000, и только редкие значения выводят вас за пределы этого. Вы можете использовать подход UTF и сказать, что блоки (ваши 8-байтовые значения) разделены на четырехзначные сегменты, и у вас всегда будет хотя бы один сегмент (четыре цифры) на кодированный блок. Если значение первого сегмента (aaaa) находится в диапазоне от 0000 до 8999 (включительно), это «терминальный» сегмент & mdash; это фактическая стоимость. Но если это 9aaa, это означает, что есть второй сегмент, и вы должны посмотреть на aaabbbb (bbbb - это значение следующего сегмента). Если , то значение находится между 0000000 и 8999999 (включительно), это терминал; но если это 9aabbbb, это означает, что посмотрите на aabbbbcccc (cccc - следующий сегмент); и т.д. Я думаю , что дало бы нам это:

00000000000000000000-00000000000000008999 ->  4 digits (xxxx)
00000000000000009000-00000000000008999999 ->  8 digits (9xxxxxxx)
00000000000009000000-00000000008999999999 -> 12 digits (99xxxxxxxxxx)
00000000009000000000-00000008999999999999 -> 16 digits (999xxxxxxxxxxxxx)
00000009000000000000-00008999999999999999 -> 20 digits (9999xxxxxxxxxxxxxxxx)
00009000000000000000-08999999999999999999 -> 24 digits (99999xxxxxxxxxxxxxxxxxxx)
09000000000000000000-18446744073709551615 -> 28 digits (999999xxxxxxxxxxxxxxxxxxxxxx)
Or special case, just use 26 digits for the last one:  (999999xxxxxxxxxxxxxxxxxxxx)

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

Так вот, это совершенно не так, и, вероятно, не так эффективно, как могло бы быть, но вы поняли идею. Это очень легко десериализовать, и, вероятно, не так сложно сериализовать.

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

Answer 2

Обрабатывает 8 байтов как 64-разрядное целое число без знака, преобразует его в десятичное и дополняет его нулями слева. Это должно сделать для самой короткой возможной строки, поскольку она использует все доступные цифры во всех позициях, кроме начальной.

Если ваши данные распределены неравномерно, есть и другие альтернативы, связанные с кодированием по Хаффману, так что наиболее часто шаблоны данных могут быть представлены более короткими строками. Одним из способов является использование первой цифры для кодирования длины строки. Все числа, кроме 1 в первой позиции, могут рассматриваться как спецификаторы длины. Таким образом, максимальная длина в 20 цифр никогда не будет превышена. (20-я цифра может быть только 0 или 1, старшее 64-битное число - 18 446 744 073 709 551 615). Точное отображение интерпретации других цифр на длину должно основываться на распределении ваших шаблонов. Если у вас есть 10 образцов, которые встречаются ОЧЕНЬ часто, вы можете, например, зарезервируйте «0», чтобы обозначить, что одна цифра представляет полную последовательность.

Любое такое более сложное кодирование, однако, приведет к необходимости более сложной упаковки / распаковки кода и, возможно, даже поиска таблиц, так что это может не стоить усилий.

Answer 3

Результат, который имеет самую короткую длину, должен преобразовать ее в десятичную форму напрямую. Это приводит к тому, что самое высокое значение составляет 18446744073709551615, но преобразование может быть затруднено без возможности целочисленной произвольной длины.

Следующий самый длинный - преобразовать его в восьмеричный как один кусок. Это приводит к максимальной длине 22 со значением 1777777777777777777777. Для конвертации требуются только смены, и с этим можно справиться достаточно легко.

Следующий самый длинный - преобразовать его в восьмеричный или десятичный байтовый код. Это приводит к длине 24 с 8 повторениями 377 или 255 соответственно. Преобразование назад и вперед тривиально и оставлено читателю в качестве упражнения.