Эффективные алгоритмы для некоторых задач обработки слов

В работе рассматриваются различные задачи обработки слов и предлагаются эффективные алгоритмы для их решения.

Рассматриваемая область интересна как с теоретической точки зрения, так и с практической: во-первых, она имеет многочисленные связи с комбинаторикой слов, теорией конечных автоматов, вычислительной геометрией, во-вторых, она имеет приложения в биоинформатике, обработке текстов, распознавании речи, компьютерном зрении.

Под словом мы понимаем конечную упорядоченную последовательность элементов конечного непустого множества, называемого алфавитом. Элементы этого множества называются буквами.

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

Первая модель вычислений, которая будет использоваться по умолчанию, — это равнодоступная адресная машина, сокращенно РАМ (см. [2]). РАМ состоит из входной ленты, с которой она может только считывать данные, выходной ленты, на которую она может только записывать данные, и памяти. Память машины состоит из последовательности ячеек, в каждой из которых можно хранить произвольное целое число в двоичной записи. Число ячеек, которое можно использовать, не ограничено сверху. Такая идеализация допустима в случаях, когда 1) размер задачи достаточно мал, чтобы она поместилась в оперативную память вычислительной машины;

2) целые числа, участвующие в вычислении, достаточно малы, чтобы их можно было помещать в одну ячейку.

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

Вторая модель, предложенная Майклом Фредманом и Дэном Бильярдом в 1993 г. [30], является вариантом первой. В этой модели, во-первых, мы фиксируем размер ячейки памяти, полагая его равным некоторой константе и требуем, чтобы все целые числа, участвующие в вычислении, не превосходили 2Ш. Во-вторых, мы включаем в список элементарных команд операцию битового сдвига над двоичными векторами длины т.

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

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

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

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

Начнем с задачи о поиске образца. Основная постановка этой задачи звучит следующим образом: перечислить начальные позиции всех вхождений слова Р в слово Т длины п. Вхождение слова Р в слово Т — это подслово слова Т, совпадающее с Р. Следуя принятой терминологии, мы будем называть слово Р образцом.

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

Первый алгоритм с временем работы 0(Р + п) был предложен в 1970 г. Джеймсом Моррисом и Воном Праттом [48]. Алгоритм Морриса и Пратта использует 0(Р) ячеек памяти. Идея алгоритма состоит в том, что в случае несовпадения букв образец можно сдвинуть вправо больше, чем на одну позицию (подробнее см. в [48, 34]). Алгоритм Морриса и Пратта сперва получает на вход образец Р и обрабатывает его, после чего для любого слова Т длины п алгоритм может вычислить все вхождения Р в Т за 0(п) времени.

С 1970 г. было разработано более 80 алгоритмов, решающих задачу о поиске образца в случае, когда образец известен заранее [26]. Классическими идеями алгоритмов решения задачи о поиске образца в этом случае являются применение сравнений букв, применение автоматов, применение операций над двоичными векторами и применение фильтрации.

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

Основными текстовыми индексами являются суффиксные деревья и суффиксные массивы. Здесь мы приводим неформальные определения суффиксных деревьев и массивов, формальные определения будут даны в главе 1. Понятие суффиксного дерева было предложено в 1973 г. Питером Вайнером [60]. Суффиксное дерево слова Т длины п — это дерево с занумерованными от 1 до п листьями, на ребрах которого написаны слова. Причем, если идти вдоль корня дерева до его листа с номером г и читать слова, написанные на ребрах, то мы прочтем в точности конкатенацию концевого отрезка (суффикса) слова Т, начинающегося в позиции г, и специальной буквы $, не встречающейся в Т. При условии, что суффиксное дерево для слова Т известно, задача о поиске образца может быть решена за 0(|Р| + output) времени, где output — количество вхождений Р в Т, что является оптимальным в общем случае. В то же время, объем памяти, занимаемый суффиксным деревом, довольно большой и зависит от размера алфавита.

