автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.17, диссертация на тему:Алгоритмы и анализ трудоемкости обработки сжатых текстов

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

На правах рукописи

Лнфшиц Юрий Михайлович

АЛГОРИТМЫ И АНАЛИЗ ТРУДОЕМКОСТИ ОБРАБОТКИ СЖАТЫХ ТЕКСТОВ

05 13 17 — Теоретические основы информатики

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

2 А МАЙ 2007

Санкт-Петербург — 2007

003060116

Работа выполнена в лаборатории математической логики Санкт-Петербургского отделения Математического института им В А Стеклова РАН

Научный руководитель член-корреспондент РАН, профессор

Матиясевич Юрий Владимирович

Официальные оппоненты доктор физико-математических наук,

профессор Романовский Иосиф Владимирович

кандидат физико-математических наук, Шень Александр Ханьевич

Ведущая организация Вычислительный центр

им А А Дородницына Российской академии наук

Защита состоится _____ 2007 г в часов

на заседании диссертационного совета Д 212 232 51 по защите диссертаций на соискание ученой степени доктора наук при Санкт-Петербургском государственном университете но адресу 198504 Санкт-Петербург, Старый Петергоф, Университетский ир , 28

С диссертацией можно ознакомиться в научной библиотеке им М Горького Санкт-Петербургского государственного университета по адресу 199034, Санкт-Петербург, Университетская наб , 7/9

7 X,

Автореферат разослан ' __ 2007 г

Ученый секретарь диссертационного совета, доктор физ -мат наук, профессор

Мартыыенко Б К

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы В последние пятнадцать лег много усилий было направленно на разработку такого представления данных, при котором, по возможности, одновременно минимизируются и размер, и время доступа Одним из наиболее перспективным подходов к этой проблеме является построение алгоритмов поиска в сжатых текстах, которые бы не требовали полной распаковки исходного файла [3, 4, 7, 13, 16, 18] Очень быстро от рассмотрения конкретных алгоритмов архивирования исследователи перешли к общей модели сжатого текста — прямолинейной программе Неформально, прямолинейная программа является грамматикой, которая порождает ровно один текст Оказалось, что тексты, сжатые практическими архиваторами (например LZ77 [22]), быстро и без значительного увеличения размера могут быть переведены в грамматику, описывающую тот же текст [21]

Опишем кратко наиболее важные результаты по обработке текстов представленных в виде прямолинейных программ Задача о равенстве двух сжатых текстов впервые была решена в работе [19] в 1994 году Была доказана оценка 0(пА) на время работы этого алгоритма, где п равно сумме размеров прямолинейных программ, порождающих два сравниваемых текста Ачгорптм для поиска сжатой подстроки в сжатом тексте впервые появился в 1995 году в статье [14] Вслед за этим удалось расширить алгоритм для вычисления различных комбинаторных свойств текста [9] Далее в 1997 году Миязаки Шннохара и Такеда [17] построили алгоритм, требующий 0(п2т2) времени для поиска подстрок, где тип — размеры сжатого шаблона и сжатого текста, соответственно

В то же время, ряд классических текстовых задач до сих пор не был решен в постановке со сжатым представлением входных данных В частности, не было предчожено ни одного алгоритма поиска подпоследовательностей напрямую в сжатом тексте Определение вложимости сжатого шаблона в сжатый текст могло оказаться как решаемым за полиномиальное

время, так и РБРАСЕ-полной задачей Также, оставалась неизвестной сложность вычисления расстояния Хэмминга между сжатыми текстами Эгот вопрос является самой простой формой приближенного поиска подстрок, который полезен для анализа как биологических данных, так и медиа-файлов Кроме того, вычисление расстояния Хэмминга между сжатыми текстами является естественным продолжением задачи о равенстве сжатых текстов

Алгоритмы на сжатых текстах имеют прямое отношение к ряду других задач теоретической информатики Так, с их помощью впервые удалось достроить полиномиальный по памяти алгоритм решения уравнений в словах [20], а также полиномиальный алгоритм верификации диаграмм сообщений [10]

Быстрый поиск по сжатым данным имеет и прикладное значение Архивирование индексов поисковых систем важно для интернет-приложений, коллекций аудио и видео, биологических баз данных Второй областью приложения явтается верификация программ и микросхем Обычно для верификации необходимо проверить некое свойство множества допустимых состояний программы и графа переходов Для современных систем число состоянии не поддается никаким переборным алгоритмам Естественный выход — хранить его в неявном виде и проверять его свойства без явного порождения

Цели работы Диссертационное исследование было направлено на решение следующих основных задач

1 Построить новые алгоритмы для сравнения сжатых текстов, поиска сжатых шаблонов в сжатых текстах, вычисления периодов сжатых текстов Упростить алгоритмы, представленные в работах [9, 12, 14, 17, 19] и/или уменьшить верхние оценки на время их работы

2 Определить существование полиномиальных алгоритмов для счеду-ющих задач вложимость явно заданного шаблона в сжатый текст, вложпмость сжатого шаблона в сжатых текст, вычисление расстоя-

ния Хэмминга между сжатыми текстами, вычисление минимального накрытия сжатого текста

3 Построить систему компактного описания текстов, основанную на использовании частично определенных слов

Общая методика работы В диссертации используются идеи, хорошо известные в рамках теоретической информатики Представленные алгоритмы основаны на методе динамического программирования и используют ряд комбинаторных свойств текстов Оценки трудоемкости получены путем сведений общепризнанно-трудных задач (1] к рассматриваемым проблемам Алгоритм поиска разреженных периодов минимального размера использует вариацию поиска кратчайших путей в ациклических графах Основные результаты

1 Разработаны алгоритмы поиска сжатых подстрок в сжатых текстах, вычисления минимальных периодов и накрытий сжатого текста, поиска явно заданной подпоследовательности в сжатом тексте

2 Доказана #Р-полнота задачи о вычислении расстояния Хэмминга между сжатыми текстами, ИР- и соЫР-трудность задачи о поиске сжатой подпоследовательности в сжатом тексте

3 Предложено понятие разреженной периодичности Найдено соотношение примитивного классического и примитивного разреженного периодов

4 Разработан алгоритм поиска разреженных периодов минимального размера

Научная новизна Все основные результаты являются новыми Практическая и теоретическая ценность Представленные алгоритмы для проверки равенства сжатых текстов и поиска сжатых подстрок в сжатых текстах могут быть попсзпы для проверки эквивалентности программ в рамках модели, предложенной в работе [15] Описание текстов с

иомощью их разреженных периодов может быть использовано для обобщения ряда классических методов архивирования, таких как кодирование длин серий (RLE) Доказательство трудности вычисления расстояния Хэмминга между сжатыми текстами показывает границы применимости алгоритмов для обработки текстов, представленных в виде прямолинейных программ Фактически, можно сделать вывод, что для эффективного приближенного сравнения сжатых текстов нужна другая модель компактного хранения

Апробация работы Основные результаты обсуждались на следующих конференциях и семинарах

• Международный симпозиум Mathematical Foundations of Computer Science, Словакия, 2006

• Международный симпозиум Computer Science in Russia, Санкт-Петербург, 2006

• Школа-семинар "Синтез и сложность управляющих схем" Санкт-Петербург, 2006

• Школа-семинар в Дагпиуле "Combinatorial and Algorithmic Foundations of Pattein ancl Association Discovery", Германия, май 2006

• Русско-французская конференция молодых ученых, Москва, 2006

• Научные семинары ПОМП РАН, СПИИРАН, МГУ, ИППИ РАН, университетов Таллина и Турку

Результаты, лежащие в основе диссертации, дважды представлялись на конкурс Мебиуса В 2005 году работа диссертанта стала финалистом конкурса, в 2006 год}' — отмечена жюри

Публикации Основные результаты диссертации опубликованы в пяти работах [23, 24, 25, 26, 27] перечисленных в конце автореферата

Работы [23, 24] опубликованы в издании, входившем в перечень ВАК на момент публикации

Структура и объем работы Диссертация объемом 82 страницы состоит из вьеденпя и четырех основных глав, разбитых па разделы и подразделы Список цитируемой литературы состоит из 47 наименований

СОДЕРЖАНИЕ РАБОТЫ

Во введении приводится обоснование актуачьности темы диссертации, формулируются основные полученные результаты, поясняется их положение в контексте текущих исследований, а также кратко описывается структура диссертации

Вторая глава содержит описание прямолинейных программ, которые являются абстрактной моделью сжатых текстов

Определение Прямолинейной программой называется контекстно-свободная грамматика V, в которой нетерминальные символы ЛГх, ,Хт упорядочены (Хт — стартовый символ), и где у каждого нетерминального символа есть только одно правило X, —> а, где а — терминал, или Хг —> для некоторых к < г

Третья глава посвящена построению алгоритмов для следующих трех задач

1 Даны два сжатых текста, представленные в виде прямолинейных программ Определить, совпадают ли исходные тексты

2 Даны два сжатых текста Определить, входит ли первый из них во второй При положительном ответе найти место первого вхождения и общее число вхождений

3 Дан шаблон (явно заданный) и сжатый текст Определить, образуют ли буквы шаблона подпоследовательность в тексте Другими словами, можно ли вычеркнуть часть букв в тексте так, чтобы остался шаблон?

В разделе 3 1 этой работы приводи гея новый алгоритм, который решает задачу о поиске подстрок за 0(п2т) шагов Применение этого алгоритма к задаче о равенстве приводит к оценке 0(п3) на время работы Таким образом, улучшены результаты всех предыдущих работ по этим двум задачам [12, 17, 14, 19, 9]

В разделе 3 2 алгоритмическая техника, использованная для решения задачи о поиске подстроки, применяется к вычислению длин минимального периода и минимального накрытия сжатого текста

Далее, в разделе 3 3 приводится алгоритм, который определяет вло-жимость шаблона в текст Этот алгоритм также выдает количество минимальных подстрок и количество подстрок определенной длины, в которые вкладывается шаблон Трудоемкость алгоритма равна 0[rnk'1\ogk) где к — длина шаблона, а т — размер прямолинейной программы, порождающей текст Таким образом, время работы линейно относительно размера сжатого текст

Четвертая глава посвящена доказательству вычислитечьной трудности следующих двух задач

1 Дано два сжатых текста одинаковой длины Определить количество несовпадающих символов (расстояние Хэммнпга) между ними

2 Дано два сжатых текста Определить, является ли один текст подпоследовательностью второго

В разделе 4 1 доказана следующая теорема

Теорема 4 11 Задача о вычислении расстояния Хэмминга между сжатыми текстами является #Р-полной

Напомним, что #Р — это класс функций, своеобразное расширенно класса предикатов ИР Далее, в раздете 4 2 доказаны две теоремы о трудности поиска сжатой подпоследовательности в сжатом тексте (задача определения вложимостп)

Теорсма 4.2 1. Задача определения вложимости сжатого шаблона в сжатый текст является NP-трудной

Теорема 4 2 2 Определение вложимости сводится (но Карпу) к определению невложимости Определение невложимосги сводится к определению вложимости

Утверждение теоремы можно переформулировать следующим образом Для каждой пары прямолинейных программ F и G можно быстро построить такую пару программ F' и G', что текст, порожденный F вкладывав хся в текст, порожденный G, тогда и только тогда, когда текст, порожденный F', не вкладывается в тексд, порожденный G' Таким образом, задача вложимости лежит вне класса NP(npn предположении NP^coNP) Последний результат оказался большой неожиданностью, так как по своей природе постановка задачи очень напоминает представителей класса NP

Пятая глава В предыдущих главах нашего исследования изучаются fijiaic1)! когирые о могут f>biib преобразованы в прямолинейную про-1рамм}, порождающую тот же текст Базовой операцией восстановления текста из такого описания является конкатенация двух уже определенных фрагментов Оставался открытым вопрос о том, есть ли такие системы представпенпя текстов, которые используют более широкий класс операций В пятой 1лаве представлено новое понятие — разреженную периодичность, — которое может быть использовано для компактного описания некоторых длинных текстов

Слово S называется чисто периодическим, если S = — П7 W Другими словами, чистая периодичность соответствует делимости р\п и равенству s¡ = sl+p для всех 1 <г<г+р<п

Два слова на иллюстрации внизу не являются чисго периодическими Однако они обладают некоторой структурной закономерностью Так, в соответствии с введенным в диссертации новым обобщенным понятием периодичности эти строки становятся периодическими

| а.|А|в|в| |А|А|В|Б|А|А|В|В|С|С|Р|Р|С|С |Р[Р]

Частично определенное слово — это слово в алфавите £и {о}, где о — это специальная прозрачная (или неопределенная) буква [2, 5, 6] Другими словами, частично определенное слово представляет собой последовательность обычных слов (блоков), разделенных пропусками фиксированной (но необязательно одинаковой) длины

Частично определенное слово 5 называется разреженным периодом (обычного) слова Т, если Т можно разделить на одну или несколько параллельно сдвинутых копий 5, которые будут удовлетворять следующим условиям

• Все определенные (видимые) буквы 5-копий совпадают с соответствующими буквами в тексте,

• Каждая буква текста покрыта в точности одной определенной (видимой) буквой из ¿'-копий

Представим, что имеется несколько копий частично определенного слова, напечатанных на прозрачной бумаге Тогда это слово будет разреженным периодом некоторого текста, если можно сложить данные копии в стопку так чтобы образовалась одна связная строка без перекрытий видимых букв

На следующей иллюстрации показаны разбиения доказывающие разреженную периодичность исходных примеров

Понятие разреженной периодичности вызывает следующие важные вопросы (1) Как перечислить все разреженные периоды7 (2) Каждое ли слово имеет единственный примитивный разреженный период? (3) Как найти все разреженные периоды минимального размера7 (4) Сколько разреженных периодов может иметь слово длины п? (5) Каково отношение между примитивным классическим периодом и примитивным разреженным периодом7

С

В разделе 5 1 определяется часшчный порядок на разреженных периодах Показано, что, в отличие от классического случая [8], у текста может оказаться несколько примитивных разреженных периодов Представлен пример (24 буквы), обладающий двумя независимыми примитивными разреженными периодами Таким образом, получено опровержение гипотезы Теро Харью об общель подразбиении [11]

В подразделе 5 2 1 установлена связь между разреженными периодами слова в однобуквенном алфавите и факторизациями его длины

Теорема 5 2 1 Существует биективное соответствие между разреженными периодами унарного слова длины п и упорядоченными разложениями п = щ пк, где п2, ,пк> 2

В подразделе 5 2 2 доказана теорема о связи примитивных разреженных периодов некоторого текста Т с его классическим примитивным периодом

Теорема 5 2 2 Любой примитивный разреженный период <5 слова Т является также разреженным периодом для классического примитивного периода Т

Из этого свойства следует, что разреженная периодичность живет внутри" классического примитивного периода Доказательство основано на расширенном алгоритме Евклида

