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

Я пишу преобразование Берроуза-Уилера и его обратное на 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

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

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

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

Декодированная строка:

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

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

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

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


python compression inverse-transform burrows-wheeler-transform
person cabralpinto    schedule 22.12.2019    source источник

Ответы (2)


arrow_upward
0
arrow_downward

Нашел ответ! Этот алгоритм основан на предположении, что строка объединяется с одним последним символом, который уникален и лексикографически меньше любого другого символа в строке. Однако, поскольку я намереваюсь использовать любое значение в диапазоне 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

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

person cabralpinto    schedule 22.12.2019

arrow_upward
0
arrow_downward

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

person Angie    schedule 18.09.2020