사전을 작성하고 싶습니다. 어떤 알고리즘/구조를 사용해야합니까?알고리즘 사전의 구조 및 구문
각 단어 또는 구문에는 해당 설명 (예, 동영상, 이미지 등)이 있습니다. 쉽게 단어를 추가/제거하고 설명을 수정할 수 있어야합니다. 빠른 액세스는 빠른 추가/제거보다 관련성이 높습니다. 설명의 일부 정보를 기반으로 단어를 필터링 할 수 있어야합니다. 일부 설명은 반쯤 비어있을 수 있습니다.
사전 파일에있는 단어와 위치에 대한 색인이 있다고 생각했습니다. 설명에서 몇 가지 정보를 빠르게 검색하는 방법은 무엇입니까?
일반적으로 사전은 나무 위에 설치되며 가장 일반적으로 자체 균형 조정 트리입니다. 가장 일반적으로 사용되는 것은 Red-Black trees과 AVL Trees입니다. 시작해야합니다.
귀하의 요구 사항을 생각해 보겠습니다 (단어가 키 (색인) 인 경우 사례를 고려 중입니다) 설명 : 해당 키가 가리키는 데이터입니다.
1. 단어를 추가/제거 할 가능성이 있습니다. 트리에서 노드를 추가하고 제거하십시오.
2. 설명 수정이 가능해야합니다. 설명, 색인이 작성되지 않았으므로, 설명을 찾을 때 트리 자체를 변경하지 않고 원하는대로 할 수 있습니다.
3. 빠른 액세스 - 확인하십시오. log2 (N) 액세스 권한이 있으며 트리 균형이 유지됩니다 (따라서 자체 균형 트리 임).
4. 일부 설명은 반쯤 비어있을 수 있습니다. 설명은 노드에 연결된 데이터 일 뿐이며 비어 있거나 좋아할만한 것으로 구조 내에서 아무 것도 변경하지 않습니다.
5. 일부 정보를 기반으로 단어 필터링 -이 것은 얻지 못합니다. 필터링 항목은 트리를 복사하여 구현할 수 있지만 필터링하지 않으려는 단어는 없으므로 다른 트리를 갖게됩니다. 당신이 원하는 단어 만 (그리고 설명은 복사되지 않습니다).
편집 : 당신이 알아야 할 한가지 - 그 나무를 잘 구현하는 것은 쉬운 일이 아닙니다. 버그 하나 또는 둘을 얻는 것은 매우 쉽습니다. 모든 단계에서 구현의 정확성을 검사해야합니다. 또한, 더 깊어지고 더 많은 구조로 들어가기를 원한다면, Knuth's을 읽고 싶을 것입니다.
Ravadre는 트리 기반 데이터 구조를 검색하려고했습니다.
큰 대안은 hash table입니다. 나무에 대한 주요 단점은 내부의 데이터가 정렬되지 않는다는 것입니다. 요소의 순서는 다소 임의적입니다. 정렬 된 순서로 요소에 액세스해야하는 경우 해시 테이블을 사용하는 것은 좋지 않습니다.
이 아닌 경우에 정렬 된 항목이 필요하지 않은 경우 해시 테이블로 이동하십시오. 평균 액세스 시간은 O (1)이며 이는 많은 요소에 따라 다르지만 액세스 시간보다 월등합니다 트리 기반 구조.
그런데 대부분의 프로그래밍 언어는 이미 하나 또는 두 가지 데이터 구조를 제공하므로 사용자가 직접 구현하지 않아도됩니다.
단어를 키로 사용하여 사전을 저장하려면 키가 일반적으로 문자열 인 데이터 구조 인 trie를 사용하는 것이 좋습니다. 꽤 좋은.
사전 자체를 배열에 저장하는 경우 단어 키 매핑 값은 설명이 단어가 나타나는 배열의 사전 항목 색인 목록 일 수 있습니다.
trie를 사용하지 않으려는 경우 : 해시 테이블이나 일종의 이진 트리를 사용할 수 있습니다.
해시 테이블을 사용하면 이론적으로 매우 빠른 조회가 가능하지만 충돌 가능성이 있습니다. 이는 성능이 시간이지나면서 악화 될 수 있음을 의미합니다. this blog post을 참조하십시오.
밸런스드 이진 검색 트리 (레드 - 블랙 트리가 널리 사용됨)를 사용하면 키 조회가 약간 느려질 수 있지만 (균형 트리를 사용하는 경우) 상대적으로 우수한 성능이 보장됩니다.
정확하게 이해하면 실제 사전, 즉 설명, 동영상 및 이미지가 포함 된 단어 목록을 만들고 싶습니까? 사전 데이터 유형을 구현하지 않습니까?
전적으로 데이터베이스가 가장 좋습니다. 전체 구조를 메모리에 유지할 필요가 없으며, 좋은 인덱싱 구조로 신속하게 액세스 할 수 있습니다. SQL 쿼리는 설명이나 다른 필드로 필터링 할 수있는 기능을 제공합니다.
이 접근법의 주된 단점은 삽입 알고리즘입니다. 데이터베이스가 단어를 삽입하는 데 걸리는 시간이 늘어나므로 (순서를 유지할 필요가 없다고 가정 할 때) 증가하게됩니다. 올바른 위치에 대한 2 진 검색은 아마도 가장 좋은 시작일 것입니다. 분명히 이것은 바이너리 트리 구조에 대한 필요성을 용이하게합니다.
실제 데이터베이스 자체에는 여러 가지 방법이 있습니다. 실제 단어를 색인으로 사용하면 가치가 있습니다. 색인을 기반으로 위치를 직접 얻을 수 있다는 이점이 있습니다 (단어 위치가 증가 할 때 문자열을 숫자로 늘릴 수 있다고 가정)
희망이 도움이됩니다.
아, 네 해시 테이블이 경우에 더 좋을 수도 있습니다. C#에서 사전이 해시 테이블을 사용하여 구현됩니다, 나는 그것이 자체라고 생각, 훨씬, 훨씬 더 쉽게 (구현하기가 훨씬 쉽다 .. .) –
@Ravadre :하지만 .NET은 또한 SortedList와 SortedDictionary를 제공하며,이 둘은 이진 검색 트리를 사용하여 구현됩니다. –