Эффективные алгоритмы анализа закономерностей в строках тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат наук Косолобов Дмитрий Александрович

• Косолобов Дмитрий Александрович
• кандидат наук
• 2016

Оглавление диссертации кандидат наук Косолобов Дмитрий Александрович

1.3 Базовые определения

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

1.3.2 Закономерности в строках

1.4 Модель RAM

1.4.1 Доступные инструкции и память

1.4.2 Входные данные

1.4.3 Время выполнения

1.5 Модель решающего дерева

1.6 Обзор результатов

1.6.1 Апробация и публикации

1.6.2 Разложение Лемпеля-Зива

1.6.3 Повторы в строках

1.6.4 Палиндромы

2 Разложение Лемпеля—Зива

2.1 Введение

2.2 Нижняя граница

2.3 Сжатый алгоритм поиска разложения Лемпеля-Зива

2.3.1 Короткие факторы

2.3.2 Средние факторы

2.3.3 Длинные факторы

3 Повторы в строках

3.1 Введение

3.2 Поиск максимальных повторов на решающем дереве

3.2.1 Максимальные повторы

3.2.2 Алгоритмы на решающих деревьях

3.2.3 Линейное решающее дерево

3.3 Поиск максимальных повторов за o(n log n)

3.3.1 Сведение к разреженному суффиксному дереву

3.3.2 Построение разреженного суффиксного дерева

3.4 Онлайновый поиск повторов с откатами

3.4.1 Ловец

3.4.2 Алгоритм на неупорядоченном алфавите

3.4.3 Алгоритм на упорядоченном алфавите

4 Палиндромы

4.1 Введение

4.2 Нижняя граница на поиск различных подпалиндромов

4.3 Распознаватель Pal и других палиндромных языков

4.3.1 Свойства палиндромов

4.3.2 Палиндромный итератор

4.3.3 Палиндромный мотор

4.3.4 Линейный алгоритм

Заключение

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

Список иллюстраций

Список таблиц

Глава

Введение диссертации (часть автореферата) на тему «Эффективные алгоритмы анализа закономерностей в строках»

Введение

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

Алгоритмы, имеющие дело с закономерностями в строках, помимо того, что активно используют существенную часть накопленного багажа знаний из области структур данных, вычислительной геометрии и алгоритмов на графах, также интенсивно применяют свой собственный обширный и постоянно совершенствующийся набор инструментов. Это позволило уже в 1985 году некоторым известным исследователям (на тот момент несколько претенциозно) утверждать, что изучение алгоритмов на строках можно считать отдельной областью, получившей название стрингология (англ. stringology от string — строка) [42]. Эта динамически развивающаяся в настоящее время область уже успела обрасти множеством публикаций, рядом монографий [24, 28, 49, 82] и по меньшей мере двумя ежегодными специализированными конференциями с высоким уровнем цитируемости: SPIRE и CPM (не говоря о нескольких менее значимых специальных конференциях). Красноречивое свидетельство живого и активного интереса к рассматриваемым вопросам — это список литературы к настоящей диссертации, в котором почти половина работ написана не ранее 2010-го года и в большинстве случаев опубликована в трудах наиболее цитируемых конференций по компьютерным наукам.

1.1 Структура диссертации и организация текста

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

Разделы 1.4 и 1.5 содержат подробное описание алгоритмического инструментария, в контексте которого проводятся все дальнейшие рассуждения. Наконец, в разделе 1.6 кратко излагаются основные результаты.

Сами основные результаты распределены по трём главам. В главе 2 речь пойдёт о способах эффективного вычисления одной из самых распространённых на сегодняшний день конструкций, используемых для сжатия данных без потерь, — разложения Лемпеля-Зива [68] (определение дано в разделе 1.3). Практическая важность этой техники, помимо применения в алгоритмах сжатия ZIP, 7z, PNG, GIF и других, подкрепляется включением разложения Лемпеля-Зива в (не столь длинный) список IEEE Milestones1, призванный увековечить ключевые вехи компьютерной революции и составленный IEEE (Institute of Electrical and Electronics Engineers) — в настоящее время общепризнанно наиболее авторитетной ассоциацией в области стандартизации в компьютерной технике. С момента изобретения разложения Лемпеля-Зива постоянно возникают всё более и более эффективные методы его вычисления. Особенно заметный бум наблюдается в последнее десятилетие [10, 21, 25, 38, 55, 75, 83, 86] в связи с развитием так называемых сжатых структур данных. В настоящей работе делается существенное теоретическое продвижение в вопросе вычисления разложения Лемпеля-Зива с эффективным использованием ресурсов машинного времени и памяти.

Главы 3 и 4 описывают близкие по духу теоретические результаты, мотивация которых основывается главным образом на внутренних задачах математики. Часто техники, применяемые при работе со строками, требуют нетривиального математического аппарата. Этот аппарат стрингология черпает в комбинаторике слов — относительно молодой, но уже достаточно состоявшейся области математики. Но не только это связывает две области. Многие задачи, решаемые в стрингологии, имеют происхождение непосредственно из комбинаторики слов и служат внутренним теоретическим нуждам последней. В то же время и сама комбинаторика слов нередко получает новые открытые вопросы и неожиданные результаты из стрингологии. Одна из центральных задач в комбинаторике слов — описание природы закономерностей в повторяющихся структурах в строках; этому, например, посвящена большая часть известной монографии по комбинаторике слов [70]. Именно внутренние задачи комбинаторики слов, связанные с повторяемостью в строках, являются нашей основной мотивацией при разработке алгоритмов поиска повторяющихся структур в главе 3. Эта тема традиционно является популярной в стрингологии, но, несмотря на это, по-прежнему богата открытыми проблемами и активно исследуется и в последнее время [6, 7, 27, 35, 37, 53, 61, 81]. В главе 3 представлены два результата. Первый из них посвящён так называемым максимальным повторам [71] (см. определение в разделе 1.3) — конструкции, позволяющей описать все повторы в строке. Мы теоретически обосновываем возможность существования более эффективных алгоритмов поиска всех максимальных повторов, чем существующие на данный момент [60, 7]. Второй результат — это алгоритм, позволяющий эффективно строить сколь угодно длинные строки без повторов — задача, постоянно возникающая в комбинаторике слов [81], но имеющая также приложение в некоторых алгоритмах из области искусственного интеллекта [69]; по возможностям, скорости и объёмам потребляемой памяти наш алгоритм превосходит все существующие решения [5, 53, 54, 69, 81]. Исследуемые нами повторяющиеся структуры также представляют интерес с точки зрения биологии, где повторяющиеся участки ДНК могут нести определённый биологический смысл [49].