Наконец, в подразделе 5 2 3 представлен алгоритм для нахождения (всех) разреженных периодов минимального размера для данного текста Время работы алгоритма составляет шагов

Список литературы

[]] Гори А/, Доконсон Д Вычислительные машины и труднорешаемые задачи // Пер с англ — Москва, Мир, 1982

[2] Шур А А/, Гамзова Ю В Частичные слова и свойство взаимодействия периодов // Известия РАН Серия математическая, 2004, 68 2, 191-214

[3] Amir A , Benson G , Farach M Let sleeping files lie Pattern matching in Z-compressed files 11 SODA '94, 1994

[4] Berrnan P , Karpmski M, Larmore L , Plandowski W, and Rytter W On the complexity of pattern matching for highly compressed two-dimensional texts // Journal of Computer and Systems Science, 65(2) 332-350, 2002

[5] Blanchet-Sadri F Periodicity on partial words // Computers and Mathematics with Applications, 47(1) 71-82, 2004

[6] Boasson L , Berstel J Partial words and a theorem of Fine and Wilf // Theoretical Computer Science, 218(1) 135-141, 1999

[7j Farach M, Thorup M String matching in Lempel-Ziv compressed strings 11 STOC '95, pages 703-712, ACM Press, 1995

[8] Fine N, Wilf H Uniqueness theorems for periodic functions // Proc Arner Math Soc , 16 109-114, 1965

[9] Gg,sieniec L, Karpmski M, Plandowski W, and Rytter W Efficient algorithms foi Lempel-Ziv encoding (extended abstract) // SWAT 96, LNCS 1097, pages 392-403, Springer-Verlag, 1996

[10] Genest B , Muscholl A Pattern matching and membership for hieiarclucal message sequence charts // LATIN'02, LNCS 2286, pages 326-340 Springer-Verlag, 2002

[11] Harju T Defect theorem // Lecture notes of "Combinatorics of words" Tarragona course, 2002/2003

[12] Hirao M, Shmohara A , Takeda M, and Arikawa S Fully compressed pattern matching algorithm for balanced straight-lme programs !/ SPIRE'00, pages 132-138, IEEE Computer Society, 2000

[13] Karkkainen J Navarro G , and Ukkonen E Approximate string matching over Ziv-Lempel compressed text //CPM'00, LNCS 1848, pages 195-209, Springei-Verlag, 2000

[14] Karpvnski M , Rytter W, and Shmohara A Pattei n-matching for strings with short descriptions // CPM'95, LNCS 937, pages 205-214, SpringerVerlag, 1995

[15] Lasota S, Rytter W Faster algorithm for bisimulation equivalence of normcd context-free processes // MFCS'06, LNCS 4162, pages 646-657 Spnnger-Verlag, 2006

[16] Lohrey M Woid problems on compressed word // ICALP'04), LNCS 3142, pages 906-918, Springer-Verlag, 2004

[17] Miyazaki M , Shmohara A , and Takeda M An improved pattern matching algorithm for strings in terms of straight line piograms // CPM '97, LNCS 1264, pages 1-11, Springer-Vw lag, 1997

[18] Navarro G , Rafßnot M A geneial practical approach to pattern matching ovei Ziv-Lempel compiessed text // CPM'99, LNCS 1645, pages 14-36, Springei-Verlag, 1999

[19] Plandowski W Testing equivalence of niorphisms on context-free languages // ESA'94, LNCS 855, pages 460-470, Spnnger-Verlag, 1994

[20] Plandowski W Satisfiability of woid equations with constants is m PSPACE 11 J ACM, 51(3) 483-496 2004

[21] Rytter W Application of Lempel-Zi\ factorization to the approximation of grammar-based compression , / Theoretical Computer Science, 302(1— 3) 211-222, 2003

[22] Zw J, Lempel A A univeisal algonthm for sequential data compression // IEEE Transactions on Information Theory, 23(3) 337-343, 1977

ПУБЛИКАЦИИ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ

[23] Каръюмяки Ю , Лифшиц 10 М Разреженная периодичность // Пре-

"* принт ПОМИ 22/06, 2006

[24] Лифшиц Ю М Алгоритмические свойства сжатых текстов // Препринт ПОМИ 23/06, 2006

[25] Лифшиц Ю М Обработка сжатых текстов // Материалы XVI Международной школы-семинара "Синтез и сложность управляющих систем", стр 64-68, Изд-во механико-математического факультета МГУ, 2006

[26] Cegielski Р, Guessarian I, Lifshits Y, and Matiyasemch Y Window subsequence problems for compressed texts // CSR '06, LNCS 3967, pages 127-136, Spnnger-Verlag, 2006

[27] Lifshits Y, Lohrey M Querying and embedding compressed texts // MFCS'06, LNCS 4162, pages 681-692, Sprmgei-Verlag, 200G

Подписано в печать с оригинал-макета 17 04 07 Формат 60x84/16 Бумага офсетная Печать ризографичеекая Уел печ л 0,4 Тираж 100 экз Заказ №1704/01-Р

Мини-типография «Знак» издательства «Знак» 191025, Санкт-Петербург, ул Восстания, д 6 тел (812)579-0891,579-38-50

1 Введение

1.1 Алгоритмы на сжатых текстах.

1.1.1 Постановка решаемых задач .б

1.1.2 Результаты.

1.2 Нижние оценки трудоемкости обработки сжатых текстов

1.3 Новый подход к архивированию: разреженная периодичность

1.3.1 Основное понятие

1.3.2 Рассматриваемые вопросы.

1.3.3 Результаты.

1.4 Обзор литературы.

1.4.1 Исследования по алгоритмам обработки сжатых текстов

1.4.2 Исследования по периодичности текстов и по обобщениям этого понятия.

1.5 Структура работы.

2 Грамматика как модель сжатого текста

3 Алгоритмы обработки сжатых текстов

3.1 Поиск сжатой подстроки в сжатом тексте.

3.1.1 Поиск подстрок с помощью таблицы прогрессий

3.1.2 Вычисление таблицы прогрессий.

3.1.3 Процедура локального поиска.

3.1.4 Обсуждение алгоритма.

3.2 Алгоритм вычисления периодов и накрытий.

3.3 Алгоритм поиска оконных подпоследовательностей

3.3.1 Вспомогательные структуры данных.

3.3.2 Вычисление вспомогательных структур данных

3.3.3 Итоговый алгоритм и его трудоемкость.

3.4 Выводы и открытые вопросы.

4 Нижние оценки на трудоемкость обработки сжатых текстов

4.1 Расстояние Хэмминга между сжатыми текстами.

4.2 Сжатые подпоследовательности в сжатых текстах.

4.2.1 NP-трудность.

4.2.2 coNP-трудность.

4.3 Выводы и открытые вопросы.

5 Разреженная периодичность

5.1 Примитивный разреженный период не единственен

5.2 Свойства разреженной периодичности.

5.2.1 Количество разреженных периодов.

5.2.2 Соотношение между разреженными и классическими периодами.

5.2.3 Алгоритм поиска разреженных периодов минимального размера.

5.3 Выводы и открытые вопросы.

Как хранить данные, чтобы одновременно иметь быстрый доступ к нужной информации и максимально уменьшить их размер? Для решения первой задачи разработано множество структур данных (сбалансированные деревья, суффиксные массивы и т.д.), ориентированных на быструю обработку конкретных видов запросов. Для уменьшения размера данных используются алгоритмы архивирования (LZ77, LZW, кодирование длин серий и т.д.). Можно ли объединить достоинства этих двух подходов? В представляемой работе построены алгоритмы вычисления ряда свойств сжатых текстов без распаковки, получены нижние оценки на трудоемкость некоторых других задач на сжатых текстах, и, наконец, предложен новый подход к архивированию текстов.

1.1 Алгоритмы на сжатых текстах

1.1.1 Постановка решаемых задач

Исследования начались с построения алгоритмов для поиска явно заданных подстрок в сжатых текстах [8, 18]. Очень быстро от рассмотрения конкретных алгоритмов архивирования исследователи перешли к общей модели сжатого текста — прямолинейной программе (ПП). Неформально, ПП является грамматикой, которая порождает ровно один текст. Оказалось, что тексты, сжатые практическими архиваторами, быстро и без значительного увеличения размера могут быть переведены в грамматику, описывающую тот же текст [42]. Мы подробно опишем прямолинейные программы в главе 2. Недавно было предложено некоторое обобщение прямолинейных программ под названием collage systems [29]. Мы будем строить алгоритмы для следующих трех задач:

1. Даны два сжатых текста, представленные в виде прямолинейных программ. Определить, совпадают ли исходные тексты.

2. Даны два сжатых текста. Определить, входит ли первый из них во второй. При положительном ответе найти место первого вхождения и общее число вхождений.

3. Дан шаблон (явно заданный) и сжатый текст. Определить, образуют ли буквы шаблона подпоследовательность в тексте. Другими словами, можно ли вычеркнуть часть букв в тексте так, чтобы остался шаблон? т

Р Mill

Вхождение шаблона Р в текст Т в виде подпоследовательности

Первая задача является частным случаем второй. Равенство сжатых текстов может использоваться для сверки различных архивных копий одной и той же системы, поиск подстрок — для верификации программ и поиска по медиа-данным (в них шаблон также может быть большим и требовать архивирования).

Задача о равенстве впервые была решена в работе [39] в 1994 году. Была доказана оценка 0(п4) на время работы этого алгоритма, где п равно сумме размеров прямолинейных программ, порождающих два сравниваемых текста. Алгоритм для поиска сжатой подстроки в сжатом тексте впервые появился в 1995 году в статье [27]. Вслед за этим удалось расширить алгоритм для вычисления различных комбинаторных свойств текста [20]. Далее, в 1997 году Миязаки, Шинохара и Такеда [35] построили алгоритм, требующий 0(п2тп2) времени для поиска подстрок, где тип — размеры сжатого шаблона и сжатого текста, соответственно. Наконец, в 2000 году удалось провести поиск подстрок за 0(пт) для еще одного специального случая [24].

Поиск подпоследовательностей является естественным "родственником" поиска подстрок. Тем не менее, до сих пор не было предложено ни одного алгоритма поиска подпоследовательностей напрямую в сжатом тексте.

1.1.2 Результаты

В разделе 3.1 этой работы нам удалось улучшить алгоритмы [24, 35, 27, 39, 20] и решить задачу о равенстве за 0(п3), а задачу о поиске подстрок за 0(п2т) шагов.

Алгоритмическая техника, которую мы применили для задачи о поиске подстроки, позволяет вычислять и комбинаторные свойства сжатых текстов, например, длины минимального периода и накрытия. Это приложение и ряд открытых вопросов сформулированы в разделе 3.4. В частности, одной из самых заманчивых задач для будущих исследований является построение сжатого суффиксного дерева.

Кроме того, мы построили алгоритм, который определяет вложи-мость шаблона в текст. Наш алгоритм также выдает количество минимальных подстрок и количество подстрок определенной длины, в которые вкладывается шаблон. Трудоемкость алгоритма равна mk2 log к, где к — длина шаблона, am — размер прямолинейной программы, порождающей текст. Таким образом, время работы нашего алгоритма линейно относительно размера сжатого текста.

1.2 Нижние оценки трудоемкости обработки сжатых текстов

Чтобы показать все преимущества хранения текстовой информации в виде прямолинейных программ, мы ставим следующую общую задачу. Для каждого классического свойства текста мы ищем алгоритм, который (1) на вход получает прямолинейную программу, (2) на выходе сообщает, обладает ли порождаемый этой программой текст данным свойством, (3) время исполнения алгоритма полиномиально ограничено относительно размера ПП.

В процессе исследований мы столкнулись с двумя задачами, для которых построить такой алгоритм никак не удавалось:

1. Дано два сжатых текста одинаковой длины. Определить количество несовпадающих символов (расстояние Хэмминга) между ними.

2. Дано два сжатых текста. Определить, является ли один текст подпоследовательностью второго.

Вычисление расстояния Хэмминга является самой простой формой приближенного поиска подстрок, который полезен для анализа как биологических данных, так и медиа-файлов. Кроме того, вычисление расстояния Хэмминга между сжатыми текстами является естественным продолжением задачи о равенстве сжатых текстов, для которой мы уже построили эффективный алгоритм.

Как было уже отмечено выше, для поиска в сжатых текстах существуют полиномиальные алгоритмы, которые находят (1) явно заданные подстроки, (2) подстроки, представленные в сжатом виде (3) вхождения в виде подпоследовательности явно заданного шаблона. Вычислительная трудность четвертой задачи — проверки вложимости "как подпоследовательность" одного сжатого текста в другой сжатый текст, оставалась совершенно неясной. Определение вложимости сжатого шаблона в сжатый текст могло оказаться как решаемым за полиномиальное время, так и PSPACE-полной задачей.

В представляемой работе удалось разработать специальную технику оценки трудности вышеприведенных задач на сжатых текстах. Мы научились сводить решение общепризнанно-трудных задач к вычислению определенных свойств сжатых текстов.

Так, в главе 4 мы докажем, что вычисление расстояния Хэмминга для сжатых текстов является #Р-полной задачей. Напомним, что #Р — это класс функций, своеобразное расширение класса предикатов NP.

Мы также показали, что задача определения вложимости сжатого шаблона в сжатый текст не только NP-трудна, но и лежит вне класса NP(npn предположении NP^coNP). Последний результат стал большой неожиданностью, так как задача по своей природе очень напоминает представителей класса NP.

1.3 Новый подход к архивированию: разреженная периодичность

В первых двух частях нашего исследования мы изучали архивы, которые легко могут быть преобразованы в прямолинейную программу, порождающую тот же текст. Базовой операцией восстановления текста из такого описания является конкатенация двух уже определенных фрагментов. Оставался открытым вопрос о том, есть ли такие системы представления текстов, которые используют более широкий класс операций. Мы представим новое понятие — разреженную периодичность, — которое может быть использовано для компактного описания некоторых длинных текстов.

1.3.1 Основное понятие

Слово S называется чисто периодическим, если S = Wk = W. W. Другими словами, чистая периодичность соответствует делимости р\п и равенству Sj — Si+p для всех 1<г<г4-р<п. В этой работе мы будем иметь дело только с чистой периодичностью.

Два слова на иллюстрации внизу не являются чисто периодическими. Однако, они обладают некоторой структурной закономерностью. В пятой главе диссертации мы вводим новое обобщенное понятие периодичности. в соответствии с которым эти строки становятся периодическими.

А А В В

А А В В А А В В СС D D С С D D

Неформально, слово Т называется разреженно периодическим, если существует такое частично определенное слово S, что Т может быть разделено на несколько параллельных копий S. Мы представим формальное определение со всеми подробностями в первых же абзацах главы 5. На следующей иллюстрации показаны разбиения, доказывающие разреженную периодичность исходных примеров.

1.3.2 Рассматриваемые вопросы

Глава 5 посвящена исследованию основных свойств разреженной периодичности и сопоставлению их с классическим определением. Нас интересуют следующие вопросы: (1) Как перечислить все разреженные периоды? (2) Каждое ли слово имеет единственный примитивный разреженный период? (3) Как найти все разреженные периоды минимального размера? (4) Сколько разреженных периодов может иметь слово длины п? (5) Каково отношение между примитивным классическим периодом и примитивным разреженным периодом?

У нас есть несколько причин изучать разреженные периоды. Во-первых, это естественное обобщение классического понятия, так как любой классический период является также и разреженным. Обратное необязательно верно. Во-вторых, в случае, когда разреженный период относительно мал, мы можем полностью описать длинную строку, сообщив только ее длину и разреженный период. Таким образом, мы получаем новый формализм для компактного описания слов из некоторый класса. И, таким образом, все слова в этом классе имеют малую колмого-ровскую сложность. Разреженная периодичность может быть полезна для построения новых алгоритмов архивирования, особенно для обобщения кодирования длин серий (RLE). Заметим здесь, что отношение между "размером" разреженного периода и длиной классического периода может быть сколь угодно мало. В-третьих, понятие разреженной периодичности дает геометрический взгляд на структуру текстов. Далее, в разделе 5.3 мы формулируем гипотезу, утверждающую что разреженная периодичность невыразима при помощи уравнений в словах. Еще одним стимулом для изучения разреженной периодичности является надежда обнаружить новые закономерности в реальных данных. Представляется интересным провести экспериментальные исследования в этом направлении.

Покажем один естественный источник разреженной периодичности.

Рассмотрим многомерный параллелепипед щ х • • • х п^. Пусть каждая его клетка покрашена в некоторый цвет. Отсортируем все клетки в алфавитном порядке их координат (от (0,., 0) до (щ — 1,., п^ — 1)) и выпишем все их цвета в единую последовательность. Предположим теперь, что исходный параллелепипед был замощен меньшим т\Х- • -хтпл, причем rai|ni,. , га^п^ и каждая копия маленького параллелепипеда была раскрашена одинаково. Тогда последовательность цветов большого параллелепипеда будет обладать разреженной периодичностью. Мы вернемся к этому примеру после введения ряда необходимых терминов. Другими источниками разреженной периодичности могут стать XML-файлы и автоматически порожденные тексты.

1.3.3 Результаты

В главе 5 мы ввели понятие разреженной периодичности. Оно выглядит очень просто и естественно, но, насколько нам известно, никогда не было явно сформулировано прежде.

Далее мы определили частичный порядок на разреженных периодах и обнаружили, что, в отличие от классического случая, у текста может оказаться несколько примитивных разреженных периодов. Наименьший из известных нам примеров (24 буквы), обладающих этим свойством, мы представим в разделе 5.1. Этот пример позволил опровергнуть гипотезу Теро Харью об общем подразбиении.

Тем не менее, в подразделе 5.2.2 мы докажем, что каждый примитивный разреженный период слова Т также является разреженным периодом классического примитивного периода Т. Из этого свойства следует, что разреженная периодичность живет "внутри" классического примитивного периода. Доказательство основано на расширенном алгоритме Евклида.

В подразделе 5.2.1 мы представим классификацию всех возможных разреженных периодов. Наиболее трудным техническим шагом является доказательство полноты нашей конструкции, то есть того факта, что наша классификация содержит все разреженные периоды. Мы получили рекурсивную формулу для вычисления функции L(n), которая дает максимальное количество разреженных периодов для слов длины п. Значение L(n) может оказаться даже больше длины исходного текста. Например, слово длиной 36 символов может иметь до L(36) = 52 разреженных периодов.

Наконец, в подразделе 5.2.3 мы представим алгоритм для нахождения (всех) разреженных периодов минимального размера для данного текста. Трудоемкость алгоритма составляет п1+0^ шагов.

1.4 Обзор литературы

1.4.1 Исследования по алгоритмам обработки сжатых текстов

Для прямолинейных программ, помимо поиска подстрок, были представлены алгоритмы для поиска регулярных выражений и приближенного поиска подстрок (соответственно, [36] и [26]).

Неожиданно оказалось, что алгоритмы на сжатых текстах имеют прямое отношение ко многим другим задачам теоретической информатики. Так, с их помощью впервые удалось построить полиномиальный по памяти алгоритм решения уравнений в словах [40]; более быстрый алгоритм проверки эквивалентности программ (естественно, в ограниченном классе) [31]; полиномиальный алгоритм верификации диаграмм сообщений [21].

Быстрый поиск по сжатым данным имеет и прикладное значение. Архивирование индексов поисковых систем важно для интернет-приложений, коллекций аудио и видео, биологических баз данных. Хочется найти такое представление данных, при котором, по возможности, одновременно минимизируются и размер, и время доступа. Второй областью приложения является верификация программ и микросхем. Обычно для верификации необходимо проверить некое свойство множества допустимых состояний программы и графа переходов. Для современных систем число состояний не поддается никаким переборным алгоритмам. Единственный выход — хранить его в неявном виде и проверять его свойства без явного порождения.

После построения ряда алгоритмов, имеющих полиномиальную сложность относительно размера сжатых текстов, исследования столкнулись с NP-трудными задачами: принадлежность сжатого текста контекстно-свободной грамматике [33], двумерный поиск подстрок [10]. Таким образом, представление текстов в виде прямолинейных программ позволяет решить далеко не все задачи без порождения исходного текста. Кроме того, недавно удалось доказать [34], что принадлежность регулярному языку является Р-полной (то есть плохо поддается распараллеливанию).

Экспериментальный анализ алгоритмов на сжатых текстах можно найти в статье [37], работы [41, 43] дают обзор всех алгоритмических исследований по сжатым текстам, книга [1] служит прекрасным введением в текстовые алгоритмы.

1.4.2 Исследования по периодичности текстов и по обобщениям этого понятия

Одним из важнейших результатов для классической периодичности является теорема Файна и Вильфа [19]. Они изучали необходимые и достаточные условия, при которых из ^-периодичности и ^-периодичности следует НОД(р, ^-периодичность (НОД = наибольший общий делитель). Мы предприняли попытку найти аналогичное свойство для разреженных периодов. К нашему удивлению, теорема Файна и Вильфа не обобщается на разреженную периодичность. Даже два чистых разреженных периода одного текста могут не иметь никакого общего подпериода.

Наше обобщение понятия периодичности является далеко не первым. Недавно Симпсон и Тайдеман обобщили теорему Файна и Вильфа на многомерные периодичности [45]. Они считают, что некоторый вектор v является периодом многомерной раскрашенной клетчатой фигуры, если любая клетка х покрашена в тот же цвет, что их + v. Другое обобщение теоремы Файна и Вильфа можно найти в статье [17].

Берстель и Боассон [14], а вслед за ними Шур и Коновалова (Гамзова) [7, 44] и Бланше-Садри [И, 12, 13] подробно изучили частичные слова и ввели понятие периодичности для них. Однако, в этой постановке не допускается перекрытие периодов (копии периода должны идти одна вслед за другой). Таким образом, в этой модели только частичные слова могут иметь разреженные периоды (то есть периоды с пропусками букв).

В работе [9] Апостолико, Фарач и Илиопулос ввели понятие накрытия (cover). Слово С называется накрытием для слова Т, если каждая буква из Т находится внутри некоторого вхождения С в Т. Таким образом, эта модель отличается от нашего понятия в двух аспектах: накрытия связны (никаких пропусков), и накрытия могут перекрываться.

Катона и Шаш в своей работе [28] предложили вариант разреженной периодичности на плоскости. К сожалению, они рассмотрели только периоды (шаблоны) из двух клеток.

Наконец, понятие периодичности было обобщено на бесконечные слова под именем почти периодических последовательностей [6].

1.5 Структура работы

В главе 2 мы подробно обсудим, что мы понимаем под "сжатым текстом". Мы опишем абстрактную модель сжатого текста (прямолинейная программа), и сформулируем теорему Риттера о преобразовании архивов общепринятых стандартов в прямолинейные программы.

Далее, в главе 3, мы подробно представим алгоритмы для поиска явно заданных подпоследовательностей и сжатых подстрок в сжатом тексте. Четвертая глава посвящена доказательству вычислительной трудности нахождения расстояния Хэмминга между сжатыми текстами и проверки вложимости одного сжатого текста в другой. В пятой главе мы введем понятие разреженной периодичности и докажем ряд его свойств.

В конце каждой главы подводятся краткие итоги и ставятся задачи для дальнейших исследований.

Глава 2

Грамматика как модель сжатого текста

Мы рассматриваем конечный алфавит Е, строкой (текстом, словом) называется любая конечная последовательность его букв. В этой работе иод сжатыми текстами мы понимаем строки, порожденные прямолинейными программами (ПП). Неформально, прямолинейная программа — это контекстно-свободная грамматика, порождающая только одно слово.

Определение: прямолинейной программой называется контекстно-свободная грамматика V, в которой нетерминальные символы Xi,., Хт упорядочены (Хт — стартовый символ), и где у каждого нетерминального символа есть только одно правило: Xi —> а, где а — терминал, или Хг —► XjXk для некоторых j, к < г.

Пример: текст аЪааЪаЪааЪааЬ может быть представлен следующей прямолинейной программой:

Xi X2 Хъ X.i Хь X, X7

Ь, a,

X2X1, X3X2, X4X3, X5X4, XqX$.

Восстановление этого текста из ПП можно проиллюстрировать в виде дерева: А

Х5 Л4 Х4 Хз \ / \ / \ /\ Х4 Хз Хз Х2 Хз х2 Х2 XI /\ /\ Хз Х2 Х2 Xi Х2 Xi /\ х2 Xi х2 Xi abaababaabaab

Мы позволим себе некоторую вольность и будем пользоваться обозначением Xk как для символа грамматики, так и для соответствующего текста, получаемого при распаковке Xk- Таким образом, мы можем написать Т = Хт.

В работе Риттера [42] доказано, что архив, полученный почти каждым прикладным архиватором (включая LZ1, LZ77, LZ78, LZW, run-length encoding, все словарные методы), может быть эффективно преобразован в прямолинейную программу почти того же размера. Важно отметить, что прямолинейные программы являются моделью декомпрессора, то есть моделируют лишь получение исходного текста из сжатого представления (набора правил). В данной работе мы совершенно не заботимся о том, как были получены сжатые тексты.

Трудность обработки сжатых текстов связана с тем, что соотношение между размером прямолинейной программы и длиной порождаемого текста может быть экспоненциальным. Таким образом, любой алгоритм, который восстанавливает текст, имеет по крайней мере экспоненциальною сложность (по памяти, а следовательно и по времени).

Глава 3

Алгоритмы обработки сжатых текстов

3.1 Поиск сжатой подстроки в сжатом тексте

Формулировка "да/нет" варианта поиска сжатого шаблона в сжатом тексте выглядит следующим образом:

ВХОДНЫЕ ДАННЫЕ:

Две прямолинейные программы, порождающие Р и Т ОТВЕТ:

Да/Нет (входит лиРвТ как подстрока?)

Другие варианты: найти первое вхождение, найти количество всех вхождений, проверить, есть ли вхождение, начиная с данной позиции. Мы построим такую структуру данных, пользуясь которой можно быстро ответить на все поставленные вопросы.

Мы будем использовать одно свойство модели вычислений, которое неявно предполагалось и во всех предыдущих работах. А именно, при анализе алгоритма мы считаем, что каждая арифметическая операция с позициями в тексте занимает один шаг. С теоретической точки зрения, позиции в тексте могут быть натуральными числами длиной до log \Т\ бит в двоичной записи. Таким образом, чтобы получить оценку трудоемкости в побитовых операциях нужно умножить наш результат 0(п2т) на некоторый множитель, полиномиально зависящий от log \Т\.

Изложение алгоритма разбито на три этапа. На первом мы представим нашу структуру данных — таблицу прогрессий. Мы также продемонстрируем, как с помощью этой таблицы быстро решаются все разновидности задачи поиска подстрок в сжатых текстах. На втором этапе будет построен алгоритм вычисления таблицы прогрессий, основанный на процедуре локального поиска. Наконец, в третьей части мы опишем алгоритм для локального иоиска.

3.1.1 Поиск подстрок с помощью таблицы прогрессий

Обозначения и терминология. Мы называем позициями в тексте координаты воображаемых точек между последовательными буквами. Таким образом, в тексте а\. ап есть позиции 0,., п, где 0 находится перед первой буквой, а позиция п — сразу за последней. Мы говорим, что некоторая подстрока касается данной позиции, если позиция находится внутри или на границе подстроки. Под термином вхождение мы подразумеваем и соответствующую подстроку, и ее стартовую позицию. Надеемся, что точный смысл всегда будет ясен из контекста.

Пусть Pi,., Рт и 7\,., Тп — это нетерминальные символы прямолинейных программ, порождающих РиТ, соответственно. Для каждого из этих промежуточных текстов мы определим специальную позицию разреза. В текстах, образованных по правилу Xi — XrXs, позицией разреза будет как раз точка, где заканчивается Хг и начинается Xs. Для полноты терминологии будем считать позицию 0 разрезом в однобук-венных текстах. Для примера из Главы 2, позицией разреза в тексте Xq будет точка между пятой и шестой буквой: abaab\aba, так как Xq был получен конкатенацией Х5 = abaab и Х4 = aba.

Наш алгоритм основан на одном комбинаторном свойстве строк (оно также было использовано в [35]):

Лемма 3.1.1 (Основная лемма). Рассмотрим все вхождения Р вТ, касающиеся некоторой фиксированной позиции в тексте. Тогда их стартовые позиции образуют арифметическую прогрессию.

Р Р Р

Касаемая позиция

Определим таблицу прогрессий следующим образом. Для каждых I < i < m.l < j < п значением TP\i,j] будет код арифметической прогрессии тех вхождений Pi в 7), которые касаются точки разреза 7). Заметим, что любая арифметическая прогрессия может быть описана тремя числами: первым элементом, шагом, количеством элементов. Если \Tj\ < \Pi\, мы формально определим TP[i,j] = 0i, а если текст достаточно велик, но не содержит ни одного вхождения, касающегося точки разреза, установим TP[i,j] = 02.

