Сортировка повернутых строк алгоритма преобразования Уилера Барроуза (BWT)

Question

В настоящее время я работаю с BWT для развлечения.: -)

Я изучил BWT и думаю, что BWT теоретически не сложен.Но до сих пор я не знаю, как на самом деле сортировать повернутые строки в реальной реализации.

Должен ли я сначала хранить все повернутые строки в массиве, чтобы можно было сортировать их, используя алгоритм наивной сортировки, такой как Bubble SortВыбор или другие?Кто-то сказал мне, что это плохая практика, поскольку для сохранения N элементов в массиве требуется больше раз.

Итак, как мне отсортировать мои повернутые строки во время их вращения?

Кто-нибудькто может ответить на это, будет очень признателен!

Заранее спасибо!

Томпсон

Answer 1

BWT довольно прост в реализации, но его слабость в том, что он становится медленнее по мере того, как сжимаемые данные становятся больше.

Я провел небольшой анализ этого алгоритма, и в результате получается (поправьте меня, если я ошибаюсь) в худшем случае требуется O (n ^ 2), но в лучшем случае может достичь постоянного времени.

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

Хорошо, когда вы кодируете данные, используя BWT, первое, что вы должны сделать, это поместить уникальный символ в данные.Он используется, чтобы сообщить кодировщику, что он завершил процесс сортировки, когда находит этот символ.Например: скажем, что вы хотите сжать строку «BANANA» и шаги:

BANANA $ ANANA $ B NANA $ BA ANA $ BAN NA $ BANA A $ BANAN $ BANANA

Поворотstrings: $ BANANA

Сортировка строки с уникальным символом (EOF), например "$ BANANA", будет быстрее, чем без использования какого-либо уникального символа.

Я опубликовал плохую статью оэтот алгоритм ...

http://philipstel.wordpress.com/2010/02/10/discussion-of-burrows-wheeler-transform-algorithm/

Answer 2

Не совсем ответ, но когда я реализовал алгоритм BWT для клиента, я использовал код, представленный здесь в качестве основы.

Один элемент исторической заметки, похоже, что C qsort был намного быстрее, чем алгоритм C ++ std :: sort. Кто-то из CodeGuru предложил использовать std :: stable_sort, и это подняло производительность до уровня C qsort. Это было в VC6.

Также запустите тесты, чтобы найти идеальную длину строки - сортировка не является линейной. Я писал процедуру сжатия для протокола передачи, поэтому сжатие должно было быть достаточным, чтобы окупить себя. Если память мне не изменяет, на 733 МГц машина работала около 4 КБ.