"Записки научных семинаров ПОМИ"
Том 402, стр. 45-68
Эффективное сжатие данных с помощью прямолинейных программ
И. С. Бурмистров, А. В. Козлова, Е. Б. Курпилянский, А. А. Хворост
Уральский федеральный университет,
институт математики и компьютерных наук,
ул. Тургенева 4,
г. Екатеринбург 620000,
Россия
burmistrov.ivan@gmail.com,
voron13e02@gmail.com, DembelZ@yandex.ru, jaamal@mail.ru
- Аннотация: Изучаются два алгоритма построения контекстно свободных
грамматик, выводящих заданный текст. Первый алгоритм является
модификацией известного алгоритма Риттера и строит грамматику на
основе AVL-деревьев, второй алгоритм использует декартовы деревья.
Описываются результаты экспериментов по сравнению эффективности этих
двух алгоритмов и алгоритма Риттера на различных наборах данных и по
сравнению алгоритмы построения грамматик с алгоритмами из семейства
алгоритмов Лемпеля-Зива по степени сжатия. Библ. -- 15 назв.
- Ключевые слова: прямолинейные программы, грамматическое сжатие, AVL-деревья,
декартовы деревья
[straight-line program, LZ-compression, AVL-tree, Cartesian tree]
Полный текст(.pdf)