Уникально кодировать любую строку ASCII в строку, которая использует подмножество ASCII.

Для этого вопроса предположим, что это Python, но это не обязательно имеет значение.

Представьте, что у вас есть произвольная строка ASCII, например:

jrioj4oi3m_=\.,ei9#

Не вдаваясь в детали, мне нужно передать эту строку как метку другой программе, но эта программа не поддерживает метки, содержащие специальные символы или даже числа. Итак, я пытаюсь закодировать строку ASCII в строку, которая использует произвольное подмножество ASCII.

Одним из очень наивных решений было бы преобразовать исходную строку в двоичную, затем преобразовать 0 в a и 1 в b. Это работает для решения моей проблемы, но я хотел бы узнать здесь лучшее решение, чтобы стать лучшим программистом.

Прежде всего, как именно называется эта проблема?

Это не совсем проблема хеширования, потому что хеширование IIRC обычно включает кодирование в строку, которая короче исходной, и включает коллизии.

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

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

Расшифровку тоже неплохо бы знать.


python string encoding decoding ascii
person cat pants    schedule 07.12.2020    source источник
comment
Вы можете просмотреть свой ввод в виде чисел в Base-N (N равно 128, если вы разрешаете полный диапазон символов ASCII, и меньше, если вы еще больше ограничите ввод), а вывод - в Base-M (M - количество разрешенных символов для ваших этикеток). Это основная идея кодировки Base64 (где N равно 256, а M равно 64).   -  person Joachim Sauer    schedule 08.12.2020

Ответы (2)


arrow_upward
4
arrow_downward

Простым решением было бы сначала преобразовать в шестнадцатеричную кодировку:

  • jrioj4oi3m_=.,ei9# => 6a72696f6a346f69336d5f3d2e2c65693923

а затем перевести любые числа в нешестнадцатеричные буквы:

  • 6a72696f6a346f69336d5f3d2e2c65693923 => waxswzwfwatuwfwzttwdvftdsescwvwztzst

Таким образом, выходная строка всегда будет ровно в два раза длиннее входной строки и всегда будет содержать только символы в диапазоне от a до z.

Это может быть легко достигнуто в python следующим образом:

>>> enc = str.maketrans('0123456789', 'qrstuvwxyz')
>>> dec = str.maketrans('qrstuvwxyz', '0123456789')
>>> s = 'jrioj4oi3m_=.,ei9#'
>>> x = s.encode('ascii').hex().translate(enc)
>>> x
'waxswzwfwatuwfwzttwdvftdsescwvwztzst'
>>> bytes.fromhex(x.translate(dec)).decode('ascii')
'jrioj4oi3m_=.,ei9#'
person ekhumoro    schedule 08.12.2020

arrow_upward
3
arrow_downward

Интересно, что на самом деле это оказывается очень простой и распространенной математической задачей: преобразование базы. Как программист, вы, вероятно, знаете, по крайней мере теоретически, как преобразовывать между представлениями значения по основанию 2, 10 и 16. Существует 96 печатных символов ASCII, поэтому любую строку ASCII можно рассматривать как представление (возможно, очень большого) значения с основанием 96. Если ваша метка принимает только 64 символа (например, прописные, строчные, цифры и 2 других), вам просто нужно преобразовать представление с основанием 96 в представление с основанием 64 того же значения. Декодирование — это просто преобразование вашего представления base 64 обратно в представление base 96.

person Mooing Duck    schedule 08.12.2020