2
어휘에 대해 trie을 구성한 다음 동일한 구조체를 공유하는 많은 분기가 있음을 발견했습니다. 나는 함께 결합하여 결과가 DAWG이되도록하려는 것이다.트라이에서 DAWG를 만드는 방법은 무엇입니까?
트라이를 DAWG로 변환하는 데 사용할 알고리즘은 무엇입니까?
A
답변
2
트라이를 DAWG로 변환하기위한 표준 알고리즘은 트라이를 deterministic finite automaton으로 처리 한 다음 트라이를 minimum-state DFA으로 변환하여 작동합니다.
이 변환을 수행하는 알고리즘이 많이 있습니다. 가장 익숙한 알고리즘은 Hopcroft's algorithm입니다.이 알고리즘은 구별 가능한 상태 쌍을 찾아 구별 할 수없는 상태를 결합하여 작동합니다.
희망이 도움이됩니다.
@phs 지시 된 비순환 식 워드 그래프. – maditya
@ user1540043 이미 시도한 내용이 있습니까? – maditya
@maditya는 거의 10k 단어로 어휘를 시도했는데, 'ing', 'er', ... suffix를 공유하는 단어가 많이 있습니다. 그리고 나는 그것들을 결합하기를 원했고, 그 결과 시도 된 것은 비순환 식 단어 그래프였습니다 . – user1540043