Понятие суффискного массива было введено в 1990 г. Джином Майерсом и Уди Манбером [46]. Суффиксный массив слова Т длины п — это массив длины п, определяющий лексикографический порядок на множестве суффиксов слова Т. Объем памяти, занимаемый суффикс-ным массивом, не зависит от размера алфавита и меньше объема памяти, занимаемого суффиксным деревом. Поэтому, несмотря на то, что время вычисления вхождений Р в Т при использовании суффиксных массивов больше, чем время вычисления при использовании суффиксных деревьев, в некоторых ситуациях суффиксные массивы предпочтительнее. На рис. 1.1 приведены вычислительные сложности алгоритмов вычисления вхождений образца при помощи суффиксных деревьев и суффиксных массивов, где п — длина слова Т.

Индекс Память Время построения индекса Время вычисл. вхождений.

Суфф. дерево Суфф. массив О (п) 0(п) 0(п) [47, 24, 58, 60] 0{п) [38, 53] 0{Р + output) 0(|Р| + log 71 + output).

Рис. 1: Вычислительные сложности алгоритмов, вычисляющих все вхождения образца в текст.

Но и суффиксный массив не является оптимальным текстовым индексом. Заметим, что для хранения слова Т длины п над алфавитом? размера и достаточно всего 0(п log а) бит (в случае, когда слово хранится в сжатом виде, и того меньше), а для хранения суффиксного массива, как мы увидим далее, необходимо 0(пlogп) бит памяти. Так как память, используемая алгоритмами, по-прежнему является существенным ограничением для практических приложений, то в этом направлении ведутся активные исследования (см. обзор [49]).