В главе 4 речь идёт о теоретических изысканиях касательно эффективности распознавания особых повторяющихся конструкций, называемых палиндромами, интересных в связи с определёнными задачами в теории формальных языков, но также неразрывно связанных с некоторыми популярными направлениями в комбинаторике слов и биоинформатике. Нами разрабатывается метод эффективного распознавания обширного естественного класса «па-линдромных» конструкций, для которых долгое время возможность эффективного анализа

1http://ethw.org/Milestones:List_of_IEEE_Milestones

оставалась открытой проблемой и которые даже одно время рассматривались как гипотетический контрпример к одной известной и важной в теории формальных языков гипотезе [57, 43, 67].

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

Объём диссертации составляет 100 страниц, библиография включает 93 наименования.

1.2 Основные методы исследования

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

Главным мерилом эффективности рассматриваемых алгоритмов выступает характер скорости роста потребляемых алгоритмом ресурсов при росте размера входных данных решаемой задачи. В качестве ресурса нас интересует время выполнения и необходимая для работы память. Чтобы абстрагироваться от деталей реализации конкретных вычислителей, характер зависимости ресурсов от объёмов входных данных чаще всего измеряется асимптотически (хотя в некоторых ситуациях резонно измерять память точно, как это делается для одной из исследуемых нами задач). Например, будем говорить, что данный алгоритм работает за O(n2) времени и использует O(n^/n) памяти, если на входных данных размера n алгоритм выполняет O(n2) элементарных операций и потребляет O(n^/n) памяти. Что именно подразумевается под размером данных, зависит от конкретной задачи. Естественно, чтобы строго определить, какие элементарные операции допустимы и в каких единицах измеряется память, необходимо описать так называемую модель вычислений — набор доступных программе инструкций и возможностей по использованию памяти. Применяемые нами модели подробно рассмотрены ниже, но, забегая вперёд, можно отметить, что почти все они являются незначительными модификациями RAM модели — модели, наиболее полно отражающей особенности современных компьютеров.

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

1.3 Базовые определения

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

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

Строки. Строка длины n — это отображение {1, 2,...,n} м- £, где £ — некоторое конечное множество, называемое алфавитом. Элементы алфавита £ называются символами. Длина строки w обозначается через |w|. Пустая строка (т.е. строка длины 0) обозначается е. Через w[1], w[2],... , w[n] обозначаются 1-й, 2-й, ..., n-й символы w, соответственно. Для произвольных целых числе i и j обозначим w[i..j] = w[i]w[i+1] • • • w[j]; если i > j, то полагаем w[i..j] = е. Строка w = w[n] ••• w[2]w[1] называется строкой, обратной к w. Для произвольных чисел i и j множество {k Е Z: i < k < j} будем обозначать через [i..j]. Обозначим (i..j] = [i..j] \ {i}, [i..j) = [i..j] \ {j}, (i..j) = (i..j] П [i..j). Везде в тексте для краткости логарифм по основанию 2 обозначается log.

Строка u называется подстрокой (или фактором) строки w, если u = w[i..j] для некоторых i и j. В этом случае пара чисел (i, j) не обязательно единственна; будем говорить, что i определяет вхождение u в w. Строка может иметь множество вхождений в другую строку. Строка вида w[1..i] [соответственно, w[i..n]] называется префиксом w [соответственно, суффиксом w]. Конкатенацией строк v и w называется строка vw = v[1]v[2]... v[|v|]w[1]w[2]... w[|w|]. Для k > 1 k-й степенью строки w называется строка wk, являющаяся конкатенацией k копий w. Строка называется примитивной, если она не является степенью какой-то более короткой строки.

