Суфіксний автомат — Вікіпедія

Суфіксний автомат
Тип	Індекс підрядків
Винайдено	1983
Винайшли	Ансельм Блумер, Джанет Блумер, Анджей Еренфехт, Девід Хаусслер, Росс Макконнелл
Обчислювальна складність у записі великого О
	Середня	Найгірша
Простір	${\displaystyle O(n)}$	${\displaystyle O(n)}$
Пошук
Вставляння
Видалення

Су́фіксний автома́т (англ. suffix automaton, directed acyclic word graph) — структура даних, що дозволяє зберігати в стислому вигляді і обробляти інформацію, пов'язану з підрядками одного рядка. Є детермінованим скінченним автоматом, який приймає всі суфікси слова ${\displaystyle S=s_{1}s_{2}\dots s_{n}}$ і тільки їх, і що має найменшу можливу кількість станів серед всіх таких автоматів. Менш формально, суфіксний автомат — це орієнтований ациклічний граф з виділеною початковою вершиною і набором «фінальних» вершин, дуги якого позначені символами, такий що у будь-якої вершини символи на вихідних з неї дугах попарно різні і для будь-якого суфікса слова ${\displaystyle S}$ існує шлях з початкової вершини в деяку фінальну вершину, символи на якому при конкатенації утворюють даний суфікс. З усіх графів, які відповідають даним опису, суффіксним автоматом називається той, який володіє найменшим можливим числом вершин.

Суфіксний автомат був вперше описаний групою вчених з Денверського і Колорадського університетів в 1983 році, вони ж показали, що розмір автомата лінійно залежить від довжини ${\displaystyle S}$, а також запропонували онлайн алгоритм для його побудови з лінійним часом роботи. У подальших роботах на цю тему був виявлений ​​тісний зв'язок суфіксного автомата з суфікснимі деревами, а сама концепція суфіксного автомата отримала різні узагальнення. Так були введені стислий суфіксний автомат, який отримують із вихідного процедурою, аналогічною тій, яка застосовується до префіксного дерева для отримання суфіксного дерева, а також узагальнений суфіксний автомат, який будується для набору слів ${\displaystyle S_{1},S_{2},\dots ,S_{k}}$ і приймає слова, які є суфіксами хоча б одного з цих.

За допомогою суфіксного автомата можна ефективно розв'зувати такі задачі як пошук підрядка в рядку, визначення найдовшого спільного підрядка двох і більше рядків тощо.

Суфіксний автомат рядка ${\displaystyle S}$ може використовуватися для розв'язання таких задач, як^[1][2]:

• Підрахунок кількості різних підрядків ${\displaystyle S}$ за час ${\displaystyle O(|S|)}$ в режимі онлайн,
• Пошук найдовшого підрядка ${\displaystyle S}$, що входить в неї хоча б два рази, за час ${\displaystyle O(|S|)}$,
• Пошук найдовшого спільного підрядка рядків ${\displaystyle S}$ і ${\displaystyle T}$ за час ${\displaystyle O(|T|)}$,
• Підрахунок кількості входжень рядка ${\displaystyle T}$ в ${\displaystyle S}$ в якості підрядка за час ${\displaystyle O(|T|)}$,
• Пошук всіх входжень ${\displaystyle T}$ в ${\displaystyle S}$ за час ${\displaystyle O(|T|+k)}$, де ${\displaystyle k}$ — кількість входжень.

Тут варто вважати, що деякий рядок ${\displaystyle T}$ подається на вхід, коли автомат вже побудований і готовий до використання.

Суфіксні автомати також знайшли своє застосування в таких прикладних задачах, як стиснення даних^[3], ідентифікація музики із записаних фрагментів^[4][5] і зіставлення геномних послідовностей^[6].