1

我正在用 Python 编写 Burrows-Wheeler 变换及其反向函数。它适用于小弦，但当我测试更大的弦时它就崩溃了。在某些时候，字符串似乎循环了。我确信它一定与解码器的最终循环有关，但我正在遵循在多个网站上找到的步骤。我的实现如下：

class BurrowsWheelerTransform:

    def __init__(self, data):
        self.data = data

    def transform(self):
        # get data size
        size = len(self.data)
        # get order (by index) of rotations
        order = sorted(range(size), key=lambda i: self.data[i:])
        # get index of original rotation
        index = order.index(0)
        # return size appended with last column of (imaginary) rotation table
        return chr(255) * (index // 255) + chr(index % 255) + ''.join(self.data[(i - 1 + size) % size] for i in order)

    def restore(self):
        # get index of end of index
        eoi = next(i for i in range(len(self.data)) if ord(self.data[i]) < 255)
        # get index
        index = 255 * eoi + ord(self.data[eoi])
        # get tranformed content
        content = self.data[eoi + 1:]
        # get lshift array
        lshift = [i - 1 for symbol in sorted(set(content)) for i, x in enumerate(self.data) if x == symbol]
        # restore
        restored = ''
        for i in range(len(content)):
            index = lshift[index]
            restored += content[index]
        # return restored
        return restored

原始字符串：

罗斯托夫不愿对公主出言不逊，没有回屋子，而是留在村子里等她离开。当她的马车驶出房子时，他骑马陪她从博古赫罗沃出发八英里，到达我们部队占领的道路。在扬克沃的客栈里，他恭敬地告别了她，这是他第一次允许自己亲吻她的手。

你怎么可以这样说话！他红着脸回答玛丽公主对她的解脱表示感谢，正如她所说的那样。任何警察都会这样做！“如果我们只有农民打，我们就不应该让敌人走这么远，”他羞愧地说道，并希望转移话题。我很高兴有机会结识你。再见，公主。祝你幸福和安慰，并希望在更幸福的情况下再次见到你。如果你不想让我脸红，请不要感谢我！

解码字符串：

罗斯托夫不愿对公主出言不逊，没有回屋子，而是留在村子里等她离开。当她的马车驶出房子时，他骑马陪她从博古赫罗沃出发八英里，到达我们部队占领的道路。在扬克沃的客栈里，他恭敬地告别了她，这是他第一次允许自己亲吻她的手。

你怎么能这样说话！罗斯托夫不愿在公主面前出言不逊，没有回屋子，而是留在村子里等着她离开。当她的马车驶出房子时，他骑马陪她从博古赫罗沃出发八英里，到达我们部队占领的道路。在扬克沃的客栈里，他恭敬地告别了她，这是他第一次允许自己亲吻她的手。

你怎么能这样说话！罗斯托夫不愿在公主面前出言不逊，没有回屋子，而是留在村子里等着她离开。什么时候

奇怪的是，我在网上找到并测试过的其他实现似乎也会发生这种情况，比如this one和this one。到底是怎么回事？我是否误解了转换的工作原理？或者这个实现不正确？

4

2 回答 2

0

找到了答案！该算法基于字符串连接到一个最终字符的假设，该字符是唯一的并且在字典上小于字符串中的任何其他字符。但是，由于我打算对任何给定字符使用 0-255 范围内的任何值，因此我无法使用额外的符号。幸运的是，多亏了 John Kurlak和一些额外的错误修复，我已经能够稍微修改我的初始实现来解决这个事实。这里是：

class BurrowsWheelerTransform:

    def __init__(self, data):
        self.data = data

    def transform(self):
        # get data size
        size = len(self.data)
        # get doubled string
        self.data *= 2
        # get order (by index) of rotations
        order = sorted(range(size), key=lambda i: self.data[i:])
        # get index of original rotation
        index = order.index(0)
        # return index appended with last column of (imaginary) rotation table
        return chr(255) * (index // 255) + chr(index % 255) + ''.join(self.data[(i - 1 + size) % size] for i in order)

    def restore(self):
        # get index of end of index
        eoi = next(i for i in range(len(self.data)) if ord(self.data[i]) < 255)
        # get index
        index = 255 * eoi + ord(self.data[eoi])
        # get tranformed content
        content = self.data[eoi + 1:]
        size = len(content)
        # get lshift array
        lshift = [i for symbol in sorted(set(content)) for i, x in enumerate(content) if x == symbol]
        # restore
        restored = ''
        for i in range(size):
            index = lshift[index]
            if index >= size: break
            restored += content[index]
        # return restored
        return restored

谢谢，约翰！

于 2019-12-22T21:44:14.317 回答
0

我在 C++ 中使用 BWT 排序算法遇到了同样的问题，感谢您的评论，我很快通过使用 16 位数组而不是 8 位来修复它，以允许最后一个字符的值高于 0xFF（255）（也必须修改 BWT稍微排序算法代码以使其接受 16 位数据）。现在完美运行，谢谢。

于 2020-09-18T18:08:41.480 回答