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

Trie Class Reference

This class represent a general Trie. More...

#include <Trie.hpp>

List of all members.

Public Member Functions

 Trie (Trie *parent, const unsigned long init)
const Trieis_included (const set< itemtype > &an_itemset, set< itemtype >::const_iterator item_it) const
 It decides whether the given itemset is included in the trie or not.

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

void delete_infrequent (const unsigned long min_occurrence, const itemtype distance_from_candidate)
 Deletes the tries that represent infrequent itemsets.

void show_content_preorder () const
 ~Trie ()

Private Member Functions

void max_path_set ()
 Sets the maximal path value.

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


Private Attributes

vector< itemtypeitemvector
 itemvector stores the label of the edges.

vector< Trie * > statevector
 statevector stores the address of the tries of the edges point to.

Trieparent
 parent stores the address of the parent of the Trie.

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

itemtype maxpath
 maxpath stores the length of the longest path starting from the Trie.


Friends

class Apriori_Trie


Detailed Description

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.


Constructor & Destructor Documentation

Trie::Trie Trie parent,
const unsigned long  counter
 

Parameters:
parent The pointer to the parent of the new trie
counter The initial counter of the new trie

Trie::~Trie  ) 
 


Member Function Documentation

void Trie::add_empty_state const itemtype  item,
const unsigned long  counter = 0
[private]
 

Adds an empty state to the trie.

Parameters:
item The label of the new edge
counter The initial counter of the new state

void Trie::delete_infrequent const unsigned long  min_occurrence,
const itemtype  distance_from_candidate_parent
 

Deletes the tries that represent infrequent itemsets.

Parameters:
min_occurrence The occurence threshold
distance_from_candidate_parent The length of the path from the root of the actual tre to a root of the trie that represents the parent of a candidate

void Trie::find_candidate const vector< itemtype > &  basket,
const itemtype  distance_from_candidate,
vector< itemtype >::const_iterator  it_basket,
const unsigned long  counter_incr = 1
 

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 trie to a trie that represents a candidate
it_basket *it_basket lead to the actual Trie. Only items following this item in the basket need to be considered
counter_incr The number times this basket occurs

const Trie * Trie::is_included const set< itemtype > &  an_itemset,
set< itemtype >::const_iterator  item_it
const
 

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

Parameters:
an_itemset The given itemset.
item_it This iterator shows the element of the basket that has to be processed.
Returns:
NULL, if the itemset is not included, otherwise the trie, that represents the itemset.

void Trie::max_path_set  )  [private]
 

Sets the maximal path value.

void Trie::show_content_preorder  )  const
 


Friends And Related Function Documentation

friend class Apriori_Trie [friend]
 


Member Data Documentation

unsigned long Trie::counter [private]
 

counter stores the occurrence of the itemset represented by the Trie

vector<itemtype> Trie::itemvector [private]
 

itemvector stores the label of the edges.

itemvector is always sorted! itemvector[i] stores the label of the ith edge. A label is a positive integer number (the code of an item).

itemtype Trie::maxpath [private]
 

maxpath stores the length of the longest path starting from the Trie.

Trie* Trie::parent [private]
 

parent stores the address of the parent of the Trie.

vector<Trie*> Trie::statevector [private]
 

statevector stores the address of the tries of the edges point to.

statevector[i] stores address of the trie of the ith edge.


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