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

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ имени М. В. ЛОМОНОСОВА

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

Стариковская Татьяна Андреевна

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

Специальность 01.01.06 — математическая логика, алгебра и теория чисел

/1

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

005051П о

Москва 2013

005051718

Работа выполнена на кафедре математической логики и теории алгоритмов Механико-математического факультета Московского государственного университета имени М. В. Ломоносова.

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

Семёнов Алексей Львович

Официальные оппоненты: Ройтберг Михаил Абрамович,

доктор физико-математических наук (Институт математических проблем биологии РАН, зав. лабораторией прикладной математики)

Горбунов Константин Юрьевич, кандидат физико-математических наук (Институт проблем передачи информации имени A.A. Харкевича РАН, старший научный сотрудник)

Ведущая организация: ФГБОУ ВПО «Санкт-Петербургский

государственный университет»

Защита диссертации состоится 22 марта 2013 г. в 16 часов 45 минут на заседании диссертационного совета Д 501.001.84 при Московском государственном университете имени М. В. Ломоносова по адресу: Российская Федерация, 119991, Москва, ГСП-1, Ленинские горы, д. 1, МГУ имени М. В. Ломоносова, Механико-математический факультет, аудитория 14-08.

С диссертацией можно ознакомиться в Фундаментальной библиотеке Московского государственного университета имени М. В. Ломоносова (Ломоносовский проспект 27, сектор А, 8-й этаж).

Автореферат разослан 22 февраля 2013 года.

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

профессор

Иванов Александр Олегович

Общая характеристика работы

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

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

Первый алгоритм с временем работы 0{\Р\ + п) был предложен в 1970 г. Джеймсом Моррисом и Боном Праттом1. Алгоритм Морриса и Пратта использует 0(|Р|) ячеек памяти. Алгоритм Морриса и Пратта сперва получает на вход образец Р и обрабатывает его, после чего для любого слова Т длины п алгоритм может вычислить все вхождения Р в Т за О(п) времени.

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

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

Основными текстовыми индексами являются суффиксные деревья, определенные Питером Вайнером в 1973 г.3, и суффиксные массивы, определение которых дали Джин Майерс и Уди Манбер в 1990 г.4. На рис. 1

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

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

3P. 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.

4U. Manber, G. Myers. Suffix arrays: a new method for on-line string searches. Proceedings 0} the 1st ACM-S1AM Symposium on Discrete algorithms, ed. by D.S. Johnson.

Индекс Память Время построения Время работы

Суфф. дерево Суфф. массив 0(п) 0(п) 0{п)л 5 и 7 0{п)8 9 0{\Р\ + output) 0(|Р| -t- logn + output)

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

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

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

