Спеціальний автомат з ланцюгів: стиснута карта кожного підланцюга

Яку проблему вирішує суфіксний автомат?

Враховуючи задану рядок довжиною n, множина його унікальних підрядків може бути величезною: приблизно до n квадратного числа, поділеного на два для рядка без повторюваних символів. Зберігати їх поодинці, один за одним, є марним і часто неможливим для довгих текстів. Суфіксний автомат обходить це, будуючи розпізнавач замість списку. Це детермінована кінцева автоматика: набір станів, з’єднаних мітками переходу, із зазначеним початковим станом, таке що дотримання переходів, які відповідають будь-якому підрядку оригінального рядка, завжди призводить до певного стану, а дотримання переходів, які не відповідають жодному підрядку, застрягає посередині. Ключовим є те, що кожний досяжний стан відповідає прийому щонайменше одного підрядка, отже кожен стан є явно приймаючим станом для підрядоків, які ведуть до нього. Гениальністю конструкції полягає в тому, що незважаючи на те, що кількість унікальних підрядоків може бути квадратичною відносно n, кількість станів у цій автоматики ніколи не перевищує приблизно 2n мінус 1, а кількість переходів ніколи не перевищує приблизно 3n мінус 4 для n більше ніж 2. Це можливо тому, що один стан в автоматиці представляє всю еквавалентну клас підрядоків, які збігаються на точно одному наборі позицій кінця в тексті. Два підрядки зводяться до одного стану лише тоді, коли кожне повторення коротшого підрядка негайно супроводжується або співпадає з кожним повторенням довшого підрядка в тексті — формально, вони мають один і той же набір позицій кінця, який називається endpos. Ця еквавалентність є серцем всієї структури: замість того, щоб представляти підрядки індивідуально, автоматика представляє класи endpos, і їх просто не так багато.Оскільки автоматика детермінована, перевірка членства механічна та швидка: почніть із початкового стану, дотримуйтесь переходу, позначеного кожним символом кандидата в шаблон, один за одним, і якщо ви ніколи не виходите за межі автоматики, шаблон є підрядком. Якщо будь-який перехід відсутній, він відсутній. Без повернення назад, без порівнянь за межами читання кожного символу шаблону один раз.

Стани, Класи Endpos та Дерево Посилань Суфіксних

Кожен стан суфіксного автомата відповідає неперервному діапазону довжин, що містить підрядки, які мають однаковий набір endpos, і цей набір підрядоків завжди є найкоротшим та найдовшим підрядками, що відображаються в стані, плюс все між ними. Отже, стан зберігає дві довжини — мінімальну та максимальну довжину підрядоків, які він представляє, і кожен підрядок у цьому діапазоні отримується з найдовшого шляхом обрізання символів з початку. Це пояснює призначення посилань суфіксних зв'язків. Кожен стан, крім першого, має посилання суфіксного зв’язку, яке вказує на стан, що представляє клас endpos найдовшого підрядка з довшою власною суфіксом, який належить до іншого, більш загального класу. Дотримуючись посилань суфіксних зв'язків від будь-якого стану, ви проходите через підрядки, що стають все коротшими, і набори endpos стають все більшими (більш загальними), і ця ланцюг завжди закінчується в першому стані, який представляє порожню рядок. Набір посилань суфіксних зв’язків, взятий разом, утворює дерево з коренем у першому стані — часто це називають деревом посилань суфіксних зв'язків або батьківським деревом. Це дерево не є побічним ефектом; це друга структура, що має таку ж важливість, як і граф переходу автомата, і багато найкорисніших обчислень автомата насправді є обчисленнями дерев, які виконуються на ньому. Наприклад, кількість разів, коли певна підрядок зустрічається в тексті, дорівнює розміру набору endpos стану, якому він відповідає, і цей розмір можна обчислити для кожного стану одноразово за допомогою опускання посилань суфіксних зв’язків.

Побудова його онлайн, по одному символу за раз

Що робить суфіксний автомат практичним, а не просто теоретично елегантним, так це те, що він може будуватися поступово. Почніть з автомата для порожньої рядки, який складається з одного початкового стану. Потім розширте його, додаючи символи один за одним: після обробки префікса довжиною k, автомат, який у вас є, точно є суфіксним автоматом для цього префікса. Додавання наступного символу перетворює його на суфіксний автомат для префікса довжиною k плюс один, не відвідуючи повторно будь-які попередні символи тексту. Кожен крок розширення створює новий стан, який представляє весь бачений досі підрядок, потім йде назад по посиланнях на суфікси від попереднього кінцевого стану, додаючи перехід на новий символ, де б він не був, поки не буде досягнуто кінця дерева (досягнення початкового стану) або не знайдено стан, який вже має перехід на новий символ. У цьому випадку здійснюється ретельна перевірка, щоб визначити, чи вже існує цей перехід представляє точно правильний клас кінцевих положень, або чи потрібно розділити його на два стани — один для довгих підрядків, які все ще мають однаковий набір кінцевих положень, і один, копія, для коротких підрядків, чий набір кінцевих положень тепер включає нову позицію. Цей крок клонування гарантує, що діапазон підрядків кожного стану залишається безперервним, а клас кінцевих положень добре визначений, і це найскладніший етап алгоритму для правильної реалізації. Незважаючи на видиму складність окремих кроків, аналіз з амортизованою витратою (кожен символ може спровокувати обмежену кількість зворотного ходіння та клонування по всьому процесу побудови) показує, що весь процес виконується за лінійний час відносно довжини рядка для будь-якої фіксованої розмірності алфавіту і використовує лінійне місцезнаходження. Ця онлайн властивість має практичний бонус: ви можете запитувати автомат для тексту, який бачили до цього часу в будь-який момент під час побудови, що саме потрібно потоковим додаткам для відповідного зіставлення підрядків.

