Какой тип кодирования я могу использовать, чтобы сделать строку короче?

Я заинтересован в кодировании строки, которая у меня есть, и мне любопытно, есть ли тип кодирования, который можно использовать, который будет включать только буквенные и числовые символы и предпочтительно сократить количество символов, необходимых для представления строки.

До сих пор я смотрел на использование кодировки Base64, чтобы сделать это, но похоже, что моя строка длиннее и иногда включает в себя то, ==чего я хотел бы избежать. Пример:

название теста | 120101

становится

dGVzdCBuYW1lfDEyMDEwMQ ==

который идет от 16 до 24 символов и включает в себя не алфавитно-цифровой.

Кто-нибудь знает другой тип кодировки, который я мог бы использовать, чтобы удовлетворить мои требования? Бонусные баллы, если он либо встроен в .NET Framework, либо существует сторонняя библиотека, которая будет выполнять кодирование.

Последний символ «=» или «==» в Base64 предназначен только для того, чтобы количество символов было кратно 4. Вы можете удалить его, так как вы всегда можете вернуть его позже. Обратите внимание, что Base64 называется так, потому что он использует 64 различных символа. Прописные буквы, строчные буквы и цифры - это 62. Поэтому Base64 также использует «/» и «+», что может соответствовать или не соответствовать вашему счету.

В общем, если вы хотите закодировать произвольные последовательности байтов в алфавитно-цифровые символы, обязательно где-то есть расширение длины, потому что для байта есть 256 возможных значений и только 62 буквенно-цифровых символа. Его иногда называют принципом голубиного отверстия . Схема кодирования должна иметь расширение средней длины коэффициента log 256 / log 62 = 1,334 (среднее по всем последовательностям байтов); в противном случае это означает, что некоторые голуби где-то уничтожены, и вы не получите их обратно без повреждений (что означает: две разные строки закодированы в одну и ту же, поэтому декодирование не может работать надежно).

Теперь вполне возможно, что ваши строки не совсем "последовательности равномерно случайных байтов"; Ваши строки имеют какое-то значение, которое означает, что большинство возможных последовательностей байтов не будут возникать, потому что они бессмысленны. Исходя из этого, вы, вероятно, можете разработать схему кодирования, которая будет иметь меньшее расширение длины, чем базовая Base64 (или Base62, если вам нужно придерживаться строгих буквенно-цифровых символов). Это сжатие данных без потерь . Он работает над четко определенной вероятностной моделью того, что может появиться в качестве входных данных.

Резюме: общая схема для кодирования строк в буквенно - цифровые последовательности , такие , что нет или мало Удлинения никогда не происходит, не могут существовать; это математическая невозможность. Конкретная схема специально для вида входной строки , которую вы ожидаете , вероятно , может существовать (но так как вы не говорите , какие строки вы можете столкнуться, никто не может помочь вам в этом).

Перекодирование символов обычно выполняется, когда принимающая система не может их обработать. Например, BASE64 представляет данные с использованием 6 битов (2 ⁶ , следовательно, 64) символов для представления более длинных последовательностей данных (иногда появляющееся "==" в конце дополняет для выравнивания). Это связано с тем, что ваш файл изображения в электронной почте может содержать 0xFE, и ваш почтовый сервер будет недоволен передачей этого (или любого другого традиционно непечатного символа).

Не существует кодировки, которая «уменьшает размер». Кодировки - это просто отображение битов на символ, который они представляют. Тем не менее, ASCII - это 7-битный набор символов (кодировка), который часто хранится в 8 битах пространства. Если вы ограничиваете диапазоны, которые вы принимаете, вы также можете отсеять управляющие символы.

Использование этого метода означает, что вы должны записывать вещи на уровне битов, и он также играет немаловажную роль со скоростью и инструкциями машины, потому что все современные машины имеют выравнивания, кратные 8 битам. Вот почему Unicode - это UTF-8, UTF-16 и UTF-32.

Если вы делаете это для безопасности (вот почему вы разместили это в Security.SE, верно?), Просто отфильтруйте вещи и сохраните их как обычно. Если вы делаете это для экономии места, подумайте, стоит ли весь дополнительный код и более медленное время доступа (потому что большинство записей пересекают границы адресов), стоит ли экономия места.

Кстати, ниже приведен фрагмент из курса CS, где нам пришлось преобразовать ASCII из 8-разрядного хранилища в 7-разрядное:

    memset(dest,0x00,8);
    memcpy(dest, source, length);

    for (int i = 0; i < 8; i++) {
            if (dest[i] & 0x80) {
                    fprintf(stderr, "%s: %s\n", dest, "Illegal byte sequence");
                    exit(EILSEQ);
            }
    }

    dest[0] = 0x7F & dest[0] | 0x80 & dest[1] << 7;
    dest[1] = 0x3F & dest[1] >> 1 | 0xC0 & dest[2] << 6;
    dest[2] = 0x1F & dest[2] >> 2 | 0xE0 & dest[3] << 5;
    dest[3] = 0x0F & dest[3] >> 3 | 0xF0 & dest[4] << 4;
    dest[4] = 0x07 & dest[4] >> 4 | 0xF8 & dest[5] << 3;
    dest[5] = 0x03 & dest[5] >> 5 | 0xFC & dest[6] << 2;
    dest[6] = 0x01 & dest[6] >> 6 | 0xFE & dest[7] << 1;
    dest[7] = 0x00; //Clearing out

Вы можете сжать данные, например, с помощью gzip, bzip2 или lzma, а затем выполнить base64, чтобы ограничить используемый набор символов. Это выгодно только для больших строк из сотен байтов или более.

почему бы не использовать сжатие LZ? это может быть достойным способом сжатия строки, но будет более эффективным в случае длинных строк. Какова длина целевой строки, которую вы хотите закодировать?