Сжатие строки до фиксированной длины

У вас есть примерно 1,3e25 возможных комбинаций, а это означает, что вам нужно 84 бита для кодирования такого количества комбинаций. Вам нужно будет выполнить арифметику по модулю 37 и некоторые трюки с информацией о длине, чтобы сжать кодировку в эти 84 бита.

Главный вопрос заключается в том, насколько большое подмножество символов Unicode вы готовы принять в закодированной строке. Без ограничений один символ Юникода может легко представлять 17 бит, поэтому 5 символов Юникода будет достаточно, поскольку они дадут вам 85 бит.

Но «Английский алфавит в любом случае, цифры, подчеркивания, скобки и другие различные символы utf8 могут использоваться для сжатия исходной строки» подразумевает, что неограниченный Unicode — это не то, что вам нужно.

Таким образом, количество различных символов, разрешенных в кодировке, возведенных в степень желаемой длины закодированной строки, должно быть больше 1,3e25, чтобы сделать кодирование возможным.

Итак, посчитайте количество различных символов, которые вы хотите разрешить в закодированной строке, и посчитайте сами. Например. Чтобы достичь длины кодировки в 8 символов, вам потребуется как минимум алфавит из 1375 разрешенных символов.

Требование, чтобы результат был действительным в формате UTF-8, и минимизация количества байтов (не символов Юникода) — интересная проблема. Не все последовательности байтов действительны в формате UTF-8.

Даже вычисление мощности потока UTF-8 является нетривиальной задачей. Если я хочу знать, сколько четырехбайтовых последовательностей действительны и полны UTF-8, мне нужно рассмотреть все комбинации количества байтов в каждом символе, которые в сумме дают четыре байта: 1-1-1-1, 1- 1-2, 1-2-1, 2-1-1, 2-2, 1-3, 3-1 и 4.

Количество допустимых символов UTF-8 длиной 1, 2, 3 и 4 байта равно 2⁷, 2¹¹-2⁷, 2¹⁶-2¹² и 2²⁰. Если применить их к комбинациям и суммировать, то получится 383 270 912 действительных и полных последовательностей UTF-8 длиной четыре байта. Это составляет около 28,5 бит из 32 занятых бит, что дает 89% использования 32 бит.

Вопрос задается фиксированной длины, поэтому мы суммируем количество возможных последовательностей символов от 3 до 16, где имеется 37 символов. Эта сумма составляет 12 680 220 578 500 976 539 002 674. Как отмечалось здесь, в двоичном кодировании потребуется 83,4 бита. Для фиксированного количества байтов потребуется одиннадцать.

Мы повторяем описанный выше процесс, чтобы подсчитать действительные последовательности UTF-8 для 5, 6 и т. д. байтов, пока не сможем охватить общее количество от 3 до 16 символов с 37 значениями. Оказывается, для этого нам нужна 12-байтовая действительная последовательность UTF-8. Существует 73 122 690 434 759 781 773 213 696 возможных таких последовательностей, что соответствует емкости 85,9 бит. Интересно, что использование более длинных последовательностей UTF-8 не намного меньше: 85,9% для 12 байт.

Ответ на вопрос заключается в том, что действительная последовательность UTF-8 минимальной длины, необходимая для представления от 3 до 16 символов с 37 значениями, составляет 12 байтов.

Для реализации кодирования и декодирования будет использоваться подсчет для присвоения целого числа каждой 12-байтовой последовательности UTF-8. Аналогичным образом, каждой последовательности из 37 значений от 3 до 16 будет присвоено целое число. Это целое число определяет, какую 12-байтовую последовательность UTF-8 оно кодирует, а декодирование дает целочисленную идентификацию исходной последовательности символов.

Если вместо UTF-8 (как указано в вопросе) ОП действительно хочет кодировать в UTF-16, как символы кодируются в Java (поскольку в комментариях упоминается тип char и вопрос помечен " Java"), то действительно указанные символы от 3 до 16, где каждый символ принимает одно из 37 значений, могут быть закодированы в шесть 16-битных значений, ограниченных допустимым UTF-16, без необходимости использования суррогатных значений, то есть старого UCS-2. Фактически, в каждый символ UTF-16 необходимо закодировать только 14 бит, поэтому можно выбрать подмножество символов, чтобы оно было более читаемым.

Чтобы реализовать кодировщик, сначала выберите 16 384 символов Юникода в допустимых кодовых точках от 0x0000 до 0xffff (исключая символы от 0xd800 до 0xdfff), чтобы разрешить их в закодированной форме. Создайте карту 0..16383 с выбранными вами символами Юникода. Затем присвойте целое число каждой последовательности из 37 значений от 3 до 16. Расчет можно выполнить с помощью класса BigInteger. Этот результат представляет собой 84-битное целое число. Разбейте 84-битное целое число на шесть 14-битных частей (идеально подходит!) и напишите соответствующую кодовую точку для каждой из 14-битных частей вашей карты.

Вот псевдокод для вычисления целого числа, соответствующего последовательности:

    // len is in 3..16, seq[i] is in 0..36
    bigint base = 0;
    bigint offset = 37 * 37;
    for (int i = 3; i < len; i++) {
        offset *= 37;
        base += offset;
    }
    offset = 0;
    for (int i = 0; i < len; i++)
        offset = 37 * offset + seq[i];
    return base + offset;

Где вам нужно будет использовать методы BigInteger для арифметических операций.