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

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

Я начал разрабатывать свой алгоритм, который представляет собой своего рода алгоритм 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

string c# encoding compression text-compression
person Jeremy D    schedule 26.06.2015    source источник
comment
поищите кодирование Хаффмана   -  person BeyelerStudios    schedule 26.06.2015
comment
Здесь находится преобразователь base-n. Сделайте Encoding.UTF8.GetBytes(myString) и передайте результат написанному там методу.   -  person xanatos    schedule 26.06.2015

Ответы (1)


arrow_upward
2
arrow_downward

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

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

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

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

person Mark Adler    schedule 26.06.2015