Trie Class Reference

This class represent a general Trie. More...

#include <Trie.hpp>

List of all members.

Public Member Functions
	Trie (const countertype 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, vector< itemtype >::const_iterator it_basket, const countertype counter_incr)
	Increases the counter for those itemsets that is contained by the given basket.
void	delete_infrequent (const double min_occurrence)
	Deletes the tries that represent infrequent itemsets.
	~Trie ()
Private Member Functions
void	add_empty_state (const itemtype item, const countertype init_counter=0)
	Adds an empty state to the trie.
Private Attributes
countertype	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 45 of file Trie.hpp.

---

Constructor & Destructor Documentation

Trie::Trie (  const countertype  init_counter  )  [inline]

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

Trie::~Trie (   )

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

---

Member Function Documentation

void Trie::add_empty_state (  const itemtype  item, const countertype  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 123 of file Trie.cpp. References edgevector, Edge::label, Edge::subtrie, and Trie(). Referenced by Apriori_Trie::candidate_generation_assist(), Apriori_Trie::delete_infrequent_two(), and Apriori_Trie::insert_frequent_items().

void Trie::delete_infrequent (  const double  min_occurrence  )

Deletes the tries that represent infrequent itemsets. Parameters: min_occurrence  The occurence threshold Definition at line 82 of file Trie.cpp. References edgevector. Referenced by Apriori_Trie::delete_infrequent().

void Trie::find_candidate (  vector< itemtype >::const_iterator  it_basket_upper_bound, vector< itemtype >::const_iterator  it_basket, const countertype  counter_incr )

Increases the counter for those itemsets that is contained by the given basket. Parameters: basket  the given basket 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 51 of file Trie.cpp. References counter, and edgevector. 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 28 of file Trie.cpp. References edgevector. Referenced by Apriori_Trie::is_all_subset_frequent().

---

Friends And Related Function Documentation

friend class Apriori_Trie [friend]

Definition at line 47 of file Trie.hpp.

---

Member Data Documentation

countertype Trie::counter [private]

counter stores the occurrence of the itemset represented by the Trie Definition at line 82 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 88 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(), and ~Trie().

---

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

• Trie.hpp
• Trie.cpp

---