include/hashcounter.h File Reference

#include <stdio.h>

Include dependency graph for hashcounter.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Data Structures
struct	Hashcounter
Defines
#define	hashcounter_hash(counter, chunk, chunk_length, hashValue, position)
Functions
Hashcounter *	hashcounter_new (unsigned long size, unsigned long seed)
void	hashcounter_insert (Hashcounter *counter, uint4 hashValue)
int	hashcounter_multiple (Hashcounter *counter, uint4 hashValue)
int	hashcounter_single (Hashcounter *counter, uint4 hashValue)
unsigned long	hashcounter_insertions (Hashcounter *counter)
void	hashcounter_write (Hashcounter *counter, FILE *stream)
void	hashcounter_count (Hashcounter *counter, FILE *stream)
void	hashcounter_reset (Hashcounter *counter)
void	hashcounter_free (Hashcounter *counter)

---

Detailed Description

The hashcounter is an efficient hash-based phrase occurrence counter specifically designed for the SPEX (Shared Phrase EXtraction) algorithm. The only requirement from the SPEX algorithm of this data structure is that it maintain a record or whether a given phrase occurred in the collection or not. Because false positives are acceptable but false negatives are not, a basic hash structure of an appropriate size is a good choice.

Because the only information that is required is whether a phrase appears multiple times (ie. the exact count is irrelevant), two bits per entry are sufficient. This allows for a large hashtable to be stored quite compactly, minimising the probability of collisions.

Id

hashcounter.h,v 1.12.4.1 2005/05/05 07:24:07 ybernste Exp

Written by Yaniv Bernstein 2004

Definition in file hashcounter.h.

---

Define Documentation

#define hashcounter_hash	(	counter,
		chunk,
		chunk_length,
		hashValue,
		position		)

Value:

if (1) \
{ \
    hashValue = 5381; \
    for (position = 0; position < chunk_length; position++) \
    { \
          hashValue ^= ((hashValue << 7) + chunk[position] + (hashValue >> 2)); \
    } \
}

Definition at line 85 of file hashcounter.h.

Referenced by cluster_spexClusterSequences(), rsdb_slottedSpex(), rsdb_spexClusterSequences(), and rsdb_winnowingSpex().

---

Function Documentation

void hashcounter_count	(	Hashcounter *	counter,
		FILE *	stream
	)

Print out a count of fields with different values

Definition at line 136 of file hashcounter.c.

References Hashcounter::byte_size, Hashcounter::hashtable, and htlookup.

Referenced by cluster_spexClusterSequences(), rsdb_slottedSpex(), and rsdb_winnowingSpex().

{
   uint64_t singles = 0, multiples = 0;
   uint64_t c = 0, d = 0;
   unsigned char cur;

   for (c = 0; c < counter->byte_size; c++)
   {
      cur = counter->hashtable[c];
      for (d = 0; d < 4; d++)
      {
         switch( htlookup[d][cur])
         {
            case 1: 
               singles++;
            case 0:
               break;

            default:
               multiples++;
         }
      }
   }

   fprintf(stream, "Hashcounter state:\nSingles: %"PRIu64"\nDuplicates: %"PRIu64"\n", singles, multiples);

   return;
}

Here is the caller graph for this function:

void hashcounter_free

(

Hashcounter *

counter

)

Clean up the hascounter when you're done.

Definition at line 174 of file hashcounter.c.

References Hashcounter::hashtable.

Referenced by cluster_spexClusterSequences(), rsdb_slottedSpex(), rsdb_spexClusterSequences(), and rsdb_winnowingSpex().

{
   free(counter->hashtable);
   free(counter);

   return;
}

Here is the caller graph for this function:

void hashcounter_insert	(	Hashcounter *	counter,
		uint4	hashValue
	)

Increment the count for the given phrase within the hashcounter. The phrase is given as an array of strings, each containing a single word.

The parameter 'words' indicates the number of words in the phrase, while 'array_size' indicates the size of the array (which is sometimes bigger when hashing subphrases). The 'offset' parameter indicates the position in the array in which the phrase starts -- the array is circular, so when the end of the array is reached, the phrase is assumed to continue at the beginning of the array.

Definition at line 87 of file hashcounter.c.

References Hashcounter::fieldmask, Hashcounter::hashtable, htinsert, Hashcounter::indmask, and Hashcounter::insertions.