В диссертации вводится новый текстовый индекс, основой которого выступает так называемое r-разреженное суффиксное дерево11, где г — произвольно задаваемый параметр. В качестве вычислительной модели рассматривается РАМ-машина с размером ячейки памяти w. Доказывается, что в этой модели вычислений указанный текстовый индекс занимает 0(бит памяти и позволяет найти начальные пози-

Philadelphia, PA, USA: Society for Industrial and Applied Mathematics, 1990. — P. 319327.

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

6M. 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.

7E. 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.

8J. Karkkainen, P. Sanders. Simple linear work suffix array construction. Proceedings of the 30th International Colloquium on Automata, Languages and Programming, ed. by J.C.M. Baeten, J.K. Lenstra, J. Parrow. G.J. Woeginger. Lecture Notes in Computer Science, Vol. 2719. Berlin etc.: Spring«-, 2003. — P. 943-955.

9S.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.

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

11 J. Karkkainen, E. Ukkonen. Sparse suffix trees. Proceedings of the 2nd Annual

International Computing and Combinatorics Conference, ed. by J.-Y. Cai, С. K. Wong.

Lecture Notes in Computer Science, Vol. 1090. Berlin etc.: Springer, 1996. — P. 219-230.

ции вхождений образца Р длины |Р| > г в текст Т длины п за время 0(|Р| ■ тах{1, + таx{output, г} • log п/ log log п), где output — коли-

чество вхождений Р в Т. В частности, при г = предложенный

текстовый индекс занимает 0(тьloger) бит памяти (меньше, чем суффикс-ное дерево или суффиксный массив) и позволяет перечислить начальные позиции вхождений образца Р длины |Р| > г в текст Т длины п за время 0(|Р| + max{output, j^} • log п/ log log n).

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

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

В диссертации изучается специальный случай этой задачи — задача

0 перекрестном поиске образца, когда образец является подсловом одного из слов Ti,T2,... ,Tm. В этом случае для определенной выше задачи можно предъявить решение с линейной памятью и временем запроса либо не зависящим от длины образца, либо зависящим слабо (как двойной логарифм от длины). Также в диссертации описывается динамический текстовый индекс для указанной задачи, который можно эффективно изменять при добавлении слова в множество S.

Следующей задачей, которая рассматривается в данной работе, является задача о вычислении разложения Лемпеля — Зива. Разложение Лемпеля — Зива слова Т — это разбиение Т — Д/2 ... /г, где подслово /¡,

1 < г < z, является либо буквой, не встречавшейся до этого, либо самым длинным начальным отрезком слова fi... fzi входящим в /1/2 ... /< хотя бы дважды. Подслова /,: называются факторами разложения Лемпеля -----Зива14 15.

Разложение Лемпеля — Зива имеет множество приложений, например, сжатие данных (разложение Лемпеля — Зива используется в таких архиваторах как gzip, WinZip, и PKZIP). Кроме того, разложение Лемпеля —

14М. Crochemore. Transducers and repetitions. Theor. Comput. Sci., Vol. 45, № 1. Essex, UK: Elsevier Science Publishers Ltd., 1986. — P. 63-68.

15 J. Ziv, A. Lempel. A universal algorithm for sequential data compression. Transactions on Information Theory, Vol. 23, N2 3. New York, NY: IEEE Computer Society Press, 1977. — P. 337-343.

Зива является основой нескольких алгоритмов16 17 и текстовых индексов. Поэтому, разработка эффективных алгоритмов построения разложения Лсмпеля — Зива является важной и актуальной задачей.

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

23 24

Тем не менее, известны только два алгоритма, использующие 0(п log а) бит памяти25 26. Идеи алгоритмов похожи (в частности, оба алгоритма используют FM-индекс27 и сжатый суффиксный массив). Ал-

16R. 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.

17D. 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.

18M. 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.

19M. I. 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.

20G. 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.

21M. 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.

22M. Crochemore, L. Ilie, C.S. Iliopoulos, M. Kubica, W. Rytter, T. Walen. LPF computation revisited. Proceedings of the 2nd International Workshop on Combinatorial Algorithms, ed. by J. Fiala, J. Kratochvil, M. Miller. Lecture Notes in Computer Science, Vol. 5874. Berlin etc.: Springer, 2009. — P. 158-169.

23M. 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.

24E. Ohlebusch, S. Gog. Lempel — Ziv factorization revisited. 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. 15-26.

25D. Okanohara, K. Sadakane, Kunihiko. An online algorithm for finding the longest previous factors. Proceedings of the 16th Annual European Symposium on Algorithms, ed. by D. Halperin, K. Mehlhorn. Lecture Notes in Computer Science, Vol. 5193. Berlin etc.: Springer, 2008. — P. 696-707.

26E. Ohlebusch, S. Gog. Lempel-Ziv factorization revisited. 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. 15-26.

27P. Ferragina, G. Manzini. Opportunistic Data Structures with Applications. Proceedings of the 31rd Annual Symposium, on Foundations of Computer Science. New York, NY: IEEE Computer Society, 2000, — P. 390-398.

горитм, предложенный Энно Охлебушем и Саймоном Гогом в 2011 г., предполагает, что слово Т известно заранее, время его работы составляет 0(п)26.

Время работы алгоритма25, разработанного Дайсуке Оканохара и Ку-нихико Садаканом в 2008 г., довольно большое, 0(nlog3 п). Его достоинство по сравнению с алгоритмом26 состоит в том, что он вычисляет разложение Лемпеля — Зива онлайн, т.е. одновременно с чтением слова Т. Рассмотрим факторы Д, /2,..., Д разложения Лсмпсля — Зива слова Т. Разложение Лемпеля — Зива слова Та, где а — буква, содержит либо г, либо i + 1 фактор: в первом случае это факторы Д, Д,..., /¿-1, Д-, где фактор /■ = Да; a во втором случае — Д, Д,..., Д, Д+ь где Д+i = а. Алгоритм25 читает Т слева направо и после прочтения каждой новой буквы обновляет разложение Лемпеля — Зива, т.е. или увеличивает длину последнего фактора на единицу, или добавляет новый фактор.

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

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

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

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

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

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

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

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

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

Цель работы. Построение текстового индекса на основе разреженного суффиксного дерева. Построение эффективного алгоритма для различных вариантов задачи о перекрестном поиске образца. Разработка онлайн алгоритма построения разложения Лемпеля-Зива, использующего линейную память. Исследование задачи об 1-неточном наибольшем общем подслове. Построение эффективных алгоритмов для решения задачи о максимальных и минимальных общих подсловах для заданного d.

Научная новизна. Результаты диссертации являются новыми и получены автором диссертации самостоятельно. Основные результаты диссертации состоят в следующем:

1. Определен новый текстовый индекс, на основе которого разработан эффективный по памяти алгоритм поиска вхождений образца в слово.

2. Разработан эффективный алгоритм решения задачи о перекрестном поиске образца.

3. Разработан новый алгоритм вычисления разложения Лемпеля — Зи-ва, вычисляющий разложение почти одновременно с чтением слова и использующий небольшой объем памяти.

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

5. Сформулированы задачи о максимальных и минимальных общих подсловах для заданного d и предложены эффективные алгоритмы их решения.

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

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

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

• на международной конференции «Сжатие, передача и обработка данных» (Compression, Communications and Processing 2011), Пали-нуро, Италия, 21—24 июня 2011 года;

• на международной конференции «Комбинаторные алгоритмы для решения задачи о поиске образца» (Combinatorial Pattern Matching 2012), Хельсинки, Финляндия, 3—5 июля 2012 года;

• на международной конференции «Математические основы информатики» (Mathematical Foundations of Computer Science 2012), Братислава, Словакия, 27—31 августа 2012 года;

• на международной конференции «Обработка слов и информационный поиск» (String Processing and Information Retrieval 2012), Картахена, Колумбия, 21—25 октября 2012 года;

• в 2011 г. на семинаре «Алгоритмические вопросы алгебры и логики» под руководством академика РАН С.И. Адяна, Москва, Россия;

• в 2008—2011 гг. на Колмогоровском семинаре по сложности вычислений и сложности определений под руководством д.ф.-м.н. Н.К. Верещагина, к.ф.-м.н. А.Е. Ромащенко, академика РАН А.Л. Семёнова, к.ф.-м.н. А.Х. Шеня, Москва, Россия;

• в 2011—2012 гг. на семинаре «Комбинаторная оптимизация и теория алгоритмов» под руководством к.ф.-м.н. М.А. Бабенко, Москва, Россия.

Публикации. Основные результаты диссертации опубликованы в пяти работах [1]—[5], из них пять — в периодических изданиях из перечня ВАК.

Структура диссертации. Работа состоит из введения, четырех глав, содержащих 22 раздела, и списка литературы. Библиография содержит 67 наименований. Текст диссертации изложен на 94 страницах.

Содержание работы

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

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

Буквы слова Т длины п обозначаются через Т[1],Т[2],... ,Т[п]. Под-слово слова Т, начинающееся в позиции г и заканчивающееся в позиции ] (включая позиции г и ]) обозначается через Т[г..^']. Индексы, равные 1 или п, опускаются. Слово Т\..]] называется префиксом слова Т, а слово Т[г..] — суффиксом слова Т.

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

1) существует число 1 < г < гшп{|Т1|, |Т2|} такое, что Тх[1..г] = Т2[1..г], аТ^г-Ы] <Т2[г + 1],

