Улучшение сжатия данных без потерь посредством перечисления подстрок
An Improvement in Lossless Data Compression via Substring Enumeration
2011-05-01
SCID: 54.1/csdje3rj
Discuss with AI
BZIP2PPMсжатие посредством перечисления подстрокбез потерь сжатие данныхперечисление подстрок
Figures from the paper
Abstract (AI)
В 2010 году Дюбе и Бодуэн предложили новую технику сжатия данных без потерь, называемую сжатием посредством перечисления подстрок (CSE). Экспериментальные результаты показали, что коэффициент сжатия, достигаемый методом CSE, сопоставим с коэффициентами сжатия некоторых из лучших вариантов PPM и BZIP2. Мы усовершенствовали метод CSE, чтобы уменьшить диапазон возможных значений, подлежащих кодированию, и аналитически прояснили характеристики сжатия усовершенствованного метода для некоторых входных строк с нулевой скоростью энтропии. Мы показываем, что характеристики коэффициента сжатия усовершенствованного метода CSE никогда не хуже, чем у исходного метода CSE, для любой исходной строки; при этом временная и пространственная сложность линейны по длине строки.
Key Findings
1
Для любой исходной строки коэффициент сжатия улучшенного CSE никогда не хуже, чем у исходного CSE.
2
В исходных экспериментах CSE демонстрировал коэффициент сжатия, сопоставимый с эффективностью сильных вариантов PPM и BZIP2.
3
Для некоторых входных строк с нулевой скоростью энтропии стало возможным аналитически охарактеризовать эффективность сжатия улучшенного CSE.
4
Улучшенный метод имеет линейную временную и пространственную сложность относительно длины входной строки.
5
В работе усовершенствован метод сжатия посредством перечисления подстрок (CSE) за счёт уменьшения диапазона возможных значений, используемых при кодировании.
Research Object
без потерь сжатие данных посредством перечисления подстрок (CSE) для исходных строк
Research Subject
показатели коэффициента сжатия улучшенного CSE, сокращение диапазона значений-кандидатов и гарантии линейной временной и пространственной сложности, включая строки с нулевой скоростью энтропии
Publication Details
Publication Date
2011-05-01
Journal
Publisher
ISSN
Access Type
Author Information
Download PDF
Subscribe to digest