Сложность по Лемпелю — Зиву
Насколько сложна последовательность: запись ЭЭГ, ряд «потеплело или похолодало», геном? В 1976 году Абрахам Лемпель и Якоб Зив предложили меру, которая не зависит ни от какой модели: сколько новых кусков приходится вводить, читая последовательность слева направо. С тех пор её считают в анализе сигналов и в геномике, а через год из этой же идеи вырос алгоритм сжатия LZ77.
Строка s длины n разбивается на фразы слева направо. Пусть очередная фраза начинается в позиции p. Найдём самый длинный кусок s[p..p + L), который встречается в s, начиная с какой-нибудь позиции j < p; вхождение может заходить за p и перекрываться с самим куском. Фраза — этот кусок и ещё одна следующая буква, то есть L + 1 букв; если до конца строки меньше, фраза — весь остаток. Сложность по Лемпелю — Зиву — число фраз.
Например, 0001101001000101 разбивается на 0 · 001 · 10 · 100 · 1000 · 101: шесть фраз. Строка из ста тысяч букв «a» — на две: «a» и весь остаток, потому что он повторяет сам себя со сдвигом на одну букву.
Среди тестов — геномы фагов и митохондрии человека, ряды «теплее ли, чем вчера» и «был ли дождь» для Алматы за 1941–2025 годы, кусок «Войны и мира» и строки, на которых квадратичный алгоритм Каспара и Шустера (1987) не успевает.
Вход
В первой строке число строк t (1 ≤ t ≤ 1000). В каждой из следующих t строк — непустая строка без пробельных знаков, в UTF-8. Суммарная длина строк не больше 100 000 знаков; длина считается в знаках, а не в байтах.
Выход
Для каждой строки — её сложность по Лемпелю — Зиву.
Примеры
Пример 1
1 0001101001000101
6
Пример 2
4 aaaa abcabc ACGT TTAGGGTTAGGGTTAGGG
2 4 4 5
Ограничения
- Время · Python
- 8000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 10 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Длина фразы зависит только от одного числа — самого длинного куска, который начинается в p и встречался раньше. Если знать это число для каждой позиции, разбиение — один проход.
2Подсказка 2
Это число называют LPF, longest previous factor. Кусок, который начинается в p и раньше, — общее начало суффикса p и какого-то суффикса j < p. Где в суффиксном массиве искать лучший такой j?
3Подсказка 3
Общее начало с суффиксом тем длиннее, чем ближе он в массиве. Значит, лучший j — ближайший к p в массиве сверху или снизу из тех, что начинаются в тексте раньше p. Их находит стек, как в задачах о ближайшем меньшем элементе.
4Идея
Строим суффиксный массив и LCP, затем LPF алгоритмом Крошмора и Илие (2008). Идём по массиву со стеком суффиксов, номера которых в тексте возрастают снизу вверх. Новый суффикс выталкивает со стека всех, кто начинается в тексте позже него: для вытолкнутого суффикса ближайший «более ранний» снизу — это он, а сверху — новая вершина стека. LPF вытолкнутого — максимум из двух общих начал, а общее начало с новым суффиксом по ходу дела уменьшается до минимума LCP на отрезке. Каждый суффикс входит в стек и выходит из него один раз.
5Разбор
Разбиение: p = 0, пока p < n — сдвиг на min(LPF[p] + 1, n − p) и счётчик фраз плюс один. Суффиксный массив и Касаи — из статьи о суффиксном массиве.
Ответы стоит сравнить с тем, что дал бы случайный текст той же длины: для него число фраз близко к n/logk n, где k — размер алфавита. Сто тысяч случайных битов дают 6134 фразы, почти ровно столько. Геном лямбды — 5988 фраз на 48 502 буквы, 96 % от случайного: в ДНК фага мало повторов. А ряд «теплее ли, чем вчера» за 50 000 дней в Алматы — 2050 фраз, около 64 % от случайного: погода повторяет свои узоры.
5+Решение
6Сложность
Массив — O(n log n), LCP и LPF — O(n), разбиение — O(n). Алгоритм Каспара и Шустера для каждой фразы перебирает все прежние начала и на случайном тексте делает порядка n²/2 сравнений.
7Типичные ошибки
- Без перекрытия. Если искать кусок только в тексте до p, строка из одних «a» распадётся на фразы длиной 1, 2, 4, 8…, а не на две. По определению вхождение может заходить за p.
- Последняя фраза. Если остаток строки целиком встречался раньше, он — последняя фраза, без лишней буквы. Строку надо досчитать до конца и не выйти за её пределы.
- Только сосед сверху. Ближайший более ранний суффикс бывает и снизу в массиве; нужны оба, и берётся лучшее общее начало.
Алгоритмы задачи
O(n · chain)
2 задачи
STR
Структура данных
Суффиксный массив
Отсортированные хвосты текста: поиск двоичным поиском, повторы и число разных кусков по соседям.
O(n log n)
2 задачи