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