Trie 구현

Trie 구현

마감되었습니다. 이 질문은 충족되지 않습니다.스택 오버플로우 가이드라인현재 답변을 받고 있지 않습니다.

---

이 질문을 개선하시겠습니까?스택 오버플로의 토픽이 되도록 질문을 업데이트합니다.

4년 전에 문을 닫았어요

커뮤니티는 지난달 이 질문을 재개할지 여부를 검토한 후 이를 종결했다.

원래 종료 이유가 해결되지 않았습니다.

이 질문을 개선하다

C/C++에서 trie의 속도와 캐시 효율이 뛰어난 구현이 있습니까?트라이가 뭔지는 알지만 바퀴를 다시 만들고 싶지는 않아 직접 구현하고 싶진 않아

ANSI C 구현을 찾고 있다면 FreeBSD에서 "스틸"할 수 있습니다.찾으시는 파일의 이름은 radix.c 입니다.커널의 라우팅 데이터를 관리하는 데 사용됩니다.

Cedar, HAT-Trie, JudyArray는 매우 훌륭합니다.여기서 벤치마크를 찾을 수 있습니다.

GCC에는, 「정책 베이스의 데이터 구조」의 일부로서 소수의 데이터 구조가 부속되어 있습니다.여기에는 몇 가지 트라이 구현이 포함됩니다.

http://gcc.gnu.org/onlinedocs/libstdc++/ext/pb_ds/trie_based_containers.html

libTrie에 행운이 따랐어요.캐시에 특별히 최적화된 것은 아니지만 성능은 항상 애플리케이션에 적합했습니다.

레퍼런스,

• Double Array Trie 구현 문서(Double Array Trie 포함)C□□□□□□□□★
• TRASH - 동적 LC-trie 및 해시 데이터 구조 -- (IP 라우팅 테이블에 주소 검색을 구현하기 위해 Linux 커널에서 사용되는 동적 LC-trie를 설명하는 2006년 PDF 참조)

질문은 준비 완료 구현에 관한 것이었지만, 참고로...

Judy를 비난하기 전에 "A Performance Comparison of Judy to Hash Tables"를 읽어야 합니다.그러면 제목을 검색하면 평생 동안 토론과 반박을 읽을 수 있게 될 것이다.

캐시 인식 트리는 HAT-trie라고 알고 있습니다.

HAT-trie는 올바르게 구현되어 있으면 매우 쿨합니다.다만, 프리픽스 검색의 경우는, 해시 버킷의 정렬 순서가 필요합니다.이것은 프리픽스 구조의 개념과 다소 상충돌합니다.

좀 더 간단한 트리(BST 등)와 트리(Trie) 사이의 보간 기능을 기본적으로 제공하는 버스트 트리)입니다.개념적으로 마음에 들고 구현하기 훨씬 쉽습니다.

Judy 어레이:매우 빠르고 메모리 효율이 뛰어난 비트, 정수 및 문자열에 대해 정렬된 스파스 다이내믹 어레이.Judy 어레이는 바이너리 검색 트리(avl 및 red-black-tree 포함)보다 고속으로 메모리 효율이 뛰어납니다.

TommyDS는 http://tommyds.sourceforge.net/에서도 시험해 볼 수 있습니다.

Nedtries 및 Judy와의 속도 비교는 사이트의 벤치마크 페이지를 참조하십시오.

캐시 최적화는 아마도 수행해야 할 작업일 것입니다. 데이터를 64바이트 정도의 단일 캐시 라인에 넣어야 하기 때문입니다(일반적으로 포인터 등 데이터 결합을 시작할 때 사용할 수 있습니다).하지만 까다롭습니다:-)

Burst Trie가 좀 더 공간 효율적인 것 같아요.CPU 캐시가 너무 작기 때문에 인덱스에서 캐시 효율성을 얼마나 얻을 수 있을지 모르겠습니다.그러나 이러한 종류의 Trie는 RAM에 대용량 데이터 세트를 보관할 수 있을 만큼 충분히 컴팩트합니다(일반 Trie에서는 그렇지 않습니다).

저는 GWT의 자동 예측 구현에서 발견한 공간 절약 기술을 통합한 버스트 트리의 Scala 구현을 작성했습니다.

https://github.com/nbauernfeind/scala-burst-trie

marisa-trie를 사용한 결과(퍼포먼스와 사이즈의 밸런스가 매우 좋음)는, 데이터 세트에 기재되어 있는 몇개의 TRIE 실장에 비해 매우 양호했습니다.

https://github.com/s-yata/marisa-trie/tree/master

기본적인 시나리오에서만 테스트된 Trie용 "빠른" 구현 공유:

#define ENG_LET 26

class Trie {
    class TrieNode {
    public:
        TrieNode* sons[ENG_LET];
        int strsInBranch;
        bool isEndOfStr;

        void print() {
            cout << "----------------" << endl;
            cout << "sons..";
            for(int i=0; i<ENG_LET; ++i) {
                if(sons[i] != NULL)
                    cout << " " << (char)('a'+i);
            }
            cout << endl;
            cout << "strsInBranch = " << strsInBranch << endl;
            cout << "isEndOfStr = " << isEndOfStr << endl;
            for(int i=0; i<ENG_LET; ++i) {
                if(sons[i] != NULL)
                    sons[i]->print();
            }

        }
        TrieNode(bool _isEndOfStr = false):isEndOfStr(_isEndOfStr), strsInBranch(0) {
            for(int i=0; i<ENG_LET; ++i) {
                sons[i] = NULL;
            }
        }
        ~TrieNode() {
            for(int i=0; i<ENG_LET; ++i) {
                delete sons[i];
                sons[i] = NULL;
            }
        }
    };

    TrieNode* head;
public:
    Trie() { head = new TrieNode();}
    ~Trie() { delete head; }
    void print() {
        cout << "Preorder Print : " << endl;
        head->print();
    }
    bool isExists(const string s) {
        TrieNode* curr = head;
        for(int i=0; i<s.size(); ++i) {
            int letIdx = s[i]-'a';
            if(curr->sons[letIdx] == NULL) {
                return false;
            }
            curr = curr->sons[letIdx];
        }

        return curr->isEndOfStr;
    }
    void addString(const string& s) {
        if(isExists(s))
            return;
        TrieNode* curr = head;
        for(int i=0; i<s.size(); ++i) {
            int letIdx = s[i]-'a';
            if(curr->sons[letIdx] == NULL) {
                curr->sons[letIdx] = new TrieNode();    
            }
            ++curr->strsInBranch;
            curr = curr->sons[letIdx];
        }
        ++curr->strsInBranch;
        curr->isEndOfStr = true;
    }
    void removeString(const string& s) {
        if(!isExists(s))
            return;
        TrieNode* curr = head;
        for(int i=0; i<s.size(); ++i) {
            int letIdx = s[i]-'a';

            if(curr->sons[letIdx] == NULL) {
                assert(false);
                return; //string not exists, will not reach here
            }
            if(curr->strsInBranch==1) {    //just 1 str that we want remove, remove the whole branch
                delete curr;
                return;
            }
            //more than 1 son
            --curr->strsInBranch;
            curr = curr->sons[letIdx];
        }
        curr->isEndOfStr = false;
    }

    void clear() {
        for(int i=0; i<ENG_LET; ++i) {
            delete head->sons[i];
            head->sons[i] = NULL;
        }
    }

};

언급URL : https://stackoverflow.com/questions/1036504/trie-implementation