2) Т\ является префиксом Тг.

В разделе 1.2 дается определение суффиксного дерева1. Суффиксное дерево слова Т длины п — это ориентированное дерево с корнем, имеющее ровно п листьев, занумерованных от 1 до п. Каждая внутренняя вершина, отличная от корня, имеет не менее двух детей, а каждое ребро помечено непустым подсловом слова Т$, где $ — буква, не входящая в слово Т. Никакие два ребра, выходящих из одной и той же вершины, не могут иметь меток, начинающихся с одного и того же символа. Наконец, если идти вдоль пути от корня до листа с номером г и читать метки вслух, то будет произнесен в точности суффикс Т[г..]$ слова Т$. В разделе 1.2.1 объясняется, как решать задачу о поиске образца с помощью суффиксного дерева. В разделе 1.2.2 перечисляются основные алгоритмы построения суффиксного дерева и приводится описание алгоритма Укконена построения суффиксного дерева.

В разделе 1.3 дается определение суффиксного массива. Пусть Т — произвольное слово длины п. Рассмотрим его суффиксы Т[1..],Т[2..],... ,Т[п] и упорядочим их лексикографически. Суффикс-ный массив 5/1 слова Т — это массив длины п, в ячейке £>А[г] которого записана начальная позиция г-ого в лексикографическом порядке суффикса слова Г, 1 < г < п. Очевидно, Б А однозначно определяется по Т.

