logo标签列表

将一组数字压缩或编码成单个字母数字字符串的最佳方法是什么？

algorithmstringencoding
8
什么是将任意长度和大小的数字列表压缩或编码为单个字母数字字符串的最佳方法？
目标是能够将像1、5、8、3、20、212、42这样的内容转换为像a8D1jN这样的内容，用于URL，然后再转换回1、5、8、3、20、212、42。
对于结果字符串，我可以接受任何数字和ASCII字母，包括小写和大写字母，因此：0-9a-zA-Z。我希望没有任何标点符号。
允许字符的范围是什么？a-z，0-9？假设标点符号和大小写差异不在考虑范围内？ - Michael Petrotta
@Michael：我已经更新了问题以进行说明。 - pupeno
“Best” 在哪方面是最好的？“d1d5d8…” 和 “…x14xD4x2A” 一样难以解释 - 哦，看看 Jens Schauder 的回答。 - greybeard
7个回答
5
如果您将列表视为字符串，则有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]
3
你可以使用像Base64这样的编码方案。

在多种编程语言中，都有常见的Base64模块或库。

Base64 会转换成大小写字母 - 这可能不是 OP 想要的。Base36 更接近，但在大多数框架中缺乏内置实现。 - Michael Petrotta
我对大小写不在意。我不确定的是我是否应该只使用逗号作为分隔符；如果用二进制来思考，似乎有些浪费，但我可能是错的。 - pupeno
如果数字的大小不全相同，则需要逗号。如果它们是相同大小的，则使用额外的空格表示较小的数字。例如，“1”作为字符占用一个字节的空间，但作为数字占用4个字节的空间。 - Telavian
3

不要使用逗号将数字分隔，而是可以进行简单的编码，将每个数字的最后一位替换为'a'+数字。所以，你的列表[1,5,8,3,20,212,42] 将变成神秘的样子bfid2a21c4c。 :)

只有在数字很少的情况下，才会使用这样的方法，因为压缩无法大幅缩短字符串。如果我们需要处理大量数字，可以尝试对数据进行某种形式的压缩 + base64 编码。

1
我喜欢这个想法，简单而优雅。 - Bob
1

根据数字范围的不同，一个简单的字典压缩方案可能会起作用。

考虑到您的编辑和估计有10k行数据，一个字典方案可以将每个数字映射到一个[A-Za-z0-9]三元组，这样可以为62*62*62个不同的条目创建唯一的映射。

这些数字是数据库中的ID；我不确定它是否构成了一个合理的范围（我不指望它会增长很多，绝对不会超过10k），我会研究一下字典压缩。谢谢。 - pupeno
0

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

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

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

对于每个组合（i j），gcd(Ni Nj) = 1。

CRT（中国剩余定理）告诉我们如何找到满足这些方程的最小数 X。

通过这种方式，您可以将数字 a1...ak 编码为 X，并保持 N 的列表固定。每个 Ni 必须大于 ai，相当重要。

0

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

有许多可供选择。

常见的编码或压缩算法是什么意思？ - pupeno
我现在能想到的是BZip、GZip和Deflate。 - Telavian
对于小序列，由于头部和哈希表，这些算法往往会显著增加数据的大小。对于英文文本字符串，有一个很好的例子叫做smaz。对于数字，它可能更为复杂，因为数字127占用1个字节，但unicode字符串“127”却占用6个字节。你不能在普遍情况下从什么中得到什么，但如果你的数据具有可预测的格式，那么它的构造规则可以被用来创建一个可以压缩的子集。 - Bob
0

“最好”的选择取决于您的标准。

如果“最好”意味着“简单”：只需将数字用固定字符分隔连接在一起：

1a5a8a3a20a212a42

这也应该是“快速”的。

如果您希望生成的字符串“小巧”，可以通过某些压缩算法（如zip）运行上述字符串，然后再通过某些编码（如base64或类似编码）运行结果。

2
我认为使用zip和base64都会使这个字符串变长。 - Bob
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接