dffast.cc

Apriori Algorithm written in Java

//
// C++ program that finds frequent itemsets - file dffast.cc
// December 12, 2003
// Wim Pijls and Walter Kosters
// Erasmus University Rotterdam and Leiden University, The Netherlands
// [e-mail] and [e-mail]
// http://www.liacs.nl/home/kosters/df/
//
// makefile: g++ -Wall -O3 -o fim_all dffast.cc
//
// Assume that the relevant database and the trie containing all frequent
// sets together fit in main memory; relevant here means: all transactions
// that contain at least 2 frequent items (the so-called relevant
// transactions), whereas only frequent items are considered. Every byte 
// contains 8 bits of the database. So its size is the number of 
// frequent items times the number of relevant transactions divided by 8.
//
// The data is read four times:
// 1. to find minimal and maximal item number that occurs
// 2. to determine the frequencies of the single item numbers
// 3. to find the relevant transactions (containing at least 2 frequent items)
// 4. to store the (relevant) database in main memory
//
// Several (time) printing commands are commented out with //
//
// This version (dffast.cc) replaces previous versions dfmemory.cc
// and dftime.cc; main difference: memory management is improved
// in order to avoid unnecessary allocations, which makes different
// memory/time efficient versions obsolete.
// Runtimes are comparable with those of its predecessors
// 

// name inputfile:
#define input_filename argv[1]
// (absolute) value of minsup:
#define macro_minsup atoi(argv[2])
// name outputfile:
#define output_filename argv[3]

#include <iostream>
#include <fstream>
#include <cstdio>
#include <cstdlib>
#include <ctime>
using namespace std;

typedef char *transaction;
const int MAXDEPTH = 100; // maximal depth of trie (for printing)

int minsup;               // minimum support
int therow;               // number of currect transaction
transaction globpointer;  // current transaction
transaction *dataset;     // the whole database
char vector[8];           // masks for fast
char *supervector;        //   array addressing

class initialcounts
{
  public:
    initialcounts (char *inputdata);
    static int *itemsorder;
    static int *items_frequency;
    static short *ranking;
    static int min_itemnr, max_itemnr;
    static int number_transactions, number_freq_items, lines;
  private:
    void first_pass ( );
    void second_pass ( );
    void third_pass ( );
    void initialsort ( );
    char *infilename;
    int *init_items_frequency;
};

class data_array
{
  public:
    data_array (char *inputdata);
  private:
    char *next_transaction;
    void inputread (char *inputdata);
};

struct bucket
{
  short itemvalue;
  int count;
  int aux;
  // if 2-itemsets have support < 60000, change
  // "int" into "unsigned short" (twice)
  short number_followers;
  struct bucket *next;
};

void count (bucket *trienode, short number_buckets);

// does currect transaction (globpointer) contain item "column"?
inline int inspect (int column)
{
  return ( ( globpointer[column >> 3] & supervector[column] ) );
}//inspect

class trie
{
  public:
    trie ( ) { };
    trie (initialcounts & initialdata, data_array & datagrid);
    void build_up ( );
    void printtrie (char *outputdata);
  private:
    int length_count[MAXDEPTH];
    void extend (int k);
    void makeaux0 (bucket *root, int number);
    FILE *outfilename;
    struct bucket *root;
    int triesize;
    int results[MAXDEPTH];
    void copying (struct bucket *p, struct bucket *q, int number_q_buckets);
    void printout (int depth, struct bucket *trienode, int number_buckets);
};

int *initialcounts::items_frequency = NULL;
short *initialcounts::ranking = NULL;
int *initialcounts::itemsorder = NULL;
int initialcounts::number_transactions = 0;
int initialcounts::lines = 0;
int initialcounts::number_freq_items = 0;
int initialcounts::min_itemnr = 0;
int initialcounts::max_itemnr = 0;

// constructor
initialcounts::initialcounts (char *inputdata)
{
  infilename = inputdata;
  first_pass ( );
  second_pass ( );
  third_pass ( );
  initialsort ( );
}//initialcounts::initialcounts