В разделе 1.4 объясняется, как понятия суффиксного дерева и суффиксного массива обобщаются на случай множества слов.

Глава 2 посвящена задаче о поиске образца. В разделе 2.1.1 описывается новый текстовый индекс. Основой текстового индекса выступает так называемое г-разреженпое суффиксное дерево. Фиксируем произвольное число г и разобьем слово Т длины п на блоки по г букв. Будем хранить в суффиксном дереве только те суффиксы, которые начинаются на границах блоков. В этом случае у суффиксного дерева будет не более п/г листьев, и, тем самым, 0(п/г) вершин. Такое определение г-разреженного суффиксного дерева впервые было рассмотрено в работе11.

г-разреженное суффиксное дерево позволяет легко находить вхождения образца, начинающиеся на границах блоков. Рассмотрим образец Р, где |-Р| > г. Для того, чтобы найти вхождения Р вТ, используется следующая идея. Сперва при помощи суффиксного дерева вычисляются вхождения суффиксов -Р[1..], Р[2..],..., Р[г..), начинающиеся на границах блоков в Т. Затем вычисляются вхождения Р[1..&], к — 1 ..г — 1, заканчивающиеся на границах блоков. Наконец, вычисляются границы блоков, которые являются одновременно последней позицией вхождения Р[1../с]

и первой позицией вхождения Р[к + 1..] для одного и того же к. Очевидно, эти границы соответствуют вхождениям Р в Т. В разделе 2.1.2 приводится подробное описание этого алгоритма и доказывается Теорема 3. Поиск всех вхождений образца Р длины \Р\ > г в слово Т требует 0(\Р\ ■ max{l, rloJa } + таx{output,r} • log п/ log log п) времени и 0(;г) памяти, где output — количество вхождений.

В разделе 2.1.3 описывается алгоритм построения г-разреженного суффиксного дерева, а также доказывается верхняя оценка на время его работы.

Теорема 4. r-разреженное суффиксное дерево для слова Т длины п может. быть построено за 0(пг) времени при использовании О(^) памяти.

В разделе 2.2 изучается задача о перекрестном поиске образца. В разделе 2.2.1 приводится постановка задачи о взвешенных предках, которая используется далее для построения эффективных алгоритмов. В разделе 2.2.2 доказываются

Теорема 5. Пусть дано множество слов S = {Т\,Тъ,... ,Тт} суммарной длины п. Для любых 1 < k,Z < т и 1 < г < j < \Tk\, количество вхождений Т^ [г.-j] в Те может быть вычислено 3aO(t + log log ттг) времени, где t = min{ л/log output/ log log output, log log(j - г +1)}, a output обозначает количество вхождений. Структуры данных, которые используются алгоритмом, занимают 0(п) памяти и могут быть построены за 0(п) времени.

