trie.h

Go to the documentation of this file.

#ifndef _TRIE_H
#define _TRIE_H

#include <assert.h>
#include "defines.h"

using namespace std;

template<typename _type>
class Trie {
        private:
                class Node {
                        public:

                                const _type value;
                                const Node* parent;
                                unsigned long frequency;
                                list<Node> childs;

                                // this is only used for initialzation in the Trie constructor
                                Node() : value(0), parent(NULL) {
                                        frequency = 1;
                                }

                                Node(const _type val, const Node* parent) : value(val), parent(parent) {
                                        frequency = 1;
                                }

                                string toString(unsigned int level) const {
                                        string ret, tab;
                                        char buf[500];
                                        for (unsigned int i=0; i<level; i++)
                                                tab += "  ";
                                        sprintf(buf, "%s%ld (%c): %ld\n", tab.c_str(), (long) value, (char) value, frequency);
                                        ret += buf;
                                        for (typename list<Node>::const_iterator node = childs.begin(); node != childs.end(); node++) {
                                                ret += (*node).toString(level+1);
                                        }
                                        return ret;
                                }
                };

                Node root;

        public:
                Trie();
                ~Trie();

                bool findSequence(const list<_type>* sequence) const;
                // this also updates the frequencies if updateFrequency is true
                void insertSequence(const list<_type>* sequence, bool updateFrequency=false);
                double calculateProbability(const list<_type>* context, const _type nextValue) const;

                // a human-readable output
                string toString() const;
                // an output in text format, but which can be read be unserialize
                string serialize() const;
                void unserialize(string data);

        private:
                // a helper function used by both findSequence and calculateProbability
                // returns NULL if the sequence was not found
                const Node* navigateTree(const list<_type>* sequence) const
                {
                        const Node* cur = &root;
                        for (typename list<_type>::const_iterator symbol = sequence->begin(); symbol != sequence->end(); symbol++) {
                                bool foundsymb = false;
                                for (typename list<Node>::const_iterator node = cur->childs.begin(); !foundsymb && node != cur->childs.end(); node++) {
                                        if ((*node).value == *symbol) {
                                                // found that symbol in the sequence at the correct trie position, go to the next level
                                                foundsymb = true;
                                                cur = &(*node);
                                        }
                                }
                                if (!foundsymb)
                                        // not found --> the sequence is not in the trie
                                        return NULL;
                        }
                        // all symbols in the sequence found, return the last node
                        return cur;
                }
};

template<typename _type>
Trie<_type>::Trie() {}

template<typename _type>
Trie<_type>::~Trie() {}

template<typename _type>
bool Trie<_type>::findSequence(const list<_type>* sequence) const
{
        return (navigateTree(sequence) != NULL);
}

template<typename _type>
void Trie<_type>::insertSequence(const list<_type>* sequence, bool updateFrequency)
{
        Node* cur = &root;
        for (typename list<_type>::const_iterator symbol = sequence->begin(); symbol != sequence->end(); symbol++) {
                bool foundsymb = false;
                for (typename list<Node>::iterator node = cur->childs.begin(); !foundsymb && node != cur->childs.end(); node++) {
                        if ((*node).value == *symbol) {
                                foundsymb = true;
                                cur = &(*node);
                                // and update the frequency of that symbol in that level - this is the old behavior for Lempel Ziv
                                //(*node).frequency++;
                        }
                }
                if (!foundsymb) {
                        // insert a new one at that level
                        Node newNode(*symbol, cur);
                        cur->childs.push_back(newNode);
                        cur = &newNode;
                }
        }
        // increase the frequency of the last symbol seen in here
        if (updateFrequency)
                (*cur).frequency++;
}

template<typename _type>
double Trie<_type>::calculateProbability(const list<_type>* context, const _type nextValue) const
{
//      printf("++++\n");
        double prob = 0.0, escapeProb = 1.0;
        unsigned long sumfreq, foundfreq;
        // to calculate the probability of some next symbol, we first need to navigate to the given context
        const Node* cur = navigateTree(context);
        assert(cur != NULL);
        /* but it is not allowed to have no childs at the node we are starting
           from (because then the inner loop would not run, sumfreq and
           foundfreq would be 0 and we would finally exit with probability 0) */
        if (cur->childs.size() == 0)
                cur = cur->parent;

        while (cur != &root && cur != NULL) {
//              printf("++++ at %d (%c): ", cur->value, cur->value);
                sumfreq = foundfreq = 0;
                // also count the sum of frequencies
                for (typename list<Node>::const_iterator node = cur->childs.begin(); node != cur->childs.end(); node++) {
//                      printf("%c ", (*node).value);
                        sumfreq += (*node).frequency;
                        // this can only happen once (because of the insertion procedure)
                        if ((*node).value == nextValue) {
                                assert(foundfreq == 0);
                                foundfreq = (*node).frequency;
                        }
                }
                prob += escapeProb * ((double) foundfreq / cur->frequency);
                escapeProb *= ((double) sumfreq / cur->frequency);
//              printf("curProb=%f, curEscapeProb=%f, prob=%f, escapeProb=%f\n", escapeProb * ((double) foundfreq / cur->frequency), ((double) sumfreq / cur->frequency), prob, escapeProb);
                cur = cur->parent;
        }
        sumfreq = foundfreq = 0;
        for (typename list<Node>::const_iterator node = cur->childs.begin(); node != cur->childs.end(); node++) {
                sumfreq += (*node).frequency;
                // this can only happen once (because of the insertion procedure)
                if ((*node).value == nextValue) {
                        assert(foundfreq == 0);
                        foundfreq = (*node).frequency;
                }
        }
        prob += escapeProb *((double) foundfreq / sumfreq);
        return prob;
}

template<typename _type>
string Trie<_type>::toString() const
{
        return root.toString(0);
}

template<typename _type>
string Trie<_type>::serialize() const
{
        throw 1;
        return "";
}

template<typename _type>
void Trie<_type>::unserialize(string data)
{
        throw 1;
}

#endif

---