Сжать последовательность из 1 и 0 в кратчайшую возможную строку ASCII

Question

Как вы могли бы преобразовать серию 1 с и 0 с в максимально короткую форму, состоящую из безопасных символов ascii URL?

например,

s = '00100101000101111010101'
compress(s)

В результате чего-то вроде:

Ysi8aaU

И, очевидно:

decompress(compress(s)) == s

(Iзадайте этот вопрос чисто из любопытства)

Answer 1

Вот решение, которое я придумал (+ слишком много комментариев):

# A set of 64 characters, which allows a maximum chunk length of 6 .. because
# int('111111', 2) == 63 (plus zero)
charset = 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789-_'

def encode(bin_string):
    # Split the string of 1s and 0s into lengths of 6.
    chunks = [bin_string[i:i+6] for i in range(0, len(bin_string), 6)]
    # Store the length of the last chunk so that we can add that as the last bit
    # of data so that we know how much to pad the last chunk when decoding.
    last_chunk_length = len(chunks[-1])
    # Convert each chunk from binary into a decimal
    decimals = [int(chunk, 2) for chunk in chunks]
    # Add the length of our last chunk to our list of decimals.
    decimals.append(last_chunk_length)
    # Produce an ascii string by using each decimal as an index of our charset.
    ascii_string = ''.join([charset[i] for i in decimals])

    return ascii_string

def decode(ascii_string):
    # Convert each character to a decimal using its index in the charset.
    decimals = [charset.index(char) for char in ascii_string]
    # Take last decimal which is the final chunk length, and the second to last
    # decimal which is the final chunk, and keep them for later to be padded
    # appropriately and appended.
    last_chunk_length, last_decimal = decimals.pop(-1), decimals.pop(-1)
    # Take each decimal, convert it to a binary string (removing the 0b from the
    # beginning, and pad it to 6 digits long.
    bin_string = ''.join([bin(decimal)[2:].zfill(6) for decimal in decimals])
    # Add the last decimal converted to binary padded to the appropriate length
    bin_string += bin(last_decimal)[2:].zfill(last_chunk_length)

    return bin_string

Итак:

>>> bin_string = '000111000010101010101000101001110'
>>> encode(bin_string)
'hcQOPgd'
>>> decode(encode(bin_string))
'000111000010101010101000101001110'

И вот оно в CoffeeScript:

class Urlify
    constructor: ->
        @charset = 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789-_'

    encode: (bits) ->
        chunks = (bits[i...i+6] for i in [0...bits.length] by 6)
        last_chunk_length = chunks[chunks.length-1].length
        decimals = (parseInt(chunk, 2) for chunk in chunks)
        decimals.push(last_chunk_length)
        encoded = (@charset[i] for i in decimals).join('')

        return encoded

    decode: (encoded) ->
        decimals = (@charset.indexOf(char) for char in encoded)
        [last_chunk_length, last_decimal] = [decimals.pop(), decimals.pop()]
        decoded = (('00000'+d.toString(2)).slice(-6) for d in decimals).join('')
        last_chunk = ('00000'+last_decimal.toString(2)).slice(-last_chunk_length)
        decoded += last_chunk

        return decoded

Answer 2

Как один из упомянутых комментариев, использование base64, вероятно, будет правильным решением.Тем не менее, вы не хотите вставлять двоичный файл без некоторого преобразования.

Два параметра сначала преобразуют в int, а затем упаковывают:

import base64

s = '0110110'
n = int(s, 2)

result = base64.urlsafe_b64encode(str(n)).rstrip('=')

Другой вариант - использовать структурумодуль для упаковки значения в двоичный формат и использования этого.(Код ниже от http://www.fuyun.org/2009/10/how-to-convert-an-integer-to-base64-in-python/)

import base64
import struct

def encode(n):
  data = struct.pack('<Q', n).rstrip('\x00')
  if len(data)==0:
    data = '\x00'
  s = base64.urlsafe_b64encode(data).rstrip('=')
  return s

def decode(s):
  data = base64.urlsafe_b64decode(s + '==')
  n = struct.unpack('<Q', data + '\x00'* (8-len(data)) )
  return n[0]

Answer 3

Я бы преобразовал 8 из этих 0 и 1 в байты, используя таблицу поиска, а затем закодировал бы эти байты с помощью base64.