classtrie.html
来自「Aprior的C++实现算法」· HTML 代码 · 共 584 行 · 第 1/2 页
HTML
584 行
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"><html><head><meta http-equiv="Content-Type" content="text/html;charset=iso-8859-1"><title>APRIORI algorithm: Trie class Reference</title><link href="doxygen.css" rel="stylesheet" type="text/css"></head><body><!-- Generated by Doxygen 1.3.5 --><div class="qindex"><a class="qindex" href="index.html">Main Page</a> | <a class="qindex" href="namespaces.html">Namespace List</a> | <a class="qindex" href="annotated.html">Class List</a> | <a class="qindex" href="files.html">File List</a> | <a class="qindex" href="functions.html">Class Members</a> | <a class="qindex" href="globals.html">File Members</a></div><h1>Trie Class Reference</h1>This class represent a general Trie. <a href="#_details">More...</a><p><code>#include <<a class="el" href="Trie_8hpp-source.html">Trie.hpp</a>></code><p>Collaboration diagram for Trie:<center><font size="2">[<a href="graph_legend.html">legend</a>]</font></center><a href="classTrie-members.html">List of all members.</a><table border=0 cellpadding=0 cellspacing=0><tr><td></td></tr><tr><td colspan=2><br><h2>Public Member Functions</h2></td></tr><tr><td class="memItemLeft" nowrap align=right valign=top> </td><td class="memItemRight" valign=bottom><a class="el" href="classTrie.html#a0">Trie</a> (<a class="el" href="classTrie.html">Trie</a> *parent_trie, const unsigned long init_counter)</td></tr><tr><td class="memItemLeft" nowrap align=right valign=top>const <a class="el" href="classTrie.html">Trie</a> * </td><td class="memItemRight" valign=bottom><a class="el" href="classTrie.html#a1">is_included</a> (const set< <a class="el" href="common_8hpp.html#a0">itemtype</a> > &an_itemset, set< <a class="el" href="common_8hpp.html#a0">itemtype</a> >::const_iterator item_it) const </td></tr><tr><td class="mdescLeft"> </td><td class="mdescRight">It decides whether the given itemset is included in the trie or not. <a href="#a1"></a><br><br></td></tr><tr><td class="memItemLeft" nowrap align=right valign=top>void </td><td class="memItemRight" valign=bottom><a class="el" href="classTrie.html#a2">find_candidate</a> (const vector< <a class="el" href="common_8hpp.html#a0">itemtype</a> > &basket, const <a class="el" href="common_8hpp.html#a0">itemtype</a> distance_from_candidate, vector< <a class="el" href="common_8hpp.html#a0">itemtype</a> >::const_iterator it_basket, const unsigned long counter_incr=1)</td></tr><tr><td class="mdescLeft"> </td><td class="mdescRight">Increases the counter for those itemsets that is contained by the given basket. <a href="#a2"></a><br><br></td></tr><tr><td class="memItemLeft" nowrap align=right valign=top>void </td><td class="memItemRight" valign=bottom><a class="el" href="classTrie.html#a3">delete_infrequent</a> (const double min_occurrence, const <a class="el" href="common_8hpp.html#a0">itemtype</a> distance_from_candidate)</td></tr><tr><td class="mdescLeft"> </td><td class="mdescRight">Deletes the tries that represent infrequent itemsets. <a href="#a3"></a><br><br></td></tr><tr><td class="memItemLeft" nowrap align=right valign=top>void </td><td class="memItemRight" valign=bottom><a class="el" href="classTrie.html#a4">show_content_preorder</a> () const </td></tr><tr><td class="mdescLeft"> </td><td class="mdescRight">Shows the content in a preorder manner. <a href="#a4"></a><br><br></td></tr><tr><td class="memItemLeft" nowrap align=right valign=top> </td><td class="memItemRight" valign=bottom><a class="el" href="classTrie.html#a5">~Trie</a> ()</td></tr><tr><td colspan=2><br><h2>Private Member Functions</h2></td></tr><tr><td class="memItemLeft" nowrap align=right valign=top>void </td><td class="memItemRight" valign=bottom><a class="el" href="classTrie.html#d0">max_path_set</a> ()</td></tr><tr><td class="mdescLeft"> </td><td class="mdescRight">Sets the maximal path value. <a href="#d0"></a><br><br></td></tr><tr><td class="memItemLeft" nowrap align=right valign=top>void </td><td class="memItemRight" valign=bottom><a class="el" href="classTrie.html#d1">add_empty_state</a> (const <a class="el" href="common_8hpp.html#a0">itemtype</a> item, const unsigned long init_counter=0)</td></tr><tr><td class="mdescLeft"> </td><td class="mdescRight">Adds an empty state to the trie. <a href="#d1"></a><br><br></td></tr><tr><td colspan=2><br><h2>Private Attributes</h2></td></tr><tr><td class="memItemLeft" nowrap align=right valign=top><a class="el" href="classTrie.html">Trie</a> * </td><td class="memItemRight" valign=bottom><a class="el" href="classTrie.html#r0">parent</a></td></tr><tr><td class="mdescLeft"> </td><td class="mdescRight">parent stores the address of the parent of the Trie. <a href="#r0"></a><br><br></td></tr><tr><td class="memItemLeft" nowrap align=right valign=top>unsigned long </td><td class="memItemRight" valign=bottom><a class="el" href="classTrie.html#r1">counter</a></td></tr><tr><td class="mdescLeft"> </td><td class="mdescRight">counter stores the occurrence of the itemset represented by the Trie <a href="#r1"></a><br><br></td></tr><tr><td class="memItemLeft" nowrap align=right valign=top>vector< <a class="el" href="structEdge.html">Edge</a> > </td><td class="memItemRight" valign=bottom><a class="el" href="classTrie.html#r2">edgevector</a></td></tr><tr><td class="mdescLeft"> </td><td class="mdescRight">edgevector stores the edges of the root the trie. <a href="#r2"></a><br><br></td></tr><tr><td class="memItemLeft" nowrap align=right valign=top><a class="el" href="common_8hpp.html#a0">itemtype</a> </td><td class="memItemRight" valign=bottom><a class="el" href="classTrie.html#r3">maxpath</a></td></tr><tr><td class="mdescLeft"> </td><td class="mdescRight">maxpath stores the length of the longest path starting from the root node. <a href="#r3"></a><br><br></td></tr><tr><td colspan=2><br><h2>Friends</h2></td></tr><tr><td class="memItemLeft" nowrap align=right valign=top>class </td><td class="memItemRight" valign=bottom><a class="el" href="classTrie.html#n0">MSApriori_Trie</a></td></tr></table><hr><a name="_details"></a><h2>Detailed Description</h2>This class represent a general Trie. <p>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. <p><p>Definition at line <a class="el" href="Trie_8hpp-source.html#l00044">44</a> of file <a class="el" href="Trie_8hpp-source.html">Trie.hpp</a>.<hr><h2>Constructor & Destructor Documentation</h2><a class="anchor" name="a0" doxytag="Trie::Trie" ></a><p><table class="mdTable" width="100%" cellpadding="2" cellspacing="0"> <tr> <td class="mdRow"> <table cellpadding="0" cellspacing="0" border="0"> <tr> <td class="md" nowrap valign="top"> Trie::Trie </td> <td class="md" valign="top">( </td> <td class="md" nowrap valign="top"><a class="el" href="classTrie.html">Trie</a> * </td> <td class="mdname" nowrap> <em>parent_trie</em>, </td> </tr> <tr> <td></td> <td></td> <td class="md" nowrap>const unsigned long </td> <td class="mdname" nowrap> <em>init_counter</em></td> </tr> <tr> <td></td> <td class="md">) </td> <td class="md" colspan="2"></td> </tr> </table> </td> </tr></table><table cellspacing=5 cellpadding=0 border=0> <tr> <td> </td> <td><p><dl compact><dt><b>Parameters:</b></dt><dd> <table border="0" cellspacing="2" cellpadding="0"> <tr><td valign=top><em>parent_trie</em> </td><td>The pointer to the parent of the new trie </td></tr> <tr><td valign=top><em>init_counter</em> </td><td>The initial counter of the new trie </td></tr> </table></dl><p>Definition at line <a class="el" href="Trie_8cpp-source.html#l00024">24</a> of file <a class="el" href="Trie_8cpp-source.html">Trie.cpp</a>.<p>Referenced by <a class="el" href="Trie_8cpp-source.html#l00150">add_empty_state()</a>. </td> </tr></table><a class="anchor" name="a5" doxytag="Trie::~Trie" ></a><p><table class="mdTable" width="100%" cellpadding="2" cellspacing="0"> <tr> <td class="mdRow"> <table cellpadding="0" cellspacing="0" border="0"> <tr> <td class="md" nowrap valign="top"> Trie::~<a class="el" href="classTrie.html">Trie</a> </td> <td class="md" valign="top">( </td> <td class="mdname1" valign="top" nowrap> </td> <td class="md" valign="top"> ) </td> <td class="md" nowrap></td> </tr> </table> </td> </tr></table><table cellspacing=5 cellpadding=0 border=0> <tr> <td> </td> <td><p><p>Definition at line <a class="el" href="Trie_8cpp-source.html#l00128">128</a> of file <a class="el" href="Trie_8cpp-source.html">Trie.cpp</a>.<p>References <a class="el" href="Trie_8hpp-source.html#l00088">edgevector</a>. </td> </tr></table><hr><h2>Member Function Documentation</h2><a class="anchor" name="d1" doxytag="Trie::add_empty_state" ></a><p><table class="mdTable" width="100%" cellpadding="2" cellspacing="0"> <tr> <td class="mdRow"> <table cellpadding="0" cellspacing="0" border="0"> <tr> <td class="md" nowrap valign="top"> void Trie::add_empty_state </td> <td class="md" valign="top">( </td> <td class="md" nowrap valign="top">const <a class="el" href="common_8hpp.html#a0">itemtype</a> </td> <td class="mdname" nowrap> <em>item</em>, </td> </tr> <tr> <td></td> <td></td> <td class="md" nowrap>const unsigned long </td> <td class="mdname" nowrap> <em>counter</em> = 0</td> </tr> <tr> <td></td> <td class="md">) </td> <td class="md" colspan="2"><code> [private]</code></td> </tr> </table> </td> </tr></table><table cellspacing=5 cellpadding=0 border=0> <tr> <td> </td> <td><p>Adds an empty state to the trie. <p><dl compact><dt><b>Parameters:</b></dt><dd> <table border="0" cellspacing="2" cellpadding="0"> <tr><td valign=top><em>item</em> </td><td>The label of the new edge </td></tr> <tr><td valign=top><em>counter</em> </td><td>The initial counter of the new state </td></tr> </table></dl><p>Definition at line <a class="el" href="Trie_8cpp-source.html#l00150">150</a> of file <a class="el" href="Trie_8cpp-source.html">Trie.cpp</a>.<p>References <a class="el" href="Trie_8hpp-source.html#l00088">edgevector</a>, <a class="el" href="common_8hpp-source.html#l00022">itemtype</a>, <a class="el" href="Trie_8hpp-source.html#l00031">Edge::label</a>, <a class="el" href="Trie_8hpp-source.html#l00032">Edge::subtrie</a>, and <a class="el" href="Trie_8cpp-source.html#l00024">Trie()</a>.<p>Referenced by <a class="el" href="MSApriori__Trie_8cpp-source.html#l00181">MSApriori_Trie::candidate_generation_assist()</a>, and <a class="el" href="MSApriori__Trie_8cpp-source.html#l00030">MSApriori_Trie::insert_frequent_items()</a>. </td> </tr></table><a class="anchor" name="a3" doxytag="Trie::delete_infrequent" ></a><p><table class="mdTable" width="100%" cellpadding="2" cellspacing="0"> <tr> <td class="mdRow"> <table cellpadding="0" cellspacing="0" border="0"> <tr> <td class="md" nowrap valign="top"> void Trie::delete_infrequent </td> <td class="md" valign="top">( </td> <td class="md" nowrap valign="top">const double </td> <td class="mdname" nowrap> <em>min_occurrence</em>, </td> </tr> <tr> <td></td> <td></td> <td class="md" nowrap>const <a class="el" href="common_8hpp.html#a0">itemtype</a> </td> <td class="mdname" nowrap> <em>distance_from_candidate_parent</em></td> </tr> <tr> <td></td> <td class="md">) </td> <td class="md" colspan="2"></td> </tr> </table> </td> </tr></table><table cellspacing=5 cellpadding=0 border=0> <tr> <td> </td> <td><p>Deletes the tries that represent infrequent itemsets. <p><dl compact><dt><b>Parameters:</b></dt><dd> <table border="0" cellspacing="2" cellpadding="0"> <tr><td valign=top><em>min_occurrence</em> </td><td>The occurence threshold </td></tr> <tr><td valign=top><em>distance_from_candidate_parent</em> </td><td>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 </td></tr> </table></dl><p>Definition at line <a class="el" href="Trie_8cpp-source.html#l00089">89</a> of file <a class="el" href="Trie_8cpp-source.html">Trie.cpp</a>.<p>References <a class="el" href="Trie_8hpp-source.html#l00088">edgevector</a>, <a class="el" href="common_8hpp-source.html#l00022">itemtype</a>, <a class="el" href="Trie_8cpp-source.html#l00134">max_path_set()</a>, <a class="el" href="Trie_8hpp-source.html#l00091">maxpath</a>, and <a class="el" href="Trie_8hpp-source.html#l00079">parent</a>. </td> </tr></table><a class="anchor" name="a2" doxytag="Trie::find_candidate" ></a><p><table class="mdTable" width="100%" cellpadding="2" cellspacing="0"> <tr> <td class="mdRow"> <table cellpadding="0" cellspacing="0" border="0"> <tr> <td class="md" nowrap valign="top"> void Trie::find_candidate </td> <td class="md" valign="top">( </td> <td class="md" nowrap valign="top">const vector< <a class="el" href="common_8hpp.html#a0">itemtype</a> > & </td> <td class="mdname" nowrap> <em>basket</em>, </td> </tr> <tr> <td></td> <td></td> <td class="md" nowrap>const <a class="el" href="common_8hpp.html#a0">itemtype</a> </td> <td class="mdname" nowrap> <em>distance_from_candidate</em>, </td> </tr> <tr> <td></td> <td></td> <td class="md" nowrap>vector< <a class="el" href="common_8hpp.html#a0">itemtype</a> >::const_iterator </td> <td class="mdname" nowrap> <em>it_basket</em>, </td> </tr> <tr> <td></td> <td></td> <td class="md" nowrap>const unsigned long </td> <td class="mdname" nowrap> <em>counter_incr</em> = 1</td> </tr> <tr> <td></td> <td class="md">) </td> <td class="md" colspan="2"></td> </tr> </table> </td> </tr></table><table cellspacing=5 cellpadding=0 border=0> <tr> <td> </td> <td>⌨️ 快捷键说明
复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?