Алгоритм построения ориентированного ациклического графа слов

Обложка

Цитировать

Полный текст

Аннотация

Алгоритм, представленный в статье, позволяет эффективно строить и модифицировать минимальные детерминированные конечные автоматы для распознавания заданного множества слов, в том числе при обработке большого объёма информации в реальном времени. Ключевой особенностью алгоритма является возможность добавления новых слов в автомат и его последующая минимизация «на лету». Алгоритм основан на лексикографическом упорядочении множества входных слов и обладает низкой вычислительной сложностью по сравнению с традиционными алгоритмами, такими как алгоритм Хопкрофта или алгоритм, использующий построение пар различимых состояний. Разработка данного алгоритма направлена на повышение скорости построения минимальных детерминированных конечных автоматов и их модификации для эффективной обработки естественного языка и анализа web-контента в реальном времени.

Об авторах

Валерий Игоревич Шиян

Кубанский государственный университет

Автор, ответственный за переписку.
Email: shiyanvi@yandex.ru

преподаватель кафедры вычислительных технологий

Россия, Краснодар

Список литературы

  1. 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.
  2. Watson B.W. A taxonomy of finite automata construction algorithms // Computing Science Notes. V. 9343, 1993.
  3. Black P.E., Pieterse V. Directed acyclic word graph // Dictionary of Algorithms and Data Structures. 1998.
  4. 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.
  5. Lucchesi C.L., Kowaltowski T. Applications of finite automata representing large vocabularies // Software: Practice and Experience. 1993. V. 23. No 1. P. 15-30.
  6. Ciura M.G., Deorowicz S. How to squeeze a lexicon. Software: Practice and Experience. 2001. V. 31. No 11. P. 1077-1090.
  7. Crochemore M., Vérin R. On compact directed acyclic word graphs // In Structures in Logic and Computer Science. 1997. P. 192-211.
  8. 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.
  9. Mihov S. Direct building of minimal automaton for given list // Annuaire de l’Université de Sofia. 1998. V. 91. No 1. P. 38-40.
  10. Kuznetsov O. P., Adelson-Velsky G. M. Avtomaty// Diskretnaya matematika dlya ingenerov [Automata // Discrete Mathematics for Engineers]. Moscow: Energiya, 1980. 344 p.
  11. Moll R.N., Arbib M.A., Kfoury A.J. An introduction to formal language theory. Springer-Verlag, 1988.
  12. Watson B.W. Taxonomies and Toolkits of Regular Language Algorithms. Ph.D. thesis, Eindhoven University of Technology, the Netherlands. 1995.
  13. 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.

Дополнительные файлы

Доп. файлы
Действие
1. JATS XML
Скачать

Согласие на обработку персональных данных

 

Используя сайт https://journals.rcsi.science, я (далее – «Пользователь» или «Субъект персональных данных») даю согласие на обработку персональных данных на этом сайте (текст Согласия) и на обработку персональных данных с помощью сервиса «Яндекс.Метрика» (текст Согласия).