trie.hpp

Aprior的C++实现算法

/***************************************************************************
                          Trie.hpp  -  description
                             -------------------
    begin                : cs dec 26 2002
    copyright            : (C) 2002 by Ferenc Bodon
    email                : [e-mail]
 ***************************************************************************/

#ifndef Trie_HPP
#define Trie_HPP

/**
  *@author Ferenc Bodon
  */

#include "common.hpp"
#include <vector>
#include <set>

using namespace std;

class MSApriori_Trie;
class Trie;

/** This struct represent an edge of a Trie.

An edge has a label, and an edge points to a subtrie.
*/
struct Edge
{
   itemtype label;
   Trie* subtrie;
};
bool Edge_point_less(const Edge edge, const itemtype label);
/** This class represent a general Trie.

   We can regard the trie as a recursive data structure. It has a root node and a list of (sub)trie.
   We can reach a subtree by a labeled edge (link).
   Since the root of the trie represents an itemset the counter stands for the occurrence.
   For the sake of fast traversal we also store the parent of a trie, the length of the maximal path starting from the root,
   and the edges are stored ordered according to their label.
*/

class Trie
{
friend class MSApriori_Trie;

public:

   Trie( Trie* parent_trie, const unsigned long init_counter );

   /// It decides whether the given itemset is included in the trie or not.
   const Trie* is_included( const set<itemtype>& an_itemset, set<itemtype>::const_iterator item_it ) const;

   /// Increases the counter for those itemsets that is contained by the given basket.
   void find_candidate( const vector<itemtype>& basket, const itemtype distance_from_candidate,
                                vector<itemtype>::const_iterator it_basket, const unsigned long counter_incr=1);

   /// Deletes the tries that represent infrequent itemsets.
   void delete_infrequent( const double min_occurrence, const itemtype distance_from_candidate );

   /// Shows the content in a preorder manner
   void show_content_preorder( ) const;
   ~Trie();

private:
   /// Sets the maximal path value.
   void max_path_set( );

   /// Adds an empty state to the trie
   void add_empty_state( const itemtype item, const unsigned long init_counter=0 );

public:
   // No public members

private:
   
   /// parent stores the address of the parent of the Trie.
   Trie* parent;

   /// counter stores the occurrence of the itemset represented by the Trie
   unsigned long counter;

   /** edgevector stores the edges of the root the trie.
     *
     * edgevector is always sorted!
     */
   vector<Edge> edgevector;
   
   /// maxpath stores the length of the longest path starting from the root node.
   itemtype maxpath;
};


#endif