Какой алгоритм наиболее подходит для преобразования Берроуза-Уилера?

Question

Кажется, многие компрессоры, реализующие BWT, используют его в сочетании с арифметическим кодированием или кодированием Хаффмана. (Не стесняйтесь выдвигать больше, особенно если они лучше.)

Мой первый вопрос: почему словарный кодер, такой как LZW или LZSS, был бы худшим выбором для использования с BWT?

Мой второй вопрос: какой лучший универсальный алгоритм использовать?

Answer 1

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

Но LZ не хуже выбора во многих ситуациях. LZ - это онлайновый алгоритм, который может работать с потоками, а BWT должен работать с большим блоком и стоить много памяти. Декомпрессия LZ очень эффективна, в то время как BWT все еще нужно как минимум 5n дополнительного пространства.

Производительность BWT связана с сортировкой суффиксов. Существует множество практических алгоритмов сортировки суффиксов: MSufSort/DivSufSort/Archon/QSufSort/DeepSwallow и теоретически оптимальных алгоритмов с O(n) -временими: SA-IS / SA-DS.

PS / Если вы пишете компрессор на основе BWT, уделите больше внимания кодированию выходных данных BWT, а не самому BWT, поскольку существует множество практических библиотек для преобразования BWT, и большинство из них используют один и тот же интерфейс. просто используйте один из них в вашем проекте.