#include <Trie.hpp>
Inheritance diagram for Trie:
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< itemtype > | maxpath |
maxpath stores the length of the longest paths. | |
vector< itemtype > | orderarray |
The frequency order of the items. | |
vector< itemtype > | inv_orderarray |
inverse of orderarray: orderarray[inv_orderarray[i]]=i |
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.
|
|
|
|
|
Adds an empty state to the trie.
Reimplemented in Trie_hash. |
|
Reimplemented in Trie_hash. |
|
|
|
Generates association rules.
|
|
Recodes the basket so that each item is substituted by its s frequency order (inv_orderarray[]).
|
|
Generates candidates.
|
|
Generates candidate of size more than two.
Reimplemented in Trie_hash. |
|
Generates candidate of size two.
|
|
Deletes the edge that goes to a given state.
Reimplemented in Trie_hash. |
|
Deletes unfrequent itemsets.
|
|
Deletes the nodes that represent infrequent itemsets.
Reimplemented in Trie_hash. |
|
Deletes the nodes that represent infrequent itemsets of size 1.
Reimplemented in Trie_hash. |
|
Deletes the nodes that represent infrequent itemsets of size 2.
temp_counter_array[stateIndex_1-1] will never be used again! temp_counter_array will never be used again! Reimplemented in Trie_hash. |
|
Increases the counter of those candidates that are contained by the given basket.
|
|
Increases the counter for those itemsets that is contained by the given basket.
Reimplemented in Trie_hash. |
|
Increases the counter for those items that are in the given basket.
|
|
Increases the counter for those itempairs that are in the given basket.
|
|
Decides if all subset of an itemset is contained in the trie.
|
|
It decides whether the given itemset is included in the trie or not.
Reimplemented in Trie_hash. |
|
Sets the maximal path value.
Reimplemented in Trie_hash. |
|
Returns the number of nodes in the trie.
|
|
Displays the trie.
Reimplemented in Trie_hash. |
|
Displays the memory need of the trie.
Reimplemented in Trie_hash. |
|
Writes the content (frequent itemsets) to the file.
|
|
Writes out the content of the trie (frequent itemset and counters).
Reimplemented in Trie_hash. |
|
countervector stores the occurences of the itemsets countervector[i] stores the occurence of the itemset represented by the ith node. |
|
inverse of orderarray: orderarray[inv_orderarray[i]]=i
|
|
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). |
|
maxpath stores the length of the longest paths. maxpath[i] stores the legth of the longest path starting from the ith node. |
|
The frequency order of the items. orderarray[1] is the most frequent item, orderarray[2] is the second most frequent... |
|
|
|
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). |
|
temp_counter_array stores the occurences of the itempairs temp_counter_array[i][j] stores the occurence of the itempair (orderarray[i],orderarray[j]). |