Class LongArrayFrontCodedBigList

java.lang.Object
java.util.AbstractCollection<long[]>
it.unimi.dsi.fastutil.objects.AbstractObjectCollection<long[]>
it.unimi.dsi.fastutil.objects.AbstractObjectBigList<long[]>
it.unimi.dsi.fastutil.longs.LongArrayFrontCodedBigList
All Implemented Interfaces:
it.unimi.dsi.fastutil.BigList<long[]>, it.unimi.dsi.fastutil.objects.ObjectBigList<long[]>, it.unimi.dsi.fastutil.objects.ObjectCollection<long[]>, it.unimi.dsi.fastutil.objects.ObjectIterable<long[]>, it.unimi.dsi.fastutil.Size64, it.unimi.dsi.fastutil.Stack<long[]>, Serializable, Cloneable, Comparable<it.unimi.dsi.fastutil.BigList<? extends long[]>>, Iterable<long[]>, Collection<long[]>, RandomAccess

public class LongArrayFrontCodedBigList extends it.unimi.dsi.fastutil.objects.AbstractObjectBigList<long[]> implements Serializable, Cloneable, RandomAccess
Compact storage of big lists of arrays using front-coding (also known as prefix-omission) compression.

This class stores immutably a big list of arrays in a single big array using front coding (of course, the compression will be reasonable only if the list is sorted lexicographically—see below). It implements an immutable type-specific list that returns the i-th array when calling get(i). The returned array may be freely modified.

Front-coding (also known as prefix-omission) compression is based on the idea that if the i-th and the (i+1)-th array have a common prefix, we might store the length of the common prefix, and then the rest of the second array.

This approach, of course, requires that once in a while an array is stored entirely. The ratio of a front-coded list defines how often this happens (once every ratio() arrays). A higher ratio means more compression, but means also a longer access time, as more arrays have to be probed to build the result. Note that we must build an array every time get(long) is called, but this class provides also methods that extract one of the stored arrays in a given array, reducing garbage collection. See the documentation of the family of get() methods.

By setting the ratio to 1 we actually disable front coding: however, we still have a data structure storing large list of arrays with a reduced overhead (just one integer per array, plus the space required for lengths).

Note that the typical usage of front-coded lists is under the form of serialized objects; usually, the data that has to be compacted is processed offline, and the resulting structure is stored permanently. Since the pointer array is not stored, the serialized format is very small.

Implementation Details

All arrays are stored in a big array. A separate array of pointers indexes arrays whose position is a multiple of the ratio: thus, a higher ratio means also less pointers.

More in detail, an array whose position is a multiple of the ratio is stored as the array length, followed by the elements of the array. The array length is coded by a simple variable-length list of k-1 bit blocks, where k is the number of bits of the underlying primitive type. All other arrays are stored as follows: let common the length of the maximum common prefix between the array and its predecessor. Then we store the array length decremented by common, followed by common, followed by the array elements whose index is greater than or equal to common. For instance, if we store foo, foobar, football and fool in a front-coded character-array list with ratio 3, the character array will contain

 3 f o o 3 3 b a r 5 3 t b a l l 4 f o o l
 
