ЭФФЕКТИВНЫЙ АЛГОРИТМ СЖАТИЯ С ПОМОЩЬЮ ПРЕОБРАЗОВАНИЯ ДАННЫХ СЛОВАРНОГО ТИПА

Рассматривается задача эффективного сжатия без потерь для данных словарного типа. Для таких данных алгоритм кодирования основан на использовании словаря, формируемого по тексту, поступающему для сжатия. Известно также, что предварительная обработка данных, например, BWT-преобразование, может улучшить коэффициент сжатия текста. В данной работе предлагается эффективный алгоритм сжатия данных словарного типа, основанный на модификации BWT-преобразования. Приведены экспериментальные результаты, подтверждающие увеличение степени сжатия данных предложенным алгоритмом по сравнению с классическим архиватором.

Список литературы

1. Burrows M. A block sorting lossless data compression algorithm // M. Burrows, D. Wheeler. Technical Report 124, Digital Equipment Corporation, 1994. 18 pages.
2. Рябко Б. Я. Data compression by means of a «book stack» // Problems of Information Transmission. 1980, V. 16: (4). P. 265–269.\
3. Хмелев Д. В. Преобразование Барроуза-Уилера, массив суффиксов и сжатие словарей // Все о сжатии данных, изображений и видео: сайт. [Эл. Рес.]: http://compression.ru/download/ articles/bwt/khmelev_2003_bwt.pdf.
4. Bell T. C., Cleary J. H., Witten I. H. Text compression // T. C. Bell, J. H. Cleary, I. H. Witten, Prentice Hall. Englewood Cliffs, 1990. С. 318.
5. K¨arkk¨ainen J., Sanders P. Simple linear work suffix array construction // In 30th International Colloquium on Automata, Languages and Programming, number 2719 in LNCS. 2003. С. 943–95