Prr,

1 m

Pi

Ti •• • Tn

Алгоритмическая задача 1: Используя таблицу прогрессий (на самом деле, достаточно ее верхней строки), массивы длин и позиций разреза всех промежуточных текстов решить каждый вариант задачи поиска подстрок в сжатых текстах за 0(п) шагов.

Алгоритмическая задача 2: Вычислить массивы длин и позиций разреза всех промежуточных текстов и заполнить таблицу прогрессий за 0(п2т) шагов.

Построим алгоритмы для первой задачи. Для "да/нет" варианта мы можем воспользоваться следующим правилом: Р входит в Т тогда и только тогда, когда существует j, для которого TP[m,j] не пусто. Другими словами, хотя бы один из текстов Tj содержит вхождение Р = Рт, касающееся его точки разреза. Считающая и проверяющая версии поиска подстрок решаются чуть сложнее.

Рекурсивный алгоритм для проверки вхождения с данной позиции: проверить, касается ли тестируемая подстрока точки разреза текущего текста Tj. Если да, нужно посмотреть в TP-таблицу и проверить принадлежность соответствующей арифметической прогрессии. В противном случае нужно рекурсивно перейти к левой или правой компоненте рассматриваемого текста.

Мы будем считать количество вхождений Р в тексты ., Тп по индукции. Для однобуквенных текстов мы просто берем мощность соответствующей арифметической прогрессии из TP-таблицы. Индукционный Ъ переход: сложить число вхождений для правой части, для левой части текста и добавить мощность арифметической прогрессии "центральных вхождений", исключив "только-касающиеся" вхождения.