Що Ви Можете Обчислити Одразу Після Будівництва

З автоматизованим апаратом і його деревом посилань на суфікси в руці, кілька класичних проблем з текстом спрощуються до простих перевірок. Перевірка підрядків: слідуйте за переходами, позначеними символами кандидата у шаблон, від початкового стану; успіх, якщо ви ніколи не застрягаєте, в часі пропорційному довжині шаблону самої, незалежно від того, наскільки довгим був оригінальний текст. Підрахунок різних підрядків: кожен стан окрім першого відповідає безперервному діапазону довжин підрядків (його довжина мінус довжина посилання на суфікс для багатьох з них), тому підсумовування цієї кількості за всіма станами дає точний лік підрядків у всьому тексті, обчислюється за час, лінійний відносно кількості станів. Підрахунок кількості входжень конкретного підряду: знайдіть стан, якому він відповідає, слідуючи за його символами, потім прочитайте розмір набору кінцевих позицій, що попередньо розрахований для цього стану (підсумована деревина зверху-вниз, описана раніше). Знаходження найменшого або найбільшого підряду заданої довжини, або перерахунок підрядків у відсортованому порядку можна виконати шляхом ходьби по графу переходів, оскільки переходи з певного стану природним чином впорядковані за символами. Можливо, найбільш вражаюча застосування - це найдовший спільний підрядок двох рядків. Побудуйте автоматизований суфікс для першого рядка лише. Потім подайте другий рядок у нього як потокове запит без читання: підтримуйте поточний стан і поточну довжину відповідності, а для кожного символу другого рядка намагайтеся продовжити відповідність; якщо існує перехід, продовжуйте; якщо ні, повертайтеся по посиланнях на суфікси (коротша поточна відповідність) доки не знайдеться перехід з відповідним станом або досягнуто початкового стану. Відстеження найкращої довжини відповідності, побаченої під час цього одноразового проходження другого рядка, дає найдовший спільний підрядок обох рядків за лінійний час відносно їх сукупної довжини — не потрібно будувати жодну структуру над конкатенацією обох рядків, і жодної структури не потрібно будувати для другого рядка взагалі.

Суфіксний автомат проти масиву суфіксів: дві точки зору на структуру підрядків

Цей сайт вже охоплює масив суфіксів, який сортує всі n суфіксів рядка лексикографічно та поєднує цей відсортований порядок із масивом LCP (найдовший спільний префікс), для кожної сусідньої пари відсортованих суфіксів записуючи, скільки літер вони поділяють на початку. Суфіксний автомат і масив суфіксів обидва в кінцевому підсумку описують один і той же фундаментальний об'єкт — структуру підрядків рядка, але представляють його в принципово різних формах, і варто безпосередньо їх порівнювати, а не розглядаючи як взаємозамінні. Масив суфіксів є фундаментально списком: n суфіксів, відсортованих, кожен запис, який повертається назад у текст, плюс допоміжний масив LCP довжиною n мінус один. Його розмір завжди пропорційний n, довжині рядка, незалежно від того, наскільки повторюваний або різноманітний вміст рядка. Суфіксний автомат, навпаки, є графом: його кількість станів обмежена приблизно 2n, але для рядків з інтенсивним внутрішнім повторенням фактична кількість використаних станів часто значно менша за цей ліміт, оскільки багато суфіксів стискаються в спільні класи endpos. Немає еквівалентного стиснення доступного у форматі масиву суфіксів, оскільки він завжди повинен перераховувати кожен суфікс як окрему відсортовану позицію — масив суфіксів для рядка, такого як двадцять повторень однієї і тієї ж літери, все ще має стільки ж записів, скільки суфіксів, тоді як відповідний суфіксний автомат залишається надзвичайно маленьким, оскільки майже все стискається в невелику кількість станів. Обидві структури також відрізняються тим, який вартість одного запиту. З масивом суфіксів плюс масивом LCP, тестування того, чи є шаблон довжиною m підрядком заданого тексту зазвичай використовує бінарний пошук по відсортованих суфіксах, що коштує приблизно m разів логарифм n порівнянь символів (або m плюс логарифм n з додатковою попередньою обробкою). З суфіксним автоматом такий самий тест коштує точно m кроків — один перехід за кожний символ шаблону — без залежності від n крім того, що автомат вже побудовано. Суфіксний автомат також будується онлайн, природним чином розширюючись зі збільшенням кількості прибулих символів, тоді як масив суфіксів зазвичай обчислюється лише після знання всього рядка за допомогою алгоритмів сортування пакетної обробки. Коротко кажучи: звертайтеся до масиву суфіксів, коли ви хочете стабільне, передбачувано розмірне представлення, добре підходяще для запитів діапазонів і ранжування; звертайтеся до суфіксного автомата, коли ви хочете найменшого можливого розпізнавача підрядків, особливо для повторюваних текстів, онлайн побудови або часу виконання запиту за шаблоном, який не залежить від довжини тексту.

Часті запитання

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте Suffix Automaton: The Compressed Map of Every Substring і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.