Кодирование бинарных данных в строку с алфавитом произвольной длины (BaseN)

[withkittens]

Binary-to-text encoding#Encoding standards
yEnc

[MichaelBorisov]

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

Есть эффективный способ перевода в произвольную систему счисления, основанный на алгоритмах, применяемых в арифметическом кодировании. Описан этот способ в книге William H. Press et al «Numerical Recipes», http://www.nr.com/

[bytecode_rus]

Тут цель несколько иная. Прелесть Base64 и прочих подобных кодировок в том, что алфавит их состоит из «безопасных символов», а значит, кодированные в таком формате данные можно передавать через любые системы, которые позволяют передавать текст.

[MichaelBorisov]

Способ, который я упомянул, производит выходные данные в произвольной системе счисления. Если выбрать такую систему счисления, основание которой равно количеству «безопасных» символов в коде ASCII — то как раз и получится передавать в виде текста произвольные данные с минимальной избыточностью. Base64 использует 64 символа, но число «безопасных» символов в ASCII больше, чем 64. Однако 64 является степенью двойки, что упрощает кодирование. Поэтому Base64 и распространена.

[EndUser]

Чем измеряется эффективность в данном случае?

[MichaelBorisov]

Количеством бит информации на каждый выходной символ. Это количество может быть дробным.

[EndUser]

На это существуют другие алгоритмы. Того же Хэмминга, например.

И автор статьи не виноват в том, что ваши ожидания не оправдались.

Потому, что он описал только «безопасное ASCII-7 кодирование» без намерения сжимать информацию.

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

[MichaelBorisov]

Метод, на который я давал ссылку, тоже не сжимает информацию. Он преобразует данные из одной системы счисления в другую. То есть решает ту же задачу, что и автор поста.

[KvanTTT]

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

Это верно. Ну да, base85 и другие алгоритмы, с длиной алфавита не кратной степени двойки, имеют некоторую избыточность.

Но, как я понимаю, если проводить аналогию между кодированием Хаффмана (дискретным) и арифметическим (дробным), то у меня первый вариант? Если так, то можно подумать, как можно реализовать такой более сложный, но более оптимальный метод кодирования.

[freopen]

Ну очевидно аналог арифметического кодирования — просто алгоритм перевода числа в другую систему счисления.

[MichaelBorisov]

Тут не надо думать — просто ссылку почитайте. В этой книге доступным языком описано арифметическое кодирование и основанный на нем способ перевода в произвольную систему счисления (без компрессии).

[lorc]

Почему не представить исходное сообщение как одно большое число? Тогда записав его в n-ричной (например 85-ричной) системе счисления мы получим теоретически самое оптимальное представление в алфавите из n символов.
Придется конечно поизвращаться с длинной арифметикой. Но кто говорил, что кодирование — это просто?

[bachin]

a)Автор как раз и написал, что не хочет заморачиваться с «большими числами».
b)Почему-то не упомянут широко известный в узких кругах алгоритм base58/base58check

[MichaelBorisov]

Там не нужно сильно извращаться с длинной арифметикой. Почитайте ссылку на Numerical Recipes, которую я приводил. Очень эффективный метод.

[KvanTTT]

Кстати да, это интересно. Попробую реализовать такой метод. По сути это то же самое, как если увеличить Max Bits Count до (размера входной строки * 8) и использовать тот же алгоритм.

[KvanTTT]

Реализовал такой алгоритм по-быстрому, на основе существующей базы (не изучая того, что прислал MichaelBorisov), где входная строка представляется в виде одного большого числа в системе счисления произвольного алфавита. Для этого просто принял, что MaxBitsCount = input.Length * 8. Но при этом алгоритм становится менее помехоустойчивым, т.к. если изменить хотя бы один бит в начале при декодировании, то хвост цепочки уже не будет валидным, в отличие от моего метода, в котором невалидным будет только блок из нескольких символов. Кроме того, получаются слишком большие числа, время операций деления и умножения с которыми будет увеличиваться при увеличении длины цепочки. А сжатие получается маленьким. Результат так же можно посмотреть здесь (добавилось One Big Number).

[MichaelBorisov]

Та реализация, на которую я давал ссылку, во-первых, не страдает проблемами масштабируемости. Сложность вычислений линейно зависит от размера входных данных, то есть на каждую единицу входной информации вычислительные затраты постоянны.

Также там используются дробные числа. Выходное число в заданной системе счисления находится в диапазоне [0..1]. Это ограничивает влияние помех на результат декодирования.