Декомпозиция Линдона

Декомпозиция Линдона была изобретена Роджером Линдоном (англ. Roger Lyndon) в 1954 году. Она используется для нахождения лексикографически минимального и максимального суффиксов строки, а также лексикографически минимального циклического сдвига.

Основные определения

Определение:

Простая строка — строка, которая лексикографически меньше любого своего суффикса.

Примеры:

[math]ababb[/math] — простая строка, так как [math]ababb \lt babb[/math], [math]ababb \lt abb[/math], [math]ababb \lt bb[/math], [math]ababb \lt b[/math].

[math]babaa[/math] — не простая строка, так как [math]babaa \gt aa[/math].

Определение:

Декомпозиция Линдона (англ. Lyndon decomposition) строки [math]s[/math] — её разложение [math]s = s_1s_2...s_k[/math], где строки [math]s_i[/math] просты, и при этом [math]s_1 \geqslant s_2 \geqslant ... \geqslant s_k[/math].

Существование и единственность

Лемма:

[math]s [/math], [math]t[/math] — простые и [math]s \lt t[/math] лексикографически. Тогда верны следующие утверждения: 1. [math]s + t \lt t[/math] 2. [math]s + t[/math] — простая

Доказательство:

[math]\triangleright[/math]

1. Так как [math]s \lt t[/math], то [math]\exists i : s[i] \lt t[i][/math] и [math]s[j] = t[j][/math], [math]j \lt i \Rightarrow s + t \lt t[/math] 2. Пусть [math]u[/math] — суффикс строки [math]s + t[/math]. Тогда рассмотрим 3 возможных случая: [math]|u| = |t| \Rightarrow u = t \Rightarrow u \gt s + t[/math] по пункту 1 [math]|u| \lt |t| \Rightarrow u[/math] — суффикс [math]t[/math]. Так как [math]t[/math] — простая, и [math]t \lt u [/math] по определению [math] \Rightarrow s + t \lt t \lt u[/math] [math]|u| \gt |t| \Rightarrow s = s' + s''[/math], [math]u = s'' + t[/math]. Так как [math]s[/math] — простая, то её суффикс [math] s'' [/math] меньше самой строки [math] s [/math] в каком-то символе, значит, [math] s + t \lt s'' + t[/math]

[math]\triangleleft[/math]

Теорема (Чен-Линдон-Фокс):

Можно построить декомпозицию Линдона любой строки [math]s[/math], причем единственным образом.

Доказательство:

[math]\triangleright[/math]

1. Существование. У каждой строки существует хотя бы одно разбиение на простые слова. Это следует из того, что отдельный символ является простым словом. Тогда среди всех разбиений строки на простые слова возьмём то, в котором меньше всего слов. Покажем, что это и будет декомпозицией Линдона данной строки. Предположим, что это не так. Значит, [math]\exists i : s_i \lt s_{i+1}[/math]. Так как слова [math] s_i [/math] и [math] s_{i+1} [/math] простые, то из доказанной леммы следует, что эти слова можно сконкатенировать и получить разбиение строки [math] s [/math] на меньшее число слов. Получили противоречие. Таким образом доказали даже более сильное утверждение: [math]s = s_1 s_2 ... s_k[/math], [math] k [/math] — минимально [math]\Leftrightarrow[/math] нет [math]s_i \lt s_{i+1}[/math] 2. Единственность. Пусть существует несколько разбиений [math]s = s_1s_2...s_k = s_1's_2'...s_k'[/math], удовлетворяющих условию теоремы. Сравним длины первых двух слов [math]s_1[/math] и [math]s_1'[/math], если [math]|s_1| = |s_1'|[/math], сравним вторые и так далее. Если длины всех слов одинаковы, то разбиения совпадают — противоречие. Иначе [math]\exists s_i : |s_i| \neq |s_i'|[/math]. Покажем, что такого не может быть: 1) Пусть [math]|s_i| \gt |s_i'|[/math], тогда [math]s_i = s_i's_{i+1}'...t[/math], где [math]t[/math] — префикс [math]s_{j+1}'[/math], [math]i \lt j[/math]. Тогда получаем: [math]s_i \lt t[/math] ([math]s_i[/math] — простая cтрока и по определению меньше своего суффикса) [math]t \lt s_{j+1}'[/math] ([math]t[/math] — префикс [math]s_{j+1}'[/math]) [math]s_{j+1}' \leqslant s_i'[/math] (по условию разбиения) [math]s_i' \lt s_i[/math] (их начало совпадает, и [math]|s_i'| \lt |s_i|[/math] по предположению) Пришли к противоречию: [math]s_i \lt s_i[/math]. 2) Случай [math]|s_i| \lt |s_i'|[/math] симметричен разобранному. То есть не может быть строк [math]s_i[/math] и [math]s_i'[/math] несовпадающей длины, значит, разбиения равны.

