simple-sds-sbwt 0.3.3

A fork of simple-sds used in the sbwt crate.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87

# Simple-SDS releases

## Current version

### Bitvectors

* `RLVector`: Run-length encoded bitvector similar to the one in RLCSA.
* Consistent conversions between bitvector types:
  * `From` trait between any two bitvector types.
  * Associated function `copy_bit_vec` for copying from a type that implements `Select`.

### Wavelet matrices

* Trait `VectorIndex` for rank/select-type queries over integer vectors.
* Implementations of `VectorIndex`:
  * `WaveletMatrix`: Plain balanced wavelet matrix.

### Other

* Better `Access` trait.
  * The default implementation is immutable.
  * The trait includes an iterator over the values.
  * `AccessIter` is a trivial implementation of the iterator using `Access::get`.
  * `Access::get_or` returns a default value if the index is not valid.

## Simple-SDS 0.3.1 (2022-02-17)

* Minor patch release for the GBZ paper.

## Simple-SDS 0.3.0 (2021-11-17)

### Compressed multisets

* Elias-Fano encoding can store duplicate values, which simplifies some uses of `SparseVector`.
* Built with `SparseBuilder::multiset` or `SparseVector::try_from`.
* Most bitvector operations generalize from sets to multisets naturally, but `rank_zero` does not work.
  * If there are multiple occurrences of value `i`, the predecessor of `i` has a higher rank than its successor.

### Interface changes

* `select` and related queries return `Option` instead of `Result`.
* `Element` trait is now `Vector`.

### Other

* Vectors have items instead of elements to avoid confusion between vector elements and serialization elements.
* Uses `rand` 0.8 instead of 0.7.
* Serialization improvements:
  * `skip_option`, `absent_option`, and `absent_option_size` for dealing with optional structures.
  * `test` for running basic serialization tests for a new type.

## Simple-SDS 0.2.0 (2021-05-02)

This is no longer a pre-release, but things may still change without warning.

### Serialization

* Documentation on the serialization formats: https://github.com/jltsiren/simple-sds/blob/main/SERIALIZATION.md
* Trait `Serializable` that indicates that a fixed-size type can be serialized by copying the bytes as one or more `u64` elements.
  * A `Vec` of `Serializable` values can always be serialized.
* Serialization for `Vec` of `u8` values and `String`.
* Some sanity checks when loading serialized structures.

### Memory mapping

* `MemoryMap` that maps a file as an immutable array of `u64` elements.
* Trait `MemoryMapped` for structures that correspond to an interval in `MemoryMap`.
* Several `MemoryMapped` implementations:
  * `MappedSlice`: `Vec` of `Serializable` values.
  * `MappedBytes`: `Vec` of `u8` values.
  * `MappedStr`: `String`.
  * `MappedOption`:  Optional structure.
  * `RawVectorMapper`: `RawVector`.
  * `IntVectorMapper`: `IntVector`.

### Other

* 64-bit ARM is now supported.
* Removed the unnecessary `Writer` trait and simplified `RawVectorWriter` and `IntVectorWriter`.
* Smaller `SparseVector`, especially for high-density vectors:
  * Approximate the optimal number of buckets / width of the low parts better.
  * Do not create unnecessary buckets.
  * Removed a redundant field from the header.

## Simple-SDS 0.1.0 (2021-01-14)

This initial release implements bit-packed integer vectors, plain bitvectors, and sparse (Elias-Fano encoded) bitvectors as well as various bitvector iterators. The performance is generally comparable to SDSL. As this is a pre-release, anything can change without warning.