Ємнісно-часова оптимізація у стисканні природномовних текстів

Anatoly Anisimov; Igor Zavadskyi

Anatoly Anisimov Doctor of Physical and Mathematical Sciences, professor, Taras Shevchenko National University of Kyiv, 4d Glushkov Ave., 03022, Kyiv, Ukraine
Igor Zavadskyi Doctor of Physical and Mathematical Sciences, associate professor, Taras Shevchenko National University of Kyiv, 4d Glushkov Ave., 03022, Kyiv, Ukraine

Ключові слова: word-based; compression; archiver; code; multi-delimiter

Анотація

У роботі розглянуто різноманітні аспекти оптимізації методів стискання природномов-них текстів за ємністю та часом. Визначено новий клас стискальних кодів змінної довжи-ни з кількома роздільниками — реверсні мультироздільникові коди (РМР). Вони є синхроні-зовними, дають можливість виконувати швидкий пошук типу Бойера-Мура у стиснутому файлі й водночас забезпечують найкращий коефіцієнт стискання серед кодів описаного типу. Як засіб передобробки тексту ці коди покращують характеристики найпотужніших сучасних архіваторів. Також було запропоновано надшвидкий алгоритм декодування РМР-кодів, що працює майже з тією самою швидкістю, що й декодування (s,c)-щільних кодів і в рази швидше, ніж декодування кодів Фібоначчі. Експерименти свідчать про високу часово-ємнісну ефективність РМР-кодів у стисканні природномовних текстів.

Посилання

A. Apostolico and A. S. Fraenkel. Robust transmission of unbounded strings using Fibonacci representations, IEEE Trans. Inf. Theory, vol. 33, 1987, pp. 238–245.

N. Brisaboa, A. Farina, G. Navarro, and M. Esteller. (s,c)-dense coding: an optimized compression code for natural language text databases, in: Proc. Symposium on String Processing and Information Retrieval, ser. LNCS, no. 2857. SVB, 2003, pp. 122–136.

S. T. Klein and M. Ben-Nissan. On the usefulness of fibonacci compression codes, Computer Journal, vol. 53, no. 6, pp. 701–716, 2010.

A. Anisimov and I. Zavadskyi. Variable-length prefix codes with multiple delimiters, IEEE Transactions Information Theory, vol. 63, no. 5, 2017, pp. 2885–2895.

I. Zavadskyi and A. Anisimov. Reverse multi-delimiter compression codes, in: 2020 Data Compression Conference, 2020, pp. 173–182.