Эффективно ли применять преобразование длины прогона после перемещения к переднему преобразованию и BWT?
Я новичок в кодировании, поэтому я пытаюсь понять основы. Я наткнулся на документ, описывающий технику сжатия текста без потерь, и в этом документе была фигура, иллюстрирующая, как работает их сжатие. Это работает так:
Source -> BWT -> MTF -> RLT -> Proprietary Entropy Encoder
Я не понимаю, почему они используют Преобразование по длине прогона после "Переместить в переднее преобразование", мне это не кажется эффективным. Насколько я понимаю, MTF сам не производит много запусков, и поэтому было бы бесполезно использовать послесловия RLT.
Некоторое объяснение будет высоко ценится!
2 ответа
Это не эффективно.
Это, вероятно, старая статья о BWT. В то время использование RLE (кодировщик длин серий) было обычной уловкой для повышения скорости. RLE, кстати, использовался не только после BWT, но и до того, чтобы ускорить стадию BWT. Та же логика может применяться к энтропийному кодеру, но вряд ли она принесет столько же пользы.
В настоящее время этот трюк полностью устарел. До BWT вы могли бы найти некоторую предварительную обработку LZP, особенно для совпадений на большие расстояния (помимо размера блока), с примерно таким же намерением, что и RLE в отношении повышения скорости, но более мощным. MTF также полностью заменен, так как он слишком загружен процессором и не так эффективен по стоимости.
Целью MTF после BWT является сокращение диапазона символов, что хорошо для энтропийного кодирования. MTF заменяет символы с их рангом, который обычно мал из-за повторений, генерируемых BWT. Кодирование нулевой длины может применяться после этого, поскольку MTF может генерировать много нулей (это просто конкретный случай RLE, где только серии нулей кодируются по длине).
Посмотрите на https://code.google.com/p/kanzi/ примеры реализации. Вы можете запустить BlockCompressor с блочным кодеком с MTF+ZLE или без него.