Произвольное множество строк (возможно бесконечное) над данным фиксированным алфавитом называется языком. Определим стандартные операции, позволяющие получать из простых языков сложные. Пусть L и M — языки. Обозначим L • M = {uv: u Е L,v Е M}. Произведение k копий языка L будем обозначать Lk. Договоримся считать, что L0 = {е}. Обозначим L* = (J~ 0 Lk.

Пусть символы рассматриваемого алфавита £ линейно упорядочены. Строка x лексикографически меньше строки y (обозначается x < y), если x является собственным префиксом y или для некоторого i Е [1..|x|] выполняется x[1..i—1] = y[1 ..i—1] и x[i] < y[i]. Ясно, что отношение лексикографического порядка линейно упорядочивает множество строк над данным упорядоченным алфавитом. Естественным образом определяются отношения x < y, x > y, x > y.

Деревья и боры. Деревом называется обыкновенный связный граф без циклов. Дерево с одной выделенной корневой вершиной (корнем) называется корневым деревом. Фактически в тексте используются только корневые деревья, поэтому будем для краткости называть их просто деревьями, а корень всегда будет ясен из контекста. Листом дерева называется некорневая вершина степени 1; все остальные вершины называются внутренними. Иногда будут рассматриваться направленные деревья, в которых рёбра всегда направлены от вершин к листьям. Путь в графе — это последовательность вершин vi, v2,... , vk такая, что v и vi+1 соединены ребром для всех i Е [1..k). В деревьях будут рассматриваться только пути, идущие от корня к листьям без повторений вершин. Число k называется высотой данного дерева T, если самый длинный путь от корня до какого-либо листа T содержит k+1 вершину. Для краткости будем использовать запись v Е T для обозначения того факта, что v — вершина T.

Бор2 для конечного множества строк S — это дерево, каждое ребро которого помечено непустой строкой так, что сумма длин меток минимальна и выполняются следующие свойства: каждая строка из S является префиксом строки, написанной на пути от корня до какого-либо листа, а каждая строка, написанная на пути от корня до листа, является строкой из S. Например, бор для множества строк

2 Этот несколько странный термин устоялся в русскоязычной литературе по алгоритмам и программированию. Его английский аналог trie — неологизм, полученный из tree и retrieval.

S = [а, аа, ааааосссаааао, аааассссассе, ааааосссааао, аааессе, ааассааса} изображён на рисунке 1.1. Ясно, что разные множества могут порождать одинаковый бор.

Рис. 1.1: Бор.

Наше определение бора незначительно отличается от общепринятого, в котором метками рёбер могут выступать не строки, а только символы. В контексте рассматриваемых в данной работе задач наше определение более удобно. Часто в бор входят строки, являющиеся подстроками какой-то одной основной в данной задаче строки в. В таком случае вместо того, чтобы указывать на каждом ребре строку-метку явно, можно просто задать позицию, в которой данная строка-метка встречается в в, и длину строки-метки. Полученное представление бора называют сжатым бором. Аналогично тому, как это было с деревьями, будем использовать запись V Е Т для обозначения того факта, что V — вершина данного [сжатого] бора Т.

Асимптотические оценки. Для асимптотической оценки роста функций в работе обширно используются обозначения O, П, в, о, ш. Напомним их определение. Через F обозначим множество неотрицательных функций целочисленного аргумента. Пусть f Е F. Тогда O(f) — это множество всех g Е F таких, что g(n) < cg f (n) для всех n > Ng, где cg и Ng — некоторые константы, зависящие от g. Обозначим Q(f) = {g Е F: f Е O(g)} и e(f) = Q(f) П O(f). Через o(f) обозначим множество всех д Е F таких, что g(n) = ag(n)f (n) для всех n > Ng, где Ng — некоторое число, зависящее от g, а ag(n) — некоторая функция, зависящая от g, такая, что lim ag(n) = 0. Обозначим ш(f) = {g Е F: f = o(g)}. Вместо g Е O(f), g Е Q(f),

g Е e(f), g Е o(f), g Е ) всегда пишут g = O(f), g = n(f), g = e(f), g = o(f), g = ш(f),

соответственно.

Также нам понадобятся аналоги введённых обозначений для случая неотрицательных функций с двумя и тремя параметрами. Например, для данной неотрицательной функции двух целочисленных аргументов f (m, n) через O(f (m, n)) будем обозначить множество неотрицательных функций g(m,n) таких, что g(m,n) < cgf (m,n) для всех m > Mg и n > Ng, где cg, Mg, Ng — некоторые константы, зависящие от g. Остальные определения аналогичны. Дальнейшее описание способов работы с этими обозначениями можно найти, например, в учебнике [22].

1.3.2 Закономерности в строках

Все исследуемые нами закономерности в строках так или иначе описывают некую повторяющуюся структуру и поэтому важную роль при их рассмотрении играет понятие периода. Целое число р Е (0..|т|] называется периодом строки т, если для каждой позиции г Е [1..|т|-р] выполняется т[г] = т[г+р]. Если р — минимальный период строки т, то число 1т1/р называется экспонентой т. Строка и называется гранью т, если и одновременно и суффикс и

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

Лемма 1.3.1 (см. [28, раздел 1.7]). Строка ад имеет период р > 0 тогда и только тогда, когда ад имеет грань длины |ад| — р.

Перейдём к определению главных объектов нашего исследования. Определения распределены по трём пунктам в соответствии с главами 2, 3, 4, в которых подробно обсуждаются соответствующие объекты.

Разложение Лемпеля—Зива

Разложение Лемпеля-Зива [68] строки s — это однозначное представление строки s в виде s = • • • Zk такое, что каждая подстрока z¿ не пуста и представляет собой либо символ, не встречавшийся ранее в строке s, либо самую длинную подстроку в данной позиции, имеющую не менее двух вхождений в строке z1z2 • • • z¿. Строки z¿ будем называть факторами Лемпеля-Зива.

Удобно представлять себе, что разложение Лемпеля-Зива строки s строится жадно слева направо. Если уже найдены факторы Лемпеля-Зива z1,z2,... , zm-1, то для построения zm нужно читать s с позиции i = |z1z2 • • • zm-1| + 1 до тех пор, пока строка s[i..i+z] имеет вхождение где-то левее в s. Нужно положить zm = s[i..i+z] для максимального такого z (или zm = s[i], если такая строка пуста).

Пример 1.3.1. Строка ababcaba имеет разложение Лемпеля-Зива a • b • ab • c • aba. Строка abababaabbbaaba имеет разложение Лемпеля-Зива a • b • ababa • ab • bb • aab • a. В последнем случае обратите внимание на «наложение на себя» факторов Лемпеля-Зива ababa и bb.

Повторы

Зафиксируем рациональное число е > 1. Строки с экспонентами большими или равными е будем называть е-повторами; если е в обсуждаемом контексте не важно, то будем говорить просто о повторах. Например, строка абаб — это 2-повтор, ааа — 3-повтор, аббсаб — 1.5-повтор. Из определения следует, что если w — е-повтор, то ад также является е'-повтором для всех е' таких, что 1 < е' < е. Например, ааа — это 3-повтор и в то же время 1.7-повтор и, например, 2-повтор. Повторы вида хх, где х — непустая строка, называются квадратами. Повторы вида ххх называются кубами. Будем говорить, что ад — строка без е-повторов или строка ад не содержит е-повторов, если в ад нет подстрок, являющихся е-повторами.

