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

Trie Class Reference

Trie (or prefix-tree) is a tree-based datastructure. More...

#include <Trie.hpp>

Inheritance diagram for Trie:

Trie_hash List of all members.

Public Member Functions

 Trie ()
void candidate_generation (const itemtype &frequent_size)
 Generates candidates.

void find_candidate (const vector< itemtype > &basket, const itemtype candidate_size, const unsigned long counter=1)
 Increases the counter of those candidates that are contained by the given basket.

void delete_infrequent (const unsigned long min_occurrence)
 Deletes unfrequent itemsets.

void association (ofstream &outcomefile, const double min_conf) const
 Generates association rules.

void basket_recode (vector< itemtype > &basket) const
 Recodes the basket so that each item is substituted by its s frequency order (inv_orderarray[]).

unsigned long node_number () const
 Returns the number of nodes in the trie.

virtual void statistics () const
 Displays the memory need of the trie.

void write_content_to_file (ofstream &outcomefile) const
 Writes the content (frequent itemsets) to the file.

virtual void show_content () const
 Displays the trie.

virtual ~Trie ()

Protected Member Functions

virtual void max_path_set (const unsigned long state_index)
 Sets the maximal path value.

virtual void delete_edge (const unsigned long state)
 Deletes the edge that goes to a given state.

virtual void add_empty_state (const unsigned long from_state, const itemtype item, const unsigned long counter=0)
 Adds an empty state to the trie.

virtual unsigned long is_included (const set< itemtype > &an_itemset) const
 It decides whether the given itemset is included in the trie or not.

bool is_all_subset_frequent (const set< itemtype > &maybe_candidate) const
 Decides if all subset of an itemset is contained in the trie.

void candidate_generation_two ()
 Generates candidate of size two.

virtual void candidate_generation_assist (unsigned long actual_state, const itemtype distance_from_generator, set< itemtype > &maybe_candidate)
 Generates candidate of size more than two.

void find_candidate_one (const vector< itemtype > &basket)
 Increases the counter for those items that are in the given basket.

void find_candidate_two (const vector< itemtype > &basket, const unsigned long counter=1)
 Increases the counter for those itempairs that are in the given basket.

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

virtual void delete_infrequent_one (const unsigned long min_occurrence)
 Deletes the nodes that represent infrequent itemsets of size 1.

virtual void delete_infrequent_two (const unsigned long min_occurrence)
 Deletes the nodes that represent infrequent itemsets of size 2.

virtual void delete_infrequent_more (const unsigned long min_occurrence)
 Deletes the nodes that represent infrequent itemsets.

void assoc_rule_find (ofstream &outcomefile, const double min_conf, set< itemtype > &condition_part, set< itemtype > &consequence_part, const unsigned long union_support) const
virtual void assoc_rule_assist (ofstream &outcomefile, const double min_conf, unsigned long actual_state, set< itemtype > &consequence_part) const
virtual void write_content_to_file_assist (ofstream &outcomefile, const unsigned long actual_state, const itemtype distance_from_frequent, set< itemtype > &frequent_itemset) const
 Writes out the content of the trie (frequent itemset and counters).


Protected Attributes

vector< vector< itemtype > > itemarray
 itemarray stores the label of the edges.

vector< vector< unsigned long > > statearray
 stetearray stores the end node of the edges.

vector< unsigned long > countervector
 countervector stores the occurences of the itemsets

vector< unsigned long > parent
vector< vector< unsigned long > > temp_counter_array
 temp_counter_array stores the occurences of the itempairs

vector< itemtypemaxpath
 maxpath stores the length of the longest paths.

vector< itemtypeorderarray
 The frequency order of the items.

vector< itemtypeinv_orderarray
 inverse of orderarray: orderarray[inv_orderarray[i]]=i


Detailed Description

Trie (or prefix-tree) is a tree-based datastructure.

Trie is a rooted directed tree. The root is defined to be at depth 0, and a node at depth d can point to nodes at depth d+1. A pointer is also called edge or link, which is labeled by an item. If node u points to node v, then we call u the parent of v, and v is a child node of u.


Constructor & Destructor Documentation

Trie::Trie  ) 
 

Trie::~Trie  )  [virtual]
 


Member Function Documentation

void Trie::add_empty_state const unsigned long  fromState,
const itemtype  item,
const unsigned long  counter = 0
[protected, virtual]
 

Adds an empty state to the trie.

Parameters:
fromState The state number that point to the new state.
item The label of the new edge
counter The initial counter of the new state

Reimplemented in Trie_hash.

void Trie::assoc_rule_assist ofstream &  outcomefile,
const double  min_conf,
unsigned long  actual_state,
set< itemtype > &  consequence_part
const [protected, virtual]
 

Reimplemented in Trie_hash.

void Trie::assoc_rule_find ofstream &  outcomefile,
const double  min_conf,
set< itemtype > &  condition_part,
set< itemtype > &  consequence_part,
const unsigned long  union_support
const [protected]
 

void Trie::association ofstream &  outcomefile,
const double  min_conf
const
 

Generates association rules.

Parameters:
outcomefile The file the output will be written to.
min_conf Confidence threshold.

void Trie::basket_recode vector< itemtype > &  basket  )  const
 

Recodes the basket so that each item is substituted by its s frequency order (inv_orderarray[]).

Parameters:
basket The given basket.

void Trie::candidate_generation const itemtype frequent_size  ) 
 

Generates candidates.

Parameters:
frequent_size Size of the frequent itemsets that generate the candidates.

void Trie::candidate_generation_assist unsigned long  actual_state,
const itemtype  distance_from_generator,
set< itemtype > &  maybe_candidate
[protected, virtual]
 

