00001
00002
00003
00004
00005
00006
00007
00008
00009 #ifndef TRIE_H
00010 #define TRIE_H
00011
00016 typedef unsigned long itemtype;
00017
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
00124
00125 public:
00126
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