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

Суфіксний автомат для abbcbc.

Су́фіксний автома́т (Шаблон:Lang-en) — структура даних, що дозволяє зберігати в стислому вигляді і обробляти інформацію, пов'язану з підрядками одного рядка. Є детермінованим скінченним автоматом, який приймає всі суфікси слова $S=s_1{s}_2\dots s_n$ і тільки їх, і що має найменшу можливу кількість станів серед всіх таких автоматів. Менш формально, суфіксний автомат — це орієнтований ациклічний граф з виділеною початковою вершиною і набором «фінальних» вершин, дуги якого позначені символами, такий що у будь-якої вершини символи на вихідних з неї дугах попарно різні і для будь-якого суфікса слова $S$ існує шлях з початкової вершини в деяку фінальну вершину, символи на якому при конкатенації утворюють даний суфікс. З усіх графів, які відповідають даним опису, суффіксним автоматом називається той, який володіє найменшим можливим числом вершин.

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

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

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

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

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

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

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

Література

• {{#invoke:Sources|renderSource|Q99428232|ref=Sgarbas et al.}}
• {{#invoke:Sources|renderSource|Q99428342|ref=Perrin}}
• {{#invoke:Sources|renderSource|Q29541479|ref=Weiner}}
• {{#invoke:Sources|renderSource|Q90300966|ref=Pratt}}
• {{#invoke:Sources|renderSource|Q90305414|ref=Slisenko}}
• {{#invoke:Sources|renderSource|Q90309073|ref=Blumer et al.}}
• {{#invoke:Sources|renderSource|Q90311855|ref=Blumer et al.}}
• {{#invoke:Sources|renderSource|Q90327976|ref=Blumer}}
• {{#invoke:Sources|renderSource|Q90329833|ref=Chen, Seiferas}}
• {{#invoke:Sources|renderSource|Q90335534|ref=Inenaga}}
• {{#invoke:Sources|renderSource|Q57518591|ref=Inenaga et al.}}
• {{#invoke:Sources|renderSource|Q90341606|ref=Inenaga et al.}}
• {{#invoke:Sources|renderSource|Q90345535|ref=Inenaga et al.}}
• {{#invoke:Sources|renderSource|Q90348192|ref=Yamamoto et al.}}
• {{#invoke:Sources|renderSource|Q90410044|ref=Fujishige et al.}}
• {{#invoke:Sources|renderSource|Q90410808|ref=Mohri et al.}}
• {{#invoke:Sources|renderSource|Q90412338|ref=Faro}}
• {{#invoke:Sources|renderSource|Q90413384|ref=Crochemore, Hancart}}
• {{#invoke:Sources|renderSource|Q90413885|ref=Crochemore, Vérin}}
• {{#invoke:Sources|renderSource|Q90414195|ref=Crochemore et al.}}
• {{#invoke:Sources|renderSource|Q90418603|ref=Hopcroft, Ullman}}
• {{#invoke:Sources|renderSource|Q90425560|ref=Fiala, Greene}}
• {{#invoke:Sources|renderSource|Q90426624|ref=Senft, Dvořák}}
• {{#invoke:Sources|renderSource|Q90427112|ref=Larsson}}
• {{#invoke:Sources|renderSource|Q90431196|ref=Brodnik, Jekovec}}
• {{#invoke:Sources|renderSource|Q90726647|ref=Rubinchik, Shur}}
• {{#invoke:Sources|renderSource|Q90432456|ref=Серебряков и др.}}
• {{#invoke:Sources|renderSource|Q90435728|ref=Рубцов}}
• {{#invoke:Sources|renderSource|Q90436837|ref=Паращенко}}