사전과 같은 것을 디자인하면서 데이터 구조를 권장합니까?

단어를 저장하기위한 사전과 같은 것을 디자인하는 동안 TRIE가 가장 권장되는 데이터 구조입니까? 시간이나 메모리 성능을 향상시키는 다른 대안?사전과 같은 것을 디자인하면서 데이터 구조를 권장합니까?

충돌이 없다면 해시가 좋을 수 있다고 생각하지만 오버 라이트, 오버랩, 오버랩, 오버랩, 오버레이 모두가 독점적 인 스토리지를 차지하면서 트라이의 공간을 공유하면서 메모리 요구 사항이 나 빠지기 시작합니다.

편집 : @Moron에게 감사하고 매우 유용한 답변을드립니다. 동의합니다 - 해시 키를 생성하는 것은 O (n)이므로 TRIE 검색입니다. 그러나 해시의 경우 체인화를 추가하면 시간이 늘어날 수 있으며 TRIE의 경우에는 발생하지 않습니다. TRIE의 모든 노드에서 사전 크기가 작 으면 불기있을 수있는 포인터를 유지해야합니다.

출처

2010-07-07 Fanatic23

해시 O (log n)은 어떻습니까? –

@Moron 연결을 위해 연결 목록을 사용하는 대신 루트 노드 위치에서 BST 또는 AVL 트리를 시작하십시오. 무작위 데이터의 경우 AVL을 선택하지 않아도 BST는 O (log n)이어야합니다. – Fanatic23

링크 된 목록 대신 원하는 것을 사용하십시오. 해시 키 값을 계산하는 것은 여전히 O (n)입니다. O (logn)는 전혀 이해가되지 않습니다. 그것은 O (n + nlog K)입니다. 여기서 K는 같은 해시를 가진 키의 수입니다. n은 해시를 계산하는 데 사용되며, logK 문자열에 대한 nlogK는 길이가 각각 n 인 K 노드 트리에서 비교됩니다 (작은 문자열이 동일한 값으로 해시되면 최하위가되지만 최악의 경우는 n입니다). –

당신은 기본적으로 트라이이지만, 더 나은 메모리 사용량을 가지고 Directed Acyclic Word graph을 고려하고, 위키에 따라 시도 할 수는 영어, 메모리 소비는 트라이보다 훨씬 낮다.

시간이 지남에 따라, 그것은 trie와 비슷하며 해시보다 가능성이 큽니다.해시에 대한 O (로그인) 시간을 알 수 없습니다. 합리적인 해시의 경우 O (n) 여야합니다. 여기서 n은 검색되는 단어의 길이입니다.

출처

2010-07-07 18:29:28

합리적인 해시는 O (1)을 의미합니까? –

@ Justin : 아니오 O (n)을 의미합니다. 여기서 n은 검색 할 단어의 길이입니다. n은 사전 크기가 아닙니다. –

@Moron : 결과 해시를 사용하여 해시 테이블을 검색하고 키를 해싱하는 작업은 두 개의 개별 작업으로 간주되므로 해시 테이블 검색은 O (1) 비용으로 간주됩니다 (합리적인 해시의 경우). – TMN

트라이는 해시 테이블에 비해 다음과 같은 장점이 있습니다

은 불완전한 해시 테이블에 비해 빠른 최악의 경우, O(m) 시간 인 트라이 데이터를 찾고 있습니다. 불완전한 해시 테이블은 주요 충돌을 가질 수 있습니다. 키 충돌은 다른 키를 해시 테이블의 동일한 위치에 매핑하는 해시 함수입니다. 불완전 해시 테이블에서 최악의 검색 속도는 O(N) 시간이지만 훨씬 더 일반적으로 O(1)이며 해시를 평가하는 데는 O(m) 시간이 걸립니다.
트라이에서 다른 키의 충돌이 없습니다.
키 충돌을 저장하는 해시 테이블 버킷과 유사한 트 리의 버킷은 단일 키가 두 개 이상의 값과 연결되어있는 경우에만 필요합니다.
트라이에 더 많은 키가 추가되면 해시 함수를 제공하거나 해시 함수를 변경할 필요가 없습니다.
트라이는 키를 사용하여 항목의 사전 순 정렬을 제공 할 수 있습니다.
1. 시도 횟수가 데이터를 직접 하드 디스크 드라이브 또는 다른 보조 스토리지에 액세스 할 특히, 데이터를 찾고에 대한 해시 테이블보다 어떤 경우에는 속도가 느려질 수 있습니다 :
시도 횟수는 다음과 같은 단점이있다 장치는 랜덤 액세스 시간이 주 메모리에 비해 높다.
모든 키를 부동 소수점과 같이 문자열로 표시하는 것은 쉽지 않습니다. 인코딩의 비트 문자열을 사용하는 간단한 인코딩은 특히 의미가없는 긴 체인과 접두어로 이어집니다.