wavelettree

README

wavelettree

waveletTree is a Go package for myriad array operations using wavelet trees.

waveletTree stores a non-negative intger array V[0...n), 0 <= V[i] < s and support almost all operations in O(log s) time (not depends on num) using at most (n * log_2 s) bits plus small overheads for storing auxiually indices.

Usage

import "github.com/hillbig/waveletTree"

builder := NewBuilder()
for i := uint64(0); i < N; i++ {
	builder.PushBack(uint64(rand.Int63())) // set values by PushBck
}
wt := builder.Build() // Build returns WaveletTree

// WaveletTree conceptually stores a non-negative integer array V[0...num)
// where 0 <= V[i] < s

// WaveletTree supports all operations in O(log s) time (not depend on num)
x := wt.Lookup(ind) // Lookup returns V[x]
rank := wt.Rank(ind, x) // Rank returns the number of xs in V[0...in)
sel := wt.Select(rank, x) // Select returns the position of (rank+1)-th x in V
v := wt.Quantile(Range{beg, end}, k) // Quantile returns k-th largest value in V[beg, end)

Benchmark

• 1.7 GHz Intel Core i7
• OS X 10.9.2
• 8GB 1600 MHz DDR3
• go version go1.3 darwin/amd64

The results shows that RSDic operations require always (almost) constant time with regard to the length and one's ratio.

go test -bench=.

// Build a waveletTree for an integer array of length 10^6 with s = 2^64
BenchmarkWTBuild1M	       1	1455321650 ns/op
// 1.455 micro sec per an interger

// A waveletTree for an integer array of length 10M (10^7) with s = 2^64
BenchmarkWTBuild10M	       1	1467061166 ns/op
BenchmarkWTLookup10M	  100000	     29319 ns/op
BenchmarkWTRank10M	  100000	     28278 ns/op
BenchmarkWTSelect10M	   50000	     50250 ns/op
BenchmarkWTQuantile10M	  100000	     28852 ns/op

// An array []uint64 of length 10M (10^7) for comparison
BenchmarkRawLookup10M	20000000	       109 ns/op
BenchmarkRawRank10M	     500	   4683822 ns/op
BenchmarkRawSelect10M	     500	   6085992 ns/op
BenchmarkRawQuantile10M	     100	  44362885 ns/op

Documentation

Overview

Package wavelettree provides a wavelet tree supporting many range-query problems, including rank/select, range min/max query, most frequent and percentile query for general array.

Index

• type Builder
  • func NewBuilder() Builder
• type Range
• type RankResult
• type WaveletTree
  • func New() WaveletTree

Types

type Builder

type Builder interface {
	PushBack(val uint64)
	Build() WaveletTree
}

Builder builds WaveletTree from intergaer array. A user calls PushBack()s followed by Build().

func NewBuilder

func NewBuilder() Builder

NewWaveletReeBuilder returns Builder

type Range

type Range struct {
	Bpos uint64
	Epos uint64
}

Range represents a range [Bpos, Epos) only valid for Bpos <= Epos

type RankResult

type RankResult struct {
	// contains filtered or unexported fields
}

type WaveletTree

type WaveletTree interface {
	// Num return the number of values in T
	Num() uint64

	// Dim returns (max. of T[0...Num) + 1)
	Dim() uint64

	// Lookup returns T[pos]
	Lookup(pos uint64) uint64

	// Rank returns the number of val's in T[0...pos)
	Rank(pos uint64, val uint64) uint64

	// Rank range returns the number of min <= c < max
	// in T[ranze.Bpos, ranze.Epos)
	RankRange(ranze Range, min uint64) Range

	// Select returns the position of (rank+1)-th val in T
	Select(rank uint64, val uint64) uint64

	// LookupAndRank returns T[pos] and Rank(pos, T[pos])
	// Faster than Lookup and Rank
	LookupAndRank(pos uint64) (uint64, uint64)

	// Quantile returns (k+1)th smallest value in T[ranze.Bpos, ranze.Epos]
	Quantile(ranze Range, k uint64) uint64

	// Intersect returns values that occure at least k ranges
	Intersect(ranges []Range, k int) []uint64

	// MarshalBinary encodes WaveletTree into a binary form and returns the result.
	MarshalBinary() ([]byte, error)

	// UnmarshalBinary decodes WaveletTree from a binary form generated MarshalBinary
	UnmarshalBinary([]byte) error
}

WaveletTree supports several range queries.

func New

func New() WaveletTree