Как называется этот алгоритм / рутина?

Question

Я пишу служебный класс, который преобразует строки из одного алфавита в другой, это полезно в ситуациях, когда у вас есть целевой алфавит, который вы хотите использовать, с ограничением на количество доступных символов.Например, если вы можете использовать строчные буквы и цифры, но только 12 символов, можно сжимать метку времени из алфавита 01234567989 -: в abcdefghijklmnopqrstuvwxyz01234567989, поэтому 2010-10-29 13:14:00 может стать 5hhyo9v8mk6avy (19 символов сокращено до 16).

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

Подумалпубликуя это через код Google, однако я, очевидно, хотел бы, чтобы другие люди нашли его и использовали - отсюда и вопрос о том, как это называется.Мне приходилось использовать этот подход в двух отдельных проектах, с Bloomberg и проприетарной системой, когда вам нужно генерировать уникальные имена файлов определенной длины, но при этом нужно сохранять какой-то открытый текст, поэтому GUID не подходят.

Answer 1

Ваши примеры имеют некоторое сходство с кодировщиком Dictionary с фиксированными целевыми и исходными словарями. Также стоит обратить внимание на кодирование Фибоначчи , которое имеет фиксированный целевой словарь (с битами переменной длины), на который нацелены переменные.

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

Answer 2

Вот простой алгоритм:

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

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

РЕДАКТИРОВАННЫЙ пример:

входной алфавит: ABC, выходной алфавит: 0123456789

сообщение ABAC будет преобразовано в 0102 в базе 3, то есть в 11 (9 + 2) в базе 10.

11 в базу 10: 11

Мыможет возникнуть проблема с его декодированием, поскольку мы не знаем, сколько нулей нужно использовать в начале декодированного результата, поэтому мы должны использовать одну из модификаций:

1) как-то кодировать вПоток размер сжатых данных.

2) использовать пустышку 1 в начале потока: таким образом наш пример станет:

10102 (база 3) = 81 +9 + 2 = 92 (база 10).

Теперь после декодирования нам просто нужно игнорировать первые 1 (это также обеспечивает базовое обнаружение ошибок).

Основная проблемаЭтот подход заключается в том, что в большинстве случаев (GCD == 1) каждый новый кодированный символ полностью меняет вывод.Это будет очень неэффективно и трудно осуществимо.В итоге мы получаем арифметическое кодирование как лучшее решение (на самом деле его упрощенная версия).

Answer 3

Вы, наверное, знаете о Base64, который делает то же самое, обычно наоборот. Жаль, что слишком много результатов Google на BaseX или BaseN ...