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

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

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

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

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

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

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

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

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

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

Примітки

Література

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.