Trie Class Reference

This class represent a general Trie. More...

#include <Trie.hpp>

List of all members.

Public Member Functions
	Trie (const unsigned long init_counter)
const 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.
void	find_candidate (vector< itemtype >::const_iterator it_basket_upper_bound, 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, unsigned long &nr_of_freq_itemsets)
	Deletes the tries that represent infrequent itemsets.
	~Trie ()
Private Member Functions
void	add_empty_state (const itemtype item, const unsigned long init_counter=0)
	Adds an empty state to the trie.
Private Attributes
unsigned long	counter
	counter stores the occurrence of the itemset represented by the Trie
vector< Edge >	edgevector
	edgevector stores the edges of the root 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 length of the maximal path starting from the root, and the edges are stored ordered according to their label.

Definition at line 46 of file Trie.hpp.

---

Constructor & Destructor Documentation

Trie::Trie (  const unsigned long  init_counter  )

Parameters: init_counter  The initial counter of the new trie Definition at line 23 of file Trie.cpp. Referenced by add_empty_state().

Trie::~Trie (   )

Definition at line 131 of file Trie.cpp. References edgevector.

---

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 Definition at line 143 of file Trie.cpp. References edgevector, itemtype, Edge::label, Edge::subtrie, and Trie(). Referenced by Apriori_Trie::candidate_generation_assist(), and Apriori_Trie::insert_frequent_items().

void Trie::delete_infrequent (  const unsigned long  min_occurrence, const itemtype  distance_from_candidate_parent, unsigned long &  nr_of_freq_itemsets )

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 Definition at line 93 of file Trie.cpp. References edgevector, and itemtype. Referenced by Apriori_Trie::delete_infrequent().

void Trie::find_candidate (  vector< itemtype >::const_iterator  it_basket_upper_bound, 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: it_basket_upper_bound  the last item in the basket, that has to be checked 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 Definition at line 61 of file Trie.cpp. References counter, edgevector, and itemtype. Referenced by Apriori_Trie::find_candidate().

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. Definition at line 36 of file Trie.cpp. References Edge_point_less(), and edgevector. Referenced by Apriori_Trie::is_all_subset_frequent().

---

Friends And Related Function Documentation

friend class Apriori_Trie [friend]

Definition at line 48 of file Trie.hpp.

---

Member Data Documentation

unsigned long Trie::counter [private]

counter stores the occurrence of the itemset represented by the Trie Definition at line 84 of file Trie.hpp. Referenced by Apriori_Trie::candidate_generation_assist(), and find_candidate().

vector<Edge> Trie::edgevector [private]

edgevector stores the edges of the root the trie. edgevector is always sorted! Definition at line 90 of file Trie.hpp. Referenced by add_empty_state(), Apriori_Trie::candidate_generation_assist(), Apriori_Trie::candidate_generation_two(), delete_infrequent(), Apriori_Trie::delete_infrequent_two(), find_candidate(), is_included(), Apriori_Trie::is_there_any_candidate(), and ~Trie().

---

The documentation for this class was generated from the following files:

• Trie.hpp
• Trie.cpp

---