Декомпозиция Линдона
Декомпозиция Линдона была изобретена Роджером Линдоном (англ. Roger Lyndon) в 1954 году. Она используется для нахождения лексикографически минимального и максимального суффиксов строки, а также лексикографически минимального циклического сдвига.
Основные определения
Определение: |
Простая строка — строка, которая лексикографически меньше любого своего суффикса. |
Примеры:
— простая строка, так как , , , .
— не простая строка, так как .
Определение: |
Декомпозиция Линдона (англ. Lyndon decomposition) строки | — её разложение , где строки просты, и при этом .
Существование и единственность
Лемма: |
1. 2. — простая |
Доказательство: |
1. Так как , то и ,2. Пусть — суффикс строки . Тогда рассмотрим 3 возможных случая:
|
Теорема (Чен-Линдон-Фокс): |
Можно построить декомпозицию Линдона любой строки , причем единственным образом. |
Доказательство: |
1. Существование. У каждой строки существует хотя бы одно разбиение на простые слова. Это следует из того, что отдельный символ является простым словом. Тогда среди всех разбиений строки на простые слова возьмём то, в котором меньше всего слов. Покажем, что это и будет декомпозицией Линдона данной строки. Предположим, что это не так. Значит, леммы следует, что эти слова можно сконкатенировать и получить разбиение строки на меньшее число слов. Получили противоречие. . Так как слова и простые, то из доказаннойТаким образом доказали даже более сильное утверждение: , — минимально нет2. Единственность. Пусть существует несколько разбиений , удовлетворяющих условию теоремы. Сравним длины первых двух слов и , если , сравним вторые и так далее. Если длины всех слов одинаковы, то разбиения совпадают — противоречие. Иначе .Покажем, что такого не может быть: 1) Пусть , тогда , где — префикс , . Тогда получаем:
Пришли к противоречию: .2) Случай То есть не может быть строк симметричен разобранному. и несовпадающей длины, значит, разбиения равны. |
Алгоритм Дюваля
Алгоритм
Алгоритм Дюваля (англ. Duval's algorithm) находит для данной строки длины
декомпозицию Линдона за время с использованием дополнительной памяти. Он строит декомпозицию только на упорядоченных алфавитах.
Определение: |
Предпростая строка — строка | , такая что , где — некоторая простая строка, а — некоторый префикс строки .
Во время работы алгоритма строка представляется в виде конкатенации трёх строк , где для строки декомпозиция Линдона уже найдена, и уже больше не используется алгоритмом; строка — это предпростая строка; строка — ещё не обработанная алгоритмом часть строки . Алгоритм Дюваля берёт первый символ строки и пытается дописать его к строке . При этом, возможно, для какого-то префикса строки декомпозиция Линдона становится известной, и эта часть переходит к строке .
Будем поддерживать три указателя:
- — на начало строки
- — на текущий символ в строке , с которым будет производиться сравнение
- — на начало строки
Внешний цикл алгоритма будет выполняться, пока
, то есть пока вся строка не перейдёт в строку . Внутри этого цикла создаются два указателя и . Затем будем пытаться добавить символ к строке , для чего необходимо произвести сравнение с символом . При этом будем поддерживать инвариант: — длина подстроки .Возникают три различных случая:
- тогда дописывыем символ к строке и увеличиваем оба указателя на единицу.
- тогда строка станет простой. Значит, мы увеличим на единицу, а передвигаем обратно на , чтобы следующий символ сравнивался с первым символом . То есть получаем новую простую строку длины .
- значит, строка уже не может быть предпростой. Добавляем к все строки , а по нашему инварианту мы знаем, что их длина равна , затем сдвигаем к началу позиции строки . После чего внешний цикл запускаем заново:
Реализация
function lyndon(string s, string[] decomposition): ns.length i 0 cur 0 while i n j i k i + 1 while k n and s[j] s[k] if s[j] s[k] j i else j k + 1 k k + 1 while i j decomposition[cur] s[i..i + k - j - 1] cur cur + 1 i i + k - j
Корректность
Покажем, что алгоритм получает нужное разложение. То есть все
— простые, и лексикографически.При обработке текущего символа в первом случае просто сдвигаем указатели, не записывая ответ. Мы сравниваем символы в
и на одинаковых позициях, а — префикс , поэтому инвариант сохраняется.Во втором случае объединяем все найденные
с и получем новую строку .Покажем, что
является простой. Рассмотрим ее суффикс. Если он начинается в середине , сравним его посимвольно со строкой , и тогда в каком-то символе он окажется больше , так как суффикс начинается с — суффикса , а строка — простая и по определению меньше всех своих суффиксов. Если суффикс начинается в , то при сравнении расхождение будет в символах и . Но , так что суффикс больше . Если же суффикс начинается с первой позиции какой-то подстроки , то отбросим общий префикс вида и придем к предыдущему случаю.В третьем случае просто выведем все
и продолжим обработку со строки , так как при добавлении , перестанет удовлетворять требованиям, ведь в этом случае суффикс строки равный будет меньше .Теперь покажем, что
.Последоваельность из
будет удовлетворять условию, так как эти строки равны. Следующее слово будет иметь общий префикс с , а после него будет стоять символ, меньший следующего символа из (новое получается по третьему случаю), либо следующее слово будет просто префиксом , и, как следствие, оно будет меньше лексикографически.Асимптотика
Внешний цикл
делает не более итераций, поскольку в конце каждой его итерации увеличивается как минимум на . Второй внутренний цикл выполнится суммарно не более , так он добавляет к ответу все символы, причём каждый символ лишь единожды.Оценим теперь количество итераций первого вложенного цикла
. Для этого рассмотрим второй вложенный цикл — он при каждом своём запуске выводит некоторое количество копий одной и той же простой строки некоторой длины . Заметим, что строка является предпростой, причём её простые строки имеют длину как раз , то есть её длина не превосходит . Поскольку длина строки равна , а указатель увеличивается на единицу на каждой итерации первого вложенного цикла , то этот цикл выполнит не более итераций. Худшим случаем является случай , и мы получаем, что первый вложенный цикл всякий раз выполняет не менее итераций. Вспоминая, что всего выводится символов, получаем, что для вывода символов требуется не более итераций первого вложенного .Итого получаем, что итоговая асимптотика алгоритма составляет
.Отметим, что алгоритму требуется
памяти: на указатели .Поиск лексикографически минимального суффикса строки
Поиск лексикографически минимального и максимального суффиксов строки - вопрос, который часто поднимается при решении различных теоретических задач. С помощью классического алгоритма Дюваля эта задача решается за линейное время и константный размер дополнительной памяти.
Если заметить, что данная нам строка
является подстрокой заранее данного текста длиной , то выполнив некоторый предподсчёт, мы можем получать значения максимального и минимального суффиксов определённой подстроки гораздо быстрее, чем линейно. Это может быть очень полезным при работе с большими объёмами данных (такими как генетический код и т.д.)Покажем, что
существует структура данных, размер которой линейно зависит от длины данного текста, со временем запроса и временем препроцессинга для запросов на нахождение минимального суффикса.Будем обозначать
и суффиксный массив и инвертированный суффиксный массив строки соответственно. Для данных индексов будем обозначать массив . SA и ISA могут быть улучшены за , чтобы отвечать на запросы вида- по данным подстрокам и строки найти и определить, какая из подстрок лексикографически меньше
- по индексам и вычислить максимальный и минимальный суффикс в
Более того, такой улучшенный суффиксный массив может отвечать на запрос "по данным
- подстрокам вычислить максимальное чило , такое, что является префиксом " за константное время. Действительно, стоит заметить, что если - префикс , тоЗапросы к перевёрнутому улучшенному суфмассиву
также имеют смысл. С его помощью мы можем для пары подстрок найти их наибольший общий суффикс и наибольшее число , такое, что является суффиксом .Возьмём строку
длины . Для каждой позиции мы выберем O(logN) подстрок , которые мы назовём каноническими. Определим как -ю кратчайшую каноническую подстроку, заканчивающуюся в позиции . Для пары целых чисел мы определим как наибольшее , такое, что - суффикс .Мы потребуем, чтобы канонические подстроки удовлетворяли определённым условиям:
- и для некоторого выполняется
- и можно вычислить за константное время для данных и соответственно
Такая структура данных работает при любом выборе канонических подстрок, которые удовлетворяют вышеприведённым условиям, например при простейшем
Лемма (1): |
Минимальный суффикс равен либо
Более того, , где -начальная позиция минимального суффикса в , либо минимальному суффиксу . может быть найдено за константное время с использованием улучшенного суффиксного массива строки . |
Доказательство: |
По Лемме 1 из 5 минимальный суффикс равен либо , либо его кратчайшему непустому бордеру. Более того, в последнем случае длина минимального суффикса равна не превышает . С другой стороны, по второму свойству канонических подстрок, длина равна как минимум . Таким образом, во втором случае минимальный суффикс является минимальным суффиксом . Заметим, что для значения не определены, но тогда выполняется случай из условия леммы. Чтобы доказать финальное выражение, вспомним, что нахождение минимального суффикса - одна из базовых операций, поддерживаемых улучшенным суфмассивом. |
Требуемая структура данных, помимо улучшенного суфмассива, должна, для каждого
содержать битовый вектор длиной . Положим тогда и только тогда, когда минимальный суффикс длиннее, чем . Для мы всегда считаем , поскольку является минимальным суффиксом самого себя. Вспомним, что количество канонических подстрок для каждого равна , поэтому каждый вмещается в константное количество машинных слов и структура данных занимает памяти.Алгоритм запроса
Предположим, что мы ищем минимальный суффикс
c . Наш подход основан на Лемме 1. Если выполняется случай , лемма позволяет нам вычислить ответ за . В общем случае, мы найдём минимальный суффикс , сравним его с и вернём меньший из них.Мы используем Лемму 1 и битовый вектор
чтобы посчитать минимальный суффикс . Назовём наибольший индекс, не превышающий , такой, что . Заметим, что такой индекс всегда существует (поскольку ) и может быть найден за константное время с использованием битовых операций. Для любого индекса мы имеем , т.е., случай Леммы 1 выполняется для . Тогда, по индукции, минимальный суффикс на самом деле является минимальным суффиксом . С другой стороны, , поэтому для последнего мы можем гарантировать, что выполняется первый случай леммы, что позволяет нам найти минимальный суффикс за константное время.Построение искомой структуры данных
Простой алгоритм построения с временем работы
также основывается на Лемме 1. Покажем, что построив улучшенный суфмассив, мы можем найти за . Мы ищем минимальный суффикс для последовательных значений . Как только мы получили результат , случай Леммы 1 даёт нам второго кандидата на минимальный суффикс , и наш улучшенный суфмассив позволяет нам выбрать наименьшего из этих двух кандидатов. Мы устанавливаем если меньший кандидат не содержится в . Стало быть, мы получили следующий результат:Теорема (2): |
Строку длины можно уместить в структуру данных с памяти, которая позволяет вычислять минимальный суффикс любой подстроки за . Эта структура данных может быть построена за . |
Вышеописанная конструкция проста и работает для любого выбора канонических подстрок, но, к сожалению, она не может быть использована для достижения компромисса между временем запроса и временем построения. Далее мы предложим особый способ выбора канонических подстрок и опишем альтернативный метод построения. Этот способ основывается на предположении, что по данной строке длины
мы можем найти минимальный суффикс для всех её префиксов за . Следовательно, нам удобно иметь много , которые являются префиксами друг друга. Тогда, естественным будет выбрать , поскольку все подстроки являются префиксами . К сожалению, подстроки, выбранные таким способом, не удовлетворяют условию , и, посему, нам необходимо немного изменить его.Для
мы определим . Для установим и определим таким образом:Заметим, что если
, то , в то время как, если , то . Очевидно, что количество таких подстрок, заканчивающихся в получается . Докажем далее, что канонические подстроки, выбранные вышеуказанным способом, имеют необходимые свойства.Теорема (3): |
Для любого и при мы имеем |
Доказательство: |
Для неравенство, очевидно, выполняется. Рассмотрим . Обозначим через , как и ранее, . Если чётно, то нечётно и мы имеем , в то время как, для нечётного выполняется |
Теорема (4): |
Для , величина может быть посчитана за константное время. |
Доказательство: |
Положим . Заметим, что
Таким образом, . , и мы можем за константное время проверить, какое из этих трёх значений корректно. |
После построения улучшенного суфмассива, мы установили все биты6). Разделим на куски длиной (где ) и запустим этот алгоритм для каждых четырёх (или менее, в конце) последовательных кусков. Это даст нам минимальные суффиксы для всех , за время . Значение определено с помощью сравнения длины вычисленного минимального суффикса с . У нас фаз алгоритма, что даёт нам время и требуемой памяти.
в 1. После этого, для каждого мы посчитали минимальные суффиксы подстрок , как указано далее. Зафиксируем и разобьём на куски размером (где ) . Теперь каждый является префиксом конкатенации максимум 4х таких кусков. Вспомним, что по данной строке можно посчитать длины минимальных суффиксов всех её префиксов за линейное время с помощью одной из вариаций алгоритма Дюваля (Алгоритм 3.1 inКомпромисс
Чтобы получить структуру данных, со временем построения
и временем запроса , мы немного по-другому определим битовые вектора. Положим размером , притом тогда и только тогда, когда или минимальный суффикс длиннее, чем . В этом случае, нам необходимо только фаз в алгоритме построения, поэтому он займёт времени.Как и ранее, предположим, что мы ищем минимальный суффикс
, при . Самое сложное в этом - найти минимальный суффикс , и далее необходимо найти , такой, что минимальный суффикс на самом деле является минимальным суффиксом , но длиннее, чем . Если для целого , мы можем найти наибольший , такой, что , и нам будет известно, что . В общем случае, мы выберем наибольший , такой что , и будем знать, что мы должны рассмотреть и , где определён, как в предыдущем случае. В результате, мы имеем возможных значений , и нам изестно, что искомый суффикс может быть найден, используя случай Леммы 1 для для каждого из этих значений. Тогда мы просто сгенерируем всех этих кандидатов и используем улучшенный суфмассив, чтобы найти наименьший суффикс среди них. В результате, запрос к нашей структуре данных будет выполняться за .Теорема (5): |
Для любого , строка длиной может храниться в структуре данных, занимающей памяти, позволяющей вычислять минимальный суффикс любой из подстрок за время . Такая структура данных может быть построена за . |
Поиск максимального суффикса
Наша структура данных, необходимая для поиска максимального суффикса, очень похожа на ту, что мы разработали для минимального суффикса. Однако, в отличие от той проблемы, свойства максимальных суффиксов позволят нам добиться линейной асимптотики.
Заметим, что единственный компонент из части о минимальном суффиксе, который не может быть сразу адаптирован к задаче о максимальном суффиксе, это Лемма 1. Так как эта лемма неприменима к нашей задаче, далее мы докажем следующую лемму, эквивалентную в смысле алгоритмического приложения. Канонические подстроки
обозначены как и ранее.Лемма (7): |
Рассмотрим подстроку . Используя улучшенный суффиксный массив строки , за можно найти индекс такой, что максимальный суффикс строки равен либо
, либо максимальный суффикс строки |
Доказательство: |
Точно так же, как и структура, описанная в части о минимальном суффиксе, наша структура данных, не считая улучшенный суффиксный массив, содержит битовые вектора очевидно, может быть адаптирован к нашей задаче, только вместо Леммы 1 мы будем использовать Лемму 7 и выбирать наибольшего из двух кандидатов в качестве ответа. Это демонстрирует следующая теорема: , с , если или максимальный суффикс строки длиннее . Алгоритм запроса, описанный в части 4.1, |
Теорема (8): |
Строка длины может храниться в структуре данных с памяти, которая позволяет вычислять максимальный суффикс любой подстроки строки за время . |
Доказательство: |
Алгоритмы построения за и компромисс между временем запросов и временем построения, описанные в секциях 4.2 и 4.3, также легко адаптируются к нашей задаче. В случае поиска максимального суффикса, тем не менее, мы можем добиться времени построения , как будет показано в секции 5.2.Ниже мы описываем алгоритм, работающий за константное время, который возвращает позицию .Заметим, что если максимальный суффикс Мы начнем со вспомогательной леммы, которая обозначалась как Лемма 2 в of короче, чем (случай (b) Леммы 7), алгоритм может вернуть любое . Далее мы предполагаем, что длиннее, чем и показываем, что при этом предположении алгоритм вернёт . Из нашего предположения свойств канонических подстрок следует, что , where , и что длины суффиксов подстроки , начинающихся с позиций в промежутке , отличаются не более чем в два раза. 1 |
Лемма (9): |
Пусть — префикс строки и пусть , где — максимальный суффикс в . Если не является префиксом , тогда . Иначе, также является префиксом строки . |
Доказательство: |
Пусть 1, но здесь мы приводим доказательства вследствие другого обозначения. | — максимальный суффикс в и — максимальный суффикс в . Очевидно, является префиксом строки . Предположим, что — префикс (иначе по Лемме 9). Длины и различаются не более чем в два раза, поэтому . Благодаря этому, и имеют некоторые интересные свойства, описанные в последующих леммах. Эти леммы по существу повторяют Леммы 4 и 5 из
Ссылки
- Wikipedia — Lyndon word
- MAXimal :: algo :: Декомпозиция Линдона. Алгоритм Дюваля
- Algebras, Rings, and Modules: Lie Algebras and Hopf Algebras", Michiel Hazewinkel, Nadezhda Mikhaĭlovna Gubareni, Vladimir V. Kirichenko, страница 242
- Computing minimal and maximal suffixes of a substring revisited
- On Minimal and Maximal Suffixes of a Substring
- Factorizing words over an ordered alphabet