Суфіксний автомат
Су́фіксний автома́т (англ. suffix automaton, directed acyclic word graph) — структура даних, що дозволяє зберігати в стислому вигляді і обробляти інформацію, пов'язану з підрядками одного рядка. Є детермінованим скінченним автоматом, який приймає всі суфікси слова і тільки їх, і що має найменшу можливу кількість станів серед всіх таких автоматів. Менш формально, суфіксний автомат — це орієнтований ациклічний граф з виділеною початковою вершиною і набором «фінальних» вершин, дуги якого позначені символами, такий що у будь-якої вершини символи на вихідних з неї дугах попарно різні і для будь-якого суфікса слова існує шлях з початкової вершини в деяку фінальну вершину, символи на якому при конкатенації утворюють даний суфікс. З усіх графів, які відповідають даним опису, суффіксним автоматом називається той, який володіє найменшим можливим числом вершин.
| Суфіксний автомат | ||
|---|---|---|
| Тип | Індекс підрядків | |
| Винайдено | 1983 | |
| Винайшли | Ансельм Блумер, Джанет Блумер, Анджей Еренфехт, Девід Хаусслер, Росс Макконнелл | |
| Обчислювальна складність у записі великого О | ||
| Середня | Найгірша | |
| Простір | ||
| Пошук | ||
| Вставляння | ||
| Видалення | ||
abbcbc.Суфіксний автомат був вперше описаний групою вчених з Денверського і Колорадського університетів в 1983 році, вони ж показали, що розмір автомата лінійно залежить від довжини , а також запропонували онлайн алгоритм для його побудови з лінійним часом роботи. У подальших роботах на цю тему був виявлений тісний зв'язок суфіксного автомата з суфікснимі деревами, а сама концепція суфіксного автомата отримала різні узагальнення. Так були введені стислий суфіксний автомат, який отримують із вихідного процедурою, аналогічною тій, яка застосовується до префіксного дерева для отримання суфіксного дерева, а також узагальнений суфіксний автомат, який будується для набору слів і приймає слова, які є суфіксами хоча б одного з цих.
За допомогою суфіксного автомата можна ефективно розв'зувати такі задачі як пошук підрядка в рядку, визначення найдовшого спільного підрядка двох і більше рядків тощо.
Застосування
Суфіксний автомат рядка може використовуватися для розв'язання таких задач, як[1][2]:
- Підрахунок кількості різних підрядків за час в режимі онлайн,
- Пошук найдовшого підрядка , що входить в неї хоча б два рази, за час ,
- Пошук найдовшого спільного підрядка рядків і за час ,
- Підрахунок кількості входжень рядка в в якості підрядка за час ,
- Пошук всіх входжень в за час , де — кількість входжень.
Тут варто вважати, що деякий рядок подається на вхід, коли автомат вже побудований і готовий до використання.
Суфіксні автомати також знайшли своє застосування в таких прикладних задачах, як стиснення даних[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, 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, 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-Verlag, 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 — NYC: ACM, 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
- Inenaga S., Hoshino H., Shinohara A. et al. On-line construction of compact directed acyclic word graphs // Discrete Applied Mathematics — Elsevier, 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, 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, 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. Martín-Vide, M. A. Vega-Rodríguez — Springer International Publishing, 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 — NYC, USA: ACM, 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
- N. Jesper Larsson Extended application of suffix trees to data compression // Proceedings. Data Compression Conference — IEEE, 1996. — P. 190–199. — ISBN 0-8186-7358-3 — ISSN 2375-0383; 2375-0391; 1068-0314; 2375-0359 — doi:10.1109/DCC.1996.488324
- 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, 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 с.