Детерминированный ациклический конечный автомат - Deterministic acyclic finite state automaton

Строки «tap», «taps», «top» и «tops» хранятся в три (слева) и DAFSA (справа), EOW означает конец слова.

В Информатика, а детерминированный ациклический конечный автомат (DAFSA),[1]также называется ориентированный ациклический граф слов (DAWG; хотя это имя также относится к связанная структура данных который функционирует как индекс суффикса[2])это структура данных что представляет собой набор струны, и позволяет выполнять операцию запроса, которая проверяет, принадлежит ли данная строка набору во времени, пропорциональном ее длине. Существуют алгоритмы для создания и обслуживания таких автоматов,[1] сохраняя их минимальный.

DAFSA - это частный случай распознаватель конечного состояния это принимает форму ориентированный ациклический граф с единственной исходной вершиной (вершина без входящих ребер), в которой каждое ребро графа помечено буквой или символом, и в котором каждая вершина имеет не более одного исходящего ребра для каждой возможной буквы или символа. Строки, представленные DAFSA, образованы символами на путях в графе от исходной вершины к любой вершине-приемнику (вершина без исходящих ребер). Фактически, детерминированный конечный автомат ацикличен если и только если он признает конечный набор строк.[1]

Сравнение с попытками

Позволяя достичь одних и тех же вершин несколькими путями, DAFSA может использовать значительно меньше вершин, чем сильно связанные три структура данных. Рассмотрим, например, четыре английских слова «tap», «taps», «top» и «tops». Дерево для этих четырех слов будет иметь 12 вершин, по одной для каждой строки, образованной как префикс одного из этих слов, или для одного из слов, за которым следует маркер конца строки. Однако DAFSA может представить эти же четыре слова, используя только шесть вершин. vя для 0 ≤я ≤ 5, и следующие ребра: ребро из v0 к v1 помечены "t", два ребра от v1 к v2 помечены "а" и "о", край от v2 к v3 с надписью "p", край v3 к v4 помечены буквой "s", а края от v3 и v4 к v5 помечены маркером конца строки. Существует компромисс между памятью и функциональностью, потому что стандартный DAFSA может сказать вам, существует ли в нем слово, но не может указать вам на вспомогательную информацию об этом слове, в то время как дерево может.

Основное различие между DAFSA и trie заключается в устранении избыточности суффиксов и инфиксов при хранении строк. Trie устраняет избыточность префиксов, поскольку все общие префиксы разделяются между строками, например между врачи и докторская степень то врач префикс общий. В DAFSA общие суффиксы также являются общими для слов, которые имеют тот же набор возможных суффиксов, что и друг друга. Для словарных наборов общеупотребительных английских слов это приводит к значительному сокращению использования памяти.

Поскольку конечные узлы DAFSA могут быть достигнуты несколькими путями, DAFSA не может напрямую хранить вспомогательную информацию, относящуюся к каждому пути, например частота слова в английском языке. Однако, если для каждого узла мы сохраняем количество уникальных путей через эту точку в структуре, мы можем использовать его для получения индекса слова или слова по его индексу.[3] Затем вспомогательная информация может быть сохранена в массиве.

Рекомендации

  1. ^ а б c Ян Дачук, Стоян Михов, Брюс Уотсон и Ричард Ватсон (2000). Инкрементальное построение минимальных ациклических конечных автоматов. Компьютерная лингвистика 26(1):3-16.
  2. ^ Эта статья включает материалы общественного достояния отNIST документ:Блэк, Пол Э. "направленный ациклический граф слов". Словарь алгоритмов и структур данных.
  3. ^ Ковальтовски, Т .; CL Lucchesi (1993). «Приложения конечных автоматов, представляющие большие словари». Программное обеспечение - практика и опыт. 1993: 15–30. CiteSeerX  10.1.1.56.5272.
  • Blumer, A .; Blumer, J .; Haussler, D .; Ehrenfeucht, A .; Chen, M.T .; Сейферас, Дж. (1985), "Самый маленький автомат, распознающий подслова текста", Теоретическая информатика, 40: 31–55, Дои:10.1016/0304-3975(85)90157-4
  • Аппель, Эндрю; Якобсен, Гай (1988), «Самая быстрая программа по скрэббл в мире» (PDF), Коммуникации ACM, 31 (5): 572–578, Дои:10.1145/42411.42420. Одно из первых упоминаний о структуре данных.
  • Jansen, Cees J. A .; Боки, Дик Э. (1990), "О значении ориентированного ациклического графа слов в криптологии", Достижения в криптологии - AUSCRYPT '90, Конспект лекций по информатике, 453, Springer-Verlag, стр. 318–326, Дои:10.1007 / BFb0030372, ISBN  3-540-53000-2.
  • Эпифанио, Кьяра; Миньози, Филиппо; Шаллит, Джеффри; Вентурини, Илария (2004), «Графы Штурма и гипотеза Мозера», в Calude, Cristian S .; Калуд, Елена; Дайнин, Майкл Дж. (Ред.), Развитие теории языка. Протоколы 8-й международной конференции (DLT 2004), Окленд, Новая Зеландия, декабрь 2004 г., Конспект лекций по информатике, 3340, Springer-Verlag, стр. 175–187, ISBN  3-540-24014-4, Zbl  1117.68454

внешняя ссылка

  • http://pages.pathcom.com/~vadco/dawg.html - ДжонПол Адамовски учит, как построить DAFSA, используя массив целых чисел.
  • http://pages.pathcom.com/~vadco/cwg.html - Джон Пол Адамовски учит, как построить хеш-функцию DAFSA, используя новую кодировку с несколькими целочисленными массивами. Эта кодировка называется графом слов Кэролайн (CWG).