使用字节移位解码编码的最佳方法

Question

我的问题是如果信息可能在过程中丢失，如何检索原始字符串。我正在审查一个使用字节转换的编码例程，如下所示：

def encode(string):
    encoded = ''
    for char in string:
        encoded += chr(ord(char) ^ (ord(char) >> 1))
    return encoded

如果向右移动一位我在某些情况下丢失信息，但我正试图想出一种方法来重建原始字符串，使得

def decode(string):
    decoded = ''
    for char in string:
        decoded += ........
    return decoded

因为我丢失了给定字符列表的信息：

In [90]: ord('A') >> 1 << 1
Out[90]: 64

In [91]: ord('B') >> 1 << 1
Out[91]: 66

In [92]: ord('C') >> 1 << 1
Out[92]: 66

是否可以反转编码的字符串？我一直在摸不着头脑，我觉得这可以做到，但我的大脑似乎被困在这里。

Answer 1

查看最高位。它未进行异或或其他修改。所以你知道。第二个最高位是与您已知的最高阶的XOR。

因此，您可以撤消此XOR并获得第二高位。重复此操作直到显示所有位。此外，最低有效位的信息也不会丢失。它仅与第二个LSB进行异或。

我不知道它是否是最有效的方法，但我会用eb对编码的字节（让我们命名为eb >> 1）进行异或。

结果是

eb2 = eb ^ eb >> 1 # == char ^ char >> 2（意思是char在这里作为字节值）

然后

eb3 = eb2 ^ eb2 >> 2 # == char ^ char >> 4
eb4 = eb3 ^ eb3 >> 4 # == char ^ char >> 8

对于一个字节char >> 8 == 0因此eb4 == char。

Answer 2

迈克尔的答案证明了这是可能的，这是一个微不足道的，可能很快的方法，使用反向查找表（这里只做ASCII）：

def decode(string):
    return string.translate({i ^ i>>1: i for i in range(128)})

演示：

>>> encode('StackOverflow')
'zNQR^hMWKUZXL'
>>> decode(encode('StackOverflow'))
'StackOverflow'

并且一个微不足道的实验证明它有效：

>>> len({i ^ i>>1 for i in range(128)})
128

128个可能的输入导致128个不同的输出，因此没有两个不同的字符被编码为相同的字符，因此可以反转该过程。