Решение второй задачи приводится в следующих двух подразделах.

3.1.2 Вычисление таблицы прогрессий

Схема вычисления таблицы прогрессий:

1. Предвычисления: считаем длины, точки разрезов, первые и последние буквы всех промежуточных текстов;

2. Вычисляем строки и столбцы таблицы прогрессий, соответствующие однобуквенным текстам;

3. От самого маленького текста к самому большому, от самого маленького шаблона к самому большому последовательно вычисляем элементы таблицы TP[i,j]: a) Находим вхождения большей компоненты шаблона Pi вокруг разреза текста 7); b) Находим вхождения меньшей компоненты шаблона Pi, которые стыкуются с уже найденными вхождениями большей половины; c) Пересекаем вхождения большей и меньшей компонент, приводим ответ к коду одной прогрессии.

Шаг 1: проводим предвычисления свойств промежуточных текстов. Индуктивно, от меньших номеров к большим, мы вычисляем массивы длин, позиций разрезов, первых и последних букв для текстов Pi,., Pm, Ti,., Тп за время 0(п + т).

Шаг 2: заполняем "однобуквенные" строки/столбцы таблицы прогрессий. Пусть для какого-то г мы знаем, что \Р{\ = 1. Тогда мы заполним г-ую строку таблицы по следующему принципу. Для каждого j мы сравним букву Pi либо с единственной буквой Tj (в случае |7)| = 1), либо с последней буквой левой части Tj и первой буквой правой части Tj (эти две буквы мы знаем из предвычислений). В ответ запишем код прогрессии, кодирующей найденные совпадения (в данном случае ноль, одну или две соседние позиции). Таким образом, на один элемент таблицы мы тратим константное время.

Пусть теперь для некоторого j оказалось, что \Т3 \ = 1. В этом случае мы заполним j-ый столбец следующим образом. Если \Pj\ > 1, мы сразу пишем 0i, в противном случае сравниваем две буквы. При удаче — записываем в ответ прогрессию из одной позиции. Здесь также достаточно константного времени на каждый элемент.

Шаг 3: вычисляем новый элемент таблицы прогрессий по "правилу пересечения". После "однобуквенных рядов" мы заполняем таблицу в алфавитном порядке пар (г, j). Пусть Pi = PrPs. Для вычисления TP[i:j] мы будем использовать уже вычисленные значения TP [г, 1],., TP{r7j] и TP[s, 1],. .,TP[s,j]. Другим словами, нам потребуется только информация о вхождении правой и левой части шаблона в текущий текст и все предшествующие тексты.

Схема использования уже вычисленных элементов при динамическом программировании

Pi — Pr Ps

Опишем правило пересечения для вычисления очередного элемента таблицы прогрессий при составном шаблоне и составном тексте. Наиболее естественным является следующий способ: (1) найти все вхождения Рг "вокруг" точки разреза Tj, (2) найти все вхождения Ps "вокруг" точки разреза Tj, (3) сдвинуть вторые вхождения на \РГ \ и пересечь с первыми.

Рг Р, Р» Рг Р» I ± ^ I ± f I т. I <- W\ I j

В работе Миязаки и др. [35] представлен алгоритм, который реализует правило пересечения за 0(тп). Мы же не будем целиком следовать предложенной схеме, что позволит нам в итоге затратить лишь 0{п) шагов на вычисление TP[i,j].

Итак, пусть Pi = PrPs, обозначим через 7 позицию разреза Tj (мы знаем это значение из предвычислений). Не умаляя общности, будем считать \Pr\ > \PS\. Заметим, что любое вхождение Pi, касающееся разреза 7 в тексте Tj, состоит из вхождения шаблона Рг и вхождения Ps внутри | Pj (-окрестности разреза. При этом Рг заканчивается в точке, откуда начинается Рн. Первый шаг правила пересечения мы оставим без изменений. Но на втором шаге мы будем искать только вхождения Ps, которые начинаются с окончаний уже найденных вхождений Рг.

Для наших вычислений мы разработали вспомогательную процедуру локального поиска, которая извлекает нужную информацию из уже со

Рг

Рг Р,

1 1 Ъ считанных элементов таблицы прогрессий. Процедура Local(i,j,[a,/3]) возвращает вхождения Д в Tj, лежащие целиком внутри интервала [а,Р]. Важные характеристики алгоритма локального поиска:

1. он корректно работает только при условии \{3 — а\ < 3|Pf|,

2. локальный поиск использует значения TP[i, к] для 1 < к < j,

3. его трудоемкость O(j) шагов,

4. на выходе локальный поиск выдает пару арифметических прогрессий, причем внутри каждой прогрессии все вхождения имеют общую точку, и все вхождения из первой прогрессии находятся левее всех вхождений из второй.

Теперь покажем, как вычислить TP[i,j] за 5 запусков локального поиска.

Шаг За: ищем большую часть шаблона. С помощью одного вызова локального поиска мы найдем все вхождения Рг в интервале Ь — \Pi\,l + \Рг\], длина которого \Pi\ + \РГ\ < 3\РГ\. В ответе мы получим две арифметические прогрессии, представляющие все потенциальные стартовые позиции для вхождений Pi, касающихся разреза. К сожалению, мы не можем поступить таким же образом с Ps, так как длина соответствующего интервала поиска может не быть константной относительно |PS|. Поэтому мы будем искать только те вхождения Ps, которые начинаются с позиций из двух арифметических прогрессий окончаний вхождений Рг.

Шаг ЗЬ: ищем меньшую часть шаблона. Будем обрабатывать каждую прогрессию по отдельности. Назовем точку окончания вхождения Рг континентальной, если она находится на расстоянии хотя бы

PS| от последнего окончания в прогрессии. Все остальные окончания будем называть приморскими.

РгРгРгРгРг

-"-I --I ^-1—1 h \Р,\ н континентальные приморские

По свойству 4 локального поиска, все вхождения Рг из одной прогрессии имеют общую точку. Следовательно, все подстроки длины \Р8\, стартующие с континентальных окончаний, полностью совпадают. Таким образом, нам необходимо проверить все приморские точки и одну континентальную. Для поиска вхождений в приморском районе мы применим локальный поиск Ps в |PS|-окрестности последнего окончания и пересечем ответ с прогрессией приморских окончаний вхождений Рг. Пересечение двух прогрессий занимает 0(log \Т\) шагов, по технике эта операция очень похожа на расширенный алгоритм Евклида. Для проверки первого континентального окончания мы применим локальный поиск к |PS|-строке, начинающейся с этого окончания.

Шаг Зс: приводим ответ к одной прогрессии. Чтобы получить множество всех вхождений Pj, касающихся разреза в Tj, остается сделать следующее. В зависимости от результатов проверки, возьмем или все континентальные окончания, или ни одно из них. Возьмем подпро-грессию приморских окончаний (тех, которые соответствуют началам вхождений Ps). Также, возьмем аналогичные множества для второй прогрессии вхождений Рг. Эти четыре части являются арифметическими прогрессиями, идущими одна после другой. Следовательно, мы можем упростить ответ (мы должны получить лишь одну прогрессию по Основной лемме) за константное время.

Анализ трудоемкости. Давайте оценим трудоемкость вычисления одного элемента таблицы прогрессий. Мы применили один локальный поиск для Рг, четыре локальных поиска для Ps и дважды вычисляли пересечения арифметических прогрессий. Таким образом, мы имеем 7 процедур по 0(п) шагов.

Замечание. В представленном алгоритме для вычисления нового элемента таблицы мы пользуемся локальным поиском, а в реализации локального поиска — значениями из таблицы прогрессий. Убедимся, что в нашем случае нет никакого порочного круга. Действительно, пусть мы вычисляем элемент таблицы в строке г, и Pi — PrPs. Тогда мы пользуемся локальным поиском для шаблонов Рг и Р$. Эти процедуры активно используют значения таблицы из строк г и s. Но, согласно определенному нами порядку заполнения таблицы, эти строки находятся ниже строки i и уже заполнены.

3.1.3 Процедура локального поиска

Локальный поиск находит в хождения Рг в подстроке Tj[a,(3], Наше решение состоит из процедуры обхода и процедуры упрощения, которые мы подробно опишем ниже.

Первый этап: запускаем рекурсивную процедуру обхода с параметрами (i,j,a,(3). После завершения работы всех веток получаем отсортированный список прогрессий вхождений Р{ в Tj в пределах а, Я

Второй этап: запускаем процедуру упрощения и приводим список прогрессий к двум прогрессиям.

Процедура обхода. На входных данных (г, j, [a, j3)) мы делаем следующее.

1. Берем (из таблицы прогрессий) вхождения РгъТ3) которые касаются разреза.

2. Обрезаем прогрессию этих вхождений, оставляя лишь находящиеся целиком внутри [см, (5\.

3. Записываем эту усеченную прогрессию в список ответов.

4. Проверяем, имеет ли пересечение [а,/?] с левой/правой частью 7) длину хотя бы \Р{\.

5. Если да, то делаем рекурсивный вызов процедуры обхода с тем же г, индексом левой/правой части 7), и интервалом пересечения.

Процедура обхода формирует динамический двунаправленный список групп вхождений шаблона (список ответов). В дополнение к основным параметрам локального поиска, мы вводим два вспомогательных параметра. Это указатель на элемент динамического списка ответов и "глобальный сдвиг". Когда мы находим очередные вхождения при "внутреннем" вызове процедуры обхода, мы добавляем к найденной позиции текущее значение сдвига. При этом, полученный ответ мы вписываем в прямо перед тем элементом, куда ведет указатель. При последующих рекурсивных вызовах для левой половины сдвиг не меняется, для правой к сдвигу нужно добавить длину левой половины. Указатели для левого/правого рекурсивного вызовов указывают, соответственно, на только что записанный ответ и на следующий за ним элемент.

В тексте Tj рассмотрим положение всех интервалов, с которыми мы работали во время процедуры обхода. Любая пара из них или вложена, или не пересекается. Причем для каждого к интервалы, на которых процедура обхода запускалась с параметром не могут быть вложенными. Напомним, мы требуем, чтобы исходный интервал был не больше 3|Д|. Следовательно, для каждого к во время обхода было не больше трех интервалов, ассоциированных с Т^. Таким образом, при обходе мы сделали не более 3j рекурсивных вызовов, и общее время работы не превосходит 0(j).

Мы предполагаем, что процедура обхода поддерживает указатель на соответствующее место в списке ответов. Это означает, что в конце работы мы получим отсортированный список не более, чем из 3 j прогрессий. Здесь отсортированный означает, что последний элемент к-ой прогрессии находится левее или равен первому элементу (к + 1)-ой прогрессии. Заметим, что, по построению процедуры обхода, выдаваемые прогрессии могут пересекаться только по граничным элементам.

Процедура упрощения. В процедуре упрощения мы пройдем по всему полученному списку прогрессий. А именно, мы будем сравнивать расстояние между последним элементом текущей прогрессии и первым элементом следующей с шагом каждой из этих прогрессий. Если все эти три числа равны друг другу, мы объединяем прогрессии. В противном случае мы объявляем новую прогрессию ответов.

Давайте мысленно вобьем два "колышка" в интервал [а, /3} так, чтобы разделить его на три приблизительно равных части. Если мы применим Основную лемму к позициям = L^f^J и fa = LnrJ» мы узнаем, что все вхождения Pi в [а, /3] образуют две (одна после другой) арифметические прогрессии. А именно, вхождения, касающиеся и вхождения, не касающиеся но касающиеся Здесь мы пользуемся неравенством /3 - а < 3|Р;|, из которого следует, что каждое вхождение Pi должно задеть <5i или 82. Таким образом, при процедуре упрощения мы будем объявлять новую прогрессию не больше одного раза.

3.1.4 Обсуждение алгоритма

Поиск сжатого шаблона в сжатом тексте (общий вид):

1. Предвычисления: находим длины промежуточных текстов и точки разрезов;

2. Последовательно, элемент за элементом, заполняем таблицу прогрессий;

3. Получаем нужные ответы (существование вхождения, первое вхождение, число вхождений).

Отметим два возможных улучшения алгоритма. Посмотрим внимательно на процедуру вычисления нового элемента таблицы прогрессий. Заметим, что локальный поиск работает за время 0(h), где h — высота прямолинейной программы (точнее, высота соответствующего дерева распаковки), порождающей Т. Пересечение арифметических прогрессий требует всего 0(log |Т|) шагов. Таким образом, если бы нам удалось "сбалансировать" любую прямолинейную программу до 0(log|T|) высоты, мы немедленно получили бы 0(nm log |Т|) оценку времени работы алгоритма.

Теперь взглянем на правила порождения текста. Коллаж-системы (collage systems) [29] и LZ77 [47] используют конкатенацию и обрезку.

Конечно, как показал Риттер [42], мы можем оставить только конкатенации, расширив размер архива лишь в 0(log \Т\) раз. Но есть надежда, что представленный алгоритм может работать напрямую с текстами, построенными по правилам конкатенации/обрезки.

Еще одной ближайшей задачей является преобразование таблицы прогрессий в прямолинейную программу размера 0(п2), описывающую все вхождения РвТ. Здесь под описанием мы понимаем бинарную строку, в которой единицы стоят в точности на местах первых символов вхождений шаблона в текст.

3.2 Алгоритм вычисления периодов и накрытий

Основной идеей нашего алгоритма поиска подстрок в сжатых текстах было вычисление таблицы прогрессий. По сути, мы проводили частичную распаковку текста, извлекая лишь существенную для поиска подстроки информацию. В этом разделе мы покажем, что быстрый алгоритм построения таблицы прогрессий помогает вычислить периоды и накрытия сжатого текста за полиномиальное (относительно сжатого размера) время.

Периодом строки Т назовем такую строку W (и ее длину |VF|), что Т является префиксом Wk для некоторого натурального к. Накрытием (от "cover", термин введен в работе [9]) строки Т называется такая строка С, что каждый символ в Т накрыт каким-то вхождением С в Т. Каждый период и каждое накрытие однозначно задаются своей длиной, так как, по определению, они являются префиксами Т. В этом разделе мы будем использовать обозначение t — |Т|.

С С С т т

Задача об определении периода/накрытия сжатого текста: дан текст Т, представленный прямолинейной программой. Найти длину минимального периода/накрытия и вычислить "сжатое" представление всех периодов и накрытий.

Наши алгоритмы основаны на комбинаторных свойствах текстов, которые были использованы при решении классических постановок (без сжатия) рассматриваемых задач:

1. У строки длины t длины периодов в интервале — — ^щ-] образуют одну арифметическую прогрессию.

2. Каждое накрытие является границей (border), то есть одновременно суффиксом и префиксом текста. Если какая-то граница с длиной в интервале [^fft, Je] является накрытием, то все меньшие границы в этом интервале также являются накрытиями.

3. Каждый текст имеет период длины и тогда и только тогда, когда у него есть граница t — и.

4. По прямолинейной программе размера п, порождающей текст Т, и по числам а, /3 мы можем построить за линейное (от п) время ПП линейного размера, порождающую подстроку Т[а, (5].

Алгоритм вычисления периодов сжатого текста. В этом разделе мы часто используем позиции в тексте, представленные в виде дробей.

Если такая дробь несократима, то мы имеем в виду ее нижнюю целую часть, но для компактности записи мы опускаем знаки целой части. Используя Свойство 3, мы будем искать границы вместо периодов, причем будем вести отдельный поиск в каждом интервале [^r, Зафиксируем к. Теперь составим два списка "кандидатов в границы".

Шаг 1: возьмем ^щ-префикс текста Т (обозначим его Рк) и найдем все его вхождения в ^-суффикс Т. По Основной лемме эти вхождения образуют одну арифметическую прогрессию. Первым списком кандидатов будут расстояния от начал вхождений Рк до конца текста Т.

Рк Рк Рк

Шаг 2: возьмем ^гн-суффикс текста Т (обозначим его Sk) и найдем все его вхождения в ^-префикс Т. По Основной лемме эти вхождения образуют одну арифметическую прогрессию. Вторым списком кандидатов будут расстояния от начала текста Т до концов вхождений Sk

Шаг 3: пересечем две прогрессии, полученные на первых двух шагах. Мы получим в точности длины всех границ текста в интервале [^fft, Поиск периодов в сжатом тексте:

1. Для каждого к от 0 до [log \Т\] мы a) Строим прямолинейные программы для описания Pk,Sk', b) Строим таблицы прогрессий для пар (Т, Sk) и (Т, Р&); c) Запускаем процедуру локального поиска Рк в ^-суффиксе

Т\ d) Запускаем процедуру локального поиска Sk в ^-префиксе Г; e) Пересекаем две полученные прогрессии.

2. Чтобы получить длины периодов, надо из t вычесть полученные длины границ.

Sk Рк

Pk Sk

Корректность: пусть число I € [^fft, попало в оба списка кандидатов. Тогда у строк Т[\.Л] и T[(t — I + l).i] совпадают первые ^ш" и последние букв. Таким образом, они полностью совпадают и I является границей. Сложность: согласно Свойству 4, длина прямолинейных программ, описывающих суффиксы и префиксы, линейна относительно п. Следовательно, построение двух таблиц прогрессий займет 0(п3). Локальный поиск и пересечение прогрессий занимает 0(п) шагов. Таким образом, суммарное время работы алгоритма по всем интервалам составляет 0(n3 log |Т|).

Задача о нахождении периода сжатого текста была поставлена в 1996 в расширенных тезисах [20]. К сожалению, полное описание алгоритма из этой работы (он требовал 0(п5 log3 \Т\) шагов) так и не было опубликовано.

Алгоритм нахождения накрытий сжатого текста. Будем вести поиск по отдельности внутри каждого интервала [^щ", Как было показано выше, мы можем найти все границы в таком интервале за время 0(п3). Согласно Свойству 2, достаточно применить бинарный поиск с помощью "проверки накрывания", чтобы найти все накрытия в интервале.

Проверка накрывания (проверить по сжатым текстам С и Г, является ли С накрытием для Т):

1. Строим таблицу прогрессий для С и Т.

2. Для каждого промежуточного текста 7) с помощью процедуры локального поиска делаем следующую проверку. Рассматриваем |С|-окрестность точки разреза 7), исключая лишь позиции, которые находятся ближе чем \С\ к краям 7). Убеждаемся, что этот интервал полностью покрыт С-вхождениями.

3. С помощью локального поиска проверяем, что |С|-префикс и \С|-суффикс текста Т полностью покрыты С-вхождениями.

Корректность: по индукции можно доказать, что С является накрытием тогда и только тогда, когда мы получили ответ "да" на все проверки шагов 2 и 3. Сложность: поиск границ по всем интервалам занимает 0(пг log \Т\) время. Проверка накрывания требует 0(п3) шагов, так как первый шаг требует 0(п3), второй — 0(п2), а третий — 0(п). Мы вызываем процедуру проверки накрывания не более log \Т\ раз в каждом из

IРОССИЙСКАЯ j ГОСУДАРCI С-ИНАЯ log \Т\ интервалов. Таким образом, суммарное время работы алгоритма по всем интервалам составляет 0(n3 log2 \Т\) шагов.

3.3 Алгоритм поиска оконных подпоследовательностей

В этом разделе мы опишем алгоритм для проверки вложимости шаблона Р в текст Т, представленный прямолинейной программой.

На практике часто требуется найти "достаточно компактную" подпоследовательность. Минимальным окном в тексте Т назовем такую подстроку S текста Т, которая 1) содержит Р, как подпоследовательность, и 2) никакая собственная подстрока S не обладает свойством 1. Мы будем также называть гоокном подстроку текста Т длины w. Мы рассматриваем следующие пять задач:

