Содержание к диссертации
Введение
1 Введение 4
1.1 Структура диссертации и организация текста 4
1.2 Основные методы исследования 6
1.3 Базовые определения
1.3.1 Основные понятия 7
1.3.2 Закономерности в строках 8
1.4 Модель RAM 10
1.4.1 Доступные инструкции и память 10
1.4.2 Входные данные 11
1.4.3 Время выполнения
1.5 Модель решающего дерева 14
1.6 Обзор результатов
1.6.1 Апробация и публикации 15
1.6.2 Разложение Лемпеля–Зива 15
1.6.3 Повторы в строках 16
1.6.4 Палиндромы 18
2 Разложение Лемпеля–Зива 19
2.1 Введение 19
2.2 Нижняя граница 19
2.3 Сжатый алгоритм поиска разложения Лемпеля–Зива
2.3.1 Короткие факторы 22
2.3.2 Средние факторы 22
2.3.3 Длинные факторы 39
3 Повторывстроках 46
3.1 Введение 46
3.2 Поиск максимальных повторов на решающем дереве
3.2.1 Максимальные повторы 48
3.2.2 Алгоритмы на решающих деревьях 50
3.2.3 Линейное решающее дерево 52
3.3 Поиск максимальных повторов за o(n log n) 57
3.3.1 Сведение к разреженному суффиксному дереву 57
3.3.2 Построение разреженного суффиксного дерева 58
3.4 Онлайновый поиск повторов с откатами 61
3.4.1 Ловец 62
3.4.2 Алгоритм на неупорядоченном алфавите 65
3.4.3 Алгоритм на упорядоченном алфавите 67
Палиндромы 71
4.1 Введение 71
4.2 Нижняя граница на поиск различных подпалиндромов 72
4.3 Распознаватель Palk и других палиндромных языков
4.3.1 Свойства палиндромов 74
4.3.2 Палиндромный итератор 76
4.3.3 Палиндромный мотор 78
4.3.4 Линейный алгоритм 81
Заключение 90
Список литературы
- Базовые определения
- Сжатый алгоритм поиска разложения Лемпеля–Зива
- Алгоритмы на решающих деревьях
- Распознаватель Palk и других палиндромных языков
Введение к работе
Актуальность темы исследования. В теории сложности, теории алгоритмов и вообще компьютерных науках строка — один из центральных объектов. Любая последовательность, будь то последовательность байтов в файле или последовательность слов в тексте, — это строка. Естественно, что такой общий взгляд на природу обрабатываемых данных оправдан не для всех проблем, но круг вопросов, оперирующих столь абстрагированным представлением, по-прежнему очень широк, ведь зачастую закономерности в исходных данных либо слишком сложны для формализации, либо вообще не известны. Алгоритмы, эффективно решающие подобные проблемы, почти всегда явно или неявно решают задачу выделения в строках определённых закономерностей, специфичных для данного конкретного вопроса. В настоящей работе исследуются как закономерности, играющие важную роль в ряде прикладных вопросов, так и закономерности, интересные с теоретической точки зрения и только нащупывающие возможности для применения.
Область, изучающая алгоритмы на строках, ещё в 1985 году получила название стрингология (англ. stringology от string — строка) ], которое сейчас стало общепринятым. Стрингология уже успела обрасти множеством публикаций, рядом монографий и по меньшей мере двумя ежегодными специализированными конференциями с высоким уровнем цитируемости: SPIRE и СРМ (не говоря о нескольких менее значимых конференциях). Красноречивое свидетельство живого и активного интереса к рассматриваемым вопросам — это список литературы к настоящей диссертации, в котором почти половина работ написана не ранее 2010-го года и в большинстве случаев опубликована в трудах наиболее цитируемых конференций по компьютерным наукам.
Диссертация посвящена исследованию алгоритмов вычисления трёх видов закономерностей в строках: разложения Лемпеля-Зива, повторов в строках и палиндромов.
Разложение Лемпеля-Зива (см. определение ниже), впервые описанное этими авторами в ], — это одна из самых распространённых на сегодняшний день конструкций, используемых для сжатия данных без потерь. Практическая важность этой техники, помимо применения в алгоритмах сжатия данных (форматы ZIP, 7z, PNG, GIF и другие), подкрепляется включением разложения Лемпеля-Зива в список IEEE
Milestones, призванный увековечить ключевые вехи компьютерной революции и составленный IEEE (Institute of Electrical and Electronics Engineers) — в настоящее время общепризнанно наиболее авторитетной ассоциацией в области стандартизации в компьютерной технике. С момента изобретения разложения Лемпеля-Зива постоянно возникают всё более и более эффективные методы его вычисления. В последнее десятилетие наблюдается новый бум (см. ссылки в ]) в связи с развитием так называемых сжатых структур данных. В настоящей работе делается существенное теоретическое продвижение в вопросе вычисления разложения Лемпеля-Зива с эффективным использованием ресурсов машинного времени и памяти.
Часто техники, применяемые при работе со строками, требуют нетривиального математического аппарата. Этот аппарат стрингология черпает в комбинаторике слов — относительно молодой, но уже достаточно состоявшейся области математики. Одна из центральных задач в комбинаторике слов — описание природы закономерностей в повторяющихся структурах в строках; этому, например, посвящена большая часть известной монографии ]. Именно внутренние задачи комбинаторики слов, связанные с повторяемостью в строках, являются нашей основной мотивацией при разработке алгоритмов поиска повторяющихся структур. Эта тема традиционно является популярной в стрингологии, но, несмотря на это, по-прежнему богата открытыми проблемами и активно исследуется и в последнее время. В связи с этой линией исследований в данной работе рассматриваются так называемые максимальные повторы (см. определение ниже) — конструкции, предложенные Мейном в ] для описания всех повторов в строке. Другая тесно связанная тема, обсуждаемая в диссертации, — это алгоритмы, позволяющие эффективно строить сколь угодно длинные строки без повторов — задача, постоянно возникающая в комбинаторике слов ], но имеющая также приложение в некоторых алгоритмах из области искусственного интеллекта ]. Исследуемые нами повторяющиеся структуры также представляют интерес с точки зрения биологии, где повторяющиеся участки ДНК могут нести определённый биологический смысл [13].
Кроме повторов, в работе исследуются конструкции, связанные с палиндромами (см. определение ниже), для которых долгое время возможность эффективных методов распознавания оставалась открытой проблемой и которые в связи с этим даже рассматривались как гипоте-
*
тический контрпример к одной известной и важной в теории формальных языков гипотезе ]. В комбинаторике слов палиндромам посвящено множество работ. В русле этих работ в данной диссертации также рассматривается задача подсчёта числа различных палиндромов в строке.
Методы исследования. В работе используются методы теории алгоритмов, теории сложности, комбинаторики слов и вычислительной геометрии, а также большое число разнообразных структур данных.
Главным мерилом эффективности рассматриваемых алгоритмов выступает порядок скорости роста потребляемых алгоритмом ресурсов при росте размера входных данных решаемой задачи. В качестве ресурса нас интересует время и необходимая для работы память. Входными данными для всех рассматриваемых в работе алгоритмов является строка и длина этой строки всегда обозначается через п. Относительно п и оценивается время работы алгоритма, т.е. число операций, которые алгоритм затрачивает на решение задачи. Например, будем говорить, что данный алгоритм работает за 0(п logп) времени и использует 0(п) памяти, если на строке длины п алгоритм выполняет O(nlogn) элементарных операций и потребляет 0{п) памяти. Чтобы строго определить, какие элементарные операции допустимы и в каких единицах измеряется память, необходимо описать модель вычислений — набор доступных программе инструкций и возможностей по использованию памяти. Применяемая нами модель — это RAM модель (англ. Random Access Machine), наиболее полно отражающая особенности современных компьютеров.
При описании представления входных данных в RAM машине естественным образом выделяют модель с общим алфавитом. Считается, что входная строка в этой модели находится во внешнем для алгоритма устройстве, а сам алгоритм может за константное время посылать в устройство запросы на сравнение символов и получать ответы. Такой алфавит может быть упорядоченным или неупорядоченным в зависимости от того, какие ответы присылает это внешнее устройство: «больше»/«меньше»/«равно» или «равно»/«не равно». Общий алфавит позволяет максимально абстрагироваться от природы входной последовательности и оперировать достаточно сложными объектами (например, словами естественного языка или структурами со множеством полей), воспринимая их как символы. Мы стремимся, по возможности, рассматривать общие алфавиты, чтобы наши алгоритмы имели наиболее широкую сферу применения. Тем не менее для многих задач больший инте-
' Всюду в автореферате через log обозначается логарифм по основанию два.
pec представляет целочисленный алфавит — самый распространённый случай необщего алфавита. Целочисленный алфавит состоит из целых чисел, умещающихся в константное число машинных слов. Размер алфавита является дополнительным параметром входных данных. Входная строка над целочисленным алфавитом {0,1,... ,сг—1} кодируется непрерывным блоком в памяти, занимающим п [log а~\ битов.
Описываемая модель входных данных не является единственно возможной. Для некоторых приложений естественным будет, если строка данных не даётся сразу вся, а поступает извне последовательно, и для каждого поступившего кусочка необходимо целиком решить поставленную задачу. Алгоритм называется онлайновым, если он читает входную строку слева направо и решает поставленную задачу для каждого считанного префикса сразу после считывания.
Цели и задачи. Целью диссертации является получение ответов на сформулированные ниже вопросы 1-6.
Напомним, что длина строки w обозначается через |ги|. Через гу[1], гу[2],... , w[n] обозначаются 1-й, 2-й, ..., n-й символы w, соответственно. Для г, j Є N обозначим w[i..j] = гф]гф+1] w\j]; строка гф..^'] называется подстрокой w. Произвольное множество строк над данным фиксированным алфавитом называется языком.
Разложение Лемпеля-Зива [] строки s — это однозначное представление строки s в виде s = Z\Z2 Zk такое, что каждая подстрока Z{ не пуста и представляет собой либо символ, не встречавшийся ранее в строке s, либо самую длинную подстроку в данной позиции, имеющую
НЄ Менее ДВуХ ВХОЖДеНИЙ В Строке Z\Z2 Z{.
Пример. Строка abababaabbbaaba имеет разложение Лемпеля-Зива а-Ъ-ababa -ab-bb- aab а. Обратите внимание, что упомянутые в определении два вхождения подстроки Z{ могут пересекаться (как это происходит для zs = ababa и z$ = bb).
На основе разложения Лемпеля-Зива реализуется простая идея сжатия без потерь: если есть подстрока z, встречавшаяся в строке ранее, то при сжатии всей строки нет необходимости записывать z целиком, а достаточно лишь указать длину z и в какой позиции встречалась z. Таким образом, каждый неодносимвольный элемент разложения Лемпеля-Зива z можно кодировать парой чисел (р, I), где р — позиция в строке, где ранее встречалась строка z (таких позиций может быть несколько и достаточно взять любую), а I — длина z. Нетрудно понять, что исход-
ная строка легко восстанавливается по этой кодировке. Конечно, формат хранения пар чисел и символов зависит от реализации, но общая идея остаётся неизменной.
Стандартные алгоритмы, вычисляющие разложение Лемпеля-Зива на общем упорядоченном алфавите, работают за 0(п log а) времени, где а — число различных символов во входной строке длины п (см. []). В связи с этим возникает первая задача, исследуемая в настоящей работе.
Вопрос 1. Можно ли на общем упорядоченном алфавите вычислять разложение Лемпеля-Зива за o(n log сг)?
Так как основное применение разложения Лемпеля-Зива — сжатие данных, которые сами по себе часто очень велики и оставляют мало места для работы самого алгоритма сжатия, естественным образом встаёт задача вычисления разложения Лемпеля-Зива в условиях крайней ограниченности доступной памяти. Для наиболее важного случая целочисленного алфавита {0,1,...,сг—1} (для простоты будем полагать, что а — это степень двойки) существует несколько линейных алгоритмов, потребляющих O(nlogn) битов памяти (здесь память целесообразно измерять в битах); лучший из них — алгоритм Карккайнена, Кемпы и Пуглизи [] (см. также ]). Но когда а мало, выделять 0(пlogп) битов памяти в дополнение к п log а битам, занимаемым самой входной строкой, становится обременительно. Для решения этой проблемы было разработано множество алгоритмов, использующих О(п log а) битов (см. ссылки в [,]). В таблице приведены время и память, потребляемые лучшими существующими решениями, вычисляющими разложение Лемпеля-Зива в рамках О(п log а) битов (включая результат из диссертации). Заметим, что п log а битов в оценках из таблицы относятся к памяти, необходимой для хранения самой входной строки, а є — это произвольная положительная рациональная константа.
Вопрос 2. Как быстро можно вычислять разложение Лемпеля-Зива строки над алфавитом {0,1,... , сг—1}, используя только еп битов дополнительной памяти, где є — произвольная фиксированная константа?
Таблица 1: Лучшие алгоритмы поиска разложения Лемпеля-Зива, использующие O(nlogcr) битов дополнительной памяти.
Повторы в строках. Целое число р, такое что 0 < р < \w\, называ-
ется периодом строки w, если для каждой позиции г < \w\ — р выполняется w[i] = w[i-\-p]. Если р — минимальный период строки w1 то число \w\/p называется экспонентой w. Зафиксируем рациональное число е > 1. Строки с экспонентами большими или равными е будем называть е-повторамщ если е в обсуждаемом контексте не важно, то будем говорить просто о повторах. Например, строка abab — это 2-повтор, ааа — 3-повтор, abbcab — 1.5-повтор. Из определения следует, что если w — е-повтор, то w также является е'-повтором для всех е' таких, что 1 < е' < е. Например, ааа — это 3-повтор и в то же время 1.7-повтор и, например, 2-повтор. Будем говорить, что строка w не содержит е-повторов) если в w нет подстрок, являющихся е-повторами.
Подстрока w[i..j] строки w называется максимальным повтором^ если w[i..j] — это 2-повтор, а подстроки w[i—l..j] и гф.^'+І] (если определены) не являются 2-повторами.
Пример. Строка t = aabaabab содержит четыре максимальных повтора t[1..2] = аа, t[4..5] = аа, t[1..7] = aabaaba, t[b..8] = abab. Экспоненты этих максимальных повторов равны 2, 2, ^, 2, соответственно.
Приложение алгоритмов поиска повторов для исследований по комбинаторике слов является нашей основной мотивацией. Хотя стоит отметить, что поиск 2-повторов имеет отдельный интерес с точки зрения биоинформатики, где участки строк ДНК, являющиеся 2-повторами, могут нести определённый биологический смысл [13].
Колпаковым и Кучеровым ] доказано, что любая строка длины п содержит 0{п) максимальных повторов. Таким образом, множество всех максимальных повторов в компактной форме определяет все 2-повторы в строке и, значит, в некотором смысле охватывает всю периодическую структуру строки. Задача поиска максимальных повторов на общем неупорядоченном алфавите давно решена: Мейном и Лоренцем доказана нижняя граница Vt{n\ogn) [] и приведён алгоритм, работающий за 0(пlogп) []. Колпаков и Кучеров ] описали алгоритм поиска всех максимальных повторов, работающий за 0{п) при условии, что разложение Лемпеля-Зива строки уже найдено (а на общем упорядоченном алфавите, как доказывается в разделе 2.2 диссертации, поиск разложения Лемпеля-Зива требует Г2(п log а) времени). Максимальным повторам посвящено немало работ, но вплоть до последнего времени все эффективные алгоритмы поиска максимальных повторов основывались на разложении Лемпеля-Зива.
Вопрос 3. Можно ли найти все максимальные повторы за 0{п) на общем упорядоченном алфавите?
Другая рассматриваемая нами задача — онлайновый поиск е-повторов. Существует целая серия онлайновых алгоритмов, проверяющих строку на наличие е-повторов. На общем неупорядоченном алфавите для е = 2 самый быстрый из них — алгоритм Апостолико и Бре-слауэра [], работающий за 0(п logп) времени и 0(п) памяти. Мейном и Лоренцом [] доказано, что для общего неупорядоченного алфавита это время оптимально.
Наш интерес к онлайновым алгоритмам проверки на наличие е-повторов обусловлен популярной в комбинаторике слов задачей построения длинных случайных строк без е-повторов (см. []). В связи с этим мы рассматриваем также операцию откати^ позволяющую на любом шаге работы онлайнового алгоритма отбрасывать последний символ прочитанной строки (подробнее см. в разделе 3.4 диссертации). Полученные алгоритмы интересны для некоторых приложений в области искусственного интеллекта (см. ]).
Вопрос 4. Можно ли на общем неупорядоченном алфавите получить онлайновый алгоритм проверки на наличие е-повторов, работающий за оптимальное время O(nlogn) и 0{п) памяти для произвольной рациональной константы е > 1? Возможно ли при этом поддерживать операцию отката? Можно ли соответствующие результаты перенести на случай упорядоченного алфавита?
Палиндром — это строка w такая, что ги[1]ги[2] ги[|ги|] = гу[|гу|] -гу[2]г(;[1]. Подпалиндром — это подстрока, являющаяся палиндромом. Например, строка aaba содержит 5 различных подпалиндромов: а, 6, аа, aba и пустую строку. Обозначим через Pal язык всех непустых палиндромов над рассматриваемым алфавитом (о каком алфавите идёт речь, будет всегда понятно из контекста). Будем говорить, что алгоритм распознаёт данный язык L, если этот алгоритм по входной строке определяет, принадлежит ли она L. Алгоритм распознаёт L онлайновое если он читает входную строку слева направо и сразу после считывания каждого префикса определяет принадлежит ли этот префикс L. Для языков L и М через L М обозначим язык {uv: и Є L,v Є М}. Индуктивно определим L1 = L и Lk = L Lk~l для к Є N.
Известно, что любая строка длины п содержит не более тИ-1 различных подпалиндромов. В ] представлен алгоритм подсчёта числа различных подпалиндромов в строке, работающий за 0{п) на целочис-
ленном алфавите, и там же сформулирован следующий вопрос.
Вопрос 5. Как быстро можно подсчитать различные подпалиндромы онлайновым алгоритмом?
Палиндромные структуры интересуют нас главным образом как трудные для распознавания объекты, представляющие теоретический интерес в теории формальных языков и комбинаторике слов. Так, в теории формальных языков одно время предполагалось, что класс па-линдромных языков Pal , где к Є N, и некоторые подобные ему классы нельзя распознать за 0{п) на RAM машине (см. ]) и гипотетически эти языки могли бы служить примером для подтверждения известной в теории формальных языков гипотезы о сложности распознавания так называемых недетерминированных контекстно-свободных языков. В свете этого Галилем и Сейферасом ] поставлен вопрос о распознавании за 0(п) языка Pal для любого фиксированного к Є N. В связи с этой проблемой естественно рассмотреть и иные палиндромные конструкции.
Вопрос 6. Можно ли за 0(п) онлайново распознать язык Раї для любого фиксированного к Є N? Если язык L онлайново распознаваем за 0(п), можно ли за 0{п) онлайново распознать язык L Pal?
Научная новизна. Все результаты диссертации являются новыми.
Теоретическая и практическая ценность. Диссертация носит преимущественно теоретический характер. Представленные в работе алгоритмы онлайнового поиска повторов реализованы в виде программных комплексов на языке C++ (хотя их экспериментальный анализ в работе не приводится) и могут быть в дальнейшем использованы в некоторых приложениях в комбинаторике слов и области искусственного интеллекта (см. []). Полученные результаты имеют ценность для дальнейших исследований в строковых алгоритмах, комбинаторике слов и теории формальных языков. Ссылки на результаты диссертации присутствуют в работах других авторов: ] ] ] ] ] ] ] ] ] ].
Апробация результатов работы. Все представленные результаты опубликованы в статьях автора [26] ] ] ] ] ] (две из них в соавторстве с Рубинчиком Михаилом Валентиновичем и Шуром Арсением Михайловичем) в журнале Information Processing Letters и в сборниках трудов следующих международных конференций: 40-й международный симпозиум по математическим основам компьютерных наук (MFCS 2015, Милан, Италия), 26-й ежегодный симпозиум по комбинаторному поиску шаблонов (СРМ 2015, о. Искья, Италия), 32-й симпозиум по теоретическим аспектам компьютерных наук (STACS 2015, Мюнхен,
Германия), 41-я международная конференция по текущим направлениям в теории и практике компьютерных наук (SOFSEM 2015, Пец-под-Снежкой, Чехия), Пражская конференция по стрингологии (PSC 2013, Прага, Чехия). Все названные журналы и сборники удовлетворяют достаточному условию ВАК для опубликования результатов диссертации. Часть результатов опубликована в тезисах [32,] (один из них в соавторстве с Рубинчиком М. В.) школ-конференций CSEdays 2013 и CSEdays 2014 в Екатеринбурге. Автор выступал с докладами на всех перечисленных конференциях. Результаты также докладывались на семинаре «Алгебраические системы» (УрФУ, рук. Шеврин Л. Н., 2014-2015).
Вклад соавторов в совместные работы , , ] таков: А. М. Шуру принадлежит постановка задачи и оптимизация некоторых доказательств в работах [,]; М.В. Рубинчику принадлежит основной алгоритм в работах ,], а также первоначальный (с худшей временной сложностью) алгоритм в работе ]; автору принадлежит нижняя оценка в работах [,], а также конструкция основного алгоритма и доказательство его корректности и эффективности в работе ].
Структура диссертации. Диссертация состоит из четырёх глав, заключения и списка литературы. Объём диссертации составляет 100 страниц, библиография включает 93 наименования.
Базовые определения
Для удобства здесь и далее вместо «общий упорядоченный алфавит» будем говорить просто упорядоченный алфавит. Аналогично вместо «общий неупорядоченный алфавит» будем говорить неупорядоченный алфавит.
Ясно, что целочисленный алфавит — частный случай упорядоченного алфавита, а упорядоченный — частный случай неупорядоченного. Несложным рассуждением покажем, что, не ограничивая общности, константный алфавит можно считаться состоящим из чисел 0,1,... , с, где с — некоторая константа (таким образом, константный алфавит — частный случай целочисленного): при работе алгоритма нужно фиксировать все встречавшиеся символы алфавита и последовательно присваивать им номера 0,1,...; тогда, чтобы определить номер очередного символа, достаточно сравнить его со всеми уже фиксированными символами, а так как алфавит константный, таких символов всего константное число, и, значит, сравнение занимает константу времени.
Описываемая модель входных данных не является единственно возможной и для некоторых приложений естественным будет, например, если строка данных не даётся сразу вся, а поступает извне последовательно и для каждого поступившего кусочка необходимо целиком решить поставленную задачу. Алгоритм называется онлайновым, если он читает входную строку слева направо и решает поставленную задачу для каждого считанного префикса сразу после считывания.
Пример 1.4.1. Онлайновый алгоритм, проверяющий строку на наличие 2-повторов, читает строку слева направо посимвольно и сразу после окончания чтения очередного префикса определяет, присутствуют ли в нём подстроки, являющиеся 2-повторами.
Аналогично, алгоритм, онлайново считающий число различных подпалиндромов в строке, возвращает число подпалиндромов в каждом префиксе этой строки сразу по окончании чтения этого префикса.
Как уже упоминалось выше, во всех рассматриваемых нами алгоритмах входные данные — это строка длины п. Пусть f(n) — некоторая неотрицательная функция. Будем говорить, что алгоритм работает за 0(f(n)), если он выполняет 0(f(n)) операций для решения данной задачи на любой строке длины п. Алгоритмы, работающие за 0(п), называются линейными. Линейный алгоритм для большинства адекватных задач на строках — это асимптотически самый быстрый алгоритм, потому что 0(п) времени требуется как минимум для того, чтобы прочитать всю входную строку. Часто будет удобно производить более тонкие оценки времени выполнения, включая помимо параметра п какой-либо естественный дополнительный параметр. Например, если о — число различных символов входной строке, то будем говорить, что алгоритм работает за 0(f(n, а)), где f(n, а) — некоторая функция, если на любой строке длины п, содержащей о различных символов, данный алгоритм выполняет 0(f(n, а)) операций. Подобным же образом определяются оценки времени, зависящие от любых других дополнительных параметров. Рассмотрим известную задачу, показывающую, что все четыре рассматриваемые нами модели алфавитов различны: требуется проверить все ли символы во входной строке длины п отличаются друг от друга. Ясно, что на константном алфавите эта задача решается за константное время: достаточно только посмотреть константное число первых символов строки. На целочисленном алфавите с символами, принимающими значение от 0 до п, задачу можно решить за линейное время: нужно создать массив с ячейками, индексируемыми числами от О до п, и отметить присутствующие в строке символы. Для упорядоченного алфавита задачу можно решить за 0(nlogn) с помощью какого-нибудь сбалансированного дерева (красно-чёрного, например; см. [22, глава 13]). Оказывается, что быстрее этого сделать нельзя.
Теорема 1.4.1 (см. [15, теорема 1.3]). Любой алгоритм, определяющий все ли символы в строке длины п над упорядоченным алфавитом различны, выполняет Q(nlogn) сравнений в худшем случае. Для неупорядоченного алфавита ситуация ещё хуже. Теорема 1.4.2 (см. [15, теорема 1.1]). Любой алгоритм, определяющий все ли символы в строке длины п над неупорядоченным алфавитом различны, выполняет Q(n2) сравнений в худшем случае. Говорят, что алгоритм распознаёт язык L или алгоритм является распознавателем L или язык L распознаваем данным алгоритмом, если этот алгоритм принимает на вход строку и определяет принадлежит ли она L или нет. Распознаватель языка L называется онлайновым (или говорят, что язык L онлайново распознаваем), если данный алгоритм читает входную строку слева направо и сразу после считывания каждого префикса определяет принадлежит ли этот префикс языку L. Пусть f(n) и д(п) — некоторые функции целочисленного аргумента. Будем говорить, что данный [онлайновый] распознаватель работает за время 0(f(n)) и 0(д(п)) памяти, если на любой строке длины п он [онлайново] определяет принадлежит ли эта строка L за время 0(f(n)) и 0(д(п)) памяти.
Структура данных — это некоторый (возможно изменяемый) набор данных, на котором поддерживается определённый специфичный для данной структуры функционал. Например, структура данных словарь поддерживает набор попарно различных символов некоторого алфавита с операцией добавления символа, которая добавляет символ в набор, если его ещё там нет, и операцией проверки на наличие символа в наборе.
Время работы операций структуры данных измеряется относительно размера поддерживаемого структурой набора данных. Причём то, что подразумевается под набором данных определяется отдельно для каждой задачи. Например, будем говорить, что операция добавления в словарь работает за O(logn), если добавление нового символа в словарь, содержащий п различных символов, требует выполнения O(logn) элементарных инструкций. Будем говорить, что данная операция в рассматриваемой структуре данных выполняется за амортизированное время 0(f(n)), где f(n) — некоторая функция, если время работы любой последовательности из т данных операций, выполняющихся на только что созданной структуре, равно 0(mf(n)), где п — максимальный размер поддерживаемых данных на протяжении работы данной последовательности из т операций.
Пример 1.4.2. Рассмотрим простую структуру — расширяющийся массив. Эта структура поддерживает массив машинных слов 6[1..п] (изначально пустой) с двумя операциями: read(z), которая читает ячейку г массива, и extend(x), которая увеличивает длину массива на единицу, присоединяя справа к массиву машинное слово х. Структура поддерживает память размера 2к под массив Ъ. Если при выполнении extend в выделенной памяти размера 2к не хватает места для расширения, структура выделяет память размера 2fc+1 и за 0(2к) копирует старое содержимое в новое место. Несложно понять, что extend работает за 0(п), но в то же время амортизированное время работы extend равно 0(1). 1.5 Модель решающего дерева
Сжатый алгоритм поиска разложения Лемпеля–Зива
Доказательство. Через S обозначим множество всех строк, сохранённых в сжатом боре Т. Для подстроки і строки s обозначим через if строку длины _N/rJ такую, что для каждо го г Є [l..t ] символ t [i] представляет собой запакованную строку t[r(i—1)+1..гг]. Будем поддерживать специальный сжатый бор Т", содержащий набор строк { : і Є S}. Словари, поддерживающие навигацию по Т", можно организовать так, что поиск и вставка в Т" неко торой строки w будут выполняться за амортизированное время 0(г / +logfc); такое дерево называют тернарным деревом ввиду некоторых деталей его реализации (см. в [39] список ссылок по этой теме). Для каждой вершины v Є Т вставим в Т" вершину, соответствующую строке lab(v) , если такой вершины в Т" ещё нет (например, таким способом из вершины 3 слева на рисунке 2.7 получена вершина 2 справа). Все вершины Т" оснащены указателями на соответствующие вершины Т (указатели изображены пунктирными линиями на рисунке 2.7). Пусть w — строка, которую ищут в Т. Используя указатели в Т", можно при спуске в Т" сверху вниз последовательно выводить вершины, соответствующие в Т префиксам w[l..r], w[1..2r],... , w[l..w r]. Обозначим через и самый длинный префикс w, представленный в Т. Как только строка и найдена в Т" за 0(м + log к) времени, продолжим обход уже в боре Т, читая строку tt[tt r..tt —1] из позиции, соответствующей строке tt[l..tt r]. Эта завершающая стадия требует О (г log а) = O(logn) времени. Вставка выполняется аналогично. П Определим вспомогательную задачу. Пусть даны два дерева Т\ и Тг и некоторое множество пар Z = {( i, )} такое, что х\ и х\ являются листьями Т\ и Тг, соответственно (см. рис. 2.8 на странице 42 ниже). Требуется поддерживать деревья Т\ и Тг и множество Z со следующими операциями: 1) добавление новых вершин в 7\ и Т2; 2) добавление новых пар листьев в Z; 3) запрос, находящий для двух данных вершин V\ Є Т\ и г 2 Є Т2 какую-либо пару (х 1, 2) Є Z такую, что Х\ является потомком г і, а Х2 — потомком г 2 (если такая пара есть). Структуру, поддерживающую деревья Ті, Тг и множество Z с указанными операциями, будем называть структурой ортогонального поиска на деревьях (см. рис. 2.8, чтобы понять откуда такое название). Для построения этой структуры будем использовать инструменты, описанные в [14] и леммах 2.3.12 и 2.3.13.
Лемма 2.3.15. Структура ортогонального поиска на деревьях, содержащих не более к вершин, поддерживающая не более к пар листьев в множестве Z, может быть реализована с использованием O(klogk) битов памяти и операциями запроса и вставки, работающими за амортизированное время 0(logk).
Доказательство. Доказательство в основном опирается на структуру ортогонального поиска, определённую следующим образом. Даны два связных списка X и У и множество пар Z = {(ХІ,УІ)} такое, что ХІ Є X и у І Є У; необходимо поддерживать на списках X и У и множестве Z такие операции: 1) вставка нового узла в список X или У; 2) вставка новой пары в множество Z; 3) запрос, возвращающий по данным элементам Х\,Х2 Є X и у\, у2 Є У пару (х,у) Є Z такую, что х лежит между элементами х\ и ж2 вХ, аy лежит между у\ и у2 в Y.
Лемма 2.3.16 (см. [14]). Структура ортогонального поиска, содержащая не более к узлов в списках X иY и не более к пар в множестве Z, может быть реализована с использованием O(klogk) битов и операциями вставки и запроса, выполняющимися за амортизированное время О (log к).
Будем поддерживать некоторый естественный линейный порядок на листьях Т\ и Т2 так, что листья из поддерева с корнем в любой вершине будут образовывать непрерывную подпоследовательность в упорядоченной последовательности листьев. Порядок на листьях поддерживается с помощью связного списка из леммы 2.3.13. Оснастим 7\ и Т2 структурой, поддерживающей операции на упорядоченных деревьях из леммы 2.3.12. Теперь построим структуру ортогонального поиска из леммы 2.3.16 на списках листьев Т\ и Т2 и множестве пар Z. Все эти структуры в сумме занимают O(klogk) битов памяти. Несложно показать, пользуясь леммами 2.3.13, 2.3.12, 2.3.16, что добавление новой вершины в 7\ или Т2 или новой пары в Z выполняется за амортизированное время 0(logk).
Структуры данных. На этапе инициализации наш алгоритм конструирует разностное покрытие D отрезка [0..т2) такое, что D = О(т). Это можно сделать за 0(т2) алгоритмом из [19]. Обозначим М = {і Є [0..п]: г mod т2 Є D}. Множество М представляет собой множество отмеченных позиций исходной строки s (включая псевдопозицию 0) и М будет играть главную роль в последующих построениях. Основная идея состоит в том, чтобы построить строковый индекс на строках, начинающихся и заканчивающихся в позициях из М. Ключевое свойство, позволяющее эффективно использовать такие ограниченные индексы для строк длины т2, — это лемма 2.3.11, из которой следует, что для любых позиций г и j, если i,j г2, то найдётся d Є [0..т2) такое, что i—d Є М и j—d Є М.
Предположим, что алгоритм уже нашёл факторы Лемпеля-Зива Z\, z2,... , Zk-\ и с помощью процедуры из подраздела 2.3.2 уже решил, что \zk\ г2. Обозначим р = \z\Zi Zk-i\. Фактор Zk начинается в позиции р+1. Будем использовать целочисленную переменную z для вычисления длины \zk\ и изначально положим z = г2. Перед обсуждением непосредственно самого алгоритма разберём участвующие в нём структуры данных. В этом подразделе удобно будет полагать, что символы s[0], s[— 1], s[—2],... и s[n+l], s[n+2],... определены и равны некоторому специальному символу, который меньше всех остальных символов в s. Введём вспомогательную целочисленную переменную t такую, что на каждом этапе работы алгоритма выполняется неравенство р t р + z. Изначально положим t = р + 1. Значение t будет увеличиваться по мере увеличения z. Обозначим Si = s[0..i] (обращаем внимание читателя на то, что специальный символ s[0] входит в Sj). Основные структуры данных в этом подразделе — это сжатые боры S и Т: S содержит строки si, а Т содержит строки s[z+l..z+r2] для всех позиций і Є [0..) П М (так как символы s[n+l], s[n+2],... равны специальному символу s[0], строки s[z+l..z+r2] корректно определены). Поскольку s[0] — специальный символ, каждая строка Si для г Є [0..) Г\М представлена в боре S некоторым отдельным листом. Боры S и Т дополним структурами из леммы 2.3.14, позволяющими выполнять быстрый поиск и вставку. Будем поддерживать структуру ортогонального поиска на деревьях S и Т с множеством пар листьев Z, которое для каждого і Є [0..) Г\М содержит пару листьев, соответствующих Sj в S и s[z+l..z+r2] в Т (см. рис. 2.8). Вдобавок снабдим S структурой взвешенного предка из леммы 2.3.2.
Алгоритмы на решающих деревьях
Будем говорить, что решающее дерево, обрабатывающее строки длины п, находит все максимальные повторы, удовлетворяющие некоторому свойству Р, если для любых строк t\ и 2 длины п, достигающих одного и того же листа в дереве, выполняется следующие свойство: для любых i,j Є [l..n] подстрока ti[i..j] является максимальным повтором в t\, удовлетворяющим свойству Р, тогда и только тогда, когда іг [ --j] является максимальным повтором в 2, удовлетворяющим свойству Р.
Будем говорить, что два решающих дерева, обрабатывающих строки длины п, эквивалентны, если для каждого достижимого листа а первого дерева найдётся достижимый лист b второго дерева такой, что любая строка t длины п достигает а тогда и только тогда, когда t достигает Ь. Базовой высотой решающего дерева назовём минимальное число к такое, что каждый путь, соединяющий корень и некоторый лист дерева, содержит не больше к рёбер, помеченных символами « » и « ».
Для положительного целого р будем говорить, что максимальный повтор г некоторой строки является р-периодическим, если 2р \г\ и р — это период г (не обязательно минимальный). Будем говорить, что максимальный повтор является максимальным р-повтором, если этот максимальный повтор является g-периодическим для какого-то q кратного р. Заметим, что любой максимальный повтор — это максимальный 1-повтор.
Пример 3.2.3. Опишем наивное решающее дерево, которое находит все максимальные р-повторы в строках длины п. Обозначим через t входную строку. Дерево просто последовательно сравнивает t[i] и t[j] для всех i,j Є [l..n] таких, что число \i — j\ кратно р. Такое дерево имеет высоту \Zi (п w) = 0(п2/р) и такую же базовую высоту.
Заметим, что алгоритм на решающем дереве, находящий максимальные повторы, не перечисляет повторы в явном виде, как это делают RAM алгоритмы. Алгоритм на решающем дереве просто собирает некоторый объём информации о взаимном расположении символов входной строки, достаточный для того, чтобы заключить, в каких позициях расположены максимальные повторы, а в каких их точно быть не может, т.е., как только полученных знаний о структуре входной строки становится достаточно для нахождения всех максимальных повторов без дальнейших сравнений символов, алгоритм останавливается и не заботится об обработке накопленной информации.
Для упрощения построения эффективного решающего дерева будет активно использоваться следующая лемма, позволяющая нам оценивать только базовую высоту дерева вместо высоты.
Доказательство. Чтобы построить эквивалентное дерево высоты к + п, будем модифицировать исходное дерево с базовой высотой к. Сначала удалим все недостижимые вершины дерева. Затем каждый путь без ветвлений (т.е. цепь) в полученном дереве сожмём до одного ребра, удалив все внутренние вершины этого пути и исходящие из этих вершин рёбра. Действительно, результат сравнений, соответствующих удаляемым внутренним вершинам, полностью определяется последовательностью сравнений, проделанных выше по дереву, так как иначе в этих вершинах остались бы ветвления после удаления недостижимых вершин. Из этого рассуждения очевидным образом следует, что полученное решающее дерево эквивалентно исходному. Теперь для завершения доказательства достаточно показать, что каждый путь, соединяющий корень и некоторый лист полученного дерева, содержит самое большее тг— 1 ребро, помеченное символом «=».
Заметим, что если выполнить п сравнений символов на строке длины п и каждое из этих сравнений в результате покажет, что сравниваемые символы равны, то результат как минимум одного из производимых сравнений следует по транзитивности из других выпол ненных сравнений. Предположим, от противного, что некоторый путь, соединяющий корень и какой-то лист, содержит не менее п рёбер с меткой «=». Из замечания выше следует, что данный путь содержит вершину, помеченную парой (i,j), такую, что ребро, исходящее из этой вершины, имеет метку «=» и равенство г-го и j-го символов входной строки следует по транзитивности из уже выполненных выше на пути сравнений символов, соответствующих рёбрам с меткой «=». Поэтому только один отпрыск данной вершины достижим. Но это невозможно, потому что все такие вершины исходного дерева были удалены на шаге сжатия путей. Это противоречие завершает доказательство. Лемма 3.2.7. Для произвольных чисел пир существует решающее дерево с базовой высотой меньшей или равной 2\п/р ], которое находит все р-периодические максимальные повторы в строках длины п.
Доказательство. Через t обозначим входную строку. Напомним, что любой алгоритм обработки t, написанный на каком-либо императивном языке программирования, посредством очевидной процедуры может быть преобразован в соответствующее решающее дерево. Итак, наш алгоритм работает следующим образом (естественно, получающееся решающее дерево будет содержать только сравнения символов t без упоминания о каких-то переменных):
Если символы t[i] и [г+р] в строке 2 не равны, то г увеличивается на р и цикл 4-5 отрабатывает до тех пор, пока не найдёт пару неравных символов. Отсюда следует, что алгоритм выполняет самое большее 2 \п/р] сравнений, в результате которых выясняется, что сравниваемые символы не равны. Значит, соответствующее решающее дерево имеет базовую высоту не больше чем 2\п/р]. Докажем, что этот алгоритм находит все р-периодические максимальные повторы.
Для любого п существует решающее дерево с высотой сп, находящее все максимальные повторы в строках длины п, где с — некоторая константа, не зависящая от п.
Доказательство. Хотя в конечном итоге нас интересует алгоритм нахождения всех максимальных повторов, фактически будет удобнее описывать алгоритм поиска всех максимальных р-повторов для данного фиксированного р. Для решения исходной задачи достаточно положить р = 1.
Из леммы 3.2.6 следует, что для доказательства теоремы достаточно построить решающее дерево с базовой высотой 0(п), находящее все максимальные р-повторы. Поэтому в процессе описания устройства алгоритма на решающем дереве будет вестись подсчёт только тех сравнений, в результате которых выясняется, что сравниваемые символы не равны. Такие сравнения будем называть антиравенственными. Например, алгоритм поиска всех максимальных р-повторов из примера 3.2.3 выполняет в худшем случае 0(п2/р) антира-венственных сравнений. Итак, для решения общей задачи достаточно доказать следующий факт: для строки t длины п и натурального числа р можно найти все максимальные р повторы, выполнив 0(п/р) антиравенственных сравнений.
Наметим общий план доказательства. Во-первых, коротко опишем по шагам наш алгоритм на решающем дереве. Во-вторых, разберём подробно каждый из этих шагов и посчитаем количество выполняемых антиравенственных сравнений на каждом шаге; это основная часть доказательства. Наконец, оценим общее число выполненных антиравенственных сравнений; основная трудность оценки заключается в рекурсивной природе нашего алгоритма.
Распознаватель Palk и других палиндромных языков
Палиндромы представляют собой один из самых интенсивно исследуемых объектов в комбинаторике слов, где им посвящено множество работ. Например, найдены палиндромные характеристики строк Штурма [29, 32] (известного объекта в данной области), исследуются строки, «богатые» палиндромами [45], рассматриваются так называемые эпиштурмовы строки [31], которые являются частным случаем «богатых» палиндромами строк. Ряд работ исследует алгоритмические проблемы, касающиеся палиндромов, такие как поиск всех подпалиндромов [73] или подсчёт числа различных подпалиндромов [48]. В этой главе нас главным образом будет интересовать связь палиндромов с некоторыми разделами теории формальных языков, а именно, будет исследоваться сложность распознавания палиндром-ных конструкций на RAM машине.
Известно, что любая строка длины п содержит не более п+1 различных подпалиндромов [31]. В [48] представлен алгоритм подсчёта числа различных подпалиндромов в строке, работающий за 0(п) на константном алфавите. В [92] получен онлайновый алгоритм, решающий ту же задачу за 0(nloga) [0(па)] на упорядоченном [неупорядоченном] алфавите, где о — число различных символов в строке. В разделе 4.2 доказывается, что на упорядоченном [неупорядоченном] алфавите любой онлайновый алгоритм подсчёта числа различных подпалиндромов в строке выполняет (nloga) [П(гг т)] операций в худшем случае. Таким образом, алгоритм из [92] является оптимальным. В контексте наших исследований этот результат означает, что некоторые задачи, касающиеся поиска палиндромов, действительно могут представлять трудности для RAM машины.
Дальнейшая наша работа связана c задачей распознавания контекстно-свободных языков — известного класса в теории формальных языков. Каждый контекстно-свободный язык распознаётся относительно медленным алгоритмом, предложенным Валиантом в [84]. До сих пор не известно, существует ли контекстно-свободный язык, который нельзя было бы распознать за линейное время на RAM машине [67]. В разделе 4.3 будет разработан эффективный инструмент для построения линейных онлайновых распознавателей широкого класса «па-линдромных» контекстно-свободных языков. Существование линейных распознавателей для некоторых из таких языков до последнего времени оставалось открытой проблемой, а одно время даже предполагалось, что такие языки являются хорошими кандидатами на роль «трудного» линейно нераспознаваемого контекстно-свободного языка. Обозначим Palev = {w Є Pal: \w\ — чётное число} и Pal i = {w Є Pal: \w\ 1}. В известной статье Кнута, Морриса, Пратта [57, раздел 6], среди прочего, был предложен линейный распознаватель языка Palev и выдвинута гипотеза, что язык ral i нельзя распознать за ҐЛ т U(n). Но впоследствии линейный распознаватель для ral i был построен в [43]. Распознавание языка Pal оказалось куда более сложной задачей. Линейные распознаватели для случаев к = 1, 2, 3, 4 представлены в [43]. В [43] и [28] была выдвинута гипотеза, что для любой натуральной константы к существует линейный распознаватель Раї . В разделе 4.3 мы строим такой распознаватель и тем самым подтверждаем эту гипотезу. Более того, построенный распознаватель является онлайновым, а разработанная нами общая алгоритмическая техника позволяет строить линейные онлайновые распознаватели для обширного класса «па-линдромных» языков. Именно, доказывается следующая теорема.
Заметим, что известен простой алгоритм онлайнового распознавания языка Раї за 0(nlogn) [79]. Связанная задача нахождения минимального к такого, что данная строка принадлежит языку Pal , может быть решена онлайново за 0(nlogn) [35]. Не известно, существует ли для этой последней задачи линейное решение.
Словарём без удалений будем называть структуру данных, поддерживающую некоторое множество элементов с операцией insqry (х), которая для данного элемента х проверяет присутствует ли ж в данном множестве и сразу после проверки, если х не находится в множестве, добавляет х в множество.
Лемма 4.2.1. Последовательность из п операций insqry на словаре без удалений, содержащем символы некоторого упорядоченного [неупорядоченного] алфавита, выполняется в худшем случае за Q(nloga) [Q(na)], где о — максимальное число символов в словаре.
Доказательство. Обозначим через D рассматриваемый словарь без удалений. Пусть Е = {а\ — упорядоченный алфавит. Допустим, что на каком-то шаге все символы с чётными индексами оказываются в словаре, в то время как символы с нечётными — нет. Применяя очевидным образом редукцию из RAM машины в решающее дерево из подраздела 1.5, можно считать, что на общем алфавите запрос «х Є D?» выполняется с помощью некоторого решающего дерева, ассоциированного с рассматриваемым словарём без удалений. Заметим, что данное дерево может кардинально меняться после внутренних изменений в словаре. Каждый узел данного дерева помечен строкой «х а » для какого-то г Є [1..га]. Чтобы алгоритм смог увидеть разницу между символами а и aj+i, дерево должно содержать по одному узлу для (ц и йг+\. Заметим, что для любого г Є [1..га] в точности один из символов а,г и йі+\ принадлежит словарю D. Итак, чтобы корректно выполнять запросы «х Є D?», решающее дерево должно иметь по отдельному узлу для каждого символа. Тогда высота дерева равна П(logга). Следовательно, для какого-то х = а2% число сравнений, необходимое, чтобы доказать, что х Є D, равно П(logте).
После обработки х содержимое словаря остаётся неизменным. Но решающее дерево может поменяться из-за возможных внутренних вспомогательных изменений. Хотя это не имеет значения, потому что можно снова выбрать символ с чётным индексом такой, на обработку которого потребуется выполнить П (log те) операций. Таким образом, можно построить «плохую» последовательность вызовов, которая начинается с заполнения словаря insqry(аг insqry(a2[m/2j), а затем каждый раз вызывает insqry(a2j) с «плохим» символом a2j, описанным выше. Ясно, что такая последовательность вызовов выполняется за Q(nlogra).