구현 시도

구현 시도

---

C / C ++에서 trie의 속도 및 캐시 효율적인 구현이 있습니까? 트라이가 뭔지는 알지만 바퀴를 재발 명해서 직접 구현하고 싶지는 않습니다.

---

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

---

나는 질문이 준비된 구현에 관한 것이라는 것을 알고 있지만 참고로 ...

Judy로 넘어 가기 전에 " A Performance Comparison of Judy to Hash Tables " 를 읽어야 합니다. 그런 다음 제목을 검색하면 평생 동안 토론과 반박을 읽을 수 있습니다.

내가 아는 캐시에 민감한 시도는 HAT-trie 입니다.

HAT-trie는 올바르게 구현되면 매우 멋집니다. 그러나 접두사 검색의 경우 해시 버킷에 대한 정렬 단계가 필요하며 이는 접두사 구조의 개념과 다소 충돌합니다.

다소 간단한 트라이는 기본적으로 일종의 표준 트리 (예 : BST)와 트라이 사이의 보간을 제공 하는 버스트 트라이입니다. 나는 그것을 개념적으로 좋아하고 구현하기가 훨씬 쉽습니다.

---

나는 libTrie 와 함께 행운을 빕니다 . 특별히 캐시에 최적화되어 있지 않을 수도 있지만 성능은 항상 내 응용 프로그램에 적합했습니다.

---

GCC는 "정책 기반 데이터 구조"의 일부로 몇 가지 데이터 구조와 함께 제공됩니다. 여기에는 몇 가지 트라이 구현이 포함됩니다.

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

---

참고 문헌,

• 두 번 배열 트리는 구현 문서 (A 포함 C구현)
• TRASH- 동적 LC-trie 및 해시 데이터 구조-(IP 라우팅 테이블에서 주소 조회를 구현하기 위해 Linux 커널에서 사용되는 동적 LC-trie를 설명하는 2006 PDF 참조)

---

Judy 배열 : 비트, 정수 및 문자열에 대해 매우 빠르고 메모리 효율적으로 정렬 된 희소 동적 배열입니다. Judy 배열은 바이너리 검색 트리 (avl 및 red-black-trees 포함)보다 더 빠르고 메모리 효율적입니다.

---

http://tommyds.sourceforge.net/ 에서 TommyDS를 사용해 볼 수도 있습니다.

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

---

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

---

캐시 최적화는 일반적으로 64 바이트 (포인터와 같은 데이터 결합을 시작하면 작동 할 것임)와 같은 단일 캐시 라인에 데이터를 맞춰야하기 때문에 아마도해야 할 일입니다. . 그러나 그것은 까다 롭습니다 :-)

---

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

나는 GWT의 type-ahead 구현에서 찾은 공간 절약 기술을 통합하는 버스트 트라이의 Scala 구현을 작성했습니다.

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

---

내 데이터 세트에 언급 된 여러 TRIE 구현에 비해 marisa-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