1. Определить, является ли шаблон Р подпоследовательностью в тексте Г.

2. Сосчитать количество минимальных окон в тексте Т, в которые вкладывается шаблон Р.

3. Определить, вкладывается ли шаблон Р в какое-нибудь и>-окно текста Т.

4. Сосчитать количество го-окон в тексте Т, в которые вкладывается Р.

5. Сосчитать количество минимальных окон в Т размером не больше w, в которые вкладывается Р.

Для решения пяти вышеописанных задач мы определим вспомогательные структуры данных. Далее мы покажем, как вычислить эти структуры и обсудим итоговый алгоритм.

3.3.1 Вспомогательные структуры данных

С этого момента мы рассматриваем текст Т, сжатый прямолинейной программой X размера га. Пусть \Р\ = к и Pi,., Pi — все различные подстроки шаблона Р. Заметим, что / < к2.

Теперь мы определим пять вспомогательных структур данных.

Левые вложения. Для каждого нетерминала Xi прямолинейной программы X и подстроки шаблона Pj мы определяем L^j как длину минимального префикса строки Хг, в которую вкладывается Pj. Если такого префикса нет, мы устанавливаем Ljj = оо.

Правые вложения. Для каждого нетерминала Х( прямолинейной программы X и подстроки шаблона Pj мы определяем Rij как длину минимального суффикса строки Xi, в который вкладывается Pj. Если такого префикса нет, мы устанавливаем R^j = оо.

Минимальные окна. Для каждого нетерминала Х{ прямолинейной программы X мы определим MWi как число минимальных окон в строке Xi, в которые вкладывается Р.

Фиксированные окна. Для каждого нетерминала Xi прямолинейной программы X мы определим FWi как число w-окон в строке Xi, в которые вкладывается Р.

Ограниченные минимальные окна. Для каждого нетерминала Xi прямолинейной программы X мы определим В MWi как число окон размером не больше w, в строке Xi, в которые вкладывается Р.

3.3.2 Вычисление вспомогательных структур данных

Покажем, как вычислить значения элементов пяти вышеописанных массивов.

Левые вложения. Будем проводить вычисления вдоль конструкции прямолинейной программы. Мы легко можем вычислить значение L для однобуквенных символов и всех возможных Pi. Пусть теперь Х{ —> ХрХд. Если Lpj ф оо, тогда просто Ьц = Lv]. В противном случае, мы должны найти такое разбиение Pj на две части PUPV, что и LP)U, и Lq,0 конечны. Нам нужно найти разбиение, максимизирующее первую часть (то есть \Ри\)- Мы будем делать это бинарным поиском. Если мы нашли такое разбиение, то L^j = \Хр\ + Lq>v, иначе Lij = оо. Таким образом, время работы на одном шаге — 0(log А:), общее время работы — 0(ml\ogk) = 0(mk2logk).

Правые вложения. Вычисляем аналогично левым вложениям.

Минимальные окна. Будем использовать вычисления вдоль конструкции прямолинейной программы, а также данные о левых и правых вложениях. Для подсчета минимальных окон в Х{ —> XpXq мы должны сложить уже вычисленные значения для Хр и Xq и прибавить некоторое количество пограничных окон. Заметим, что для каждого разбиения Р — PUPV может быть не более одного минимального пограничного окна, в котором Ри вкладывается внутри Хр, Pv внутри Xq. Используя данные о правых и левых вложениях, мы определим, для каких разбиений такие пограничные минимальные окна есть. В этом месте нужно быть аккуратным. Одному минимальному окну может соответствовать несколько последовательных разбиений. Поэтому будем действовать следующим образом. Мы будем рассматривать все разбиения шаблона от "все в Хр до "все в Xq и увеличивать счетчик пограничных окон только в случае, когда 1) первая часть разбиения вкладывается в Хр, а вторая в Xq; и 2) получившееся минимальное окно сдвинуто относительно предыдущего успешного вложения. Таким образом, трудоемкость вычисления этого массива равна 0(тк).

Фиксированные окна. Схема вычисления такая же, как и для минимальных окон. Здесь мы лишь покажем, как сосчитать пограничные фиксированные окна для Х{ —> XpXq. Основное наблюдение: любое пограничное w-окно, в которое вкладывается Р, также содержит минимальное окно, в которое вкладывается Р. Также, как и в предыдущем абзаце, мы рассматриваем по очереди все разбиения шаблона Р. Для каждого разбиения, пользуясь данными о правых и левых вложениях, мы находим минимальное окно, соответствующее этому разбиению. Сравнивая его с предыдущим, мы прибавляем к счетчику количество w-окон, которые содержат новое минимальное окно, но не старое. Трудоемкость вычисления этого массива также равна 0(mk)

Ограниченные минимальные окна. Используем ту же технику, что и для минимальных окон. Просто при подсчете мы игнорируем слишком большие пограничные минимальные окна.

3.3.3 Итоговый алгоритм и его трудоемкость

Наши структуры содержат ответы для всех пяти задач:

1. Шаблон Р является подпоследовательностью в тексте Т тогда и только тогда, когда Ф оо (мы считаем Р\ = Р),

2. Количество минимальных окон в Т, в которые вкладывается Р, равно MWm,

3. Шаблон Р является подпоследовательностью некоторого го-окна тогда и только тогда, когда FWm ^ О,

4. Количество го-окон, в которые вкладывается Р, равно FWrn,

5. Количество окон размера не больше w, в которые вкладывается Р, равно BMWm.

Таким образом, итоговая трудоемкость нашего алгоритма для шаблона длины к и текста, представленного прямолинейной программой размера га, равна 0(mk2 log к).

Замечание. По теореме Риттера [43] по тексту, сжатому алгоритмом LZ78, можно построить прямолинейную программу, лишь линейно увеличив размер архива. Сама процедура преобразования также линейна. Это значит, что наши задачи могут быть решены за время 0(mk2 log к), уже где т — размер 1^78-сжатого текста.

Замечание. Для 1й77-сжатия также можно осуществить переход к прямолинейной программе [43]. Трудоемкость и размер получившейся программы оценивается как 0(т log п), где т — размер Ьй77-сжатого текста, an — оригинального. Таким образом, применив сначала переход к прямолинейной программе, а затем наш основной алгоритм, мы получим трудоемкость 0(mk2 log к log п) для Ь277-сжатия.

3.4 Выводы и открытые вопросы

Алгоритмические свойства грамматик. Желательно охарактеризовать все свойства, которые могут быть вычислены по сжатому тексту за полиномиальное время, и найти для них оптимальные алгоритмы.

• Для поиска сжатого шаблона (размер архива га) в сжатой строке (размер архива п) мы построили алгоритм, работающий за время 0(п2т). Можно ли решить эту задачу быстрее? Гипотеза: достаточно 0(nm log |Т|) времени. Более точно, мы надеемся, что каждый элемент таблицы прогрессий может быть вычислен за время 0(log|T|).

• Можно ли ускорить вычисление редакторского расстояния (расстояния Левенштейна) в случае, когда один из текстов хорошо сжимается? Формально, можно ли вычислить редакторское расстояние за время О(пш), где п — это длина Ti, am — размер грамматики, порождающей Т2? Такой результат позволил бы ускорить вычисление редакторского расстояния для любого "сверхлогарифмического 2 сжатия". Напомним, классический алгоритм требует O(j^) шагов для решения этой задачи.

• Можно ли вычислить длину наибольшей общей подстроки двух текстов, представленных прямолинейными программами, за полиномиальное (от размера ПП) время?

• Можно ли ускорить предложенный в этой работе алгоритм для поиска оконных подпоследовательностей? Точнее, можно ли уменьшить /^-зависимый сомножитель в оценке времени работы алгоритма?

Архивирование суффиксного дерева. Алгоритмы поиска явно заданного шаблона в сжатом тексте работают за время, близкое к линейному от размера архива. Но как провести предварительные вычисления, если мы хотим подготовить текст ко многократному поиску шаблонов? Более формально, существует ли такая структура данных, которая (1) поддерживает поиск шаблона за время, линейное относительно длины шаблона, и (2) для "хорошо-сжимаемых" текстов имеет размер меньше, чем длина самого текста?

Применения к верификации. Одним из главных прорывов в верификации моделей программ является алгоритм символьной верификации. Он оперирует не с множествами состояний программы, а с описаниями этих множеств в виде упорядоченных двоичных решающих диаграмм (OBDD). Можно показать, что OBDD-представление можно перевести в представление грамматикой того же размера. С другой стороны, есть множества, для которых представление грамматикой будет экспоненциально короче. Чтобы встроить более выразительное описание множеств грамматиками в алгоритм символьной верификации, необходимо ответить на следующий вопрос. Как по двум множествам А я В, представленных грамматиками, получить близкую к минимальной грамматику, представляющую А Г) В, и грамматику, представляющую A U В?

Глава 4

Нижние оценки на трудоемкость обработки сжатых текстов

4.1 Расстояние Хэмминга между сжатыми текстами

Расстоянием Хэмминга называется количество различий между двумя текстами равной длины. Задача о расстоянии Хэмминга между сжатыми текстами (считающий вариант): даны два текста одинаковой длины Т и S, представленные в виде прямолинейных программ. Найти расстояние Хэмминга HD(T, S) между ними.

В теории сложности говорят, что функция принадлежит классу #Р, если существует такая недетерминированная полиномиальная машина Тьюринга М, что значением функции будет число принимающих веток

М на соответствующих входных данных. Иначе говоря, существует такая полиномиально-вычислимая функция G(x, у) и многочлен р, что fix) = #{y\G{x,y) = "да", и \у\ < р(|х|)}.