Подстрока ад[г..^] строки ад называется максимальным повтором, если ад[г..^'] — это 2-повтор, а подстроки ад[г—1..^'] и ад[г..^ + 1] (если определены) не являются 2-повторами.

Палиндромы

Палиндром — это строка w такая, что W = ад. Подстроку v [соответственно, суффикс v, префикс v] данной строки будем называть подпалиндрюмом [соответственно, суффикс-палиндромом, префикс-палиндромом], если v является палиндромом. Например, строка ababa содержит 5 различных подпалиндромов: b, bab, e, a, aba, ababa; четыре последних подпалин-дрома имеют вхождения, являющиеся суффикс-палиндромами и префикс-палиндромами исходной строки. Обозначим через Pal язык всех непустых палиндромов над рассматриваемым алфавитом (о каком алфавите идёт речь будет всегда понятно из контекста).

1.4 Модель RAM

Базовая модель, используемая нами для построения алгоритмов, — это RAM модель (от англ. Random Access Machine или Random Access Model). В подразделе 1.4.1 сформулировано, какие именно инструкции являются допустимыми в RAM алгоритме и рассмотрены некоторые совсем неочевидные особенности модели памяти RAM машины, которые будут играть существенную роль в обсуждаемых впоследствии алгоритмических построениях. В подразделе 1.4.2 явно определено, в каком виде RAM алгоритм взаимодействует с входными данными, а также вводится важное понятие онлайнового алгоритма. Подраздел 1.4.3 посвя-щён описанию способа оценки времени выполнения RAM алгоритмов в различных моделях входных данных и здесь же определяется в дальнейшем очень часто применяемое понятие структуры данных.

1.4.1 Доступные инструкции и память

В модели RAM алгоритму доступны все базовые арифметические операции: сложение, вычитание, умножение, деление, а также побитовые операции: побитовый сдвиг, побитовые «и», «или», отрицание, но самое главное, что есть возможность использовать массивы, индексируемые целыми числами, — это память с произвольным доступом (Random Access Memory). Для простоты можно полагать, что элементами массивов выступают только целые числа. Известно, что с помощью таких массивов можно имитировать массивы, состоящие из структур произвольного фиксированного размера (см. [22, раздел 10.3]). Чтение и запись в ячейку массива, равно как и каждая арифметическая или побитовая операция, выполняются за фиксированное константное время. Входными данными для всех рассматриваемых в тексте алгоритмов является строка и длина этой строки всегда обозначается через n. Относительно n и оценивается время работы алгоритма, т.е. число операций, которые алгоритм затрачивает на решение задачи.

Часто алгоритмы или фрагменты алгоритмов для RAM машины будут кодироваться псевдокодом, похожим на традиционные императивные языки, такие как C или Pascal. В псевдокоде, помимо стандартных конструкций присваивания, циклов и ветвлений, присутствует трёхоперандный цикл for, как в языке C. Запись для массивов аналогична записи для строк, но нам будет удобно всякий раз явно оговаривать, с какой позиции начинается индексация в массиве. Например, в псевдокоде ниже используется массив b[0..n-1]. Дальнейшие расширения языка псевдокода будут вводиться по мере надобности. 1: алгоритм обрабатывает строку w длины n

2: for (i ^ 1; i < n; i ^ i + 1) do > тернарный цикл for

3: b[i-1] ^ 0; > присвоить 0 в ячейку массива b

4: if w[i] = a then 5: b[i-1] ^ 1;

6: while i < n and w[i+1] = a do

7: i ^ i + 1;

Данный алгоритм отмечает в b позиции начала блоков, состоящих из символов «a», во входной строке. Если не вдаваться в детали, то можно заключить, что этот алгоритм использует O(n) памяти. Хотя вопрос оценки памяти стоит обсудить отдельно.

С RAM моделью связана одна на первый взгляд неочевидная тонкость. Алгоритм почти наверняка на входной строке длины n будет оперировать целыми числами порядка n, хотя бы просто чтобы иметь доступ к символам строки. И операции над числами, принимающими значение от 0 до n, выполняются за константное время, конечно. Таким образом, одно целое число, с которым алгоритм может совершать операции за константное время, содержит ©(logn) битов. Такая элементарная целочисленная ячейка, содержащая ©(logn) битов,

называется машинным словом. Поэтому RAM модель иногда называют RAM моделью с константными операциями над словами. Эта особенность RAM модели отражает реальный факт: компьютер для выполнения операции сложения, например, использует схему, которая работает параллельно и вычисляет результат за константное время. Таким образом, RAM машина имеет толику параллелизма внутри себя. И это немаловажно для нас, так как в некоторых случаях позволяет улучшать асимптотическое время работы алгоритмов, оперируя за константное время блоками данных, состоящими из O(log n) битов. Этот трюк часто называют методом четырёх русских (см. [1]). В свете этого стоит уточнить, что RAM алгоритмы используют массивы не произвольных целых чисел, а целых чисел, помещающихся в машинное слово.

Везде в тексте потребляемая память измеряется в машинных словах; если же память измеряется в битах (как это часто происходит в разделе 2.3), это каждый раз оговаривается явно. Таким образом, будем говорить, что, например, алгоритм потребляет O(n2) памяти, если на любой входной строке длины n алгоритм использует O(n2) машинных слов, что фактически равно O(n2 logn) битам. Будем говорить, что алгоритм использует линейную память, если он потребляет O(n) памяти (как в примере выше). Линейная память зачастую воспринимается как наилучшая возможная асимптотическая оценка, потому что как минимум O(n) памяти требуется для хранения входной строки. Тем не менее для некоторых задач естественно предполагать, что входная строка расположена в некоем внешнем хранилище или же, что входная строка занимает o(nlog n) битов памяти. В этом случае будем говорить не о памяти, а о дополнительной памяти, чтобы подчеркнуть, что речь идёт о памяти помимо входной строки. Лучшее на что можно надеяться при решении задачи с такими ограничениями — это 0(1) дополнительной памяти (константная память).

