Main Page | Namespace List | Class Hierarchy | Class List | File List | Class Members | File Members

Trie.hpp

Go to the documentation of this file.
00001 /***************************************************************************
00002                           trie.h  -  description
00003                              -------------------
00004     begin                : cs dec 26 2002
00005     copyright            : (C) 2002 by Ferenc Bodon
00006     email                : bodon@mit.bme.hu
00007  ***************************************************************************/
00008 
00009 #ifndef TRIE_H
00010 #define TRIE_H
00011 
00016 typedef unsigned long itemtype;
00017 //typedef unsigned short itemtype;
00018 
00019 #include <fstream>
00020 #include <set>
00021 #include <vector>
00022 #include <cstdio>
00023 using namespace std;
00024 
00033 class Trie
00034 {
00035 
00036 public:
00037 
00038    Trie();
00039 
00041    void candidate_generation( const itemtype& frequent_size );
00042 
00044    void find_candidate( const vector<itemtype>& basket, const itemtype candidate_size, const unsigned long counter=1 );
00045 
00047    void delete_infrequent( const unsigned long min_occurrence );
00048 
00050    void association( ofstream& outcomefile, const double min_conf ) const;
00051 
00053    void basket_recode( vector<itemtype>& basket ) const;
00054 
00056    unsigned long node_number() const;
00057 
00059    virtual void statistics() const;
00060 
00062    void write_content_to_file( ofstream& outcomefile ) const;
00063 
00065    virtual void show_content() const;
00066 
00067    virtual ~Trie();
00068 
00069 protected:
00070 
00072    virtual void max_path_set( const unsigned long state_index );
00073 
00075    virtual void delete_edge( const unsigned long state );
00076 
00078    virtual void add_empty_state( const unsigned long from_state, const itemtype item, const unsigned long counter=0 );
00079 
00081    virtual unsigned long is_included( const set<itemtype>& an_itemset ) const;
00082 
00084    bool is_all_subset_frequent( const set<itemtype>& maybe_candidate ) const;
00085 
00087    void candidate_generation_two();
00088 
00090    virtual void candidate_generation_assist( unsigned long actual_state, const itemtype distance_from_generator,
00091                                              set<itemtype>& maybe_candidate );
00092 
00094    void find_candidate_one( const vector<itemtype>& basket );
00095 
00097    void find_candidate_two( const vector<itemtype>& basket, const unsigned long counter=1 );
00098 
00100    virtual void find_candidate_more( const vector<itemtype>& basket, const itemtype distance_from_candidate,
00101                                      vector<itemtype>::const_iterator it_basket, const unsigned long actual_state,
00102                                      const unsigned long counter=1 );
00103 
00105    virtual void delete_infrequent_one( const unsigned long min_occurrence );
00106 
00108    virtual void delete_infrequent_two( const unsigned long min_occurrence );
00109 
00111    virtual void delete_infrequent_more( const unsigned long min_occurrence );
00112 
00113    void assoc_rule_find( ofstream& outcomefile, const double min_conf, set<itemtype>& condition_part,
00114                          set<itemtype>& consequence_part, const unsigned long union_support) const;
00115 
00116    virtual void assoc_rule_assist( ofstream& outcomefile, const double min_conf,unsigned long actual_state,
00117                                    set<itemtype>& consequence_part) const;
00118 
00120    virtual void write_content_to_file_assist( ofstream& outcomefile, const unsigned long actual_state, const itemtype distance_from_frequent,
00121                                               set<itemtype>& frequent_itemset) const;
00122 private:
00123    // No private methods
00124 
00125 public:
00126    // No public members
00127 
00128 protected:
00136    vector< vector<itemtype> > itemarray;
00137 
00144    vector< vector<unsigned long> > statearray;
00145 
00150     vector<unsigned long> countervector;
00151 
00152     vector<unsigned long> parent;
00153 
00158    vector< vector<unsigned long> > temp_counter_array;
00159 
00164   vector<itemtype> maxpath;
00165 
00170   vector<itemtype> orderarray;
00171 
00173   vector<itemtype> inv_orderarray;
00174 
00175 
00176 };
00177 
00178 #endif

Generated on Tue Mar 2 18:12:10 2004 for APRIORI algorithm by doxygen 1.3.5