Суфіксний автомат для abbcbc. Су́фіксний автома́т (англ. suffix automaton, directed acyclic word graph ) — структура даних , що дозволяє зберігати в стислому вигляді і обробляти інформацію, пов'язану з підрядками одного рядка. Є детермінованим скінченним автоматом , який приймає всі суфікси слова
S
=
s
1
s
2
…
s
n
{\displaystyle S=s_{1}s_{2}\dots s_{n}}
найменшу можливу кількість станів серед всіх таких автоматів. Менш формально, суфіксний автомат — це орієнтований ациклічний граф з виділеною початковою вершиною і набором «фінальних» вершин, дуги якого позначені символами , такий що у будь-якої вершини символи на вихідних з неї дугах попарно різні і для будь-якого суфікса слова
S
{\displaystyle S}
шлях з початкової вершини в деяку фінальну вершину, символи на якому при конкатенації утворюють даний суфікс. З усіх графів, які відповідають даним опису, суффіксним автоматом називається той, який володіє найменшим можливим числом вершин.
Суфіксний автомат був вперше описаний групою вчених з Денверського і Колорадського університетів в 1983 році, вони ж показали, що розмір автомата лінійно залежить від довжини
S
{\displaystyle S}
онлайн алгоритм для його побудови з лінійним часом роботи . У подальших роботах на цю тему був виявлений тісний зв'язок суфіксного автомата з суфікснимі деревами , а сама концепція суфіксного автомата отримала різні узагальнення. Так були введені стислий суфіксний автомат, який отримують із вихідного процедурою, аналогічною тій, яка застосовується до префіксного дерева для отримання суфіксного дерева, а також узагальнений суфіксний автомат, який будується для набору слів
S
1
,
S
2
,
…
,
S
k
{\displaystyle S_{1},S_{2},\dots ,S_{k}}
За допомогою суфіксного автомата можна ефективно розв'зувати такі задачі як пошук підрядка в рядку , визначення найдовшого спільного підрядка двох і більше рядків тощо.
Суфіксний автомат рядка
S
{\displaystyle S}
[ 1] [ 2]
Підрахунок кількості різних підрядків
S
{\displaystyle S}
O
(
|
S
|
)
{\displaystyle O(|S|)}
Пошук найдовшого підрядка
S
{\displaystyle S}
O
(
|
S
|
)
{\displaystyle O(|S|)}
Пошук найдовшого спільного підрядка рядків
S
{\displaystyle S}
T
{\displaystyle T}
O
(
|
T
|
)
{\displaystyle O(|T|)}
Підрахунок кількості входжень рядка
T
{\displaystyle T}
S
{\displaystyle S}
O
(
|
T
|
)
{\displaystyle O(|T|)}
Пошук всіх входжень
T
{\displaystyle T}
S
{\displaystyle S}
O
(
|
T
|
+
k
)
{\displaystyle O(|T|+k)}
k
{\displaystyle k}
Тут варто вважати, що деякий рядок
T
{\displaystyle T}
Суфіксні автомати також знайшли своє застосування в таких прикладних задачах, як стиснення даних[ 3] [ 4] [ 5] [ 6]
↑ Crochemore, Hancart, 1997 , pp. 39—41↑ Crochemore, Hancart, 1997 , pp. 36—39↑ Yamamoto et al., 2014 , p. 675↑ Crochemore et al., 2003 , p. 211↑ Mohri et al., 2009 , p. 3553↑ Faro, 2016 , p. 145
Sgarbas K. N., Fakotakis N. D., Kokkinakis G. K. Optimal insertion in deterministic DAWGs // Theoretical Computer Science — Elsevier BV , 2003. — Vol. 301, Iss. 1-3. — P. 103–117. — ISSN 0304-3975 ; 1879-2294 — doi:10.1016/S0304-3975(02)00571-6 Perrin D. Finite Automata // Formal Models and Semantics Handbook of Theoretical Computer Science / J. v. Leeuwen — Elsevier BV , 1990. — Vol. B. — P. 1–57. — ISBN 978-0-444-88074-1 — doi:10.1016/B978-0-444-88074-1.50006-8 Weiner P. Linear pattern matching algorithms // Symposium on Foundations of Computer Science — 1973. — P. 1–11. — 213 p. — doi:10.1109/SWAT.1973.13 Pratt V. R. Improvements and applications for the Weiner repetition finder — 1973. Slisenko A. O. Detection of periodicities and string-matching in real time // Journal of Soviet mathematics — Springer Science+Business Media , 1983. — Vol. 22, Iss. 3. — P. 1316–1387. — ISSN 1072-3374 ; 1573-8795 — doi:10.1007/BF01084395 Blumer A. C. , Blumer J. , Ehrenfeucht A. et al.Building the minimal DFA for the set of all subwords of a word on-line in linear time // Automata, Languages and Programming — 1984. — P. 109–118. — 526 p. — ISBN 978-3-540-13345-2 — doi:10.1007/3-540-13345-3_9 Blumer A. C. , Blumer J. , Ehrenfeucht A. et al.Complete inverted files for efficient text retrieval and analysis // J. ACM / D. J. Rosenkrantz — New York, N.Y. : Association for Computing Machinery , 1987. — Vol. 34, Iss. 3. — P. 578–595. — ISSN 0004-5411 — doi:10.1145/28869.28873 Blumer J. How much is that DAWG in the window? A moving window algorithm for the directed acyclic word graph // Journal of Algorithms — Academic Press , 1987. — Vol. 8, Iss. 4. — P. 451–469. — ISSN 0196-6774 ; 1090-2678 — doi:10.1016/0196-6774(87)90045-9 Chen M., Seiferas J. Efficient and Elegant Subword-Tree Construction // Combinatorial Algorithms on Words / A. Apostolico , Z. Galil — Springer Berlin Heidelberg , 1985. — P. 97–107. — ISBN 978-3-642-82456-2 — doi:10.1007/978-3-642-82456-2_7 Inenaga S. Bidirectional Construction of Suffix Trees // Nordic Journal of Computing — 2003. — Vol. 10, Iss. 1. — P. 52–67. — ISSN 1236-6064 Mauri G. On-line construction of compact directed acyclic word graphs // Discrete Applied Mathematics — Elsevier BV , 2005. — Vol. 146, Iss. 2. — P. 156–179. — ISSN 0166-218X ; 1872-6771 — doi:10.1016/J.DAM.2004.04.012 Inenaga S., Hoshino H., Shinohara A. et al. Construction of the CDAWG for a trie // Prague Stringology Conference — Czech Technical University in Prague : 2001. — P. 37–48. Inenaga S., Shinohara A., Takeda M. et al. Compact directed acyclic word graphs for a sliding window // Journal of Discrete Algorithms — Elsevier BV , 2004. — Vol. 2, Iss. 1. — P. 33–51. — ISSN 1570-8667 ; 1570-8675 — doi:10.1016/S1570-8667(03)00064-9 Yamamoto J., Tomohiro I, Bannai H. et al. Faster Compact On-Line Lempel-Ziv Factorization // Symposium on Theoretical Aspects of Computer Science / E. Mayr , N. Portier — 2014. — Vol. 25. — P. 675–686. — ISBN 978-3-939897-65-1 — ISSN 1868-8969 — doi:10.4230/LIPICS.STACS.2014.675 Fujishige Y., Tsujimaru Y., Inenaga S. et al. Computing DAWGs and Minimal Absent Words in Linear Time for Integer Alphabets // Mathematical Foundations of Computer Science / P. Faliszewski , A. Muscholl , R. Niedermeier — 2016. — Vol. 58. — P. 38:1–38:14. — ISBN 978-3-95977-016-3 — ISSN 1868-8969 — doi:10.4230/LIPICS.MFCS.2016.38 Mohri M., Moreno P., Weinstein E. General suffix automaton construction algorithm and space bounds // Theoretical Computer Science — Elsevier BV , 2009. — Vol. 410, Iss. 37. — P. 3553–3562. — ISSN 0304-3975 ; 1879-2294 — doi:10.1016/J.TCS.2009.03.034 Faro S. Evaluation and Improvement of Fast Algorithms for Exact Matching on Genome Sequences // Algorithms for Computational Biology / M. Botón-Fernández , C. M. Vide , M. A. Vega-Rodríguez — Springer Nature Switzerland AG , 2016. — P. 145–157. — ISBN 978-3-319-38827-4 — doi:10.1007/978-3-319-38827-4_12 Crochemore M. , Hancart C. Automata for Matching Patterns // Handbook of Formal Languages / G. Rozenberg , A. Salomaa — Springer Berlin Heidelberg , 1997. — Vol. 2. — P. 399–462. — ISBN 978-3-642-59136-5 — doi:10.1007/978-3-662-07675-0_9 Crochemore M. , Vérin R. On compact directed acyclic word graphs // Structures in Logic and Computer Science A Selection of Essays in Honor of A. Ehrenfeucht / J. Mycielski , G. Rozenberg , A. Salomaa — Springer Berlin Heidelberg , 1997. — P. 192–211. — ISBN 978-3-540-69242-3 — doi:10.1007/3-540-63246-8_12 Crochemore M. , Iliopoulos C. S. , Navarro G. et al.A Bit-Parallel Suffix Automaton Approach for (δ,γ)-Matching in Music Retrieval // String Processing and Information Retrieval / M. A. Nascimento , Edleno S. de Moura , A. L. Oliveira — Springer Berlin Heidelberg , 2003. — P. 211–223. — ISBN 978-3-540-39984-1 — doi:10.1007/978-3-540-39984-1_16 Hopcroft J. E. , Ullman J. D. Introduction to Automata Theory, Languages, and Computation — 1 — MA : Addison-Wesley , 1979. — 418 p. — ISBN 978-81-7808-347-6 Fiala E. R., Greene D. H. Data compression with finite windows // Commun. ACM — [New York] : Association for Computing Machinery , 1989. — Vol. 32, Iss. 4. — P. 490–505. — ISSN 0001-0782 ; 1557-7317 — doi:10.1145/63334.63341 Senft M., Dvořák T. Sliding CDAWG Perfection // String Processing and Information Retrieval / A. Turpin , A. Moffat , A. Amir — Springer Berlin Heidelberg , 2008. — P. 109–120. — ISBN 978-3-540-89097-3 — doi:10.1007/978-3-540-89097-3_12 Brodnik A. , Jekovec M. Sliding Suffix Tree // Algorithms — MDPI , 2018. — Vol. 11, Iss. 8. — P. 118. — ISSN 1999-4893 — doi:10.3390/A11080118 Rubinchik M., Shur A. M. Eertree : An efficient data structure for processing palindromes in strings // European Journal of Combinatorics / Patrice Ossona de Mendez , P. Rosenstiehl , Éric Colin de Verdière et al. — Elsevier BV , 2018. — Vol. 68. — P. 249–265. — ISSN 0195-6698 ; 1095-9971 — doi:10.1016/J.EJC.2017.07.021 — arXiv:1506.04862 Серебряков В. А. , Галочкин М. П. , Фуругян М. Г. и др.Теория и реализация языков программирования : Учебное пособие — Москва : МЗ Пресс , 2006. — 352 с. — ISBN 5-94073-094-9 Рубцов А. А. Заметки и задачи о регулярных языках и конечных автоматах — Москва : МФТИ , 2019. — 112 с. — ISBN 978-5-7417-0702-9 Паращенко Д. А. Обработка строк на основе суффиксных автоматов — СПб : ИТМО , 2007. — 35 с.