1.4.2 Входные данные

Как закодированы входные данные для RAM машины? Естественным образом выделяют модель с общим алфавитом. Удобно представлять себе, что входная строка в этой модели находится во внешнем для алгоритма устройстве, а сам алгоритм может за константное время посылать в устройство запросы на сравнение символов и получать ответы. Такой алфавит может быть упорядоченным или неупорядоченным (подробное описание ниже) в зависимости от того, какие ответы присылает это внешнее устройство. Общий алфавит позволяет максимально абстрагироваться от природы входной последовательности и оперировать достаточно сложными объектами (например, словами естественного языка или структурами со множеством полей), воспринимая их как символы. Мы стремимся, по возможности, рассматривать общие алфавиты, чтобы наши алгоритмы имели наиболее широкую сферу применения. Тем не менее для многих задач больший интерес представляют целочисленный и константный алфавиты (определены ниже) — два самых распространённых случая необщего алфавита.

Список литературы диссертационного исследования кандидат наук Косолобов Дмитрий Александрович, 2016 год

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

[1] Об экономном построении транзитивного замыкания ориентированного графа / В. Л. Арлазаров, Е. А. Диниц, М. А. Кронрод, И. А. Фараджев // Доклады АН СССР. — 1970. — Т. 134, № 3. — С. 1209-1210.

[2] Abouelhoda M. I., Kurtz S., Ohlebusch E. Replacing suffix trees with enhanced suffix arrays // J. of Discrete Algorithms. - 2004. - Vol. 2, no. 1. — P. 53-86.

[3] Aho A. V., Hirschberg D. S., Ullman J. D. Bounds on the complexity of the longest common subsequence problem // J. of ACM (JACM). — 1976. — Vol. 23, no. 1. — P. 1-12.

[4] A comparison of index-based Lempel-Ziv LZ77 factorization algorithms / A. Al-Hafeedh, M. Crochemore, L. Ilie et al. // ACM Computing Surveys (CSUR).— 2012.- Vol. 45, no. 1. — P. 5.

[5] Apostolico A., Breslauer D. An optimal 0(loglogn)-time parallel algorithm for detecting all squares in a string // SIAM J. on Computing. — 1996. — Vol. 25, no. 6. — P. 1318-1331.

[6] Badkobeh G., Crochemore M., Toopsuwan C. Computing the maximal-exponent repeats of an overlap-free string in linear time // SPIRE 2012 / Springer Berlin Heidelberg. — Vol. 7608 of LNCS. - 2012. - P. 61—72.

[7] The "runs" theorem / H. Bannai, T. I, S. Inenaga et al. // arXiv preprint arXiv:1406.0263v4.— 2014.

[8] Beame P., Fich F. E. Optimal bounds for the predecessor problem // STOC 1999 / ACM.— 1999.— P. 295—304.

[9] Belazzougui D. Succinct dictionary matching with no slowdown // CPM 2010 / Springer.— Vol. 6129 of LNCS. — 2010. — P. 88—100.

10] Belazzougui D., Puglisi S. J. Range predecessor and Lempel—Ziv parsing // arXiv preprint arXiv:1507.07080. — 2015.

11] Computing the longest common prefix array based on the Burrows—Wheeler transform / T. Beller, S. Gog, E. Ohlebusch, T. Schnattinger // J. of Discrete Algorithms. —— 2013. —— Vol. 18. — P. 22—31.

12] Two simplified algorithms for maintaining order in a list / M. A. Bender, R. Cole, E. D. Demaine et al. // Algorithms-ESA 2002. — Springer, 2002. — Vol. 2461 of LNCS. — P. 152—164.

13] Time-space trade-offs for longest common extensions / P. Bille, I. L. G0rtz, B. Sach, H. W. Vildh0j // J. of Discrete Algorithms. — 2014. — Vol. 25. — P. 42—50.

14] Blelloch G. E. Space-efficient dynamic orthogonal point location, segment intersection, and range reporting // SODA 2008 / SIAM. - 2008. — P. 894—903.

151 Breslauer D. Efficient string algorithmics : Ph. D. thesis / D. Breslauer ; Columbia University. - 1992.

16] Breslauer D., Gasieniec L. Efficient string matching on coded texts // CPM 1995. — Vol. 937 of LNCS. - Springer, 1995. - P. 27-40.

17] Breslauer D., Grossi R., Mignosi F. Simple real-time constant-space string matching // CPM 2011. — Vol. 6661 of LNCS. - Springer, 2011. — P. 173-183.

18] Breslauer D., Italiano G. F. Near real-time suffix tree construction via the fringe marked ancestor problem // Journal of Discrete Algorithms. — 2013. — Vol. 18. — P. 32-48.

19] Burkhardt S., Karkkainen J. Fast lightweight suffix array construction and checking // CPM 2003. — Vol. 2676 of LNCS. - Springer, 2003. — P. 55-69.

20] A block-sorting lossless data compression algorithm : Rep. : 124 / Digital Equipment Corporation ; Executor: M. Burrows, D. J. Wheeler. — Palo Alto, California : 1994.

21] Chen G., Puglisi S. J., Smyth W. F. Lempel-Ziv factorization using less time & space // Mathematics in Computer Science. — 2008. — Vol. 1, no. 4. — P. 605-623.

22] Introduction to algorithms second edition / T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein. — MIT press, 2001.

23] Crochemore M. Transducers and repetitions // Theoretical Computer Science.— 1986.— Vol. 45. - P. 63-86.

