DAWG/DAFSA의 메타 정보

Question

효율적인 검색 및 삽입을 지원하는 동적 문자열 용 문자열 조회 데이터 구조를 구현하고 싶습니다. 현재는 트라이를 사용하고 있지만 가능한 경우 메모리 사용 공간을 줄이려고합니다. This Wikipedia article은 DAWG/DAFSA를 설명하며 접미어를 압축하여 많은 공간을 절약합니다. 그러나 문자열이 합법적인지 여부를 명확하게 테스트하지만 불법 문자열을 제외 할 수있는 방법이 있는지는 분명하지 않습니다. 예를 들어, 단어 "인용"와 "고양이"는 "t"와 "E"를 사용하여 단말기 상태가하는 개같은은/DAFSA는 다음과 같이 보일 것이다 :

 c 
    /\ 
    a i 
    \/
     t 
     | 
     e 

와 "CIT"와 "케이트를" 일부 메타 정보가없는 올바른 문자열로 잘못 인식됩니다.

질문 :

1) 임마/DAFSA 이러한 적법성과 같은 문자열/경로()에 대한 메타 정보를 저장하기 위해 선호하는 방법이 있나요?

2) DAWG/DAFSA가 요구 사항 (효율적인 검색/삽입 및 메타 정보 저장)과 호환되지 않는 경우 사용할 수있는 최상의 데이터 구조는 무엇입니까? 최소한의 메모리 공간 만 있으면 좋겠지 만 절대적으로 필요한 것은 아닙니다.

Answer 1

DAWG에서는 상태를 완전히 구분할 수없는 경우에만 상태를 압축합니다. 즉, 실제로 CAT과 CITE의 T 노드를 결합하지 않을 것입니다. 즉, CIT에 대해 거짓 긍정 (false positive) 또는 CAT에 대해 false negative를 제공합니다.

DAWG는 일반적으로 공통 접미사가있는 엄청난 단어가있는 경우 정적 사전에 가장 효과적입니다. 예를 들어 모든 영어에 대한 DAWG는 복수 단어의 끝에 모든 접미사 "s"를 결합하고 gerunds의 "ING"접미어의 대부분을 결합하여 많은 공간을 절약 할 수 있습니다. DAWG에서 한 단어를 추가하거나 제거하면 이전에 결합 된 많은 지점을 필요로하는 파급 효과를 유발할 수 있기 때문에 DAWG는 삽입 또는 삭제 작업을 많이하는 경우가 거의 확실합니다. 분할되거나 그 반대의 경우.

상당한 크기의 데이터 세트의 경우 trie는 나쁜 호출이 아닙니다. 모든 영어에 대한 trie는 26MB와 같은 것을 사용합니다. 그리 많지는 않습니다. 공간 사용량이 정말 프리미엄이고 많은 삽입이나 삭제를하지 않으면 DAWG 만 사용합니다.

희망이 도움이됩니다.