Generates candidate of size more than two.

Reimplemented in Trie_hash.

void Trie::candidate_generation_two  )  [protected]
 

Generates candidate of size two.

void Trie::delete_edge const unsigned long  toState  )  [protected, virtual]
 

Deletes the edge that goes to a given state.

Parameters:
toState the state to the edge points.

Reimplemented in Trie_hash.

void Trie::delete_infrequent const unsigned long  min_occurrence  ) 
 

Deletes unfrequent itemsets.

Parameters:
min_occurrence The threshold of absolute support.

void Trie::delete_infrequent_more const unsigned long  min_occurrence  )  [protected, virtual]
 

Deletes the nodes that represent infrequent itemsets.

Parameters:
min_occurrence The occurence threshold

Reimplemented in Trie_hash.

void Trie::delete_infrequent_one const unsigned long  min_occurrence  )  [protected, virtual]
 

Deletes the nodes that represent infrequent itemsets of size 1.

Parameters:
min_occurrence The occurence threshold

Reimplemented in Trie_hash.

void Trie::delete_infrequent_two const unsigned long  min_occurrence  )  [protected, virtual]
 

Deletes the nodes that represent infrequent itemsets of size 2.

Parameters:
min_occurrence The occurence threshold

temp_counter_array[stateIndex_1-1] will never be used again!

temp_counter_array will never be used again!

Reimplemented in Trie_hash.

void Trie::find_candidate const vector< itemtype > &  basket,
const itemtype  candidate_size,
const unsigned long  counter = 1
 

Increases the counter of those candidates that are contained by the given basket.

void Trie::find_candidate_more const vector< itemtype > &  basket,
const itemtype  distance_from_candidate,
vector< itemtype >::const_iterator  it_basket,
const unsigned long  actual_state,
const unsigned long  counter = 1
[protected, virtual]
 

Increases the counter for those itemsets that is contained by the given basket.

Parameters:
basket the given basket
distance_from_candidate The length of the path from the actual node to a node that represents a candidate
it_basket *it_basket lead to the actual_state. Only items following this item need to be considered
actual_state The index of the actual state
counter The number the processed basket occures in the transactional database

Reimplemented in Trie_hash.

void Trie::find_candidate_one const vector< itemtype > &  basket  )  [protected]
 

Increases the counter for those items that are in the given basket.

Parameters:
basket the given basket

void Trie::find_candidate_two const vector< itemtype > &  basket,
const unsigned long  counter = 1
[protected]
 

Increases the counter for those itempairs that are in the given basket.

Parameters:
basket the given basket
counter The number the processed basket occures in the transactional database

bool Trie::is_all_subset_frequent const set< itemtype > &  maybe_candidate  )  const [protected]
 

Decides if all subset of an itemset is contained in the trie.

Parameters:
maybe_candidate The itemset that has to be checked.

unsigned long Trie::is_included const set< itemtype > &  an_itemset  )  const [protected, virtual]
 

It decides whether the given itemset is included in the trie or not.

Parameters:
an_itemset The given itemset.
Returns:
0, if the itemset is not included, otherwise the state number, that represents the itemset.

Reimplemented in Trie_hash.

void Trie::max_path_set const unsigned long  stateIndex  )  [protected, virtual]
 

Sets the maximal path value.

Parameters:
stateIndex the state whose max_path value has to be set.

Reimplemented in Trie_hash.

unsigned long Trie::node_number  )  const
 

Returns the number of nodes in the trie.

void Trie::show_content  )  const [virtual]
 

Displays the trie.

Reimplemented in Trie_hash.

void Trie::statistics  )  const [virtual]
 

Displays the memory need of the trie.

Reimplemented in Trie_hash.

void Trie::write_content_to_file ofstream &  outcomefile  )  const
 

Writes the content (frequent itemsets) to the file.

void Trie::write_content_to_file_assist ofstream &  outcomefile,
const unsigned long  actual_state,
const itemtype  distance_from_frequent,
set< itemtype > &  frequent_itemset
const [protected, virtual]
 

Writes out the content of the trie (frequent itemset and counters).

Reimplemented in Trie_hash.


Member Data Documentation

vector<unsigned long> Trie::countervector [protected]
 

countervector stores the occurences of the itemsets

countervector[i] stores the occurence of the itemset represented by the ith node.

vector<itemtype> Trie::inv_orderarray [protected]
 

inverse of orderarray: orderarray[inv_orderarray[i]]=i

vector< vector<itemtype> > Trie::itemarray [protected]
 

itemarray stores the label of the edges.

itemarray[i] belongs to the ith node. itemarray[i] is always sorted. itemarray[i][j] stores the label of the jth edge (of the ith node). A label is a positive integer number (the code of an item).

vector<itemtype> Trie::maxpath [protected]
 

maxpath stores the length of the longest paths.

maxpath[i] stores the legth of the longest path starting from the ith node.

vector<itemtype> Trie::orderarray [protected]
 

The frequency order of the items.

orderarray[1] is the most frequent item, orderarray[2] is the second most frequent...

vector<unsigned long> Trie::parent [protected]
 

vector< vector<unsigned long> > Trie::statearray [protected]
 

stetearray stores the end node of the edges.

statearray[i] belongs to the ith node. statearray[i] is always sorted! statearray[i][j] stores the end node of the jth edge (of the ith node).

vector< vector<unsigned long> > Trie::temp_counter_array [protected]
 

temp_counter_array stores the occurences of the itempairs

temp_counter_array[i][j] stores the occurence of the itempair (orderarray[i],orderarray[j]).


The documentation for this class was generated from the following files:
Generated on Tue Mar 2 18:12:10 2004 for APRIORI algorithm by doxygen 1.3.5