24] Crochemore M., Hancart C., Lecroq T. Algorithms on strings. — Cambridge University Press, 2007.

25] Crochemore M., Ilie L., Smyth W. F. A simple algorithm for computing the Lempel-Ziv factorization // Data Compression Conference (DCC'08) / IEEE. — 2008. — P. 482-488.

26] Crochemore M., Ilie L., Tinta L. The "runs" conjecture // Theoretical Computer Science.— 2011. — Vol. 412, no. 27. — P. 2931-2941.

27] On the maximal sum of exponents of runs in a string / M. Crochemore, M. Kubica, J. Ra-doszewski et al. // J. of Discrete Algorithms. — 2012. — Vol. 14. — P. 29-36.

28] Crochemore M., Rytter W. Jewels of stringology.— World Scientific Publishing Co. Pte. Ltd., 2002.

29] de Luca A. Sturmian words: structure, combinatorics and their arithmetics // Theoretical Computer Science. - 1997. - Vol. 183. - P. 45-82.

30] Fast relative Lempel—Ziv self-index for similar sequences / H. H. Do, J. Jansson, K. Sadakane, W.-K. Sung // Theoretical Computer Science. - 2014. - Vol. 532. — P. 14-30.

31] Droubay X., Justin J., Pirillo G. Episturmian words and some constructions of de Luca and Rauzy // Theoretical Computer Science. — 2001. — Vol. 255.— P. 539-553.

32] Droubay X., Pirillo G. Palindromes and Sturmian words // Theoretical Computer Science. — 1999. — Vol. 223. - P. 73-85.

33] Linear-time computation of local periods / J.-P. Duval, R. Kolpakov, G. Kucherov et al. // Theoretical Computer Science. — 2004. — Vol. 326, no. 1. — P. 229-240.

[34] Fiala E. R., Greene D. H. Data compression with finite windows // Communications of the ACM. - 1989. - Vol. 32, no. 4. - P. 490-505.

[35] A subquadratic algorithm for minimum palindromic factorization / G. Fici, T. Gagie, J. Karkkainen, D. Kempa // J. of Discrete Algorithms. — 2014. — Vol. 28. — P. 41-48.

[36] Fine N. J., Wilf H. S. Uniqueness theorems for periodic functions // Proceedings of the American Mathematical Society.— 1965. — Vol. 16, no. 1.— P. 109-114.

[37] Beyond the runs theorem / J. Fischer, S. Holub, T. I, M. Lewenstein // arXiv preprint arXiv:1502.04644. — 2015.

[38] Fischer J., IT., Kappl D. Lempel-Ziv computation in small space (LZ-CISS) // CPM 2015. — Vol. 9133 of LNCS. — Springer International Publishing, 2015. — P. 172-184.

[39] Franceschini G., Grossi R. A general technique for managing strings in comparison-driven data structures // ICALP 2004. — Vol. 3142 of LNCS. — Springer, 2004. — P. 606-617.

[40] A faster grammar-based self-index / T. Gagie, P. Gawrychowski, J. Karkkainen et al. // LATA 2012. — Springer, 2012. — Vol. 7183 of LNCS. — P. 240-251.

[41] LZ77-based self-indexing with faster pattern matching / T. Gagie, P. Gawrychowski, J. Karkkainen et al. // LATIN 2014: Theoretical Informatics. — Springer, 2014. — P. 731-742.

[42] Galil Z. Open problems in stringology // Combinatorial Algorithms on Words. — Springer, 1985. — P. 1-8.

[43] Galil Z., Seiferas J. A Linear-Time On-Line Recognition Algorithm for "Palstar" // J. of ACM (JACM). — 1978. — Vol. 25, no. 1. — P. 102-111.

[44] Galil Z., Seiferas J. Time-space-optimal string matching // J. of Computer and System Sciences. - 1983. - Vol. 26, no. 3. — P. 280-294.

[45] Palindromic richness / A. Glen, J. Justin, S. Widmer, L. Zamboni // European J. of Combinatorics. - 2009. - Vol. 30. — P. 510-531.

[46] Goto K., Bannai H. Space efficient linear time Lempel-Ziv factorization for small alphabets // Data Compression Conference (DCC'14) / IEEE. — 2014. — P. 163-172.

[47] More haste, less waste: Lowering the redundancy in fully indexable dictionaries / R. Grossi, A. Orlandi, R. Raman, S. S. Rao // STACS 2009.- Vol. 3 of LIPIcs. — Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2009.— P. 517-528.

[48] Groult R., Prieur E., Richomme G. Counting distinct palindromes in a word in linear time // Information Processing Letters. — 2010. — Vol. 110. — P. 908-912.

[49] Gusfield D. Algorithms on strings, trees and sequences: computer science and computational biology. — Cambridge university press, 1997.

[50] Hagerup T., Miltersen P. B., Pagh R. Deterministic dictionaries // J. of Algorithms. — 2001. — Vol. 41, no. 1. — P. 69-85.

[51] Harel D., Tarjan R. E. Fast algorithms for finding nearest common ancestors // SIAM J. on Computing. — 1984. — Vol. 13, no. 2. — P. 338-355.

[52] Hon W.-K., Sadakane K., Sung W.-K. Breaking a time-and-space barrier in constructing full-text indices // FOCS 2003 / IEEE. — 2003. — P. 251-260.

[53] Hong J.-J., Chen G.-H. Efficient on-line repetition detection // Theoretical Computer Science. — 2008. — Vol. 407, no. 1. — P. 554-563.

[54] Jansson J., Peng Z. Online and dynamic recognition of squarefree strings // MFCS 2005.— Springer, 2005. — Vol. 3618 of LNCS. — P. 520-531.

[55] Karkkainen J., Kempa D., Puglisi S. J. Lightweight Lempel-Ziv parsing // SEA 2013. — Vol. 7933 of LNCS. - Springer, 2013. — P. 139-150.

