Детерминированный ациклический конечный автомат
В информатике — детерминированный ациклический конечный автомат ( DAFSA ), [1] также называется направленным ациклическим графом слов ( DAWG ; хотя это имя также относится к связанной структуре данных , которая функционирует как суффиксный индекс [2] ) — это структура данных , которая представляет набор строк и позволяет выполнять операцию запроса, проверяющую, принадлежит ли данная строка набору за время, пропорциональное ее длине. Существуют алгоритмы для создания и обслуживания таких автоматов . [1] сохраняя при этом их минимальными .
DAFSA — это частный случай конечного распознавателя состояний , который принимает форму ориентированного ациклического графа с одной исходной вершиной (вершина без входящих ребер), в которой каждое ребро графа помечено буквой или символом, и в котором каждая вершина имеет не более одного исходящего ребра для каждой возможной буквы или символа. Строки, представленные DAFSA, формируются символами на путях графа от исходной вершины до любой вершины-приемника (вершины без исходящих ребер). Фактически, детерминированный конечный автомат является ациклическим тогда и только тогда, когда он распознает конечный набор строк . [1]
Сравнение с попытками [ править ]
Позволяя достигать одних и тех же вершин несколькими путями, DAFSA может использовать значительно меньше вершин, чем сильно связанная структура данных дерева . Рассмотрим, например, четыре английских слова «tap», «taps», «top» и «tops». Дерево для этих четырех слов будет иметь 12 вершин, по одной для каждой строки, сформированной как префикс одного из этих слов, или для одного из слов, за которым следует маркер конца строки. Однако DAFSA может представлять те же четыре слова, используя только шесть вершин v i для 0 ≤ i ≤ 5 и следующие ребра: ребро от v 0 до v 1 , помеченное как «t», два ребра от v 1 до v 2 , помеченные как «t». «a» и «o», ребро от v 2 до v 3 , помеченное как «p», ребро от v 3 до v 4 , помеченное как «s», и ребра от v 3 и v 4 до v 5 , помеченные концом -строковый маркер. Существует компромисс между памятью и функциональностью, поскольку стандартный DAFSA может сказать вам, существует ли в нем слово, но он не может указать вам вспомогательную информацию об этом слове, тогда как trie может.
Основное различие между DAFSA и trie заключается в устранении избыточности суффиксов и инфиксов при хранении строк. Дерево исключает избыточность префиксов, поскольку все общие префиксы являются общими для всех строк, например, между и докторской степенью префикс врача врачами является общим. В DAFSA также используются общие суффиксы для слов, которые имеют одинаковый набор возможных суффиксов, что и друг друга. Для словарных наборов общеупотребительных английских слов это приводит к значительному сокращению использования памяти.
Поскольку к конечным узлам DAFSA можно добраться по нескольким путям, DAFSA не может напрямую хранить вспомогательную информацию, относящуюся к каждому пути, например, частоту употребления слов в английском языке. Однако если для каждого узла мы сохраним количество уникальных путей через эту точку структуры, мы сможем использовать его для получения индекса слова или слова по его индексу. [3] Вспомогательная информация затем может быть сохранена в массиве.
Ссылки [ править ]
- ^ Перейти обратно: а б с Ян Дачук, Стоян Михов, Брюс Уотсон и Ричард Уотсон (2000). Инкрементальное построение минимальных ациклических конечных автоматов. Компьютерная лингвистика 26 (1):3-16.
- ^
В этой статье использованы общедоступные материалы из Пол Э. Блэк. «направленный ациклический граф слов» . Словарь алгоритмов и структур данных . НИСТ .
- ^ Ковальтовски, Т.; С.Л. Луккези (1993). «Приложения конечных автоматов, представляющих большие словари». Программное обеспечение-практика и опыт . 1993 : 15–30. CiteSeerX 10.1.1.56.5272 .
- Блюмер, А.; Блумер, Дж.; Хаусслер, Д.; Эренфойхт, А.; Чен, Монтана; Сейферас, Дж. (1985), «Наименьший автомат, распознающий подслова текста», Theoretical Computer Science , 40 : 31–55, doi : 10.1016/0304-3975(85)90157-4
- Аппель, Эндрю; Якобсен, Гай (1988), «Самая быстрая в мире программа скрэббл» (PDF) , Communications of the ACM , 31 (5): 572–578, doi : 10.1145/42411.42420 . Одно из первых упоминаний о структуре данных.
- Янсен, Сис Дж.А.; Боки, Дик Э. (1990), «О значении направленного ациклического графа слов в криптологии», « Достижения в криптологии – AUSCRYPT '90» , «Конспекты лекций по информатике» , том. 453, Springer-Verlag , стр. 318–326, doi : 10.1007/BFb0030372 , ISBN. 3-540-53000-2 .
- Эпифанио, Кьяра; Миньози, Филиппо; Шалит, Джеффри; Вентурини, Илария (2004), «Графы Штурма и гипотеза Мозера», в Калуде, Кристиан С.; Калуд, Елена; Дайнин, Майкл Дж. (ред.), Развитие теории языка. Труды 8-й международной конференции (DLT 2004), Окленд, Новая Зеландия, декабрь 2004 г. , Конспекты лекций по информатике, том. 3340, Springer-Verlag , стр. 175–187, ISBN. 3-540-24014-4 , Збл 1117.68454
- Тресольди, Тьяго (2020), «DAFSA: библиотека Python для детерминированных ациклических автоматов с конечным состоянием», Журнал программного обеспечения с открытым исходным кодом , 5 (46): 1986, doi : 10.21105/joss.01986 , hdl : 21.11116/0000-0005- AD0D-B Реализация с открытым исходным кодом Python .
Внешние ссылки [ править ]
- « Направленный ациклический граф слов или DAWG » - Джон Пол Адамовский учит, как построить DAFSA с использованием массива целых чисел ( архивировано 22 июля 2022 г. в Wayback Machine ).
- « Граф Кэролайн Word или CWG » - Джон Пол Адамовский учит, как построить хеш-функцию DAFSA с использованием новой кодировки с несколькими целочисленными массивами ( архивировано 27 июля 2022 г. на Wayback Machine ).