Детерминированный ациклический конечный автомат
В информатике — детерминированный ациклический конечный автомат ( DAFSA ), [1] — это структура данных , которая представляет набор строк и позволяет выполнять операцию запроса, проверяющую, принадлежит ли данная строка набору за время, пропорциональное ее длине. Существуют алгоритмы для создания и обслуживания таких автоматов . [1] сохраняя при этом их минимальными .DAFSA — это повторное открытие структуры данных под названием «Направленный ациклический граф слов» (DAWG). [2] хотя то же имя уже было присвоено другой структуре данных, связанной с суффиксом автомат . [3]
DAFSA — это частный случай конечного распознавателя состояний , который принимает форму ориентированного ациклического графа с одной исходной вершиной (вершина без входящих ребер), в которой каждое ребро графа помечено буквой или символом, и в котором каждая вершина имеет не более одного исходящего ребра для каждой возможной буквы или символа. Строки, представленные DAFSA, формируются символами на путях графа от исходной вершины до любой приемной вершины (вершины без исходящих ребер). Фактически, детерминированный конечный автомат является ациклическим тогда и только тогда, когда он распознает конечный набор строк . [1]
История
[ редактировать ]Блумер и др. [3] впервые определенная терминология Направленный ациклический граф слов (DAWG) в 1983 году. Аппель и Якобсен [2] использовали то же название для другой структуры данных в 1988 году. Независимо от более ранних работ, Daciuk et al. [1] заново открыл последнюю структуру данных в 2000 году, но назвал ее DAFSA.
Сравнение с попытками
[ редактировать ]Позволяя достигать одних и тех же вершин несколькими путями, 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 не может напрямую хранить вспомогательную информацию, относящуюся к каждому пути, например, частоту употребления слов в английском языке. Однако если для каждого узла мы сохраним количество уникальных путей через эту точку структуры, мы сможем использовать его для получения индекса слова или слова по его индексу. [4] Вспомогательная информация затем может быть сохранена в массиве.
Ссылки
[ редактировать ]- ^ Перейти обратно: а б с д Ян Дачук, Стоян Михов, Брюс Уотсон и Ричард Уотсон (2000). Инкрементальное построение минимальных ациклических конечных автоматов. Компьютерная лингвистика 26 (1):3-16.
- ^ Перейти обратно: а б Аппель, Эндрю; Якобсен, Гай (1988). Самая быстрая в мире программа скрэббл. Сообщения ACM, 31 (5): 572–578.
- ^ Перейти обратно: а б Ансельм Блюмер, Джанет Блумер, Анджей Эренфойхт, Дэвид Хаусслер, Росс М. МакКоннелл (1983). Конечные автоматы линейного размера для множества всех подслов слова - схема результатов. Бык Европа. доц. Теория. Вычислить. Наука, 21 : 12-20
- ^ Ковальтовски, Т.; С.Л. Луккези (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-Publishers , стр. 101–1. стр. 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 ).