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

Анотація

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