Мы говорим, что функция / имеет [1]-Тьюринг сведение к функции д, если существуют такие полиномиально-вычислимые функции Е и D, что f(x) = D{g{E(x))). Функция называется #Р-полной (относительно [1]-Тьюринг сведений), если она принадлежит классу #Р, и любая другая функция этого класса имеет к ней [1]-Тьюринг сведение. Фразы "функция / является #Р-полной" и "задача вычисления / является #Р-полной" являются синонимами.

Теорема 4.1.1. Задача о расстоянии Хэмминга между сжатыми текстами является #Р-полной.

Доказательство. Принадлежность jfP. Для расстояния Хэмминга в качестве функции G мы можем взять сравнение текстов по одной позиции: G(T, S; у) = "да", если Ту Ф Sy. Тогда количество у, дающих ответ "да", в точности равно расстоянию Хэмминга. Функция G — полиномиально вычислима, так как, зная длины всех вспомогательных текстов, мы можем пройти грамматику "сверху вниз". Каждый раз спускаясь в нужную ветку, мы придем к символу Ту.

Р-полнота. Для доказательства полноты задачи достаточно свести к ней другую полную задачу в рассматриваемом классе. Напомним формулировку ^Р-полной задачи сумма размеров [2]: даны натуральные числа u>i,. ,wn,t в двоичной записи. Требуется определить, сколько существует таких наборов xi,.,xn £ {0,1}, что J2i=i хг' wi = ^ Иначе говоря, сколько подмножеств w = (w\,., wn) имеют сумму элементов, равную t.

Построим [1]-Тьюринг сведение от суммы размеров к расстоянию Хэмминга между сжатыми текстами. Зафиксируем входные данные для суммы размеров. Построим описания двух текстов прямолинейными программами так, чтобы по расстоянию между ними можно было определить ответ для суммы размеров.