Теорема 6. Пусть дано множество слов S = {Т\, ... ,Тт} суммарной длины п. Все вхождения Tk[i..j] в Т( могут быть перечислены за 0(loglogm + output) времени, где output — количество вхоокдений. Используемая структура данных занимает 0(п) памяти и может быть построена за 0(п) времени.

В разделе 2.2.3 описывается динамический текстовый индекс для задачи о перекрестном поиске образца. А именно, доказывается следующая теорема:

Теорема 7. Пусть дано множество слов S — {Т\, Г2, ■ • •, Тт} суммарной длины п. Существует динамическая структура данных, позволяющая вычислять количество вхождений Tk[i..j] в Тg за O(logn) времени, а перечислять вхождения — за 0(logn + output) времени, где output — количество вхождений. Эта структура данных занимает 0(п) памяти. Время ее обновления при добавлении нового слова в множество S составляет O(logn) на букву.

В Главе 3 изучается задача построения разложения Лемпеля — Зива слова Т над алфавитом размера а. Разложение Лемпеля — Зива слова Т — это разбиение Т = /1/2 • • ■ где подслово 1 < i < z, является либо буквой, не встречавшейся до этого, либо самым длинным префиксом fi - ■■ fz, входящим в /1/2 ... fi хотя бы дважды14 15. Подслова fi называются факторами разложения Лемпеля — Зива. Предъявленный алгоритм вычисляет разложение Лемпеля — Зива одновременно с чтением слова Т. А именно, он читает Т слева направо и после прочтения очередных log^n букв обновляет разложение Лемпеля — Зива.

В разделе 3.1 дается описание используемых структур данных и алгоритма. В разделе 3.2 объясняются детали реализации структур данных. В разделе 3.3 доказываются оценки времени работы алгоритма и объема используемой им памяти:

Теорема 9. Предъявленный алгоритм вычисляет разложение Лемпеля — Зива слова Т длины п за 0(п log2 п) времени, используя при этом О(пloger) бит памяти.

Глава 4 посвящена задачам об общих подсловах множества слов. Определим d-неточное наибольшее общее подслово слов Т\ и Т2 как наибольшее по длине подслово слова Т\, для которого существует подслово слова Х2, отличающееся от него в не более чем d буквах. В разделе 4.1 рассматривается задача о вычислении 1-неточного наибольшего общего подслова слов Т\ и Т2. Доказывается следующая теорема:

Теорема 10. 1 -неточное наибольшее общее подслово слов Т\ и Т2 длин щ и 712 соответственно (П2 > п\) может быть вычислено за вр&ия 0(n\ri2) при использовании 0(ni) памяти (не считая памяти, требуемой для хранения самих слов). Алгоритм читает слово Т2 только слева направо, начиная с первой буквы.

Пусть W\ — 1-неточное наибольшее общее подслово Tj и Г2, a W2 — подслово Т2, которое отличается от в не более чем одной букве. Обозначим совпадающие части слов W\ и W2 через W и W". Пусть позиции несовпадающих букв в словах W\ и Wj- это позиция г в Т\ и позиция j в Т2 ■ Очевидно, W' — наибольший общий суффикс префиксов слов Ti [. Л -1] и T2[..j -1], a W" — наибольший общий префикс суффиксов слов [г + 1..] и Т2Ц +1..]. В разделе 4.1.2 описывается процедура, вычисляющая наибольшие общие префиксы слова Ti[i..] и слов Т2[j..], j = 1,2,. ..,пг. В разделе 4.1.3 описывается процедура, вычисляющая наибольшие общие суффиксы слова Гх[г..] и слов T2[j..}, j = 1,2,... ,тг2. В разделе 4.1.1 объясняется, как указанные процедуры используются для вычисления W\.

Раздел 4.2 посвящен задаче о минимальных и максимальных общих

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

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

Теорема 11. Пусть дано множество слов S — {Т1; Т2,..., Тт} суммарной длины п. Для любого образца Р и числа d, максимальные общие подслова для d, являющиеся расширениями образца Р вправо, могут быть перечислены за 0(|Р| + output) времени, где output — количество таких продолжений. Используемые структуры данных занимают 0(п) памяти и могут быть построены за 0(п) времени, где п — суммарная длина слов в множестве S.

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

Теорема 12. Пусть дано множество слов S = {Т\, Т2,... ,Тт} суммарной длины п. Для любого образца Р и числа d, минимальные общие подслова для d, являющиеся расширениями образца Р вправо, могут быть перечислены за 0{\Р\ + log log п + output) времени. Используемая структура данных занимает 0(п) памяти и может быть построена за O(nlogn) времени.

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

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

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

[2] R. Kolpakov, G. Kucherov, Т. Starikovskaya. Pattern Matching on Sparse Suffix Trees. Proceedings of the 1st International Conference on Data Compression, Communications and Processing. New York, NY: IEEE Computer Society Press, 2011. — P. 92-97.

