Отправить статью по E-mail Алгоритм построения ориентированного ациклического графа слов
- Авторы: Шиян В.И.1
-
Учреждения:
- Кубанский государственный университет
- Выпуск: № 3 (2024)
- Страницы: 104-112
- Раздел: Анализ текстовой и графической информации
- URL: https://ogarev-online.ru/2071-8594/article/view/265362
- DOI: https://doi.org/10.14357/20718594240308
- EDN: https://elibrary.ru/JUSFEQ
- ID: 265362
Цитировать
Полный текст
Аннотация
Алгоритм, представленный в статье, позволяет эффективно строить и модифицировать минимальные детерминированные конечные автоматы для распознавания заданного множества слов, в том числе при обработке большого объёма информации в реальном времени. Ключевой особенностью алгоритма является возможность добавления новых слов в автомат и его последующая минимизация «на лету». Алгоритм основан на лексикографическом упорядочении множества входных слов и обладает низкой вычислительной сложностью по сравнению с традиционными алгоритмами, такими как алгоритм Хопкрофта или алгоритм, использующий построение пар различимых состояний. Разработка данного алгоритма направлена на повышение скорости построения минимальных детерминированных конечных автоматов и их модификации для эффективной обработки естественного языка и анализа web-контента в реальном времени.
Об авторах
Валерий Игоревич Шиян
Кубанский государственный университет
Автор, ответственный за переписку.
Email: shiyanvi@yandex.ru
преподаватель кафедры вычислительных технологий
Россия, КраснодарСписок литературы
- Daciuk J., Mihov S., Watson B.W., Watson R.E. Incremental construction of minimal acyclic finite-state automata // Computational Linguistics. 2000. V. 26. No 1. P. 3-16.
- Watson B.W. A taxonomy of finite automata construction algorithms // Computing Science Notes. V. 9343, 1993.
- Black P.E., Pieterse V. Directed acyclic word graph // Dictionary of Algorithms and Data Structures. 1998.
- Blumer A.C., Blumer J.A., Haussler D., Ehrenfeucht A., Chen M.-T., Seiferas J.I. The smallest automation recognizing the subwords of a text // Theoretical Computer Science. 1985. P. 31-55.
- Lucchesi C.L., Kowaltowski T. Applications of finite automata representing large vocabularies // Software: Practice and Experience. 1993. V. 23. No 1. P. 15-30.
- Ciura M.G., Deorowicz S. How to squeeze a lexicon. Software: Practice and Experience. 2001. V. 31. No 11. P. 1077-1090.
- Crochemore M., Vérin R. On compact directed acyclic word graphs // In Structures in Logic and Computer Science. 1997. P. 192-211.
- Daciuk J., Watson B.W., Watson R.E. Incremental construction of minimal acyclic finite state automata and transducers // Proceedings of the International Workshop on Finite State Methods in Natural Language Processing. 1998. P. 48-56.
- Mihov S. Direct building of minimal automaton for given list // Annuaire de l’Université de Sofia. 1998. V. 91. No 1. P. 38-40.
- Kuznetsov O. P., Adelson-Velsky G. M. Avtomaty// Diskretnaya matematika dlya ingenerov [Automata // Discrete Mathematics for Engineers]. Moscow: Energiya, 1980. 344 p.
- Moll R.N., Arbib M.A., Kfoury A.J. An introduction to formal language theory. Springer-Verlag, 1988.
- Watson B.W. Taxonomies and Toolkits of Regular Language Algorithms. Ph.D. thesis, Eindhoven University of Technology, the Netherlands. 1995.
- Hopcroft D., Motwani R., Ullman D. Vvedenie v teoriyu avtomatov, yazykov i vychisleniy. Uchebnik. 2-e izdanie. [Introduction to Automata Theory, Languages, and Computation: Textbook: 2nd Edition]. Moscow: Williams Publishers. 2002. 61 p.
Дополнительные файлы
