Steklov Institute of Mathematics at St.Petersburg

PREPRINT 23/2006


Юрий Лифшиц

АЛГОРИТМИЧЕСКИЕ СВОЙСТВА СЖАТЫХ ТЕКСТОВ

This preprint was accepted December 16, 2006

ABSTRACT:
Можно ли эффективно (не проводя полную распаковку) изучать различные
свойства сжатых текстов? В работе мы рассматриваем три фундаментальных
задачи: (1) проверить равенство двух сжатых текстов, (2) определить, является ли
один сжатый текст подстрокой другого и (3) найти количество несовпадающих
символов (расстояние по Хэммингу)
у двух сжатых текстов одинаковой длины.

В работе построен алгоритм, решающий задачу о равенстве за
O(n^3), а задачу поиска подстрок --- за O(n^2m) шагов. Здесь
n --- размер архива текста, m --- размер архива шаблона. Мы также
доказали, что очень близкая по формулировке задача (3) оказалась
#P-полной. Алгоритмическая техника, которую мы применили для
задач (1) и (2), также позволяет вычислять комбинаторные свойства
сжатых текстов, такие как длина минимального периода и накрытия.

Завершает работу список открытых проблем по алгоритмам на сжатых
текстах, их применению к мультимедиа-поиску, архивированию
структур данных и верификации программ.
[Full text:
(.ps.gz)]


Back to all preprints
Back to the Steklov Institute of Mathematics at St.Petersburg