Как лучше всего сжимать или кодировать список чисел в одну буквенно-цифровую строку?

Question

Как лучше всего сжимать или кодировать список чисел произвольной длины и размеров в одну буквенно-цифровую строку?

Цель состоит в том, чтобы иметь возможность преобразовать что-то вроде 1,5,8,3,20,212,42 в нечто вроде a8D1jN для использования в URL, а затем обратно в 1,5,8,3,20,212,42 .

Для полученной строки я в порядке с любым числом и любым символом ascii, строчными и прописными, поэтому: 0-9a-zA-Z. Я предпочитаю не иметь пунктуации вообще.

ОБНОВЛЕНИЕ : добавлено примечание о том, какие символы хороши.

Answer 1

Если вы рассматриваете свой список как строку, то у вас есть 11 различных символов для кодирования (0-9 и запятая).Это может быть выражено в 4 битах.Если вы хотите добавить, скажите $ и!к вашему списку допустимых символов, тогда у вас будет 64 различных выходных символа, и, следовательно, вы сможете закодировать 6 бит на символ.

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

Таким образом, вы можете перекодировать ряд чисел [1,5,8,3,20,212,42] в строку "gLQfoIcIeQqq".

ОБНОВЛЕНИЕ: Я был вдохновлен и написал решение для Python для этого решения (не быстро, но достаточно функционально ...)

ZERO = ord('0')
OUTPUT_CHARACTERS = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789$!"

def encode(numberlist):

    # convert to string -> '1,5,8,3,20,212,42'
    s = str(numberlist).replace(' ','')[1:-1]

    # convert to four bit values -> ['0010', '1011', '0110', ... ]
    # (add 1 to avoid the '0000' series used for padding later)
    four_bit_ints = [0 <= (ord(ch) - ZERO) <= 9 and (ord(ch) - ZERO) + 1 or 11 for ch in s]
    four_bits = [bin(x).lstrip('-0b').zfill(4) for x in four_bit_ints]

    # make binary string and pad with 0 to align to 6 -> '00101011011010111001101101...'
    bin_str = "".join(four_bits)
    bin_str = bin_str + '0' * (6 - len(bin_str) % 6)

    # split to 6bit blocks and map those to ints
    six_bits = [bin_str[x * 6 : x * 6 + 6] for x in range(0, len(bin_str) / 6)]
    six_bit_ints = [int(x, 2) for x in six_bits]

    # map the 6bit integers to characters
    output = "".join([OUTPUT_CHARACTERS[x] for x in six_bit_ints])

    return output

def decode(input_str):

    # map the input string from characters to 6bit integers, and convert those to bitstrings
    six_bit_ints = [OUTPUT_CHARACTERS.index(x) for x in input_str]
    six_bits = [bin(x).lstrip('-0b').zfill(6) for x in six_bit_ints]

    # join to a single binarystring
    bin_str = "".join(six_bits)

    # split to four bits groups, and convert those to integers
    four_bits = [bin_str[x * 4 : x * 4 + 4] for x in range(0, len(bin_str) / 4)]
    four_bit_ints = [int(x, 2) for x in four_bits]

    # filter out 0 values (padding)
    four_bit_ints = [x for x in four_bit_ints if x > 0]

    # convert back to the original characters -> '1',',','5',',','8',',','3',',','2','0',',','2','1','2',',','4','2'
    chars = [x < 11 and str(x - 1) or ',' for x in four_bit_ints]

    # join, split on ',' convert to int
    output = [int(x) for x in "".join(chars).split(',') if x]

    return output


if __name__ == "__main__":

    # test
    for i in range(100):
        numbers = range(i)
        out = decode(encode(numbers))
        assert out == numbers

    # test with original series
    numbers = [1,5,8,3,20,212,42]
    encoded = encode(numbers)
    print encoded         # prints 'k2UBsZgZi7uW'
    print decode(encoded) # prints [1, 5, 8, 3, 20, 212, 42]

Answer 2

Вы можете использовать схему кодирования, например Base64.

Base64 модули или библиотеки распространены на нескольких языках программирования.

Answer 3

Вместо того, чтобы разделять числа запятыми, вы можете сделать простую кодировку, в которой вы заменяете последнюю цифру каждого числа на цифру «а» +.Таким образом, ваш список [1,5,8,3,20,212,42] станет загадочным bfid2a21c4c.:)

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

Answer 4

Зависит от диапазона чисел - с разумным диапазоном может работать простая схема сжатия словаря .

Учитывая ваше редактирование и оценку 10 тыс. Строк, словарная схема, в которой каждое число сопоставлено с тройкой [A-Za-z0-9], может быть уникальной для 62 * 62 * 62 различных записей.

Answer 5

Вы также можете использовать китайскую теорему об остатках.

Идея состоит в том, чтобы найти число X такое, что

X = a1 mod n1
X = a2 mod n2
...
X = ak mod nk

gcd (Ni Nj) = 1 для каждой комбинации (i j).

CRT говорит, как найти наименьшее число X, которое удовлетворяет этим уравнениям.

Таким образом, вы можете закодировать числа a1 ... ak как X и сохранить список Ns фиксированным. Каждый Ni должен быть больше, чем ai, именно так.

Answer 6

«лучший» зависит от ваших критериев.

Если лучше всего означает простой : просто объедините числа, разделенные фиксированным символом:

1a5a8a3a20a212a42

Это также должно быть быстро

Если вы хотите, чтобы результирующая строка была small , вы можете запустить приведенную выше строку через некоторый алгоритм сжатия, такой как zip, а затем результат через некоторую кодировку, например base64 или аналогичную.

Answer 7

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

Существует множество доступных для выбора.