Spec OpenAddressingQGramIndex
A q-gram that uses open addressing hashing instead of an array.

Extends IndexQGram
All Extended Index, IndexQGram
All Impl'd StringTrieConcept
Defined in <seqan/index.h>
Signature template <typename TIndex, typename TShapeSpec> class Index<TText, IndexQGram<TShapeSpec, OpenAddressing> >;

Template Parameters

TText The text type.
TShapeSpec The Shape specialization type.

Interface Function Overview

Interface Functions Inherited From Index

Interface Functions Inherited From IndexQGram

Interface Metafunction Overview

Interface Metafunctions Inherited From Index

Member Variable Overview

Detailed Description

This index uses a non-trivial hashing for mapping q-gram hash values to buckets. This reduces the sizes of bucket directories (QGramDir, QGramCountsDir fibres) from Σq to min(α · n, \Sigmaq), for a load factor α > 1. A bucket still stores occurrences (or counts) of the same q-gram, but in contrast to the IndexQGram index, buckets are in random order due to the hashing.

Member Variables Detail

double OpenAddressingQGramIndex::alpha

Load factor. Controls space/time-tradeoff and must be greater 1. Default value is 1.6.