Преобразование Барроуза-Уиллера (BWT) повторяющаяся строка

Question

Я пишу преобразование Барроуза-Уиллера и его обратное на Python. Он отлично работает для небольших струн, но развалился, когда я тестировал струны большего размера. Иногда кажется, что струна зацикливается. Я уверен, что это должно быть связано с последним циклом декодера, но я следую шагам, которые можно найти на нескольких веб-сайтах. Моя реализация выглядит следующим образом:

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

Исходная строка:

Не желая навязываться на княжну, Роств не вернулся в дом, а остался в деревне в ожидании ее отъезда. Когда ее экипаж выехал из дома, он сел на нее и сопровождал ее в восьми милях от Богучрово до того места, где дорога была занята нашими войсками. В гостинице в Янкво он почтительно простился с ней, впервые позволив себе поцеловать ее руку.

Как ты можешь так говорить! он покраснел, отвечал принцессе Марис на выражения благодарности за ее избавление, как она назвала то, что произошло. Любой полицейский сделал бы столько же! "Если бы у нас были только крестьяне, мы бы не позволили врагу зайти так далеко", - сказал он с чувством стыда и, желая сменить тему. Я только рад возможности познакомиться с вами. До свидания, принцесса. Желаю вам счастья и утешения и надеюсь снова встретиться с вами в более счастливых обстоятельствах. Если ты не хочешь заставить меня покраснеть, пожалуйста, не благодари меня!

Расшифрованная строка:

Не желая навязываться на княжну, Роств не вернулся в дом, а остался в деревне в ожидании ее отъезда. Когда ее экипаж выехал из дома, он сел на нее и сопровождал ее в восьми милях от Богучрово до того места, где дорога была занята нашими войсками. В гостинице в Янкво он почтительно простился с ней, впервые позволив себе поцеловать ее руку.

Как можно так говорить! Не желая навязываться на княжну, Роств не вернулся в дом, а остался в деревне в ожидании ее отъезда. Когда ее экипаж выехал из дома, он сел на нее и сопровождал ее в восьми милях от Богучрово до того места, где дорога была занята нашими войсками. В гостинице в Янкво он почтительно простился с ней, впервые позволив себе поцеловать ее руку.

Как можно так говорить! Не желая навязываться на княжну, Роств не вернулся в дом, а остался в деревне в ожидании ее отъезда. когда

Как ни странно, похоже, что это происходит с другими реализациями, которые я нашел в Интернете и протестировал, например, этот и этот. Что здесь происходит? Я неправильно понял, как работает преобразование? Или это некорректная реализация?

Answer 1

Нашел ответ! Этот алгоритм основан на предположении, что строка объединена с одним конечным символом, который уникален и лексикографически меньше любого другого символа в строке. Однако, поскольку я намерен использовать любое значение в диапазоне 0-255 для любого данного символа, в моем распоряжении нет дополнительных символов. К счастью, благодаря Джону Курлаку и некоторым дополнительным исправлениям ошибок я смог немного изменить свою первоначальную реализацию, чтобы учесть этот факт. Вот:

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

Спасибо, Джон!

Answer 2

Я столкнулся с той же проблемой с алгоритмом сортировки BWT в C++, благодаря вашему комментарию я быстро исправил ее, используя 16-битный массив вместо 8-битного, чтобы разрешить значение выше 0xFF (255) для последнего символа (также пришлось изменить BWT код алгоритма сортировки немного, чтобы он принимал 16-битные данные). Теперь он отлично работает, спасибо.