将数字列表压缩或编码为单个字母数字字符串的最佳方法是什么？

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

您可以进行简单的编码，用“a”+数字替换每个数字的最后一位数字，而不是用逗号分隔数字。因此，您的列表[1,5,8,3,20,212,42]将变得神秘起来bfid2a21c4c。 :)

仅当有少量数字时我才会使用类似的东西，其中压缩无法大大缩短字符串。如果它是我们正在讨论的很多数字，您可以尝试对数据执行某种压缩 + Base64 编码。

Answer 4

取决于数字的范围——在合理的范围内，简单的字典压缩方案就可以工作。

考虑到您对 10k 行的编辑和估计，每个数字映射到 [A-Za-z0-9] 的三元组的字典方案对于 62*62*62 不同的条目来说可能是唯一的。

Answer 5

可能有一个超级酷且高效的算法适合您的情况。然而，一个非常简单、经过测试且可靠的算法是对逗号分隔的数字字符串使用“通用”编码或压缩算法。

有很多可供选择。

Answer 6

“最好”取决于您的标准是什么。

如果最好的意思是简单：只需将数字串在一起并用固定字符分隔：

1a5a8a3a20a212a42

这也应该快速

如果您希望结果字符串小， em>，您可以通过某种压缩算法（如 zip）运行上面的字符串，然后通过某种编码（如 base64 或类似算法）运行结果。

Answer 7

您也可以使用中国剩余定理。

这个想法是找到一个数字 X，使得

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

每个组合 (ij) 的 gcd(Ni Nj)=1。

CRT 说明了如何找到满足这些方程的最小数 X。

像这样，您可以将数字 a1...ak 编码为 X，并保持 N 的列表固定。每个 Ni 必须大于 ai，确实如此。