Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Строки «tap», «taps», «top» и «tops» хранятся в trie (слева) и DAFSA (справа), EOW означает конец слова.

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

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

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

Позволяя достичь одних и тех же вершин несколькими путями, DAFSA может использовать значительно меньше вершин, чем сильно связанная структура данных trie . Рассмотрим, например, четыре английских слова «tap», «taps», «top» и «tops». Дерево для этих четырех слов будет иметь 12 вершин, по одной для каждой из строк, образованных как префикс одного из этих слов, или для одного из слов, за которым следует маркер конца строки. Однако DAFSA может представить эти же четыре слова, используя только шесть вершин v i для 0 ≤  i  ≤ 5 и следующие ребра: ребро от v 0 до v 1, помеченное «t»,два ребра от v 1 до v 2обозначены "a" и "o", ребро от v 2 до v 3 обозначено "p", ребро от v 3 до v 4 обозначено "s", а ребра от v 3 и v 4 до v 5 обозначены концом - строковый маркер. Существует компромисс между памятью и функциональностью, потому что стандартный DAFSA может сказать вам, существует ли в нем слово, но не может указать вам на вспомогательную информацию об этом слове, тогда как дерево может.

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

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

Ссылки [ править ]

  1. ^ a b 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, MT; Seiferas, J. (1985), "Самый маленький автомат признания полслов текста", теоретическая информатика , 40 : 31-55, DOI : 10.1016 / 0304-3975 (85) 90157-4
  • Аппель, Эндрю; Jacobsen, Guy (1988), "самый быстрый в мире Эрудит Программа" (PDF) , связь по АКМ , 31 (5): 572-578, DOI : 10,1145 / 42411,42420. Одно из первых упоминаний о структуре данных.
  • Jansen, Cees JA; Боки, Дик Э. (1990), «О значении ориентированного ациклического графа слов в криптологии», Достижения в криптологии - AUSCRYPT '90 , Lecture Notes in Computer Science , 453 , Springer-Verlag , pp. 318–326, doi : 10.1007 / BFb0030372 , ISBN 3-540-53000-2.
  • Эпифанио, Кьяра; Миньози, Филиппо; Шаллит, Джеффри; Вентурини, Илария (2004), «Графы Штурма и гипотеза Мозера», в Calude, Cristian S .; Калуд, Елена; Дайнин, Майкл Дж. (Ред.), Развитие теории языка. Proceedings, 8-я международная конференция (DLT 2004), Окленд, Новая Зеландия, декабрь 2004 г. , Lecture Notes in Computer Science, 3340 , Springer-Verlag , pp. 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).