// computes minimal and maximal item number that occur in the database;
// if these are known in advance, this function can be easily adapted
// function reads whole file!
void initialcounts::first_pass ( )
{
  int itemnr;
  bool first = true;
  ifstream fin (infilename);
  if ( ! fin ) 
    cout << "No such filename" << endl;
  char c; 
  int pos;
  do {
    do {
      fin.get (c);
      itemnr = 0;
      pos = 0;
      while ( ( c >= '0' ) && ( c <= '9' ) && ! fin.eof ( ) )
      {
        itemnr = 10*itemnr + (int)(c) - (int)('0');
        pos++;
        fin.get (c);
      }//while
      if ( pos ) {
	if ( first )
          max_itemnr = min_itemnr = itemnr;
	first = false;
        if ( itemnr < min_itemnr )
          min_itemnr = itemnr;
        else if ( itemnr > max_itemnr )
          max_itemnr = itemnr;
      }//if
    } while ( c != '\n' && ! fin.eof ( ) );
  } while ( ! fin.eof ( ) );
  fin.close ( );
}//initialcounts::first_pass

// determines frequency for all items, and number of frequent items
// function reads whole file!
void initialcounts::second_pass ( )
{
  int k;
  ifstream fin (infilename);
  if ( ! fin ) 
    cout << "No such filename" << endl;
  int itemrange = max_itemnr-min_itemnr+1;
  init_items_frequency = new int[itemrange];
  for ( k = 0; k < itemrange; k++ ) 
    init_items_frequency[k] = 0;
  char c; 
  int item, pos;
  do {
    do	{
      fin.get (c);
      item = 0;
      pos = 0;
      while ( ( c >= '0' ) && ( c <= '9' ) && ! fin.eof ( ) )
      {
        item = 10*item + (int)(c) - (int)('0');
        pos++;
        fin.get (c);
      }//while
      if ( pos )
        init_items_frequency[item-min_itemnr]++;
    } while ( c != '\n' && ! fin.eof ( ) );
  } while ( ! fin.eof ( ) );
  fin.close ( );
  for ( k = 0; k < itemrange; k++ )
    if ( init_items_frequency[k] >= minsup )
      number_freq_items++;
//  printf ("Number of frequent items: %d\n", number_freq_items);
}//initialcounts::second_pass

// determines number of relevant transactions, i.e., those
// that contain at least two frequent items
// (those that contain one frequent item have already been accounted for
// while determining the frequency of the single items)
// function reads whole file!
void initialcounts::third_pass ( )
{
  number_transactions = 0;
  ifstream fin (infilename);
  if ( ! fin ) 
    cout << "No such filename" << endl;
  char c;
  int item, pos, items_in_trans;
  bool line;
  do {  
    line = false;
    items_in_trans = 0;
    do {
      fin.get (c);
      item = 0;
      pos = 0;
      while ( ( c >= '0' ) && ( c <= '9' ) && ! fin.eof ( ) )
      {
        item = 10*item + (int)(c) - (int)('0');
        pos++;
        line = true;
        fin.get (c);
      }//while
      if ( pos && init_items_frequency[item-min_itemnr] >= minsup )
        items_in_trans++;
    } while ( c != '\n' && ! fin.eof ( ) );
    if ( line ) 
      lines++;
    if ( items_in_trans >= 2 ) 
      number_transactions++;
  } while ( ! fin.eof ( ) );
//  printf ("Number of relevant transactions: %d\n", number_transactions);
//  printf ("Number of lines: %d\n", lines);
  fin.close ( );
}//initialcounts::third_pass

// sort items with respect to support - and renumber
void initialcounts::initialsort ( )
{
  int left_cursor = 0;
  int right_cursor = max_itemnr-min_itemnr;
  int itemrange = right_cursor+1;
  int *items_numbers;
  int i, j, k;
  items_numbers = new int[number_freq_items];
  for ( k = 0; k < number_freq_items; k++ )
    items_numbers[k] = k;
  while ( left_cursor < right_cursor )
  {