[56] Karkkainen J., Kempa D., Puglisi S. J. Linear time Lempel-Ziv factorization: Simple, fast, small // CPM / Springer. — Vol. 7922 of LNCS. — 2013. — P. 189-200.

[57] Knuth D. E., Morris J. H., Pratt V. R. Fast pattern matching in strings // SIAM J. on Computing. — 1977. — Vol. 6. — P. 323-350.

[58] A linear time algorithm for seeds computation / T. Kociumaka, M. Kubica, J. Radoszewski et al. // SODA 2012 / SIAM. — 2012. — P. 1095-1112.

[59] Kolpakov R. On primary and secondary repetitions in words // Theoretical Computer Science. — 2012. — Vol. 418. — P. 71-81.

[60] Kolpakov R., Kucherov G. Finding maximal repetitions in a word in linear time // FOCS 1999. — IEEE, 1999. — P. 596-604.

[61] Searching of gapped repeats and subrepetitions in a word / R. Kolpakov, M. Podolskiy, M. Posypkin, N. Khrapov // CPM 2014 / Springer International Publishing.— LNCS.—

2014. — P. 212-221.

[62] Kopelowitz T., Lewenstein M. Dynamic weighted ancestors // SODA 2007. — SIAM, 2007. — P. 565-574.

[63] Koppl D., Sadakane K. Lempel Ziv computation in compressed space (LZ-CICS) // arXiv preprint arXiv:1510.02882. — 2015.

[64] Kosolobov D. Computing runs on a general alphabet // arXiv preprint arXiv:1507.01231. ——

2015.

[65] Kreft S., Navarro G. Self-indexing based on LZ77 // CPM 2011 / Springer. — Vol. 6661 of LNCS. — 2011. — P. 41-54.

[66] Kreft S., Navarro G. On compressing and indexing repetitive sequences // Theoretical Computer Science. — 2013. — Vol. 483. - P. 115-133.

[67] Lee L. Fast context-free grammar parsing requires fast boolean matrix multiplication // J. of ACM (JACM). - 2002. — Vol. 49, no. 1. - P. 1-15.

[68] Lempel A., Ziv J. On the complexity of finite sequences // IEEE Transactions on Information Theory. — 1976. — Vol. 22, no. 1. — P. 75-81.

[69] Leung H.-F., Peng Z., Ting H.-F. An efficient online algorithm for square detection // Computing and Combinatorics. — Springer, 2004. — P. 432-439.

[70] Lothaire M. Combinatorics on words. — Cambridge University Press, 1997.

[71] Main M. G. Detecting leftmost maximal periodicities // Discrete Applied Mathematics. — 1989. — Vol. 25, no. 1. —P. 145-153.

[72] Main M. G., Lorentz R. J. Linear time recognition of squarefree strings // Combinatorial Algorithms on Words. — Springer, 1985. — P. 271-278.

[73] Manacher G. A new linear-time on-line algorithm finding the smallest initial palindrome of a string // J. of ACM (JACM). — 1975. — Vol. 22, no. 3. - P. 346-351.

[74] Navarro G., Sadakane K. Fully functional static and dynamic succinct trees // ACM Transactions on Algorithms (TALG). — 2014. — Vol. 10, no. 3. — P. 16.

[75] Ohlebusch E., Gog S. Lempel-Ziv factorization revisited // CPM 2011 / Springer. — Vol. 6661 of LNCS. — 2011. — P. 15-26.

[76] Okanohara D., Sadakane K. An online algorithm for finding the longest previous factors // Algorithms-ESA 2008. — Springer, 2008. — Vol. 5193 of LNCS. — P. 696-707.

[77] Raman R., Raman V., Rao S. S. Succinct indexable dictionaries with applications to encoding k-ary trees and multisets // SODA 2002 / SIAM. - 2002. - P. 233-242.

[78] Rodeh M., Pratt V. R., Even S. Linear algorithm for data compression via string matching // J. of ACM (JACM). - 1981. - Vol. 28, no. 1. - P. 16-24.

[79] Rubinchik M., Shur A. M. Eertree: An efficient data structure for processing palindromes in strings // arXiv preprint arXiv:1506.04862.— 2015.

[80] Rytter W. The number of runs in a string: Improved analysis of the linear upper bound // STACS 2006. - Springer, 2006. - Vol. 3884 of LNCS. - P. 184-195.

[81] Shur A. M. Generating square-free words efficiently // Theoretical Computer Science.— 2015. — Vol. 601. — P. 67-72.

[82] Smyth W. Computing patterns in strings. — Pearson Education, 2003.

[83] Starikovskaya T. Computing Lempel-Ziv factorization online // MFCS 2012.— Springer, 2012. — Vol. 7464 of LNCS. - P. 789-799.

[84] Valiant L. G. General context-free recognition in less than cubic time // J. of Computer and System Sciences. — 1975. — Vol. 10, no. 2. — P. 308-314.

[85] Weiner P. Linear pattern matching algorithms // Switching and Automata Theory, 1973. SWAT'08. IEEE Conference Record of 14th Annual Symposium on / IEEE. — 1973. — P. 111.

[86] Faster compact on-line Lempel-Ziv factorization / J. Yamamoto, T. I, H. Bannai et al. // STACS 2014. — Vol. 25 of LIPICS. - 2014. — P. 675-686.

Работы автора по теме диссертации

[87] Kosolobov D. Online square detection // Strings, Languages, Automata. Abstracts of Reports and Other Materials of the 7th School "Computer Science Days in Ekaterinburg" A. M. Shur (ed.). — Ekaterinburg: Ural University Press, 2014.— P. 19-21.

[88] Kosolobov D. Faster lightweight Lempel-Ziv parsing // MFCS 2015 / Springer-Verlag Berlin Heidelberg. — Vol. 9235 of LNCS. - 2015. - P. 432-444.

