@agaliullin
CEO & Founder of Futureinapps, LLC

Наиболее эффективная реализация алгоритмов преобразования BWT и MTF?

BWT (Burrows-Wheeler Transform) и MTF (Move-to-Front) очень интересные алгоритмы преобразования информации перед сжатием. Эффективно подходят для текстовых данных. Знаете ли вы интересные реализации данных алгоритмов (!проверенные), на любом языке программирования. И в связки с каким алгоритмом сжатия вы бы применили данные преобразования?
P.S.: особенно интересна реализация на Node.js
  • Вопрос задан
  • 918 просмотров
Пригласить эксперта
Ответы на вопрос 2
2ord
@2ord
Насчёт более эффективной не знаю, но Mark Nelson полагает (1996), что данная схема достаточно эффективна:
RLE input-file | BWT | MTF | RLE | ARI > output-file

A brief description of each of the programs follows:
RLE.CPP This program implements a simple run-length encoder. If the input file has many long runs of identical characters, the sorting procedure in the BWT can be degraded dramatically. The RLE front end prevents that from happening.
BWT.CPP The standard Burrows-Wheeler transform is done here. This program outputs repeated blocks consisting of a block size integer, a copy of L, the primary index, and a special last character index. This is repeated until BWT.EXE runs out of input data.
MTF.CPP The Move to Front encoder operates as described in the previous section.
RLE.CPP The fact that the output file is top-heavy with runs containing zeros means that applying another RLE pass to the output can improve overall compression. I believe that further processing of the MTF output will provide fertile ground for additional improvements.
ARI.CPP This is an order-0 adaptive arithmetic encoder, directly derived from the code published by Witten and Cleary in their 1987 CACM article.

marknelson.us/1996/09/01/bwt
К статье также прилагаются исходные тексты программ на Си++.

А есть исходники BWT и MTF на JS: https://gist.github.com/SKAhack/14b2dfc4208349f00799
Ответ написан
Комментировать
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
Вот тут посмотрите: https://stackoverflow.com/questions/7857674/whats-...

Идея - построить суффиксный массив (что почти тоже самое, что BWT). Там рекомендуют libdivsufsort. Вроде как, его можно использовать и в node.js: https://www.npmjs.com/package/divsufsort
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Похожие вопросы