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