Идея конструкции заключается в следующем. Пусть s = w\-{-----1-wn.

Оба текста будут иметь длину (s + 1)2П. Мысленно мы будем представлять их себе как последовательность 2П блоков по s + 1 символу каждый. Первый текст Т будет кодировать число t. Все его блоки будут одинаковы. Все символы, кроме одного, — "О", единственная "1" стоит на t+1 месте. Блоки второго текста S будут соответствовать всем возможным подмножествам w. В каждом из них единственная "1" будет стоять непосредственно после позиции, равной сумме элементов подмножества. Формулами тексты Т и S можно записать так:

2n—1

Т = (О'Ю5-*)2", S = П (0*®10e-*-®).

2=0

Здесь х о w = XjWi, a f] обозначает конкатенацию.

Строка S (будем называть ее строка Лори) впервые появилась в работе Маркуса Лори [33]. Лори доказал [33], что зная входные параметры задачи о сумме размеров, мы можем построить ПП полиномиального размера, описывающие строки S и Т.

Заметим теперь, что HD(T, S) равно удвоенному числу тех подмножеств w, чья сумма не равна t. Таким образом, ответ для суммы размеров можно получить по формуле 2n — \HD(T, S).

Оказывается, в классе ^Р-полных задач можно выделять подклассы, несводимые друг к другу по Карпу. Напомним здесь, что функция f(x) сводится по Карпу к функции д(х), если существует такая полиномиально вычислимая функция t, что f(x) = g(t(x)). Недавно [38] был введен интересный класс функций TotP. Функция / принадлежит классу TotP, если существует такая недетерминированная полиномиальная машина Тьюринга М, что f(x) равно числу всех веток вычисления М(х) минус один. В класс TotP попадают многие задачи, для которых "да/нет" версия (то есть проверка, равно ли f(x) нулю) полиномиально разрешима, а считающий вариант — #Р-полон.

Можно показать, что расстояние Хэмминга между сжатыми текстами принадлежит классу TotP. В самом деле, можно сравнивать интервалы исходных текстов и разветвлять вычисления всякий раз, когда обе половины интервала из первого текста не равны аналогичным участкам второго. Для каждой пары неравных текстов нужно также добавить дополнительную искусственную ветку вычислений, чтобы компенсировать вычитание единицы из определения принадлежности TotP.

4.2 Сжатые подпоследовательности в сжатых текстах

В этом разделе мы дадим две нижние оценки на вычислительную сложность следующей задачи:

• Поиск сжатой подпоследовательности в сжатом тексте (для краткости — Вложимостъ). Даны прямолинейные программы, представляющие строку Р (шаблон) и строку Т (текст). Требуется определить, являются ли буквы шаблона подпоследовательностью в строке Т (обозначение: Р <->Т).

В этом разделе представлено два основных результата. Мы начнем со сведения известной NP-полной задачи (Сумма размеров) к задаче Вло-жимости. Таким образом, мы получим NP-трудность последней. Следующим шагом будет сведение Вложимости к Невложимости и наоборот. Немедленным следствием из этой симметричности станет со NP-трудность изучаемой задачи.

4.2.1 NP-трудность

На этот раз нам понадобится "да/нет" версия NP-полной задачи Сумма размеров (см. [2]):

• Дана двоичная запись натуральных чисел w\,. ,wn,t. Требуется определить, существуют ли Х\,., хп € {0,1} такие, что г=1

Теорема 4.2.1. Сумма размеров сводится к Вложимости.

Доказательство. Пусть t,w = (w\., wn) - входные данные Суммы размеров (будем считать, что п > 1). Мы построим такие прямолинейные программы Т и (/ (порождающие тексты F, G), что подмножество w с суммой t существует тогда и только тогда, когда F ► G. п t.

Введем обозначения s = w\ + • • • + wn, N = 2ns. Каждому подмножеству w можно поставить в соответствие строчку х = х\. хп длины п из нулей и единиц, то есть целое число от 0 до 2П — 1. По-прежнему, будем пользоваться обозначением х о w = Ya=i xiwi- Фактически, х о w дает сумму подмножества w, кодируемого числом х.

Конструкция. Наша задача "закодировать" каждый набор входных данных для Суммы размеров через входные данные для Вложимости. Опишем текстовые строки F и G: ri si5N /пг ГУ /от

Lr — Lrg СТО =

2n—1

Gi= П(10а) = (1()5)2П = °2N х=0

2"—1

С3= П (О^Ю3-^) G4 = 0Ш х=0

F = FqN~x Fo = 10ZN+tl0N+1

Мы использовали знак П для обозначения конкатенации соответствующих слов в порядке изменения индекса от нижнего предела к верхнему.

Этими равенствами мы определили тексты F и G. Ниже мы докажем, что они могут быть порождены прямолинейными программами Т и д. Но сначала убедимся, что вложимость текста F в G равносильна существованию подмножества w с суммой t.

Равносильность существования подмножества с заданной суммой и вложимости.

Существует подмножество вложимость". Пусть х — код подмножества w с суммой то есть х о w = t. Рассмотрим начало С, то есть

G1G2G3G4G1., и выделим следующее вложение Fq. Отметим 1 в х-ом блоке G\, затем 3N +1 нулей, далее (в точности потому что х о w = t) стоит 1 и, отметив следующие N +1 нулей, мы окажемся перед ж-й единицей во втором Gь Таким образом, имея bN блоков Go = G1G2G3G4, мы сможем вложить 5N — 1 копий Fq. Что, собственно, и требовалось проверить: F ^ G.

G\ G2 G3 G4 ю.о[ I10.0I I о . 0 I I [.010.1 I 0 . 0 .

N нулей 2 N N нулей t+1

Вложимость существует подмножество". Пусть F G. Предположим также, что ответ в Сумме размеров отрицательный. Выведем из этих двух утверждений противоречие.

Мы будем искать нули в G, которые не задействованы во вложении F в G. Это вложение представляет собой 5N — 1 непересекающихся вложений Fq в G. Слово Fq содержит две единицы, между которыми расположено ровно 3N + t нулей.

Убедимся, от противного, что в G нет двух единиц, между которыми расположено в точности столько же нулей. Рассмотрим два случая: первая единица находится в блоке G\ (скажем, в подблоке номер у). Тогда, сдвинувшись на 3N + t нулей, мы попадем в у-ый подблок G3. Если бы в этом подблоке после t нулей стояла единица, то мы бы получили у о w = t — противоречие с несуществованием подмножества с суммой t.

-ый подблок у-ый подблок о-о| I I I-.010.I I

N-v-,

Gi 3N+t нулей Gz

Второй случай: левая единица лежит в блоке G3. Тогда, сдвинувшись на 3N +1 нулей, мы попадем внутрь блока где вообще нет единиц. з G4 G1 С?2

I 1ю-о1 I I I О . О

N нулей t + 1 N нулей 2N нулей

Следовательно, при каждом вложении Fq хотя бы один ноль (между двух единиц) остается незадействованным. Осталось лишь оценить с двух сторон количество нулей в G. По построению, их там 5N-(£N+t+l). С другой стороны, каждое слово Fq содержит 4N + t + 1 нулей и еще хотя бы 5iV — 1 ноль не задействован. Таким образом, общее количество нулей в G должно быть не меньше, чем

5N-l)-(W+t+l)+5N-l = bN-(4N+t+l)+(N-t-2) > 5iV-(4JV-K+l).

Поясним последнее неравенство: N = s2n > 4s > t + 2. То есть мы получили больше нулей в G, чем там есть по построению, что и дает нам противоречие.

Реализация F uG в виде прямолинейных программ. Заметим, что, за одним исключением, F и G строятся из 0 и 1 только с помощью полиномиального числа конкатенаций и возведения в степень (двоичная запись всех использованных степеней - полиномиального размера). Такие конструкции напрямую реализуются сжатыми словами полиномиального размера. Единственным нетривиальным блоком является G3. Этот блок мы уже представили как строку Лори в предыдущем разделе, посвященном расстоянию Хэмминга. Конструкция сжатой версии полиномиального размера впервые была предложена Маркусом Лори в работе [33).

Полиномиальность сведения. Для завершения доказательства необходимо убедиться, что построение прямолинейных программ, вычисляющих F и G, полиномиально относительно размера входных данных задачи Сумма размеров. Чтобы убедиться в этом, достаточно заметить, что в построении F и G мы использовали лишь конкатенации и возведение в степени, являющиеся результатами арифметических действий над t и W\,., wn. □

Следствие 4.2.1. Вложимостъ NP-трудна. 4.2.2 coNP-трудность

Теорема 4.2.2. Вложимостъ сводится (по Карпу) к Невложимости. Невложимость сводится к Вложимости.

Доказательство. Мы будем доказывать следующее утверждение: существует полиномиальный алгоритм, позволяющий для любых сжатых слов F и G построить такие сжатые слова F\ и G\ (естественно, что в размер их сжатого представления может быть лишь полиномиально больше, чем у F и G), что

F^G^Fi^Gi. (*)

В случае унарного алфавита обе задачи лежат в Р. Будем считать, что в алфавите хотя бы 2 буквы. Заметим, что за полиномиальное время можно вычислить последнюю букву F и дописать в конец к G другую букву (получив G') и при этом F G <£> F G'. Так что, не умаляя общности, можно считать, что F и G заканчиваются на разные буквы.

Пусть F = /1. fk, G = <71. gm. Для каждой буквы алфавита а введем обозначение Ха = (£/a)m+1, где (Е/а) - конкатенация всех букв алфавита, кроме а, в любом порядке. Конструкция:

Fi = G = gi. дт Gi = Xfji. Xfjk

Проверка свойства (*): Мы можем представить G в следующем виде: Rifi. RifiRi+1, где Ri не содержит буквы /;. Утверждение F ^ G равносильно выполнению равенства I = к для нашего представления.

Если I < к, то F\ G\, так как для каждого 1 < г < / +1 выполнено Ri ^ Xf. и fi = fi.

RifiR2X2 RifiRi+i II III

XfJl XflflXfl+1'"

Если I = к, то Ri+1 не пусто, так как gm по предположению не равно fk. По индукции можно убедиться в том, что

Rifi-.Rifi</+XfJ1.Xfi.

Действительно, при г = 1 это следует из факта fi у^ Xfv Переход г —> г+1: если бы вложение существовало бы для г+1, то, так как fk+i </-> xfk+v т0 fk+1 попадало бы не правее Д, а значит было бы вложение и для г, что противоречит предположению индукции. Рассмотрим наше утверждение при г = к и в сумме с фактом Rk+i ^ fk мы получим

Fl ^ Gi. fil/l Rkfk)Rk+l i /

Полиномиальность конструкций: Заметим, что строится за полиномиальное от log га время. Для построения G\ остается лишь добавить правила вида А —> Хаа для всего алфавита и использовать в конструкции эти нетерминальные символы вместо соответствующих терминалов. □

Следствие 4.2.2. Вложимостъ coNP-трудна.

Доказательство. Согласно Теореме 1 Вложимостъ NP-трудна. Следовательно, так как мы используем сведение но Карпу, Невложимость — coNP-трудна. Так как Невложимость сводится к Вложимости (Теорема 2), то Вложимостъ также является coNP-трудной. □

4.3 Выводы и открытые вопросы

Для поиска сжатой подпоследовательности удалось получить нижние оценки на вычислительную сложность. Мы построили доказательство (при предположении NP^coNP), что эта задача лежит за пределами класса NP. С другой стороны, известна только тривиальная верхняя оценка сложности — легко построить алгоритм из класса PSPACE. Главным открытым вопросом остается сближение этих оценок.

Одной из причин интереса к поиску в сжатых текстах являются применения разрабатываемых алгоритмов к медиа-поиску. К сожалению, для поиска по изображениям, аудио и видео материалам грамматики являются, по всей видимости, неудачной моделью сжатых данных. Нам известны теоремы о вычислительной трудности двумерного поиска подстрок [10]. В этой главе мы доказали, что поиск подпоследовательностей и даже вычисление расстояния Хэмминга (при предположении P^NP) не может быть вычислено за полиномиальное время. Таким образом, необходимо найти новую модель сжатых данных, которая бы допускала эффективный поиск приближенного вхождения шаблона.

Глава 5

Разреженная периодичность

Частично определенное слово — это слово в алфавите £ U {о}, где о — это специальная прозрачная (или неопределенная) буква. Другими словами, частично определенное слово представляет собой последовательность обычных слов (блоков), разделенных пропусками фиксированной (но необязательно одинаковой) длины.

Частично определенное слово S называется разреженным периодом (обычного) слова Г, если мы можем разделить Т на одну или несколько параллельно сдвинутых копий S, которые будут удовлетворять следующим условиям:

• Все определенные (видимые) буквы 5-копий совпадают с соответствующими буквами в тексте;

• Каждая буква текста покрыта в точности одной определенной (видимой) буквой из 5-копий.

Представим, что у нас есть несколько копий частично определенного слова, напечатанных на прозрачной бумаге. Тогда это слово будет разреженным периодом некоторого текста, если мы можем сложить наши копии в стопку так, чтобы образовалась одна связная строка без перекрытий видимых букв.

Пример: XoY является разреженным периодом для XXYY.

5.1 Примитивный разреженный период не единственен

Частичный порядок на частично определенных словах. Будем говорить, что одно частичное слово S меньше другого частичного слова Q, если Q может быть разделено на несколько параллельно сдвинутых копий S так, чтобы были выполнены следующие свойства:

• Все определенные (видимые) буквы S*-копий совпадают с соответствующими буквами Q

• Каждая буква Q покрыта в точности одной определенной буквой из S-копий.

В частности, любой разреженный период меньше, чем сам текст. На самом деле, это определение просто расширяет разреженную периодичность на частично определенные слова. Пример:

А Е8 в ШЕ8ИШШ СИР ИННИИ меньше чем

А А В В А А В В С с D D с с D D

В классической периодичности для каждого текста существует единственный примитивный чистый период. Здесь под словом "примитивный" мы имеем в виду, что любой другой период является всего лишь последовательным повторением нескольких копий примитивного периода. Для обнаружения разреженной периодичности было бы крайне важно иметь такое же свойство.

Вопрос о примитивном разреженным периоде: верно ли, что для каждого обычного слова существует единственный примитивный разреженный период (то есть он меньше любого другого)? Переформулировка: верно ли, что любые два разреженных периода одного слова имеют общий разреженный "иодпериод"?

Удивительно, но эта столь естественно выглядящая гипотеза неверна. Здесь мы представляем наименьший из известных нам (24 буквы) контрпримеров. Следующие разреженные периоды

AAA А|А AIAIAIBIA А В В А А В А А А А А А А А и

А А А А А А А А В А А В В А А В А А А А А А А А несравнимы между собой. Дадим лишь краткий набросок объяснения, почему у них не может быть общего подпериода. Предположим, что он все же есть. Тогда это частично определенное слово имеет только одну букву В. Так как расстояние между первой и второй буквами В в тексте равно трем, сдвиг между первой и второй копией нашего подпериода тоже равен трем. Таким образом, это частично определенное слово начинается с трех подряд идущих А. Но с другой стороны, сдвиг третьей копии относительно второй равен единице. Следовательно, стартовые блоки второй и третьей копии перекрываются.

Как получить больше двух попарно несравнимых разреженных периодов? Мы можем использовать для этой цели "рекурсивную конструкцию". Пусть Т — это текст вышеприведенного контрпримера, а тексты Та^х и Тд2в2 получены из Т просто использованием других букв. Построим текст Т2, заменяя каждую букву А в Г на Та1в1 и каждую В в Т на Та2в2 ■ Теперь мы можем описать четыре несравнимых периода для TV Сам текст Т2 имеет длину 242. Сгруппируем его буквы на 24 блока по 24 буквы. Оставим лишь 12 блоков, используя как шаблон одно из двух вышеприведенных частично определенных слов. Теперь внутри каждого блока тоже оставим лишь 12 символов, используя один из двух разреженных периодов исходного контрпримера (одинаково в каждом блоке).

Мы можем повторять эту конструкцию несколько раз. Тогда текст Т\ будет иметь длину 24* и у него будет 2к попарно несравнимых периодов. Асимптотически, эта конструкция дает нижнюю оценку п^5 > на количество примитивных разреженных периодов.

В 2003 году в своем курсе лекций [22] Теро Харью поставил следующий вопрос. Предположим, что некоторая раскрашенная клетчатая фигура имеет разбиение на одинаковые копии одного шаблона и может быть разбита на копии другого шаблона. Верно ли, что всегда существует такой третий шаблон, что на его копии можно разбить и первый, и второй? Этот вопрос был мотивирован изучением defect effect в комбинаторике на словах [23]. Наш пример дает отрицательный ответ на вопрос Харью даже для одномерных (но необязательно связных!) фигур.

5.2 Свойства разреженной периодичности

Начнем наше исследование с классификации всех возможных разреженных периодов унарного (используется только одна буква) слова длины п. Так мы получим точную верхнюю оценку на количество всех разреженных периодов для текста длины п. Далее мы переформулируем разреженную периодичность в алгебраических терминах (аналогично правилу Si = Si+P для классической периодичности). Пользуясь этой переформулировкой мы докажем, что каждый примитивный разреженный период меньше классического примитивного периода. Наконец, мы представим алгоритм поиска всех разреженных периодов минимального размера.

5.2.1 Количество разреженных периодов

Теорема 5.2.1. Существует биективное соответствие между разреженными периодами унарного слова длины п и упорядоченными разложениями п = пу . •щ, где щ,. > 2.

Доказательство. Мы начнем с описания множества разреженных периодов (иерархическая конструкция) унарного слова длины п. После этого мы докажем полноту этого множества, а именно: любой разреженный период в него входит.

0-уровень ШШЦ^Ш 6

1-уровень ИНИЕХХ!

3-2

2-уровень ЩЮЛ^]

1-2-3

2-3

1-3-2

1-6

Мы разделяем множество всех разреженных периодов на уровни. Каждому периоду в нашей системе будет поставлен в соответствие специальный код. Весь текст будет единственным периодом 0-уровня и ему будет соответствовать код п. Для каждого разложения п = щ • Пг, где П2 > 2, блок из первых щ букв будет периодом 1-уровня с кодом щ • щ. На самом деле, 0-уровень и 1-уровень вместе составляют множество всех классических (то есть связных) периодов.

Объясним теперь, как, отталкиваясь от периода Р из fc-уровня и с кодом п\.nk, построить новый разреженный период Q из /с + 2-у ровня.

Нужно взять разложение щ = т\ • т,2 • шз, где Ш2, тз > 2. В течение всего процесса построения первое число в коде равно длине непрерывных блоков в периоде (в рамках наших построений все блоки в периоде имеют равную длину). Для построения нового разреженного периода Q мы возьмем каждый блок Р, разделим его на газ групп по rai - гаг символов, и в каждой такой группе оставим только т\. Заметим здесь, что Р может быть покрыто т,2 копиями Q (со сдвигами 0, rai,., mi • (rri2 — 1)). Таким образом, Q также является разреженным периодом. Мы присвоим ему код rai • гаг • газ • П2- . -щ. Подчеркнем, что наше построение сохраняет неравенство П2,., > 2 для всех кодов.

Докажем теперь, что каждый разреженный период включен в наше построение. Возьмем произвольный разреженный период Р. Все его блоки должны иметь одинаковую длину s, и длина каждого пропуска должна быть кратна s. В самом деле, в замощении текста вторая копия Р сдвинута на длину первого блока si. Таким образом, чтобы избежать перекрытия, все другие блоки по длине не превосходят si. Предположим теперь, что какой-то блок Ь оказался первым из тех, чья длина все же строго меньше чем si. Тогда длина пропуска между блоком b из первой копии Р и Ъ из второй копии Р строго больше si и строго меньше 2s\. Следовательно, этот пропуск не может быть полностью заполнен. Каждый пропуск в Р заполнен несколькими связными блоками из других копий. Следовательно, все пропуски кратны s = s\.

Нам потребуется определить простую степень для каждого разреженного периода Р. Пусть s — это размер блока, a g-s — длина первого пропуска. Простой степенью Р будет объединение д + l копии Р со сдвигами 0, s, 2s,. ,д • s.

Факт: Простая степень произвольного разреженного периода Р также является разреженным периодом.

Доказательство: возьмем разбиение текста на Р-копии. Пусть s — это размер блока, a g-s — длина первого пропуска в Р. Разделим все копии Р на группы по д + 1 экземпляров следующим образом. Будем рассматривать все копии слева направо. Пропуск между первыми двумя блоками первой копии Р может быть заполнен только первыми блоками других Р-копий. Первый экземпляр Р и участники заполнения первого пропуска составят нашу первую группу. Предположим теперь, что у нас уже создано несколько групп. Рассмотрим самую левую из еще не использованных копий Р. Посмотрим на ее первый пропуск. Все Р-копии, включенные в уже созданные группы, идут чересчур длинными (не менее s - (д + 1)) непрерывными участками. Таким образом, рассматриваемый пропуск тоже заполнен новыми, еще не использованными копиями. Так как мы обрабатываем копии строго слева направо, для заполнения нашего пропуска используются только первые блоки других копий. Следовательно, мы можем объединить их в очередную группу из д -Hi копии, идущей непрерывно одна за другой. Отметим, что каждая группа в точности является простой степенью Р. Таким образом, мы доказали, что исходный текст имеет разбиение на копии простой степени. Утверждение доказано.

Если существует хоть один разреженный период Р вне нашей конструкции, то будет и такой разреженный период Р\ что (1) сам он не включен в наше построение и (2) его простая степень Q входит в нашу иерархию. Выведем противоречие из этих посылок. В самом деле, пусть пу. .-щ — код Q, длина блоков Р' равна s, a s • д равно длине первого пропуска. Тогда размер блока п\ в разреженном периоде Q кратен s • (д -Н 1). Пусть mi = s,m2 = <7 + 1,тз = n>i/(s ■ {д + 1))- Остается заметить, что Р' на самом деле является разреженным периодом нашей иерархии с кодом mi • rri2 ■ тг ■ п? . -щ.

Теорема доказана. □

Следствие. Пусть Ь(п) — это количество разреженных периодов унарного слова длины п. Только что доказанная теорема утверждает, что L(n) равно количеству разложений п = п\.где щ,., > 2.

Группируя все разложения по крайне правому сомножителю, мы получим следующую рекуррентную формулу:

Замечание. Энциклопедия целочисленных последовательностей [46], поддерживаемая Ней лом Слоаном, содержит две интересные для нас последовательности. Последовательность А067824 определяется в точности формулой из Следствия 1. Последовательность А107736 выражает

L{ 1) = 1; Цп) = 1 + d\п,<1фп количество многочленов р с коэффициентами из {0,1}, которые делят хп — 1, и таких, что коэффициенты частного при делении (хп - 1)/((х — 1 )р{х)) также принадлежат {0,1}. Но это число в точности равно количеству разреженных периодов унарного слова длины п. В самом деле, умножая р на многочлен с коэффициентами из {0,1}, мы проводим разбиение п "единиц" на несколько параллельно сдвинутых копий р без перекрытий. Таким образом, из Теоремы 1 и Следствия вытекает, что последовательности А067824 и А107736 совпадают. Действительно, количество многочленов равно количеству разреженных периодов, количество разреженных периодов равно числу разложений (Теорема 1), а число разложений удовлетворяет нужной рекурсивной формуле (Следствие 1).

Независимо от представленного здесь доказательства, за полгода до публикации работы о разреженной периодичности [3], в статье [15] было дано другое доказательство равенства А067824 и А107736. Сравнивая эти работы, отметим два достоинства доказательства, приведенного в этой диссертации. Во-первых, мы установили конструктивное соответствие между разложениями длины текста на множители и разреженными периодами. Во-вторых, мы внесли определенную структуру в множество всех периодов, разделив их на уровни.

Функция Ь(п) и число разложений также появлялись в книге Дональда Кнута "Искусство программирования" [30]. Тем не менее, никакой замкнутой формулы для вычисления Ь(п) пока не известно. Простыми вычислениями мы можем показать, что для всяких простых чисел р и q верны следующие равенства:

• L(p) = 2,

• L{pk) = 2k,

• L{pq) - 6,

• L(p2q) = 1 + L(l) + L{jp) + L(g) + L(pq) + L(p2) = 16,

• L(p2q2) = 52, в частности L(36) = 52.

Как мы видим, слово длины 36 может иметь до 52 разреженных периодов. Следовательно, найдутся два разных периода с одинаковым "размахом" (расстоянием между первой и последней видимой буквой).

Теперь мы можем сказать больше и о примере во введении. Если d-мерный параллелепипед разбит на копии меньшего параллелепипеда, то последовательность цветов будет обладать разреженным периодом 2d-уровня. Размер этого периода (число видимых букв) будет равно объему меньшего параллелепипеда.

5.2.2 Соотношение между разреженными и классическими периодами

Определение. Будем говорить, что слово Т = to. tn-\ имеет чистый ограниченный период (а,Ъ) (или период а с ограничением 6), если Ь\п, а\Ь, а <Ь и выполнено следующее утверждение: г г + а

Ъ Ь

Другими словами, если мы разделим весь текст на блоки длины 6, то каждый из блоков будет иметь чистый период а. Классический период р можно описать как ограниченный период (р, п).

A1AIBIBIAIAIBIBICICID1DIC1CIDID

Этот текст имеет ограниченные периоды (1,2) и (4,8).

Лемма 5.2.1. У слова Т есть разреженный период Р с кодом щ-. -Щк тогда и только тогда, когда текст обладает ограниченными периодами

2k-l 2к (ni,nin2),.,( Л т, п;). i=1 i=1

У слова Т есть разреженный период Р с кодом щ-. -П2к+1 тогда и только тогда, когда текст обладает ограниченными периодами

2к-1 2к i=1 i=1

Доказательство. Шаг 1: от разреженного периода к ограниченным пе-риодичностям. Будем использовать индукцию по уровню разреженного периода. Рассмотрим соответствующее разбиение текста. Напомним, что все копии Р могут быть разделены на группы по щ экземпляров, со сдвигами внутри группы 0,п\,. ,ni(ri2 — 1). Таким образом, если мы разделим весь текст на блоки по щщ букв, каждый блок будет покрыт Р-копиями из одной группы. Следовательно, внутри каждый блок будет ni-периодическим. Таким образом, мы доказали (nl5 п^)-ограниченную периодичность. Все остальные ограниченные периодичности следуют из индукционного предположения для простой степени Р.

Шаг 2: от ограниченных периодичностей к разреженному иериоду. Рассмотрим верхнюю ограниченную периодичность (П^Г1 Ш=1 пг)

Возьмем частичное слово Q, соответствующее коду (П^Г1 пг)' п2к для

Ш2к-\ \ i=1 Щ) • П2к • Щк+\ для нечетного варианта. Напрямую из верхней ограниченной периодичности следует, что каждая копия Q на одинаковых позициях имеет одинаковые буквы. Следовательно, Q является разреженным периодом текста. Продолжая рассуждение, с помощью второй ограниченной периодичности можно построить следующий разреженный период R внутри Q. В конце концов, из последней ограниченной периодичности мы сможем вывести существование разреженного периода с требуемым кодом. □

Лемма 5.2.2. Пусть у текста Т есть классический период р и ограниченный период (а, Ь), тогда или Ь\р или у текста есть также классический период НОД(а,р).