[math]\triangleleft[/math]

Алгоритм Дюваля

Алгоритм

Алгоритм Дюваля (англ. Duval's algorithm) находит для данной строки длины [math]n[/math] декомпозицию Линдона за время [math]O(n)[/math] с использованием [math]O(1)[/math] дополнительной памяти. Он строит декомпозицию только на упорядоченных алфавитах.

Определение:

Предпростая строка — строка [math]s[/math], такая что [math]s = ww \dots ww'[/math], где [math]w[/math] — некоторая простая строка, а [math]w'[/math] — некоторый префикс строки [math]w[/math].

Во время работы алгоритма строка [math]s[/math] представляется в виде конкатенации трёх строк [math]s = s_1s_2s_3[/math], где для строки [math]s_1[/math] декомпозиция Линдона уже найдена, и [math]s_1[/math] уже больше не используется алгоритмом; строка [math]s_2[/math] — это предпростая строка; строка [math]s_3[/math] — ещё не обработанная алгоритмом часть строки [math]s[/math]. Алгоритм Дюваля берёт первый символ строки [math]s_3[/math] и пытается дописать его к строке [math]s_2[/math]. При этом, возможно, для какого-то префикса строки [math]s_2[/math] декомпозиция Линдона становится известной, и эта часть переходит к строке [math]s_1[/math].

Будем поддерживать три указателя:

• [math]i[/math] — на начало строки [math]s_2[/math]
• [math]j[/math] — на текущий символ в строке [math]s_2[/math], с которым будет производиться сравнение
• [math]k[/math] — на начало строки [math]s_3[/math]

Внешний цикл алгоритма будет выполняться, пока [math]i \lt n[/math], то есть пока вся строка [math]s[/math] не перейдёт в строку [math]s_1[/math]. Внутри этого цикла создаются два указателя [math] j [/math] и [math] k [/math]. Затем будем пытаться добавить символ [math]s[k][/math] к строке [math]s_2[/math], для чего необходимо произвести сравнение с символом [math]s[j][/math]. При этом будем поддерживать инвариант: [math]k - j[/math] — длина подстроки [math] w [/math].

Возникают три различных случая:

• [math]s[j] = s[k]:[/math] тогда дописывыем символ [math]s[k][/math] к строке [math]s_2[/math] и увеличиваем оба указателя на единицу.
• [math]s[j] \lt s[k]:[/math] тогда строка [math]s_2 + s[k][/math] станет простой. Значит, мы увеличим [math]k[/math] на единицу, а [math]j[/math] передвигаем обратно на [math]i[/math], чтобы следующий символ сравнивался с первым символом [math]s_2[/math]. То есть получаем новую простую строку длины [math]k - j[/math].
• [math]s[j] \gt s[k]:[/math] значит, строка [math]s_2 + s[k][/math] уже не может быть предпростой. Добавляем к [math] s_1 [/math] все строки [math] w [/math], а по нашему инварианту мы знаем, что их длина равна [math] k - j [/math], затем сдвигаем [math] i [/math] к началу позиции строки [math] w' [/math]. После чего внешний цикл запускаем заново:

Реализация

function lyndon(string s, string[] decomposition):
   n [math]\leftarrow[/math] s.length
   i [math]\leftarrow[/math] 0
   cur [math]\leftarrow[/math] 0
   while i [math] \lt  [/math] n
       j [math]\leftarrow[/math] i
       k [math]\leftarrow[/math] i + 1
       while k [math] \lt  [/math] n and s[j] [math] \leqslant [/math] s[k]
           if s[j] [math] \lt  [/math] s[k]
               j [math]\leftarrow[/math] i
           else
               j [math]\leftarrow[/math] k + 1
           k [math]\leftarrow[/math] k + 1
       while i [math]\leqslant[/math] j
           decomposition[cur] [math]\leftarrow[/math] s[i..i + k - j - 1]
           cur [math]\leftarrow[/math] cur + 1
           i [math]\leftarrow[/math] i + k - j

Корректность

Покажем, что алгоритм получает нужное разложение. То есть все [math]s_i[/math] — простые, и [math]s_1 \geqslant s_2 \geqslant ... \geqslant s_k[/math] лексикографически.

При обработке текущего символа в первом случае просто сдвигаем указатели, не записывая ответ. Мы сравниваем символы в [math] w [/math] и [math] w' [/math] на одинаковых позициях, а [math] w' [/math] — префикс [math] w [/math], поэтому инвариант сохраняется.

Во втором случае объединяем все найденные [math]w[/math] с [math]w'[/math] и получем новую строку [math]w''[/math].

Покажем, что [math]w''[/math] является простой. Рассмотрим ее суффикс. Если он начинается в середине [math]w[/math], сравним его посимвольно со строкой [math]s_2[/math], и тогда в каком-то символе он окажется больше [math]s_2[/math], так как суффикс [math] w'' [/math] начинается с [math] u [/math] — суффикса [math]w[/math], а строка [math]w[/math] — простая и по определению меньше всех своих суффиксов. Если суффикс начинается в [math]w'[/math], то при сравнении расхождение будет в символах [math]s[j][/math] и [math]s[k][/math]. Но [math]s[j] \lt s[k][/math], так что суффикс больше [math]w''[/math]. Если же суффикс начинается с первой позиции какой-то подстроки [math]w[/math], то отбросим общий префикс вида [math]ww \dots w[/math] и придем к предыдущему случаю.

В третьем случае просто выведем все [math]w[/math] и продолжим обработку со строки [math]w'[/math], так как при добавлении [math]s[k] [/math], [math]s_2[/math] перестанет удовлетворять требованиям, ведь в этом случае суффикс строки [math] s_2 [/math] равный [math] w'[/math] будет меньше [math]w[/math].

Теперь покажем, что [math]s_i \geqslant s_{i + 1}[/math].

Последоваельность из [math]w[/math] будет удовлетворять условию, так как эти строки равны. Следующее слово будет иметь общий префикс с [math]w[/math], а после него будет стоять символ, меньший следующего символа из [math]w[/math] (новое [math]w[/math] получается по третьему случаю), либо следующее слово будет просто префиксом [math] w [/math], и, как следствие, оно будет меньше [math] w [/math] лексикографически.

Асимптотика

Внешний цикл [math]\mathrm{while}[/math] делает не более [math]n[/math] итераций, поскольку в конце каждой его итерации [math] i [/math] увеличивается как минимум на [math] 1 [/math]. Второй внутренний цикл выполнится суммарно не более [math] n [/math], так он добавляет к ответу все символы, причём каждый символ лишь единожды.

Оценим теперь количество итераций первого вложенного цикла [math]\mathrm{while}[/math]. Для этого рассмотрим второй вложенный цикл [math]\mathrm{while}[/math] — он при каждом своём запуске выводит некоторое количество [math]r \geqslant 1[/math] копий одной и той же простой строки некоторой длины [math]p = k - j[/math]. Заметим, что строка [math]s_2[/math] является предпростой, причём её простые строки имеют длину как раз [math]p[/math], то есть её длина не превосходит [math]r \cdot p + p - 1[/math]. Поскольку длина строки [math]s_2[/math] равна [math]k - i[/math], а указатель [math]k[/math] увеличивается на единицу на каждой итерации первого вложенного цикла [math]\mathrm{while}[/math], то этот цикл выполнит не более [math]r \cdot p + p - 2[/math] итераций. Худшим случаем является случай [math]r = 1[/math], и мы получаем, что первый вложенный цикл [math]\mathrm{while}[/math] всякий раз выполняет не менее [math]2p - 2[/math] итераций. Вспоминая, что всего выводится [math]n[/math] символов, получаем, что для вывода [math]n[/math] символов требуется не более [math]2n - 2[/math] итераций первого вложенного [math]\mathrm{while}[/math].

Итого получаем, что итоговая асимптотика алгоритма составляет [math] O(n) [/math].

Отметим, что алгоритму требуется [math] O(1) [/math] памяти: на указатели [math] i, j, k [/math].

Поиск лексикографически минимального суффикса строки

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

Если заметить, что данная нам строка [math]S[/math] является подстрокой заранее данного текста [math]T[/math] длиной [math]n[/math], то выполнив некоторый предподсчёт, мы можем получать значения максимального и минимального суффиксов определённой подстроки гораздо быстрее, чем линейно. Это может быть очень полезным при работе с большими объёмами данных (такими как генетический код и т.д.)

Покажем, что [math]\forall\tau: 1\le\tau\le\log{n}[/math] существует структура данных, размер которой линейно зависит от длины данного текста, со временем запроса [math]O(\tau)[/math] и временем препроцессинга [math]O(n\log{n/\tau})[/math] для запросов на нахождение минимального суффикса.

Будем обозначать [math]SA(T)[/math] и [math]ISA(T)[/math] суффиксный массив и инвертированный суффиксный массив строки [math]T[/math] соответственно. Для данных индексов [math]i\lt j[/math] будем обозначать [math]Suf[i,j][/math] массив [math]\{T[i,i+1, \ldots ,|T|-1], \ldots , T[j,j+1, \ldots ,|T|-1]\}[/math]. SA и ISA могут быть улучшены за [math]O(n)[/math], чтобы отвечать на запросы вида

• по данным подстрокам [math]x[/math] и [math]y[/math] строки [math]T[/math] найти [math]lcp(x,y)[/math] и определить, какая из подстрок лексикографически меньше
• по индексам [math]i[/math] и [math]j[/math] вычислить максимальный и минимальный суффикс в [math]Suf[i,j][/math]

Более того, такой улучшенный суффиксный массив может отвечать на запрос "по данным [math]x,y[/math] - подстрокам [math]T[/math] вычислить максимальное чило [math]\alpha[/math], такое, что [math]x^{\alpha}[/math] является префиксом [math]y[/math]" за константное время. Действительно, стоит заметить, что если [math]x[/math] - префикс [math]y = T[i..j][/math], то [math]\alpha |x| \le lcp(T[i..j],T[i+|x|..j] \lt (\alpha+1)|x|)[/math]

Запросы к перевёрнутому улучшенному суфмассиву [math]T^{R}[/math]также имеют смысл. С его помощью мы можем для пары [math]x,y[/math] подстрок [math]T[/math] найти их наибольший общий суффикс [math]lcs(x,y)[/math] и наибольшее число [math]\alpha[/math], такое, что [math]x^{\alpha}[/math] является суффиксом [math]y[/math].

Возьмём строку [math]T[/math] длины [math]n[/math]. Для каждой позиции [math]j[/math] мы выберем O(logN) подстрок [math]T[k..j][/math], которые мы назовём каноническими. Определим как [math]S^{l}_{j}[/math] [math]l[/math]-ю кратчайшую каноническую подстроку, заканчивающуюся в позиции [math]j[/math]. Для пары целых чисел [math]1\le i\lt j\le n[/math] мы определим как [math]\alpha(i,j)[/math] наибольшее [math]l[/math], такое, что [math]S^{l}_{j}[/math] - суффикс [math]T[i..j][/math].

Мы потребуем, чтобы канонические подстроки удовлетворяли определённым условиям:

• [math]S^{1}_{j} = T[j..j][/math] и для некоторого [math]l=O(logN)[/math] выполняется [math]S^{l}_{j} = T[1..j][/math]
• [math]\forall l:|S^{l+1}_{j}|\le 2|S^{l}_{j}|[/math]
• [math]\alpha(i,j)[/math] и [math]|S^{l}_{j}|[/math] можно вычислить за константное время для данных [math](i,j)[/math] и [math](i,l)[/math] соответственно

Такая структура данных работает при любом выборе канонических подстрок, которые удовлетворяют вышеприведённым условиям, например при простейшем [math]|S^{l}_{j}| = \min(2^{l-1}, j)[/math]

Лемма:

Минимальный суффикс [math]T[i..j][/math] равен либо [math]T[p..j][/math], где [math]p[/math]-начальная позиция минимального суффикса в [math]Suf[i,j][/math], либо минимальному суффиксу [math]|S^{\alpha(i,j)}_{j}|[/math]. Более того, [math]p[/math] может быть найдено за константное время с использованием

Доказательство:

[math]\triangleright[/math]

По лемме 1 из 1 минимальный суффикс равен либо [math]T[p..j][/math], либо его кратчайшему непустому бордеру. Более того, в последнем случае длина минимального суффикса равна не превышает [math]\displaystyle \frac{1}{2}|T[p..j]|\leq\frac{1}{2}|T[i..j]|[/math]. С другой стороны, по второму свойству канониеских подстрок, длина [math]S_{j}^{\alpha(i,j)}[/math] равна как минимум [math]\displaystyle \frac{1}{2}|T[i..j]|[/math]. Таким образом, во втором случае минимальный суффикс [math]T[i..j][/math] является минимальным суффиксом [math]S_{j}^{\alpha(i,j)}[/math]. Заметим, что для [math]i=j[/math] значения [math]\alpha(i,\ j)[/math] не определены, но тогда выполняется первый случай из условия леммы. Чтобы доказать финальное выражение, вспомним, что нахождение минимального суффикса [math]Suf [i,\ j][/math] - одна из базовых операций, поддерживаемых улучшенным суфмассивом.

[math]\triangleleft[/math]

Требуемая структура данных, помимо улучшенного суфмассива, должна, для каждого [math]j=1,\ \ldots,\ n[/math] содержать битовый вектор [math]B_{j}[/math] длиной [math]\alpha(1,\ j)[/math]. Положим [math]B_{j}[\ell]=1[/math] тогда и только тогда, когда минимальный суффикс [math]S_{j}^{\ell}[/math] длиннее, чем [math]|S_{j}^{\ell-1}|[/math]. Для [math]\ell=1[/math] мы всегда считаем [math]B_{j}[1]=1[/math], поскольку [math]S_{j}^{1}[/math] является минимальным суффиксом самого себя. Вспомним, что количество канонических подстрок для каждого [math]j[/math] равна [math]\mathcal{O}(\log n)[/math] , поэтому каждый [math]B_{j}[/math] вмещается в константное количество машинных слов и структура данных занимает [math]\mathcal{O}(n)[/math] памяти.

Ссылки

• 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