Суфіксний автомат

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку
Суфіксний автомат
Тип Індекс підрядків
Винайдено 1983
Винайшли Ансельм Блумер, Джанет Блумер, Анджей Еренфехт, Девід Хаусслер, Росс Макконнелл
Обчислювальна складність
у записі великого О
Середня Найгірша
Простір
Пошук
Вставляння
Видалення
Суфіксний автомат для abbcbc.

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

Суфіксний автомат був вперше описаний групою вчених з Денверського і Колорадського університетів в 1983 році, вони ж показали, що розмір автомата лінійно залежить від довжини , а також запропонували онлайн алгоритм для його побудови з лінійним часом роботи. У подальших роботах на цю тему був виявлений ​​тісний зв'язок суфіксного автомата з суфікснимі деревами, а сама концепція суфіксного автомата отримала різні узагальнення. Так були введені стислий суфіксний автомат, який отримують із вихідного процедурою, аналогічною тій, яка застосовується до префіксного дерева для отримання суфіксного дерева, а також узагальнений суфіксний автомат, який будується для набору слів і приймає слова, які є суфіксами хоча б одного з цих.

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

Застосування

[ред. | ред. код]

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

  • Підрахунок кількості різних підрядків за час в режимі онлайн,
  • Пошук найдовшого підрядка , що входить в неї хоча б два рази, за час ,
  • Пошук найдовшого спільного підрядка рядків і за час ,
  • Підрахунок кількості входжень рядка в в якості підрядка за час ,
  • Пошук всіх входжень в за час , де  — кількість входжень.

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

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

Примітки

[ред. | ред. код]

Література

[ред. | ред. код]