Доказательство. Возьмем произвольную букву текста Т{. Мы будем стараться сделать несколько прыжков величиной ±р и +а, чтобы в итоге достичь позиции i + НОД(а,р). Нам хочется все время находиться на позициях с одинаковыми буквами. Поэтому мы запретим себе делать прыжок +а из последнего а-блока в каждом 6-блоке. Согласно свойствам расширенного алгоритма Евклида, существуют такие натуральные числа к и I, что НОД(а, р) = ка — 1р. Мы будем использовать следующую жадную стратегию. Если мы имеем право сделать прыжок +а, мы его делаем. В противном случае, попытаемся сделать несколько прыжков ±р. После того, как мы сделаем в точности к прыжков +а, нам останется лишь провести все недостающие передвижения ±р, чтобы очутиться на желаемой позиции. Единственной преградой на пути жадной стратегии может стать ситуация, когда для некоторого j < р для каждой из позиций j,j + — 1 )р нам запрещен прыжок +а. То есть слу

71 чай, когда все эти позиции попали в последние а-блоки в своих 6-блоках. Предположим теперь, что р не делится на Ъ. Тогда и = НОД(р, Ь) < Так как р\п и Ь\п, среди чисел j mod 6,.,[;' + — 1)р] mod b встречаются все такие остатки h по модулю Ь, что h = j(mod и). Следовательно, один из них не больше и, что в свою очередь не превосходит 6/2. Но это значит, что соответствующая позиция никак не могла попасть в последний а-блок своего 6-блока. □

Теорема 5.2.2. Любой примитивный разреженный период Q слова Т является также разреженным периодом для классического примитивного периода Т.

Доказательство. Воспользуемся индукцией по длине текста. Для одно-буквенных слов теорема верна. Пусть р — длина классического периода, а (а, Ь) — верхняя ограниченная периодичность (полученная из кода Q по Лемме 1). Если р = п, теорема верна, поэтому будем считать, что р < п. Согласно иерархической конструкции, все видимые буквы частично определенного слова Q находятся в первых а-блоках своих Ь-блоков. Применим Лемму 2. Если Ь\р, то мы можем получить новый разреженный период Qоставив от Q только ту часть, которая входит в первые р символов текста. Согласно р-периодичности, Q может быть разбито на несколько копий Q' со сдвигами 0, р, 2р,., (^ — 1 )р. Мы получили противоречие с примитивностью Q.

Таким образом, верно второе утверждение из Леммы 2: текст обладает классическим НОД(а,р)-периодом. Но по условию теоремы, р является примитивным классическим периодом. Следовательно, р\а. А раз текст является р-периодическим, то он также и а-периодичен и Ь-нериодичен. На этот раз мы можем оставить от Q только буквы, входящие в первый а-блок текста. Этим мы или получим меньший разреженный период Q' (противоречие с примитивностью Q), или Ь = п и все видимые буквы Q расположены в первом а-блоке текста. В последнем случае, и классический период р, и разреженный Q являются периодами первого а-блока. Так как а < Ъ/2 < п/2, мы можем применить индукционное предположение. □

Следствие 2. Для каждого разреженного периода Q и классического периода р найдется общий разреженный подпериод.

Доказательство. Возьмем примитивный разреженный период Qкоторый меньше (то есть разбивает) Q. Рассмотрим классический примитивный период р'. Из единственности чистого классического примитивного периода следует р'\р. По Теореме 2 разреженный период Q' является также разреженным периодом для первого р'-блока текста. Таким образом, Q' является искомым разреженным подпериодом для Q и р. □

Замечание. Используя технику из Леммы 1, Леммы 2 и Теоремы 2, можно показать, что примитивный разреженный период единственен в случае п = 2к. От противного: возьмем два несравнимых примитивных разреженных периода. Рассмотрим их верхние ограниченные периодичности. Применим рассуждения, подобные Лемме 2. Либо один из этих периодов не примитивен, либо эти верхние ограниченные периодичности совпадают. Двигаясь дальше вниз, мы либо докажем их равенство, либо получим противоречие с примитивностью.

5.2.3 Алгоритм поиска разреженных периодов минимального размера

Определим размер разреженного периода как число его видимых букв. Как найти все разреженные периоды минимального размера? Будем пользоваться Леммой 1 для ответа на этот вопрос. Мы знаем, что каждому разреженному периоду соответствует цепочка вложенных ограниченных периодичностей (ai, 5i),., (a*, bk). Под "вложенностью" мы понимаем делимость fy\щ+1 для каждого г. Заметим, что размер такого разреженного периода равен произведению п Пг*=1

Алгоритм поиска разреженных периодов минимального размера:

1. Для каждой пары а < Ь, такой что а\Ь и 6|п, проверить, обладает ли текст (а, ^-ограниченной периодичностью.

2. Построить ациклический граф из найденных ограниченных периодичностей. Пары (а, Ъ) будут вершинами, и мы будем проводить ребро от (а, 6) к (с, d), если Ь\с.

3. В каждую вершину (а, Ъ) записать значение а/Ь.

4. Найти все пути в графе с наименьшим произведением значений в вершинах.

Анализ алгоритма. Первый шаг требует 0{(ft{n)ri) времени при переборном подходе. Здесь d(n) обозначает количество делителей п. Четвертый шаг лишь незначительно отличается от поиска кратчайших путей в ациклических графах. Сначала нужно совершить один проход по всему графу сверху (маленький период, маленькое ограничение) вниз (большой период, большое ограничение). При проходе мы будем стирать все ребра, которые не участвуют в получении минимальных произведений по путям. В итоге мы получим несколько стоков (вершин без исходящих ребер), и оставим только тот (или те) из них, которые дают минимальное произведение по пути, и удалим все остальные стоки и ребра ведущие к ним. После этого нужно пройти весь граф обратно снизу вверх и стереть все ребра, не участвующие в минимальных путях. В оставшемся графе каждый путь из некоторого истока (вершины без входящих ребер) к некоторому стоку соответствует разреженному периоду минимального размера. Таким образом, мы получили сжатое представление всех разреженных периодов минимального размера. Четвертый шаг алгоритма требует лишь линейное время относительно размера графа. Следовательно время работы алгоритма составляет 0(d2(n)n + d?(n)) =

5.3 Выводы и открытые вопросы

Мы можем предложить ряд естественных, важных и, возможно, не столь сложных вопросов для дальнейшего исследования разреженных периодов. Приведем список этих задач.

1. Изучить не обязательно чистую разреженную периодичность.

2. Найти точную асимптотическую верхнюю оценку L(n).

3. Построить более эффективный (линейный?) алгоритм для нахождения разреженного периода минимального размера.

4. Вычислить, как часто случайное слово (в разных моделях) обладает собственным разреженным периодом. Сравнить полученные результаты с классическим случаем.

5. Проверить, можно ли выразить свойство "слово имеет разреженный квадратный корень" через уравнения в словах. Мы отсылаем читателя к работе [25] для знакомства с исследованиями по выразительной силе уравнений в словах.

6. Проверить, верно ли, что все примитивные периоды имеют одинаковое число видимых букв.

7. Найти другие естественные источники разреженной периодичности.

8. Определить и изучить разреженную периодичность на деревьях и других объектах.

9. Определить и изучить приближенную разреженную периодичность (допускающую небольшие ошибки).

10. Определить и изучить разбиения на копии двух (или более) частичных слов. Этот тип разбиений может оказаться еще более подходящим для применений в архивировании.

На наш вкус, первый вопрос является наиболее важным, так как такое расширение понятия разреженной периодичности позволит описать намного больше структурных свойств текстов. Кроме решения вышеприведенных вопросов, необходимо найти близкие результаты и техники в комбинаторике. Такое естественное понятие, как разреженная периодичность, просто обязано иметь предшественников в дискретной математике.

Литература

1] Гасфилд Д. Строки, деревья и последовательности в алгоритмах: информатика и вычислительная биология // Пер. с англ.— BHV, Санкт-Петербург, 2003.

2] Гэри М., Джонсон Д. Вычислительные машины и труднорешае-мые задачи // Пер. с англ.— Москва, Мир, 1982.

3] Карьюмяки Ю., Лифшиц Ю.М. Разреженная периодичность // Препринт ПОМИ 22/06, 2006.

4] Лифшиц Ю.М. Алгоритмические свойства сжатых текстов // Препринт ПОМИ 23/06, 2006.

5] Лифшиц Ю.М. Обработка сжатых текстов // Материалы XVI Международной школы-семинара "Синтез и сложность управляющих систем", стр. 64-68, Изд-во механико-математического факультета МГУ, 2006.

6] Притыкин Ю.Л. Конечно-автоматные преобразования строго почти периодических последовательностей // Математические заметки, 2006, 80:5, 751-756.

7] Шур A.M., Гамзова Ю.В. Частичные слова и свойство взаимодействия периодов // Известия РАН. Серия математическая, 2004, 68:2, 191-214.

8] Amir A., Benson G., Farach М. Let sleeping files lie: Pattern matching in Z-compressed files // SODA'Ц, 1994.

9] Apostolico A., Farach M., Iliopoulos C.S. Optimal superprimitivity testing for strings // Information Processing Letters, 39(1): 17-20, 1991.

10] Berman P., Karpinski M., Larmore L., Plandowski W., and Rytter W. On the complexity of pattern matching for highly compressed two-dimensional texts // Journal of Computer and Systems Science, 65(2):332-350, 2002.

11] Blanchet-Sadri F. Periodicity on partial words // Computers and Mathematics with Applications, 47(l):71-82, 2004.

12] Blanchet-Sadri F. Primitive partial words // Discrete Applied Mathematics, 148:195-213, 2005.

13] Blanchet-Sadri F., Hegstrom R. Partial words and a theorem of Fine and Wilf revisited // Theoretical Computer Science, 270(1 /2):401— 419, 2002.

14] Boasson L., Berstel J. Partial words and a theorem of Fine and Wilf // Theoretical Computer Science, 218(1):135—141, 1999.

15] Bodini O., Rivals E. Tiling an interval of the discrete line // CPM'06, LNCS 4009, pages 117-128, Springer-Verlag, 2006.

16] Cegielski P., Guessarian I., Lifshits Y., and Matiyasevich Y.

Window subsequence problems for compressed texts // CSR'06, LNCS 3967, pages 127-136, Springer-Verlag, 2006.

17] Constantinescu S., Ilie L. Generalised Fine and Wilf's theorem for arbitrary number of periods // Theoretical Computer Science, 339(l):49-60, 2005.

18] Farach M., Thorup M. String matching in Lempel-Ziv compressed strings // STOC '95, pages 703-712, ACM Press, 1995.

19] Fine N., Wilf H. Uniqueness theorems for periodic functions // Proc. Amer. Math. Soc., 16:109-114, 1965.

20] G§sieniec L., Karpinski M., Plandowski W., and Rytter W.

Efficient algorithms for Lempel-Ziv encoding (extended abstract) // SWAT'96, LNCS 1097, pages 392-403, Springer-Verlag, 1996.

21] Genest В., Muscholl A. Pattern matching and membership for hierarchical message sequence charts // LATIN'02, LNCS 2286, pages 326-340, Springer-Verlag, 2002.

22] Harju T. Defect theorem // Lecture notes of "Combinatorics of words" Tarragona course, 2002/2003.

23] Harju Т., Karhumaki J. Many aspects of defect theorems // Theoretical Computer Science, 324(l):35-54, 2004.

24] Hirao M., Shinohara A., Takeda M., and Arikawa S. Fully compressed pattern matching algorithm for balanced straight-line programs // SPIRE'00, pages 132-138, IEEE Computer Society, 2000.

25] Karhumaki J., Mignosi F., and Plandowski W. The expressibility of languages and relations by word equations / / 1С ALP'97, number 1256 in LNCS, pages 98-109, Springer-Verlag, 1997.

26] Karkkainen J., Navarro G., and Ukkonen E. Approximate string matching over Ziv-Lempel compressed text // CPM'00, LNCS 1848, pages 195-209, Springer-Verlag, 2000.

27] Karpinski M., Rytter W., and Shinohara A. Pattern-matching for strings with short descriptions // CPM'95, LNCS 937, pages 205-214, Springer-Verlag, 1995.

28] Katona G., Szasz D. Matching problems // J. of Combinatorial Theory Ser B, 10(l):60-92, 1971.

29] Kida Т., Matsumoto Т., Shibata Y., Takeda M., Shinohara A., and Arikawa S. Collage system: a unifying framework for compressed pattern matching // Theoretical Computer Science, 298(1):253—272, 2003.

30] Knuth D. The Art of Computer Programming, Volume 4, Fascicle 3: Generating All Combinations and Partitions / D. Knuth // Addison-Wesley, 2005.

31] Lasota S., Rytter W. Faster algorithm for bisimulation equivalence of normed context-free processes // MFCS'06, LNCS 4162, pages 646-657, Springer-Verlag, 2006.

32] Lifshits Y., Lohrey M. Querying and embedding compressed texts // MFCS'06, LNCS 4162, pages 681-692, Springer-Verlag, 2006.

33] Lohrey M. Word problems on compressed word // 1СALP'04, LNCS 3142, pages 906-918, Springer-Verlag, 2004.

34] Markey N., Schnoebelen P. A PTIME-complete matching problem for SLP-compressed words // Information Processing Letters, 90(l):3-6, 2004.

35] Miyazaki M., Shinohara A., and Takeda M. An improved pattern matching algorithm for strings in terms of straight line programs // CPM '97, LNCS 1264, pages 1-11, Springer-Verlag, 1997.

36] Navarro G. Regular expression searching on compressed text // J. of Discrete Algorithms, l(5-6):423-443, 2003.

37] Navarro G., Raffinot M. A general practical approach to pattern matching over Ziv-Lempel compressed text // CPM'99, LNCS 1645, pages 14-36, Springer-Verlag, 1999.

38] Pagourtzis A., Zachos S. The complexity of counting functions with easy decision version // MFCS'06, LNCS 4162, pages 741-752, Springer-Verlag, 2006.

39] Plandowski W. Testing equivalence of morphisms on context-free languages // ESA'94, LNCS 855, pages 460-470, Springer-Verlag, 1994.

40] Plandowski W. Satisfiability of word equations with constants is in PSPACE // J. ACM, 51(3):483-496, 2004.

41] Rytter W. Compressed and fully compressed pattern matching in one and two dimensions // Proceedings of the IEEE, 88(11):1769-1778, 2000.

42] Rytter W. Application of Lempel-Ziv factorization to the approximation of grammar-based compression // Theoretical Computer Science, 302(l-3):211-222, 2003.

43] Rytter W. Grammar compression, LZ-encodings, and string algorithms with implicit input // ICALP'04, LNCS 3142, pages 15-27, Springer-Verlag, 2004.

44] Shur A., Konovalova Y. On the periods of partial words // MFCS'01, LNCS 2136, pages 657-665, Springer-Verlag, 2001.

45] Simpson R., Tijdeman R. Multi-dimensional versions of a theorem of Fine and Wilf and a formula of Sylvester // Proc. Amer. Math. Soc., 131:1661-1667, 2003.

46] Sloane N.J A. Sequence A067824 from The On-Line Encyclopedia of Integer Sequences // [Электронный ресурс] http://www.research.att.com/~njas/sequences/A067824.

47] Ziv J., Lempel A. A universal algorithm for sequential data compression // IEEE Transactions on Information Theory, 23(3):337-343, 1977.