hash.cpp

apriori算法是数据挖掘的经典算法,它基于关联规则的思想.此为我的第3个收藏

#include <stdlib.h>
#include <malloc.h> 
#include <string.h>
#include <stdio.h>
#include <math.h>

#include "hash.h"
#include "util.h"

HashTree::HashTree()
{

    root = newnode(LEAF);
    return;

}

HashTree::~HashTree()
{

    freenode(root);
    root = (HashNode *)NULL;
    return;

}

//  Produces a hash code for a item set.
int HashTree::hash(ItemSet *itemset, int level)
{

    return((int)(itemset->itemof(level) % TABLE_SIZE));

}


/* creates a new cell accordint to the desired type (t) and fill it with null values*/
HashNode* HashTree::newnode(int nodetype)
{
    HashNode *node;

    node = (HashNode*) new HashNode();
    node->nodetype = nodetype;
    
    if (nodetype == INTERNAL)
    {
        for (int i = 0; i < TABLE_SIZE; i++)
            node->vp.tab[i] = (HashNode *)NULL;
    }
    else
    {
        node->vp.largeset = (ItemSets *)new ItemSets();
    }

    return(node);
};



/* free the sub hash tree with the root node */
void HashTree::freenode(HashNode *node)
{

    if (node->nodetype == INTERNAL)
    {
        for (int i = 0; i < TABLE_SIZE; i++)
        {
            if(node->vp.tab[i] != (HashNode *)NULL)
                freenode(node->vp.tab[i]);
        }
    }
    else
        delete node->vp.largeset;

    delete node;

    return;
}


/*inserts a new itemset - s in the hash tree - cp according to the level lev*/
void HashTree :: insert( HashNode **hp, ItemSet *s, int level )
{
    HashNode *c1;
    HashNode *head = (HashNode *) *hp;
    ItemSets *prev;
    ItemSet *pset;
    int i;

    s->support = 0;

    if (head == (HashNode *)NULL)
    {
        head = newnode(LEAF);
        head->vp.largeset->add(s);
    }
    else if(head->nodetype == INTERNAL)
    {
        c1 = head->vp.tab[hash(s, level)];
        insert(&c1, s, level+1);
    }
    else if( (head->vp.largeset->count < BUCKET_SIZE) || (level >= (s->count-1)) )
    {
        head->vp.largeset->add(s);
    }
    else
    {
        prev = head->vp.largeset;

        for (i = 0; i < TABLE_SIZE; i++)
            head->vp.tab[i] = (HashNode *)newnode(LEAF);

        head->nodetype = INTERNAL;

        for(i = 0; i < prev->count; i++)
        {
            pset = prev->pointof(i);
            c1 = head->vp.tab[hash(pset, level)];
            c1->vp.largeset->add(pset);
        }

        delete prev;

        c1 = head->vp.tab[hash(s, level)];
        c1->vp.largeset->add(s);
    }
    
    return;
}



/* increments the counts of each subset of transaction t which are in the hash tree cp (candidate sets)*/
void HashTree :: subset(HashNode *head, ItemSet *t, int m)
{
    ItemSet *node;
    ItemSet *visited;
    int i, j;

    if(m >= t->count)
        return;

    if(head != (HashNode *)NULL)
    {
        if (head->nodetype == INTERNAL ) 
        {
            visited = new ItemSet();

            for (i = m; i < t->count; i++)
            {
                j = t->itemof(i);
                j = j%TABLE_SIZE;
                if(visited->indexof(j) < 0)
                {
                    visited->add(j);
                    subset(head->vp.tab[j], t, i+1);
                }
            }

            delete visited;
        }
        else
        {
            for(i = 0; i < head->vp.largeset->count; i++)
            {
                node = head->vp.largeset->pointof(i);
        
                if((node->diff(t) == MAKEUP) || (node->diff(t) == TOTALEQUAL))
                    node->support++;
            }
        }
    }

    return;
}





/* 
   traverses the hash tree - cp, collects the itemsets in a list of itemsets - p1
   and frees the cells of the hash trees********** stands for go and release
*/

void  HashTree :: scan(HashNode *head, ItemSets *result, long minsup) 
{
    ItemSet *node;
    int i, j;
    
    if(head == (HashNode *)NULL)
        return;

    if(head->nodetype == INTERNAL)
    {
        for (i = 0; i < TABLE_SIZE; i++)
            scan(head->vp.tab[i], result, minsup);
    }
    else
    {
        for(i = 0; i < head->vp.largeset->count; i++)
        {
            node = head->vp.largeset->pointof(i);

            if(node->support >= minsup)
                result->add(node);
        }
    }
    
    return;
}