Кодировать / декодировать заданную строку в общей заданной (нестандартной) кодировке в массиве минимальных байтов

Question

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

Я начал разрабатывать мой, который является своего рода алгоритмом Base'n 'to Base 2, но я думаю, что нечто подобное уже было разработано.

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

Изменить: Максимальная длина моей строки составляет 160 символов. Я могу дополнить их, если это необходимо.

Edit2: я должен знать количество битов наихудшего случая.

byte[] encode(string charset, string value)

string decode(string charset, byte[] encodedValue)

Использование:

string myString = "HELLO WORLD";
string charSet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ "; // Base 27
byte[] encodedString = encode(charset, myString); // Base 27 -> Base 2
Debug.Assert(myString.Equals(decode(charset, encodedString))); // Base 2 -> Base 27

Answer 1

Вы можете использовать простой, быстрый префиксный код, который использует k или k-1 бит на символ. Тогда худший случай - это m k битов для m символов.

Для основания n пусть k = потолок (log₂(n)). Индексируйте символы от 0 до n-1. Если индекс x символа меньше 2^k-n, тогда испускаем x как целое число k-1 бита. В противном случае выведите 2^k-n + x как целое число k- бит.

Это намного быстрее, чем базовое кодирование / декодирование, которое требует умножения / деления соответственно. Давайте рассмотрим крайний случай, когда базовое кодирование подходит как можно лучше в 64 бита. (За исключением тривиальных случаев, когда основание составляет, например, 2, 4, 16 или 256.) Наилучшим случаем является ситуация, когда имеется 138 символов, где девять таких символов просто вписываются в 64 бита, и вы можете использовать аппарат инструкции умножения и деления на 64-разрядные целые числа без знака. 138⁹= 18151468971815029248, что составляет 98,4% от 2⁶⁴= 18446744073709551616. С базовым кодированием, есть 7,111 бит на символ. При использовании вышеупомянутого кодирования префикса среднее значение составляет 7,145 бит на символ.

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