В информатике детерминированный ациклический конечный автомат ( DAFSA ) [1] — это структура данных , которая представляет набор строк и позволяет выполнять операцию запроса, которая проверяет, принадлежит ли заданная строка набору за время, пропорциональное ее длине. Существуют алгоритмы для построения и поддержки таких автоматов [1] , сохраняя их минимальность . DAFSA — это повторное открытие структуры данных, называемой направленным ациклическим графом слов (DAWG) [2] , хотя такое же название уже было дано другой структуре данных, которая связана с суффиксным автоматом [3] .
DAFSA — это особый случай конечного распознавателя , который принимает форму направленного ациклического графа с одной исходной вершиной (вершиной без входящих ребер), в котором каждое ребро графа помечено буквой или символом, и в котором каждая вершина имеет не более одного исходящего ребра для каждой возможной буквы или символа. Строки, представленные DAFSA, образованы символами на путях в графе от исходной вершины до любой вершины стока (вершины без исходящих ребер). Фактически, детерминированный конечный автомат является ациклическим тогда и только тогда, когда он распознает конечное множество строк . [1]
Блумер и др . [3] впервые определили термин «направленный ациклический граф слов» (DAWG) в 1983 году. Аппель и Якобсен [2] использовали то же название для другой структуры данных в 1988 году. Независимо от более ранней работы, Дачук и др. [1] заново открыли последнюю структуру данных в 2000 году, но назвали ее DAFSA.
Позволяя достигать одних и тех же вершин несколькими путями, DAFSA может использовать значительно меньше вершин, чем сильно связанная структура данных trie . Рассмотрим, например, четыре английских слова "tap", "taps", "top" и "tops". Trie для этих четырех слов будет иметь 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 может сказать вам, существует ли в нем слово, но он не может указать вам на вспомогательную информацию об этом слове, тогда как trie может.
Основное различие между DAFSA и trie заключается в устранении избыточности суффиксов и инфиксов при хранении строк . Trie устраняет избыточность префиксов, поскольку все общие префиксы являются общими для строк, например, между doctor и doctorate префикс doctor является общим. В DAFSA общие суффиксы также являются общими для слов, которые имеют одинаковый набор возможных суффиксов друг у друга. Для наборов словарей общих английских слов это приводит к значительному сокращению использования памяти.
Поскольку конечные узлы DAFSA могут быть достигнуты несколькими путями, DAFSA не может напрямую хранить вспомогательную информацию, относящуюся к каждому пути, например, частоту слова в английском языке. Однако, если для каждого узла мы сохраним количество уникальных путей через эту точку в структуре, мы можем использовать его для получения индекса слова или слова по его индексу. [4] Затем вспомогательная информация может быть сохранена в массиве.
