tudocomp
– The TU Dortmund Compression Framework
tdc::KarpRabinHash Class Reference

This is a randomized version of the Karp-Rabin hash function. More...

#include <rabinkarphash.h>

Inheritance diagram for tdc::KarpRabinHash:
tdc::Algorithm

Public Types

typedef uint64_t hashvaluetype
 
typedef unsigned char chartype
 
typedef hashvaluetype key_type
 

Public Member Functions

void operator+= (char c)
 
hashvaluetype operator() () const
 
void clear ()
 
 KarpRabinHash (Env &&env)
 
template<class container >
hashvaluetype hash (container &c)
 
void eat (chartype inchar)
 
void update (chartype outchar, chartype inchar)
 
- Public Member Functions inherited from tdc::Algorithm
virtual ~Algorithm ()=default
 
 Algorithm (Algorithm const &)=default
 
 Algorithm (Algorithm &&)=default
 
Algorithmoperator= (Algorithm const &)=default
 
Algorithmoperator= (Algorithm &&)=default
 
 Algorithm (Env &&env)
 Instantiates an algorithm in the specified environment. More...
 
Envenv ()
 Provides access to the environment that the algorithm works in. More...
 
const Envenv () const
 

Static Public Member Functions

static Meta meta ()
 

Public Attributes

hashvaluetype hashvalue
 
int n
 
const int wordsize
 
CharacterHash< hashvaluetype, chartypehasher
 
const hashvaluetype HASHMASK
 
hashvaluetype BtoN
 

Static Public Attributes

static const hashvaluetype B =37
 

Detailed Description

This is a randomized version of the Karp-Rabin hash function.

Each instance is a rolling hash function meant to hash streams of characters. Each new instance of this class comes with new random keys.

Recommended usage to get L-bit hash values over n-grams: KarpRabinHash<> hf(n,L ); for(uint32 k = 0; k<n;++k) { unsigned char c = ... ; // grab some character hf.eat(c); // feed it to the hasher } while(...) { // go over your string hf.hashvalue; // at all times, this contains the hash value unsigned char c = ... ;// points to the next character unsigned char out = ...; // character we want to forget hf.update(out,c); // update hash value }

Definition at line 28 of file rabinkarphash.h.

Member Typedef Documentation

typedef unsigned char tdc::KarpRabinHash::chartype

Definition at line 31 of file rabinkarphash.h.

Definition at line 30 of file rabinkarphash.h.

Definition at line 32 of file rabinkarphash.h.

Constructor & Destructor Documentation

tdc::KarpRabinHash::KarpRabinHash ( Env &&  env)
inline

Definition at line 43 of file rabinkarphash.h.

Member Function Documentation

void tdc::KarpRabinHash::clear ( )
inline

Definition at line 39 of file rabinkarphash.h.

void tdc::KarpRabinHash::eat ( chartype  inchar)
inline

Definition at line 70 of file rabinkarphash.h.

template<class container >
hashvaluetype tdc::KarpRabinHash::hash ( container &  c)
inline

Definition at line 55 of file rabinkarphash.h.

static Meta tdc::KarpRabinHash::meta ( )
inlinestatic

Definition at line 33 of file rabinkarphash.h.

hashvaluetype tdc::KarpRabinHash::operator() ( ) const
inline

Definition at line 38 of file rabinkarphash.h.

void tdc::KarpRabinHash::operator+= ( char  c)
inline

Definition at line 37 of file rabinkarphash.h.

void tdc::KarpRabinHash::update ( chartype  outchar,
chartype  inchar 
)
inline

Definition at line 76 of file rabinkarphash.h.

Member Data Documentation

const hashvaluetype tdc::KarpRabinHash::B =37
static

Definition at line 87 of file rabinkarphash.h.

hashvaluetype tdc::KarpRabinHash::BtoN

Definition at line 86 of file rabinkarphash.h.

CharacterHash<hashvaluetype,chartype> tdc::KarpRabinHash::hasher

Definition at line 84 of file rabinkarphash.h.

const hashvaluetype tdc::KarpRabinHash::HASHMASK

Definition at line 85 of file rabinkarphash.h.

hashvaluetype tdc::KarpRabinHash::hashvalue

Definition at line 81 of file rabinkarphash.h.

int tdc::KarpRabinHash::n

Definition at line 82 of file rabinkarphash.h.

const int tdc::KarpRabinHash::wordsize

Definition at line 83 of file rabinkarphash.h.


The documentation for this class was generated from the following file: