Дистанционное кодирование (DC) BWT

Question

Я пытаюсь написать BWT с помощью программы сжатия Хаффмана с Java. В BWT я хочу реализовать кодирование расстояния (DC). Я ищу несколько примеров, но их не так много.

Я нашел этот пример:

http://www.cs.ucr.edu/~stelo/cpm/cpm07/move_to_front_gagie.pdf

DC начинается с 29 стр. Но это действительно трудно понять, потому что нет комментариев.

Может быть, кто-то реализовал DC или знает теорию, как реализовать его в реальном коде? :)

Я понял ту часть, которая, прежде всего, должна написать, что такое char. Но потом с расстоянием я не понял.

Я отмечаю, что для каждого символа DC находит свое следующее вхождение в последовательности, записывает его в S и выводит расстояние до него. Если вхождения нет, напишите 0.

Спасибо.

Answer 1

Я написал реализацию на Java: http://code.google.com/p/kanzi/source/browse/java/src/kanzi/function/DistanceCodec.java

Вы можете увидеть объяснение алгоритма в начале кода (полный пример). Также взглянем на блочный кодер (он включает в себя BWT + MoveToFront + преобразование нулевой длины + энтропийное кодирование): http://code.google.com/p/kanzi/source/browse/java/src/kanzi/function/BlockCodec.java

Я пытался использовать дистанционное кодирование вместо перемещения вперед. Выход меньше (лучше сжатие) с DC по сравнению с MTFT. Однако после энтропийного кодирования результат обратный: MTFT выглядит более поддающимся энтропийному сжатию.