Что самый эффективный путь состоит в том, чтобы закодировать произвольный GUID в читаемый ASCII (33-127)?
Стандартное строковое представление GUID берет приблизительно 36 символов. Который очень хорош, но также и действительно расточителен. Я задаюсь вопросом, как закодировать его в самом коротком способе использовать все символы ASCII в диапазоне 33-127. Наивная реализация производит 22 символа, просто потому что 128 битов / 6 битов уступают 22.
Кодирование методом Хаффмана является моим второстепенным вариантом, единственный вопрос состоит в том, как выбрать коды....
Кодирование должно быть без потерь, конечно.
6 ответов
Используйте базу 85. См. Раздел 4.1. Почему 85? из Компактное представление адресов IPv6
Адрес IPv6, как и GUID, состоит из восьми 16-битных частей.
Предполагая , что все ваши GUID генерируются с помощью одного и того же алгоритма, вы можете сэкономить 4 бита, не кодируя полубайт алгоритма, перед применением любой другой кодировки: - |
У вас доступно 95 символов - то есть больше 6 бит, но не так много, как 7 (на самом деле около 6,57). Вы можете использовать 128 / log2 (95) = около 19,48 символов для кодирования в 20 символов. Если сохранение двух символов в закодированной форме стоит потери удобочитаемости для вас, что-то вроде (псевдокод):
char encoded[21];
long long guid; // 128 bits number
for(int i=0; i<20; ++i) {
encoded[i] = chr(guid % 95 + 33);
guid /= 95;
}
encoded[20] = chr(0);
, который по сути является общим кодом «кодировать число в некотором базовом» коде, за исключением того, что нет необходимости переворачивать » цифр », поскольку порядок в любом случае произвольный (а метод прямого порядка байтов более прямой и естественный). Возвращение guid из закодированной строки очень похоже на вычисление полинома по основанию 95 (конечно, после вычитания 33 из каждой цифры):
guid = 0;
for(int i=0; i<20; ++i) {
guid *= 95;
guid += ord(encoded[i]) - 33;
}
по существу использует подход Хорнера к вычислению полиномов.
Произвольный GUID? «Наивный» алгоритм даст оптимальные результаты. Единственный способ дополнительно сжать GUID - использовать шаблоны в данных, исключенные вашим «произвольным» ограничением.
Использование полного диапазона от 33 (кстати, что не так с пробелом?) До 127 дает 95 возможных символов. Выражение 2 ^ 128 возможных значений guid в базе 95 будет использовать 20 символов. Это лучшее, что вы можете сделать (по модулю таких вещей, как отбрасывание нибблов, которые будут постоянными). Избавьте себя от неприятностей - используйте базу 64.