[3] G. Kucherov, Y. Nekrich, T. Starikovskaya. Computing discriminating and generic subwords. Proceedings of the 19th International Symposium on String Processing and Information Retrieval, ed. by E. Ch&vez, N. Ziviani. Lecture Notes in Computer Science, Vol. 7608. Berlin etc.: Springer, 2012. - P. 307-317.

[4] G. Kucherov, Y. Nekrich, T. Starikovskaya. Cross-document pattern matching. Proceedings of the 23rd Symposium on Combinatorial Pattern Matching, ed. by J. Karkkainen, J. Stoye. Lecture Notes in Computer Science, Vol. 7354. Berlin etc.: Springer, 2012. — P. 196-207.

[5] T.A. Starikovskaya. Computing Lempel-Ziv factorization online. Proceedings of the 37th International Symposium on Mathematical Foundations of Computer Science, ed. by V. Sassone, P. Widmayer. Lecture Notes in Computer Science, Vol. 7464. Berlin etc.: Springer, 2012. - P. 789-799.

В [1] M.A. Бабенко принадлежит постановка задачи, автору диссертации принадлежат описание алгоритма и доказательство оценок времени работы и используемой памяти.

В [2] автору принадлежат описания и доказательства оценок сложности для процедуры LeftSearch и алгоритма построения разреженного суффиксного дерева.

В работе [3] автору принадлежат доказательства теорем 1 и 2.

В совместной работе [4] автору диссертации принадлежит постановка задачи, а также теоремы 2, 3 и 4.

Отпечатано в отделе оперативной печати Геологического ф-та МГУ Тираж ¡ООэкз. Заказ № к

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ имени М. В. ЛОМОНОСОВА МЕХАНИКО-МАТЕМАТИЧЕСКИЙ ФАКУЛЬТЕТ

04201357126 На правах РУК0ИИСИ

УДК 510.52

Стариковская Татьяна Андреевна

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

Специальность 01.01.06 — математическая логика, алгебра

и теория чисел

ДИССЕРТАЦИЯ на соискание ученой степени кандидата физико-математических наук

Научный руководитель: академик РАН.

профессор Семёнов Алексей Львович

МОСКВА - 2012

Оглавление

Введение 4

1 Основные понятия и структуры данных 15

1.1 Понятия алфавита и слова....................................15

1.2 Суффиксное дерево ............................................16

1.2.1 Приложение: задача о поиске образца................18

1.2.2 Построение суффиксного дерева......................19

1.3 Суффиксный массив............................................23

1.4 Обобщенные суффиксные деревья и массивы................26

2 Поиск вхождений образца 28

2.1 Поиск вхождений образца с помощью разреженного суффиксного дерева................................................28

2.1.1 Разреженное суффиксное дерево......................30

2.1.2 Алгоритм................................................32

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

2.2 Перекрёстный поиск образца..................................44

2.2.1 Задача о взвешенных предках..........................44

2.2.2 Задача о перекрёстном поиске образца................45

2.2.3 Динамические структуры данных ....................48

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

3.1 Алгоритм........................................................55

3.1.1 Структуры данных......................................55

3.1.2 Процедура Р<г..........................................57

3.1.3 Процедура Р>г..........................................58

3.2 Детали реализации..............................................63

3.2.1 Бор........................................................63

3.2.2 Суффиксное дерево ....................................64

3.3 Оценки времени работы и объема памяти....................69

4 Общие подслова 71

4.1 1-неточное наибольшее общее подслово......................71

4.1.1 Общее описание алгоритма............................72

4.1.2 Вычисление наибольших общих префиксов..........75

4.1.3 Вычисление наибольших общих суффиксов..........76

4.2 Максимальные и минимальные общие подслова ............80

4.2.1 Максимальные общие подслова для заданного с1 . . 81

4.2.2 Минимальные общие подслова для заданного с£ . . . 84

Литература 86

Введение

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

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

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

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

Первая модель вычислений, которая будет использоваться по умолчанию, — это равнодоступная адресная машина, сокращенно РАМ (см. [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/2 • • • где подслово /¿, 1 < г < z, является либо буквой, не встречавшейся до этого, либо самым длинным начальным отрезком слова fi.. . fz, входящим в /1/2 ... /,; хотя

бы дважды [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 встреча