현재 DAWG를 조사하고 있는데 비주기 오토 마톤을 구성하는 좋은 방법을 찾지 못했습니다.Directed Acyclic Word Graph (DAWG)를 구성하는 가장 좋은 방법
그래서 기본적으로 제가하고 싶은 것은 이것이다 :
그것은 기본적으로 국가의 수가 감소하는 나무입니다. 숫자와 함께 사용 하겠지만 개념은 완전히 동일합니다.
가장 빠른 방법은 무엇일까요? 내 실제 계획은 왼쪽에 표시된 그래프를 작성한 다음 낮은 수준의 상태를보고 비슷한시기에 병합하는 것입니다.
비록 이것이 최선의 방법인지는 모르겠지만 누구나 그것을 구성하는 방법에 대한 아이디어가 있습니다.
감사합니다.
DAWG는 문자열이 저장되는 경우 특정 세트에 대한 최소 상태 유한 자동 항목입니다. 가지고있는 트라이를 비 한정형 유한 오토 마톤으로 취급하고 표준 DFA 최소화 알고리즘을 실행하여 구성 할 수 있습니다. 이것은 아마도 DAWG를 구성하는 가장 쉬운 방법이며 아마도 가장 빠른 방법 일 것입니다.
희망이 도움이됩니다.
글쎄요, 그렇습니다.하지만 여러 개의 최소화 알고리즘이 있습니다. DAWG를 "직접"빌드하는 것을 선호합니다. 배열에 배열을 저장해야하기 때문입니다. 어떤 점에서. 실제로 트리를 얻으려면 의사 코드를 찾고 있습니다 -> DAWG. – Anoracx
@ Anoracx- 나는 당신이 묻는 것에 대해 혼란스러워합니다. trie-> DAWG 단계는 DFA 최소화 단계입니다. DAWG를 직접 만드시겠습니까? – templatetypedef
글쎄, 위키 백과에서 DAWG (DAFSA)는 일반적인 트리/DFA로 구성된 트리 유형이라고 생각했습니다. 그래서 실제로 그 알고리즘을 수행 할 특정 알고리즘이 있다고 생각했습니다. 그리고 최소화 알고리즘 만이 아닙니다. 그래서 제가 직접하고 싶다고 말했을 때 실제로 DFA에서 DAFSA (DAWG)로 변환하는 방법을 찾고있었습니다. 그리고 바닥부터 시작한다는 아이디어가 좋은 아이디어라면. – Anoracx
당신은 DFA를 가지고 있습니다. 최소한의 DFA (상당히 표준 알고리즘이 있습니다)로 줄일 수 있습니다 – SheetJS
알아요,하지만 실제로 그 중 하나 (또는 의사 코드)를 찾는 방법을 찾고 있어요 – Anoracx
https://en.wikipedia.org/wiki /DFA_minimization#Hopcroft.27s_algorithm – SheetJS