В разделе 2.1 определяется новый текстовый индекс, основой которого выступает так называемое ?^-разреженное суффиксное дерево [39], где г — произвольно задаваемый параметр. В качестве вычислительной модели рассматривается РАМ-машина с размером ячейки памяти w. Доказывается, что указанный текстовый индекс занимает О (^) бит памяти и позволяет найти начальные позиции вхождений образца Р длины Р > г в текст Т длины п за время 0(Р • шах{1, + max{output, r] ¦ log п/ log log n)), где output — количество вхождений P в Т. В частности, при г = О (щ^) предложенный текстовый индекс занимает O (nlogcr) бит памяти (меньше, чем суффиксное дерево или суффиксный массив) и позволяет перечислить начальные позиции вхождений образца Р длины |Р| > г в текст Т длины п за время 0(Р + max (output, • log п/ log log п).

Рассмотрим теперь обобщение задачи о поиске образца. Пусть дано множество слов S = {Ti, T2,., Tm}. Задача состоит в построении текстового индекса для этого множества слов, используя который мы бы могли эффективно перечислить все вхождения образца Р в слово Т (G S или найти количество вхождений образца Р в слово Tg Е S.

Как мы уже говорили, первая подзадача может быть решена на суффиксном дереве для слова Тс за 0(Р + output) времени, для решения второй задачи потребуется 0(Р) времени.

В разделе 2.2 мы изучаем специальный случай задачи о поиске образца — задачу о перекрёстном поиске образца, когда образец является подсловом одного из слов ТЬТ2,., Тт. В этом случае можно предъявить решения определенных выше задач с памятью 0(п) и временем запроса либо не зависящим от длины образца, либо зависящим слабо (как двойной логарифм от длины). Мы также описываем динамический текстовый индекс, который можно эффективно изменять при добавлении слова в множество S.

Следующей задачей, которую мы рассматриваем в данной работе, является задача о вычислении разложения Лемпеля — Зива. Разложение Лемпеля — Зива слова Т — это разбиение Т = /½ • • • где подслово /?, 1 < г < z, является либо буквой, не встречавшейся до этого, либо самым длинным начальным отрезком слова fi.. fz, входящим в /½. /, — хотя бы дважды [18, 62]. Подслова /г называются факторами разложения Лемпеля — Зива.

Разложение Лемпеля — Зива имеет множество приложений, например, сжатие данных (разложение Лемпеля — Зива используется в таких архиваторах как gzip, WinZip, и PKZIP). Кроме того, разложение Лемпеля — Зива является основой нескольких алгоритмов [41, 35] и текстовых индексов [42]. Поэтому, разработка эффективных алгоритмов построения разложения Лемпеля — Зива является важной и актуальной задачей.

Пусть Т — слово длины п над алфавитом размера ст. Известно несколько алгоритмов, вычисляющих разложение Лемпеля — Зива с использованием O (nlogn) бит памяти. Основой этих алгоритмов служат суффиксные деревья [54], суффиксные автоматы [18] и суффиксные массивы [1, 14, 19, 20, 21, 52].

Тем не менее, известны только два алгоритма, использующие 0(пlogсг) бит памяти [51, 52]. Идеи алгоритмов похожи (в частности, оба алгоритма используют FM-индекс [28] и сжатый суффиксный массив). Алгоритм, предложенный Энно Охлебушем и Саймоном Гогом в 2011 г., предполагает, что слово Т известно заранее, время работы алгоритма составляет 0(п) [52].

Время работы алгоритма [51], разработанного Дайсуке Оканохара и Кунихико Садаканом в 2008 г., довольно большое, 0(пlog3 п). Его достоинство, по сравнению с алгоритмом Охлебуша и Го га, состоит в том, что он вычисляет разложение Лемпеля — Зива одновременно с чтением слова Т. Рассмотрим факторы /ь /г, • • •, /г разложения Лемпеля — Зива слова Т. Разложение Лемпеля — Зива слова Та, где, а — буква, содержит либо г, либо г+1 фактор: в первом случае это факторы /1- /2,., /г1, /г', где фактор Д = /гаа во втором случае — /ь /2,., /г, /г+ь где /г+1 = а. Алгоритм [51] читает Т слева направо и после прочтения каждой новой буквы обновляет разложение Лемпеля — Зива, т. е. или увеличивает длину последнего фактора на единицу, или добавляет новый фактор.

Для многих практических приложений, работающих с большими объемами данных, было бы естественно разрешить обновлять разложение Лемпеля — Зива не так часто, например, только после прочтения г > 1 букв, с целью уменьшения времени работы алгоритма. К сожалению, прямолинейное применение этой идеи к алгоритму [51] не позволяет получить более быстрый алгоритм.

В главе 3 мы предлагаем новый алгоритм с памятью О (n log <т) бит, который достигает разумного компромисса между временем работы и частотой обновления разложения Лемпеля — Зива. Алгоритм обновляет разложение Лемпеля — Зива слова Т каждые г = ^^ букв. Время работы алгоритма равно 0(n log2 п).

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

Последний класс задач, который мы рассматриваем в данной работе, связан с задачей вычисления наибольшего общего подслова множества слов. Наибольшее общее подслово двух слов Ti, T2 — это слово максимальной длины, являющееся и под словом слова Ti, и под словом слова TV Стандартным подходом к задаче вычисления наибольшего общего подслова двух слов является построение обобщенного суффиксного дерева слов Т и TV После того, как дерево построено, легко найти вершины, в поддеревьях которых встречаются и листья, соответствующие суффиксам Т, и листья, соответствующие суффиксам TV Среди этих вершин выбирается вершина с максимальной длиной слова, написанного вдоль пути от корня до данной вершины. Слово, написанное вдоль пути, является ответом на поставленную задачу. Более подробно этот алгоритм описан в главе 7.9 [34]).

В разделе 4.2 мы рассматриваем две задачи. Предположим, что дано множество слов S = {Ti, Т2,., Tm} суммарной длины п. Максимальным общим подсловом для заданного d будем называть слово W, входящее в, по меньшей мере, d различных слов множества S, такое, что любое слово Wa, где, а — произвольная буква алфавита, встречается в менее чем d словах множества S. Минимальные общие подслова для заданного d определяются аналогично: слово W называется минимальным общим подсловом для d и S, если W встречается не более, чем в d словах множества 5, а любой его начальный отрезок — в более чем d словах.

Предположим, что даны образец Р и число d < т. Первая задача состоит в вычислении максимальных общих под слов для.

В качестве примера рассмотрим слова Ti = ababa, Т2 = aabbba, Т3 = bbabcb. Максимальные общие подслова для d = 2 (и пустого образца Р) — это ab, bab и bba. Заметим, что ab входит в три слова, но каждое из слов aba, abb и abc входит только в одно слово. Минимальные общие подслова для P = bad = 2 — это bab и bb..

Решения определенных выше задач используют обобщенное суф-фиксное дерево для слов Ti, Т2,., Тт. Для первой из задач мы предлагаем решение с оптимальным временем работы 0(Р + output). Для второй задачи мы предлагаем решение со временем работы 0(Р + log log п + output), сводя задачу к известной задаче вычислительной геометрии. В каждой из оценок времени output обозначает количество слов, которые будут выданы алгоритмом. Алгоритмы не выписывают слова явно, так как это могло бы занять слишком много времени, а представляют их в некотором компактном виде, подробнее это описано в разделе 4.2..

До сих пор мы говорили о точных наибольших общих подсловах..

Определим ¿—неточное наибольшее общее подслово слов Т и Т2 как наибольшее по длине подслово слова Т, для которого существует подслово слова Т2, отличающееся от него в не более чем с? буквах. Существует несколько подходов к решению задачи о вычислении ¿—неточного наибольшего общего подслова двух слов, одним из которых является динамическое программирование. С его помощью можно построить алгоритм, использующий время и память, пропорциональные произведению длин слов Т и Т2 [34]..

В главе 4.1 описывается алгоритм для нахождения 1-неточного наибольшего общего подслова слов Т и Т2 с временем работы 0(|Тх| •.

Т2)..

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

Предположим, что длина Т2 существенно больше длины Т и что слово Т хранится в РАМ-памяти, а Т2 — на жестком диске. Если бы алгоритму требовалось много раз читать произвольную букву слова Т2, то время его работы на практике было бы очень большим..

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

Благодарности.

Автор выражает глубокую признательность своему научному руководителю академику РАН Алексею Львовичу Семёнову, академику РАН Сергею Ивановичу Адяну, к.ф.-м.н. Максиму Александровичу Бабенко, к.ф.-м.н. Андрею Альбертовичу Мучнику (1958 — 2007) за постановку задач и обсуждения работы. Автор благодарен всем сотрудникам кафедры математической логики и теории алгоритмов за творческую доброжелательную атмосферу..

Результаты работы неоднократно обсуждались на Колмогоров-ском семинаре по сложности вычислений и сложности определений под руководством д.ф.-м.н. Николая Константиновича Верещагина, к.ф.-м.н. Андрея Евгеньевича Ромащенко, академика РАН Алексея Львовича Семёнова, к.ф.-м.н. Александра Ханьевича Шеня, на семинаре «Алгоритмические вопросы алгебры и логики» под руководством академика РАН Сергея Ивановича Адяна, а также на семинаре «Комбинаторная оптимизация и теория алгоритмов» под руководством к.ф.-м.н. Максима Александровича Бабенко. Автор благодарен руководителям и участникам этих семинаров за поддержку и внимание к работе..

1. М. 1. Abouelhoda, S. Kurtz, E. Ohlebusch. Replacing suffix trees with enhanced suffix arrays.. J. of Discrete Algorithms, Vol. 2, № 1. Amsterdam, The Netherlands: Elsevier Science Publishers В. V., 2004. — P. 53−86..

2. A.V. Aho, J.E. Hopcroft, J. Ullman. Data structures and algorithms. Reading, Mass.: Addison-Wesley, 1983.A.B. Ахо, Альфред, Дж. Хопкрофт, Дж. Д. Ульман. Структуры данных и алгоритмы М.: «Вильяме», 2000..

3. A. Amihood, G.M. Landau, М. Lewenstein, D. Sokol. Dynamic text and static pattern matching. ACM Trans. Algorithms, Vol. 3, № 2, 2007..

4. M.A. Bender, M. Farach-Colton. The level ancestor problem simplified. Theor. Comput. Sei., Vol. 321, № 1. Essex, UK: Elsevier Science Publishers Ltd., 2004. P. 5−12..

5. J. L. Bentley. Multidimensional divide-and-conquer. Commun. ACM, Vol. 23, № 4, 1980. P. 214−229.9. 0. Berkman, U. Vishkin. Finding level-ancestors in trees. J. Comput. Syst. Sei., Vol. 48, № 2. Orlando, FL, USA: Academic Press, Inc., 1994. P. 214−230..

6. T.M. Chan. Persistent predecessor search and orthogonal point location on the word RAM. Proceedings of the 22nd ACM-SIAM Symposium on Discrete Algorithms. Philadelphia, PA, USA: Society for Industrial and Applied Mathematics, 2011. P. 1131−1145..

7. T.M. Chan, K.G. Larsen, M. Patra§ cu. Orthogonal range searching on the RAM, revisited. Proceedings of the 27th annual ACM symposium on Computational geometry, ed. by F. Hurtado, M. van Kreveld. New York, NY, USA: ACM, 2011. — P. 1−10..

8. G. Chen, S.J. Puglisi, W.F. Smyth. Lempel-Ziv factorization using less time & space. Mathematics in Computer Science, Vol. 1, № 4. Birkhauser Basel, 2008. P. 605−623..

9. S.-Y. Chiu, W.-K. Hon, R. Shah, J.S. Vitter. Geometric Burrows-Wheeler transform: linking range searching and text indexing. Proceedings of the 18th Data Compression Conference. New York, NY: IEEE Computer Society, 2008. P. 252−261..

10. S.-Y. Chiu, W. Hon, R. Shah, J.S. Vitter. I/O-Efficient Compressed Text Indexes: From Theory to Practice. Proceedings of the 20th Data Compression Conference, ed. by J.A. Storer, M.W. Marcellin. New York, NY: IEEE Computer Society, 2010. P. 426−434..

11. M. Crochemore. Transducers and repetitions. Theor. Comput. Sei., Vol. 45, № 1. Essex, UK: Elsevier Science Publishers Ltd., 1986. -P. 63−68..

12. M. Crochemore, L. Ilie. Computing longest previous factor in linear time and applications. Inf. Process. Lett., Vol. 106, № 2. Amsterdam, The Netherlands: Elsevier North-Holland, Inc., 2008. P. 75−80..

13. M. Crochemore, L. Ilie, W.F. Smyth. A simple algorithm for computing the Lempel-Ziv factorization. Proceedings of the 18th Data Compression Conference. New York, NY: IEEE Computer Society, 2008. P. 482 488..

14. M. Crochemore, W. Rytter. Jewels of stringology. River Edge, NJ, USA: World Scientific Publishing Co. Inc., 2003..

15. P. Dietz, D. Sleator. Two algorithms for maintaining order in a list. Proceedings of the 19th Annual ACM Symposium on Theory of Computing, ed. by A.V. Aho. New York, NY, USA: ACM, 1987. P. 365−372..

16. M. Farach. Optimal suffix tree construction with large alphabets. Proceedings of the 38th Annual Symposium on Foundations of Computer Science. New York, NY: IEEE Computer Society, 1997. P. 137−143..

17. S. Faro, T. Lecroq. The exact string matching problem: a comprehensive experimental evaluation. Computing Research Repository, 2010..

18. P. Ferragina, J. Fischer. Suffix arrays on words. Proceedings of the 18th Annual Symposium on Combinatorial Pattern Matching, ed. by B. Ma, K. Zhang. Lecture Notes in Computer Science, Vol. 4580. Berlin etc.: Springer, 2007. P. 328−339..

19. P. Ferragina, G. Manzini. Opportunistic Data Structures with Applications. Proceedings of the Slrd Annual Symposium on Foundations of Computer Science. New York, NY: IEEE Computer Society, 2000, P. 390−398..

20. P. Ferragina, G. Manzini, V. Makinen, N. Gonzalo. Compressed representations of sequences and full-text indexes. ACM Transactions on Algorithms, Vol. 3, № 2. New York, NY, USA: ACM, 2007..

21. M.L. Fredman, D.E. Willard. Surpassing the information theoretic bound with fusion trees. Journal of Computer and System Sciences, Vol. 47. Orlando, FL, USA: Academic Press, Inc., 1993. P. 424−436..

22. A. Golynski, J. I. Munro, S. S. Rao. Rank/select operations on large alphabets: a tool for text indexing. Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms. New York, NY, USA: ACM, 2006. P. 368−373..

23. D. Gusfield. Algorithms on strings, trees, and sequences: computer science and computational biology. New York, NY, USA: Cambridge University Press, 1997. Строки, деревья и последовательности в алгоритмах. Санкт-Петербург: «Невский диалект», 2003..

24. D. Gusfield, J. Stoye. Linear time algorithms for finding and representing all the tandem repeats in a string. J. Comput. Syst. Sci., Vol. 69, № 4. Orlando, FL, USA: Academic Press, Inc., 2004. P. 525−546..

25. W.-K. Hon, R. Shah, J. Vitter. Ordered Pattern Matching: Towards Full-Text Retrieval. Technical report № 06−008. Purdue University, 2006..

26. J. Karkkainen, E. Ukkonen. Sparse suffix trees. Proceedings of the 2nd Annual International Computing and Combinatorics Conference, ed. by J.-Y. Cai, C. K. Wong. Lecture Notes in Computer Science, Vol. 1090. Berlin etc.: Springer, 1996. P. 219−230..

27. R. Kolpakov, G. Kucherov. Finding maximal repetitions in a word in linear time. Proceedings of the 40th Symposium on Foundations of Computer Science. New York, NY: IEEE Computer Society, 1999. — P. 596−604..

28. S. Kreft, G. Navarro. Self-indexing based on LZ77. Proceedings of the 22nd annual conference on Combinatorial Pattern Matching, ed. by R. Giancarlo, G. Manzini. Lecture Notes in Computer Science, Vol. 6661. Berlin etc.: Springer, 2011. — P. 41−54..

29. V. Makinen, G. Navarro. Dynamic entropy-compressed sequences and full-text indexes. ACM Trans. Algorithms, Vol. 4, № 3. New York, NY, USA: ACM, 2008. P. 32:1−32:38..

30. V. Makinen, G. Navarro, Gonzalo. Position-restricted substring searching. Proceedings of the 7th Latin American Symposium, ed. by J.R. Correa, A. Hevia, M.A. Kiwi. Lecture Notes in Computer Science, Vol. 3887. Berlin etc.: Springer, 2006. P. 703−714..

31. E.M. McCreight. A space-economical suffix tree construction algorithm. J. ACM, Vol. 23, № 2. New York, NY, USA: ACM, 1976. P. 262−272..

32. J. H. Morris, V. R. Pratt. A linear pattern-matching algorithm. Technical report 40. University of California, Berkley, 1970..

33. G. Navarro, V. Makinen. Compressed full-text indexes. ACM Comput. Surv., Vol. 39, № 1. New York, NY, USA: ACM, 2007..

34. Y. Nekrich. Orthogonal range searching in linear and almost-linear space. Comput. Geom. Theory Appl, Vol. 42, № 4. Essex, UK: Elsevier Science Publishers B. V., 2009. P. 342−351..

35. S.J. Puglisi, W.F. Smyth, A.H. Turpin. A taxonomy of suffix array construction algorithms. ACM Comput. Surv., Vol. 39, № 2. New York, NY, USA: ACM, 2007..

36. M. Rodeh, V.R. Pratt, S. Even. Linear algorithm for data compression via string matching. J. ACM, Vol. 28, № 1. New York, NY, USA: ACM, 1981. P. 16−24..

37. B. Schieber, U. Vishkin. On finding lowest common ancestors: simplification and parallelization. SI AM Journal on Computing, Vol. 17, № 6, 1988. P. 111−123..

38. W. F. Smyth. Computing patterns in strings. ACM Press Bks. UK: Pearson/Addison-Wesley, 2003..

39. E. Ukkonen. Constructing suffix trees on-line in linear time. Proceedings of the 12th World Computer Congress on Algorithms, Vol. 1. Amsterdam, The Netherlands: North-Holland Publishing Co., 1992. — P. 484−492..

40. E. Ukkonen. On-line construction of suffix trees. Algorithmica, Vol. 14, № 14. New York, NY, USA: Springer New York, 1995. P. 249−260..

41. P. Weiner. Linear pattern matching algorithms. Proceedings of the 14th Annual Symposium on Foundations of Computer Science. New York, NY: IEEE Computer Society, 1973. P. 1−11..

42. J. Ziv, A. Lempel. A universal algorithm for sequential data compression. Transactions on Information Theory, Vol. 23, № 3. New York, NY: IEEE Computer Society Press, 1977. P. 337−343.Работы автора по теме диссертации.

43. М. А. Бабенко. Т. А. Стариковская. Вычисление длиннейшей общей подстроки с одной ошибкой. Пробл. передачи информ., Том 47, № 1 (2011), 33−39..