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