See Also:
  • Nested Class Summary

    Nested classes/interfaces inherited from class it.unimi.dsi.fastutil.objects.AbstractObjectBigList

    it.unimi.dsi.fastutil.objects.AbstractObjectBigList.ObjectRandomAccessSubList<K>, it.unimi.dsi.fastutil.objects.AbstractObjectBigList.ObjectSubList<K>
  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    protected final long[][]
    The big array containing the compressed arrays.
    protected final long
    The number of arrays in the list.
    protected long[][]
    The pointers to entire arrays in the list.
    protected final int
    The ratio of this front-coded list.
  • Constructor Summary

    Constructors
    Constructor
    Description
    LongArrayFrontCodedBigList(Collection<long[]> c, int ratio)
    Creates a new front-coded list containing the arrays in the given collection.
    LongArrayFrontCodedBigList(Iterator<long[]> arrays, int ratio)
    Creates a new front-coded list containing the arrays returned by the given iterator.
  • Method Summary

    Modifier and Type
    Method
    Description
    int
    arrayLength(long index)
    Computes the length of the array at the given index.
    Returns a copy of this list.
    void
     
    long[]
    get(long index)
    int
    get(long index, long[] a)
    Stores in the given array an array stored in this front-coded list.
    int
    get(long index, long[] a, int offset, int length)
    Stores in the given array elements from an array stored in this front-coded list.
    long[]
    getArray(long index)
    Returns an array stored in this front-coded list.
    it.unimi.dsi.fastutil.objects.ObjectBigListIterator<long[]>
    listIterator(long start)
     
    int
     
    protected long[][]
    Computes the pointer big array using the currently set ratio, number of elements and underlying array.
    long
     
     

    Methods inherited from class it.unimi.dsi.fastutil.objects.AbstractObjectBigList

    add, add, addAll, addAll, addElements, addElements, clear, compareTo, contains, ensureIndex, ensureRestrictedIndex, equals, forEach, getElements, hashCode, indexOf, iterator, lastIndexOf, listIterator, peek, pop, push, remove, removeElements, set, setElements, size, size, subList, top

    Methods inherited from class java.util.AbstractCollection

    containsAll, isEmpty, remove, removeAll, retainAll, toArray, toArray

    Methods inherited from class java.lang.Object

    finalize, getClass, notify, notifyAll, wait, wait, wait

    Methods inherited from interface it.unimi.dsi.fastutil.objects.ObjectBigList

    addAll, addAll, addAll, addAll, getElements, setElements, setElements, spliterator

    Methods inherited from interface it.unimi.dsi.fastutil.Stack

    isEmpty
  • Field Details

    • n

      protected final long n
      The number of arrays in the list.
    • ratio

      protected final int ratio
      The ratio of this front-coded list.
    • array

      protected final long[][] array
      The big array containing the compressed arrays.
    • p

      protected transient long[][] p
      The pointers to entire arrays in the list.
  • Constructor Details

    • LongArrayFrontCodedBigList

      public LongArrayFrontCodedBigList(Iterator<long[]> arrays, int ratio)
      Creates a new front-coded list containing the arrays returned by the given iterator.
      Parameters:
      arrays - an iterator returning arrays.
      ratio - the desired ratio.
    • LongArrayFrontCodedBigList

      public LongArrayFrontCodedBigList(Collection<long[]> c, int ratio)
      Creates a new front-coded list containing the arrays in the given collection.
      Parameters:
      c - a collection containing arrays.
      ratio - the desired ratio.
  • Method Details

    • ratio

      public int ratio()
    • arrayLength

      public int arrayLength(long index)
      Computes the length of the array at the given index.
      Parameters:
      index - an index.
      Returns:
      the length of the index-th array.
    • get

      public long[] get(long index)
      Specified by:
      get in interface it.unimi.dsi.fastutil.BigList<long[]>
    • getArray

      public long[] getArray(long index)
      Returns an array stored in this front-coded list.
      Parameters:
      index - an index.
      Returns:
      the corresponding array stored in this front-coded list.
    • get

      public int get(long index, long[] a, int offset, int length)
      Stores in the given array elements from an array stored in this front-coded list.
      Parameters:
      index - an index.
      a - the array that will store the result.
      offset - an offset into a where elements will be store.
      length - a maximum number of elements to store in a.
      Returns:
      if a can hold the extracted elements, the number of extracted elements; otherwise, the number of remaining elements with the sign changed.
    • get

      public int get(long index, long[] a)
      Stores in the given array an array stored in this front-coded list.
      Parameters:
      index - an index.
      a - the array that will store the content of the result (we assume that it can hold the result).
      Returns:
      if a can hold the extracted elements, the number of extracted elements; otherwise, the number of remaining elements with the sign changed.
    • size64

      public long size64()
      Specified by:
      size64 in interface it.unimi.dsi.fastutil.Size64
    • listIterator

      public it.unimi.dsi.fastutil.objects.ObjectBigListIterator<long[]> listIterator(long start)
      Specified by:
      listIterator in interface it.unimi.dsi.fastutil.BigList<long[]>
      Specified by:
      listIterator in interface it.unimi.dsi.fastutil.objects.ObjectBigList<long[]>
      Overrides:
      listIterator in class it.unimi.dsi.fastutil.objects.AbstractObjectBigList<long[]>
    • clone

      Returns a copy of this list.
      Overrides:
      clone in class Object
      Returns:
      a copy of this list.
    • toString

      public String toString()
      Overrides:
      toString in class it.unimi.dsi.fastutil.objects.AbstractObjectBigList<long[]>
    • rebuildPointerArray

      protected long[][] rebuildPointerArray()
      Computes the pointer big array using the currently set ratio, number of elements and underlying array.
      Returns:
      the computed pointer big array.
    • dump

      public void dump(DataOutputStream array, DataOutputStream pointers) throws IOException
      Throws:
      IOException