tract.c

Data Minig中的FP GROWTH 算法,附带test实例及实验数据分析

int ta_filter (int *items, int n, const char *marks)
{                              
  int i, k;                    

  assert(items && (n >= 0));    
  for (i = k = 0; i < n; i++)  
    if (marks[items[i]]) items[k++] = items[i];
  return k;                     
} 

/*--------------------------------------------------------------------*/

static int ta_cmp (const void *p1, const void *p2, void *data)
{                               
  int       k, k1, k2;          
  const int *i1, *i2;           

  assert(p1 && p2);             
  i1 = ((const TRACT*)p1)->items;
  i2 = ((const TRACT*)p2)->items;
  k1 = ((const TRACT*)p1)->cnt; 
  k2 = ((const TRACT*)p2)->cnt; 
  for (k  = (k1 < k2) ? k1 : k2; --k >= 0; i1++, i2++) {
    if (*i1 > *i2) return  1;  
    if (*i1 < *i2) return -1;  
  }                            
  if (k1 > k2) return  1;      
  if (k1 < k2) return -1;      
  return 0;                    
}  

/*--------------------------------------------------------------------*/

static int ta_cmpx (const TRACT *ta, const int *items, int n)
{                               
  int       k, m;               
  const int *p;                 

  assert(ta && items);         
  p = ta->items; m = ta->cnt;  
  m = ta->cnt;
  for (k = (n < m) ? n : m; --k >= 0; p++, items++) {
    if (*p > *items) return  1; 
    if (*p < *items) return -1; 
  }                             
  if (m > n) return  1;         
  if (m < n) return -1;         
  return 0;                     
}  



TASET* tas_create (ITEMSET *itemset)
{                               
  TASET *taset;                 

  assert(itemset);              
  taset = malloc(sizeof(TASET));
  if (!taset) return NULL;      
  taset->itemset = itemset;     
  taset->cnt     = taset->vsz = taset->max = taset->total = 0;
  taset->tracts  = NULL;        
  return taset;                 
}  

/*--------------------------------------------------------------------*/

void tas_delete (TASET *taset, int delis)
{                               
  assert(taset);                
  if (taset->tracts) {          
    while (--taset->cnt >= 0)   
      free(taset->tracts[taset->cnt]);
    free(taset->tracts);      
  }                           
  if (delis && taset->itemset) is_delete(taset->itemset);
  free(taset);                  
}          

/*--------------------------------------------------------------------*/

int tas_add (TASET *taset, const int *items, int n)
{                               
  TRACT *ta;                    
  int   *p;                     
  TRACT **vec;                  
  int   size;                   

  assert(taset);                
  size = taset->vsz;            
  if (taset->cnt >= size) {     
    size += (size > BLKSIZE) ? (size >> 1) : BLKSIZE;
    vec   = (TRACT**)realloc(taset->tracts, size *sizeof(TRACT*));
    if (!vec) return -1;       
    taset->tracts = vec; taset->vsz = size;
  }                             
  if (!items) {                 
    items = is_tract(taset->itemset);
    n     = is_tsize(taset->itemset);
  }                             
  ta = (TRACT*)malloc(sizeof(TRACT) +(n-1) *sizeof(int));
  if (!ta) return -1;           
  taset->tracts[taset->cnt++]  = ta;
  if (n > taset->max)           
    taset->max = n;             
  taset->total += n;           
  for (p = ta->items +(ta->cnt = n); --n >= 0; )
    *--p = items[n];            
  return 0;                    
}  

/*--------------------------------------------------------------------*/

void tas_recode (TASET *taset, int *map, int cnt)
{                               
  int   i, k, n, x;             
  TRACT *t;                     
  int   *p;                     

  assert(taset && map);         
  taset->max = taset->total = 0;
  for (n = taset->cnt; --n >= 0; ) {
    t = taset->tracts[n];       
    p = t->items;               
    for (i = k = 0; i < t->cnt; i++) {
      x = map[p[i]];            
      if (x < cnt) p[k++] = x;  
    }                           
    if (k > taset->max)         
      taset->max = k;           
    taset->total += k;          
    ta_sort(t->items, t->cnt = k);
  }                            
}  

/*--------------------------------------------------------------------*/

int tas_filter (TASET *taset, const char *marks)
{                               
  int   i, max = 0;             
  TRACT *t;                    

  assert(taset && marks);       
  taset->total = 0;             
  for (i = taset->cnt; --i >= 0; ) {
    t = taset->tracts[i];       
    t->cnt = ta_filter(t->items, t->cnt, marks);
    if (t->cnt > max) max = t->cnt;
    taset->total += t->cnt;     
  }                             
  return max;                   
}  

/*--------------------------------------------------------------------*/

void tas_sort (TASET *taset, int heap)
{                               
  assert(taset);                
  if (heap) v_heapsort(taset->tracts, taset->cnt, ta_cmp, NULL);
  else      v_sort    (taset->tracts, taset->cnt, ta_cmp, NULL);
} 

/*--------------------------------------------------------------------*/

int tas_occur (TASET *taset, const int *items, int n)
{                               
  int l, r, m, k = taset->cnt;  

  assert(taset && items);       
  for (r = m = 0; r < k; ) {    
    m = (r + k) >> 1;           
    if (ta_cmpx(taset->tracts[m], items, n) > 0) k = m;
    else                                         r = m+1;
  }
  for (l = m = 0; l < k; ) {    
    m = (l + k) >> 1;           
    if (ta_cmpx(taset->tracts[m], items, n) < 0) l = m+1;
    else                                         k = m;
  }
  return r -l;                  
}  

