golomb

README

Golomb coding

Package golomb is golang implementation of Golomb_coding.

References

• Smaller than Bloom filters
• Golomb-coded sets: smaller than Bloom filters

Documentation

Index

• func DecodeAll(rd io.Reader, p uint) ([]uint, error)
• func Encode(w io.Writer, src []uint, p uint) error

Examples

• Encode

Functions

func DecodeAll

func DecodeAll(rd io.Reader, p uint) ([]uint, error)

DecodeAll decodes...

func Encode

func Encode(w io.Writer, src []uint, p uint) error

Encode encodes the given uint array and writes to underlying writer. p is false-positive probability. The src array must be uniformly distribute set of values.

Example

// Number of elements and false positive probability.
//
// Minimum number of bits is N*log(P)
// = 26 * log(1<<6) = 156 bits = 19 bytes
N, P := uint(26), uint(1<<6)

// Example data set comes from https://github.com/rasky/gcs
file := "./testdata/words.nato"
f, _ := os.Open(file)
sc := bufio.NewScanner(f)
defer f.Close()

hashF := func(v []byte) uint {
	h := md5.New()
	h.Write(v)
	b := h.Sum(nil)

	s := hex.EncodeToString(b[12:16])
	i, err := strconv.ParseUint(s, 16, 32)
	if err != nil {
		panic(err)
	}
	return uint(i) % (N * P)
}

a := make([]uint, 0, N)
for sc.Scan() {
	a = append(a, hashF(sc.Bytes()))
}
sort.Slice(a, func(i, j int) bool {
	return a[i] < a[j]
})

// Encode hash value array to Golomb-coded sets
// and write it to buffer.
var buf bytes.Buffer
Encode(&buf, a, P)

fmt.Printf("%x", buf.Bytes())

Output:

cba920f780663a061f2065198ab1032d624c50331e66ae9818