Class EliasFanoEncoder
Encode a non decreasing sequence of non negative whole numbers in the Elias-Fano encoding that was introduced in the 1970's by Peter Elias and Robert Fano.
The Elias-Fano encoding is a high bits / low bits representation of
a monotonically increasing sequence of numValues > 0 natural numbers x[i]
0 <= x[0] <= x[1] <= ... <= x[numValues-2] <= x[numValues-1] <= upperBound
where upperBound > 0 is an upper bound on the last value.
The Elias-Fano encoding uses less than half a bit per encoded number more than the smallest representation that can encode any monotone sequence with the same bounds.
The lower L bits of each x[i] are stored explicitly and contiguously
in the lower-bits array, with L chosen as (Log() base 2):
L = max(0, floor(log(upperBound/numValues)))
The upper bits are stored in the upper-bits array as a sequence of unary-coded gaps (x[-1] = 0):
(x[i]/2L) - (x[i-1]/2L)
The unary code encodes a natural number n by n 0 bits followed by a 1 bit:
0...01.
In the upper bits the total the number of 1 bits is numValues
and the total number of 0 bits is:
floor(x[numValues-1]/2L) <= upperBound/(2max(0, floor(log(upperBound/numValues)))) <= 2numValues
The Elias-Fano encoding uses at most
2 + Ceil(Log(upperBound/numValues))
bits per encoded number. With upperBound in these bounds (p is an integer):
2p < x[numValues-1] <= upperBound <= 2*(p+1)
the number of bits per encoded number is minimized.
In this implementation the values in the sequence can be given as long,
numValues = 0 and upperBound = 0 are allowed,
and each of the upper and lower bit arrays should fit in a long[].
An index of positions of zero's in the upper bits is also built.
this implementation is based on this article:
Sebastiano Vigna, "Quasi Succinct Indices", June 19, 2012, sections 3, 4 and 9. Retrieved from http://arxiv.org/pdf/1206.4300 .
The articles originally describing the Elias-Fano representation are:
Peter Elias, "Efficient storage and retrieval by content and address of static files", J. Assoc. Comput. Mach., 21(2):246â€"260, 1974.
Robert M. Fano, "On the number of bits required to implement an associative memory", Memorandum 61, Computer Structures Group, Project MAC, MIT, Cambridge, Mass., 1971.
@lucene.internal
Inheritance
Assembly: DistributedLucene.Net.dll
Syntax
public class EliasFanoEncoder : objectConstructors
| Name | Description |
|---|---|
| EliasFanoEncoder(Int64, Int64) | Construct an Elias-Fano encoder using DEFAULT_INDEX_INTERVAL. |
| EliasFanoEncoder(Int64, Int64, Int64) | Construct an Elias-Fano encoder.
After construction, call EncodeNext(Int64) |
Fields
| Name | Description |
|---|---|
| DEFAULT_INDEX_INTERVAL | The default index interval for zero upper bits. |
Properties
| Name | Description |
|---|---|
| IndexBits | Expert. The index bits. |
| LowerBits | Expert. The low bits. |
| UpperBits | Expert. The high bits. |
Methods
| Name | Description |
|---|---|
| EncodeNext(Int64) | Call at most Lucene.Net.Util.Packed.EliasFanoEncoder.numValues times to encode a non decreasing sequence of non negative numbers. |
| Equals(Object) | |
| GetDecoder() | Returns an EliasFanoDecoder to access the encoded values. Perform all calls to EncodeNext(Int64) before calling GetDecoder(). |
| GetHashCode() | |
| SufficientlySmallerThanBitSet(Int64, Int64) | Provide an indication that it is better to use an EliasFanoEncoder than a FixedBitSet to encode document identifiers. This indication is not precise and may change in the future. An EliasFanoEncoder is favored when the size of the encoding by the EliasFanoEncoder (including some space for its index) is at most about 5/6 of the size of the FixedBitSet, this is the same as comparing estimates of the number of bits accessed by a pair of FixedBitSets and by a pair of non indexed EliasFanoDocIdSets when determining the intersections of the pairs. A bit set is preferred when It is assumed that DEFAULT_INDEX_INTERVAL is used. |
| ToString() |
