Как создать DAWG?
Как можно создать DAWG? Я обнаружил, что есть два пути; один превращает дерево в dawg, а другой сразу же создает новую DAWG? Какой из них самый простой? Можете ли вы уточнить эти два и дать некоторые ссылки?
1 ответ
Один из способов думать о DAWG - это DFA с минимальным состоянием для всех слов в вашем списке слов. В результате традиционный алгоритм построения DAWG выглядит следующим образом:
- Начните с создания дерева для набора слов.
- Добавьте новый узел в дерево с ребрами от себя к себе на всех входах.
- Для каждого перехода отсутствующей буквы в дереве добавьте переход от начального узла к этому новому мертвому узлу.
- (На данный момент у вас есть (вероятно, не минимальный) DFA для набора слов.)
- Минимизируйте DFA, используя стандартный алгоритм минимизации состояния DFA.
После того, как вы это сделаете, у вас останется DAWG для набора интересующих вас слов.
Время выполнения этого алгоритма заключается в следующем. Построение начального DFA может быть выполнено путем построения дерева для всех исходных слов (которое занимает время O(n), где n - общее количество символов во всех входных строках), затем заполняя пропущенные переходы (что занимает время O(n|Σ|), где | Σ | - количество символов в вашем алфавите). Оттуда алгоритм минимизации выполняется за время O (n2 | Σ |). Это означает, что общее время выполнения алгоритма составляет O (n2 | Σ |).
Насколько мне известно, не существует простого алгоритма для постепенного построения DAWG. Как правило, вы должны создать DAWG для набора слов, только если у вас уже были все слова заранее. Интуитивно понятно, что это правда, потому что вставка нового слова с уже существующими суффиксами в DAWG может потребовать значительной реструктуризации DAWG, чтобы некоторые старые принимающие состояния не принимали и наоборот. Теоретически, это приводит к тому, что вставка нового слова может кардинально изменить классы эквивалентности отношения различимости DFA, что может потребовать существенных изменений в структуре DFA.
Надеюсь это поможет!