Referenced by cluster_spexClusterSequences(), rsdb_slottedSpex(), and rsdb_winnowingSpex().

{
   unsigned long ind, field;
   unsigned char cur;

   ind = (hashValue & counter->indmask) >> 2;
   field = hashValue & counter->fieldmask;

   cur = counter->hashtable[ind];
   counter->hashtable[ind] = htinsert[field][cur];

   counter->insertions++;

   return;
}

Here is the caller graph for this function:

unsigned long hashcounter_insertions

(

Hashcounter *

counter

)

returns the number of phrases that have been inserted into this hashcounter

Definition at line 121 of file hashcounter.c.

References Hashcounter::insertions.

{
   return counter->insertions;
}

int hashcounter_multiple	(	Hashcounter *	counter,
		uint4	hashValue
	)

Returns a nonzero value value if the phrase in question appears more than once in the hashcounter. See the comment for 'hashcounter_new' for notes on the meanings of the various parameters.

Definition at line 103 of file hashcounter.c.

References Hashcounter::hashtable, htlookup, and Hashcounter::indmask.

Referenced by cluster_spexClusterSequences(), rsdb_slottedSpex(), rsdb_spexClusterSequences(), and rsdb_winnowingSpex().

{
   unsigned char cur;

   cur = counter->hashtable[(hashValue & counter->indmask) >> 2];
   return htlookup[hashValue & 3][cur] & 2;

}

Here is the caller graph for this function:

Hashcounter* hashcounter_new	(	unsigned long	size,
		unsigned long	seed
	)

Initialise a new hashcounter of size size. Note that size is the size in bytes -- the hashtable will in fact contain 4 * bytes fields

Definition at line 56 of file hashcounter.c.

References Hashcounter::byte_size, Hashcounter::fieldmask, global_malloc(), hashcounter_reset(), Hashcounter::hashseed, Hashcounter::hashtable, Hashcounter::indmask, init_lookups(), Hashcounter::insertions, and Hashcounter::size.

Referenced by cluster_spexClusterSequences(), rsdb_slottedSpex(), and rsdb_winnowingSpex().

{
   Hashcounter *new_counter;
   int c;

   init_lookups();
   new_counter = (Hashcounter *) global_malloc(sizeof(Hashcounter));

   for (new_counter->indmask = 0, c = 0; c < logsize; c++)
   {
      new_counter->indmask <<= 1;
      new_counter->indmask++;
   }
   new_counter->indmask <<= 2;
   new_counter->fieldmask = 3;
   
   new_counter->byte_size = 1 << logsize;
   /* We can fit 4 entries in each byte */
   new_counter->size = 4 * new_counter->byte_size;
   new_counter->hashseed = seed;
   new_counter->insertions = 0;
   
   new_counter->hashtable = global_malloc(new_counter->byte_size);

   printf("New hashcounter size=%.1f Mb\n", (float)new_counter->byte_size / 1024.0 / 1024.0);

   hashcounter_reset(new_counter);

   return new_counter;
}

Here is the call graph for this function:

Here is the caller graph for this function:

void hashcounter_reset

(

Hashcounter *

counter

)

Clear the hashcounter

Definition at line 165 of file hashcounter.c.

References Hashcounter::byte_size, Hashcounter::hashtable, and Hashcounter::insertions.

Referenced by hashcounter_new().

{

   counter->insertions = 0;
   memset(counter->hashtable, 0, counter->byte_size);

   return;
}

Here is the caller graph for this function:

int hashcounter_single	(	Hashcounter *	counter,
		uint4	hashValue
	)

Definition at line 112 of file hashcounter.c.

References Hashcounter::hashtable, htlookup, and Hashcounter::indmask.

Referenced by cluster_spexClusterSequences(), and rsdb_slottedSpex().

{
   unsigned char cur;

   cur = counter->hashtable[(hashValue & counter->indmask) >> 2];
   return htlookup[hashValue & 3][cur];
   
}

Here is the caller graph for this function:

void hashcounter_write	(	Hashcounter *	counter,
		FILE *	stream
	)

Write the hashtable out to stream 'stream'

Definition at line 126 of file hashcounter.c.

References Hashcounter::hashtable, and Hashcounter::size.

{
   uint64_t c;

   for (c = 0; c < counter->size / 4; c++)
   {
      fputc(counter->hashtable[c], stream);
   }
}

---