Лучший способ построить направленный ациклический граф слов (DAWG)
В настоящее время я смотрю на DAWG и не смог найти ни одного хорошего способа построения ациклического автомата.
В общем, я хочу сделать следующее:
Это в основном дерево, где количество состояний сокращено. Я бы использовал это с числами, но концепция точно такая же.
Интересно, что было бы самым быстрым способом сделать это, мой реальный план состоял в том, чтобы построить график, как показано слева, а затем посмотреть на состояния низкого уровня и, когда они похожи, объединить их.
Хотя я не уверен, что это лучший способ сделать это, есть ли у кого-нибудь идеи о том, как его построить.
С уважением.
1 ответ
DAWG - это конечные автоматы с минимальным состоянием для конкретного набора, если они хранят строки. Вы можете построить их, рассматривая имеющееся у вас дерево как неминимальный конечный автомат и запустив на нем стандартный алгоритм минимизации DFA. Это, пожалуй, самый простой способ построения DAWG, а также, возможно, самый быстрый.
Надеюсь это поможет!