/*--------------------------------------------------------------------*/
#ifndef NDEBUG

void tas_show (TASET *taset)
{                               
  int   i, k;                   
  TRACT *t;                     

  assert(taset);                
  for (i = 0; i < taset->cnt; i++) {
    t = taset->tracts[i];      
    for (k = 0; k < t->cnt; k++) {  
      if (k > 0) putc(' ', stdout); 
      printf(is_name(taset->itemset, t->items[k]));
    }                           
    putc('\n', stdout);         
  }                             
  printf("%d transaction(s)\n", taset->cnt);
}  /* tas_show() */

#endif


TATREE* _create (TRACT **tracts, int cnt, int index)
{                              
  int    i, k, t;               
  int    item, n;               
  TATREE *tat;                  
  TATREE **vec;                 

  assert(tracts                 
     && (cnt >= 0) && (index >= 0));
  if (cnt <= 1) {               
    n   = (cnt > 0) ? (*tracts)->cnt -index : 0;
    tat = (TATREE*)malloc(sizeof(TATREE) +(n-1) *sizeof(int));
    if (!tat) return NULL;     
    tat->cnt  = cnt;            
    tat->size = -n;
    tat->max  =  n;
    while (--n >= 0) tat->items[n] = (*tracts)->items[index +n];
    return tat;
  }
  for (k = cnt; (--k >= 0) && ((*tracts)->cnt <= index); )
    tracts++;                  
  n = 0; item = -1;             
  for (tracts += i = ++k; --i >= 0; ) {
    t = (*--tracts)->items[index]; 
    if (t != item) { item = t; n++; }
  }                             
  #ifdef ARCH64                 
  i = (n & 1) ? n : (n+1);      
  #else                          
  i = n;                        
  #endif                        
  tat = (TATREE*)malloc(sizeof(TATREE) + (i-1) *sizeof(int)
                                       + n     *sizeof(TATREE*));
  if (!tat) return NULL;        
  tat->cnt  = cnt;              
  tat->size = n;
  tat->max  = 0;
  if (n <= 0) return tat;       
  vec  = (TATREE**)(tat->items +i);
  item = tracts[--k]->items[index];
  for (tracts += i = k; --i >= 0; ) {
    t = (*--tracts)->items[index];     
    if (t == item) continue;   
    tat->items[--n] = item; item = t;
    vec[n] = _create(tracts+1, k-i, index+1);
    if (!vec[n]) break;         
    t = vec[n]->max +1; if (t > tat->max) tat->max = t;
    k = i;                      
  }                             
  if (i < 0) {                  
    tat->items[--n] = item;    
    vec[n] = _create(tracts, k+1, index+1);
    if (vec[n]) {               
      t = vec[n]->max +1; if (t > tat->max) tat->max = t;
      return tat;               
    }                           
  }                             
  for (i = tat->size; --i > n; ) tat_delete(vec[i]);
  free(tat);                   
  return NULL;                 
}  

/*--------------------------------------------------------------------*/

TATREE* tat_create (TASET *taset, int heap)
{                               
  assert(taset);                
  if (heap) v_heapsort(taset->tracts, taset->cnt, ta_cmp, NULL);
  else      v_sort    (taset->tracts, taset->cnt, ta_cmp, NULL);
  return _create(taset->tracts, taset->cnt, 0);
}  

/*--------------------------------------------------------------------*/

void tat_delete (TATREE *tat)
{                               
  int    i;                     
  TATREE **vec;                 

  assert(tat);                  
  #ifdef ARCH64                 
  i = (tat->size & 1) ? tat->size : (tat->size+1);
  #else                         
  i = tat->size;               
  #endif                        
  vec = (TATREE**)(tat->items +i);
  for (i = tat->size; --i >= 0; )
    tat_delete(vec[i]);         
  free(tat);                    
}  

/*--------------------------------------------------------------------*/
#ifdef ARCH64

TATREE* tat_child (TATREE *tat, int index)
{                              
  int s;                       

  assert(tat                    
     && (index >= 0) && (index < tat->size));
  s = (tat->size & 1) ? tat->size : (tat->size +1);
  return ((TATREE**)(tat->items +s))[index];
}  

#endif
/*--------------------------------------------------------------------*/

void tat_mark (TATREE *tat)
{                               
  int i;                        

  assert(tat);                  
  if      (tat->size < 0)       
    tat->items[tat->max-1] |= INT_MIN;  
  else {                        
    for (i = tat->size; --i >= 0; )
      tat_mark(tat_child(tat, i));
  }                             
} 

/*--------------------------------------------------------------------*/
#ifndef NDEBUG

void _show (TATREE *tat, int ind)
{                               
  int    i, k;                 
  TATREE **vec;                

  assert(tat && (ind >= 0));    
  if (tat->size <= 0) {         
    for (i = 0; i < tat->max; i++)
      printf("%d ", tat->items[i] & ~INT_MIN);
    printf("\n"); return;       
  }                             
  vec = (TATREE**)(tat->items +tat->size);
  for (i = 0; i < tat->size; i++) {
    if (i > 0) for (k = ind; --k >= 0; ) printf("  ");
    printf("%d ", tat->items[i]);
    _show(vec[i], ind+1);       
  }                             
}  

/*--------------------------------------------------------------------*/

void tat_show (TATREE *tat)
{                               
  assert(tat);                  
  _show(tat, 0);                
}  

#endif