– 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:

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

◆ chartype

typedef unsigned char tdc::KarpRabinHash::chartype

Definition at line 31 of file rabinkarphash.h.

◆ hashvaluetype

Definition at line 30 of file rabinkarphash.h.

◆ key_type

Definition at line 32 of file rabinkarphash.h.

Constructor & Destructor Documentation

◆ KarpRabinHash()

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

Definition at line 43 of file rabinkarphash.h.

Member Function Documentation

◆ clear()

void tdc::KarpRabinHash::clear ( )

Definition at line 39 of file rabinkarphash.h.

◆ eat()

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

Definition at line 70 of file rabinkarphash.h.

◆ hash()

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

Definition at line 55 of file rabinkarphash.h.

◆ meta()

static Meta tdc::KarpRabinHash::meta ( )

Definition at line 33 of file rabinkarphash.h.

◆ operator()()

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

Definition at line 38 of file rabinkarphash.h.

◆ operator+=()

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

Definition at line 37 of file rabinkarphash.h.

◆ update()

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

Definition at line 76 of file rabinkarphash.h.

Member Data Documentation

◆ B

const hashvaluetype tdc::KarpRabinHash::B =37

Definition at line 87 of file rabinkarphash.h.

◆ BtoN

hashvaluetype tdc::KarpRabinHash::BtoN

Definition at line 86 of file rabinkarphash.h.

◆ hasher

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.

◆ hashvalue

hashvaluetype tdc::KarpRabinHash::hashvalue

Definition at line 81 of file rabinkarphash.h.

◆ n

int tdc::KarpRabinHash::n

Definition at line 82 of file rabinkarphash.h.

◆ wordsize

const int tdc::KarpRabinHash::wordsize

Definition at line 83 of file rabinkarphash.h.

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