[89] Kosolobov D. Lempel-Ziv factorization may be harder than computing all runs // STACS 2015. — Vol. 30 of LIPIcs. — Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2015. — P. 582-593.

[90] Kosolobov D. Online detection of repetitions with backtracking // CPM 2015 / Springer International Publishing. — Vol. 9133 of LNCS. — 2015. — P. 295-306.

[91] Kosolobov D., Rubinchik M. An optimal online algorithm for finding all distinct subpalindromes of a string // Algorithms & Complexity. Abstracts of Reports and Other Materials of the 6th School "Computer Science Days in Ekaterinburg" A. S. Kulikov, A. M. Shur (eds.). — Ekaterinburg: Ural University Press, 2013. — P. 44-46.

[92] Kosolobov D., Rubinchik M., Shur A. M. Finding distinct subpalindromes online // Proc. Prague stringology conference 2013 / Ed. by Jan Holub, Jan Zdarek. — CTU, 2013. — P. 6369.

[93] Kosolobov D., Rubinchik M., Shur A. M. Palk is linear recognizable online // SOFSEM 2015: Theory and Practice of Computer Science. — Springer-Verlag Berlin Heidelberg, 2015. — Vol. 8939 of LNCS. - P. 289-301.

Список иллюстраций

1.1 Бор............................................ 8

1.2 Решающее дерево высоты 2, анализирующее строки длины 3. Строки aaa и bbb достигают закрашенной вершины........................... 14

2.1 Толстые вершины и рёбра находятся в боре Q0................... 27

2.2 т2 = 4; префиксные ссылки, ассоциированные с вершинами, обозначены прямоугольниками..................................... 29

2.3 Толстые вершины и рёбра находятся в боре Q0. Здесь pv(a) = iv,pv(b) = iv + 4,pv (d) = rji + 5,pv (c) = rji + 7,pv (e) = rji + 11, Pv (o) = rji + 12,pv (t) =

rj2 + 1,pv(x) = rj2 + 2 и поэтому Pi = {a, b}, P2 = {t, x}, P3 = {d, c, e, o}..... 30

2.4 Массивы Av, Bv, Cv и их размеры. Здесь q = 9................... 31

2.5 Толстые рёбра находятся в боре Q0.......................... 33

2.6 Вершины v и w, соответствующие tf-1 и tf; здесь tf = s[/]t', lab(w) = s[/]t't''. 37

2.7 Сжатый бор T (слева) и соответствующее тернарное дерево T' (справа). Если r = 4, поиск w = aaaaccccaaaac последовательно находит вершины 6,6,8,8, соответствующие префиксам w длины r, 2r, 3r и |w|................ 40

2.8 Структура ортогонального поиска на деревьях S и T. Здесь т = 3, D = {0,1, 3, 6} — разностное покрытие отрезка [0..т2), позиции из множества M подчёркнуты....................................... 42

2.9 Боры S и S' для s[0..t] = $bbacbabacbacba (позиции из M подчёркнуты). Здесь сбалансированные деревья поиска Bi, B2,... , Bg в S' содержат индексы листьев бора S.......................................... 45

3.1 Накладывающиеся кубические максимальные повторы t1 и t2 такие, что 2$ < p(ti) < p(t2) < 3$.................................... 49

3.2 Максимальный р-повтор, соответствующий d-дефектному максимальному повтору t'[fci..fc2] = e/ge, где ki = 2, k2 = 5, р = 4, d =2, q = 3, k = 3, l = 2pq = 24,

i = (ki-2)p+1 = 1, j = (k2+d)p = 28......................... 54

3.3 Кубический максимальный повтор в t' с минимальным периодом q = 3 < d = 5,

где p = 4, ki = 2, k2 = 11, k = 4, = 3, l = 3, p' = 2pq = 24........... 56

3.4 Бор T для w = abcabcababcabb$ (подчёркнутые позиции лежат в M, т2 = 4). Здесь сбалансированные деревья поиска Bi, B2,..., Bg в S содержат индексы листьев бора T...................................... 60

3.5 e-повтор w[k..n], где k = 5, n =16. Здесь i = 6, j = 7 и w[i..j] = w[14..15]. ... 62

3.6 Система ловцов, покрывающих отрезок [1..n-s+1]................. 65

3.8 Система ловцов {ck}m=0 с m = 2 (дополнительный ловец c3 нарисован для

понятности), e ~ 1.5, а ~ |.............................. 68

4.1 Предсказуемые вызовы................................. 83

4.2 Дополнительное предсказание; c0 = maxPal, c' = refl(c, c0), i = c — r, i' = c + r — 1. 84

4.3 Серии палиндромов с общим периодом p. Случаи (а) p > в+1 (= r° + r^ = 5)

и (б) в+1 > p (= r0 + ri = 6)............................. 87

4.4 Суффикс т на момент пересчёта г. Отмечены позиции п и п2 некоторых (не обязательно последних!) предыдущих пересчётов г. Показаны (заштрихованы) соответствующие пересчитанные циклические отрезки блока г^..^]....... 88

Список таблиц

1.1 Лучшие алгоритмы поиска разложения Лемпеля-Зива, использующие

O(n log а) битов..........................................................................16

2.1 Значения BWT, SA, Ф для x = Saabadcaababadcaaba................................24

2.2 Структуры для поддержания эффективных операций на S........................44

3.1 Таблица значений m^- в примере для j = 1, 2........................................53

3.2 Значения m^i, Sj, t'[i] в примере........................................................54

3.3 Значения mi,1, Sj, t'[i] в примере с двумя максимальными р-повторами, соответствующими одному максимальному повтору в t'................................55

4.1 Пример rad и nextPal для т = aabacabaa..............................................76

4.2 Максимальные ведущие подпалиндромы, начинающиеся в позициях строки т = ababab......................................................................................81