Generating dictionaries

[klauspost]

@brancz

[...]are there any plans, or has anyone already written the ability to train a zstd dict in Go? I have a use case I'd love to try zstd dicts for but would prefer to avoid calling out to the binary.

I don't have any plans for it. I did write one at some point just for fun (just doing the backreference dict), but there was a long way for it to be useful.

[brancz]

I don't have any plans for it. I did write one at some point just for fun (just doing the backreference dict), but there was a long way for it to be useful.

Do you happen to have any amount of code start to work off of?

[klauspost]

@brancz Updated a slightly updated version that is better at eliminating duplicates and adds a bit of start context for each entry.

Not really sure if better, but output makes more sense. Also using --hash=8 may be better.

[klauspost]

(remember the most important matches are at the end, since they have a lower cost to encode in terms of offset)

For example, this is the last part of a dict on the Go source code:

	}
	if g(path)
	if err == nil {
			return
		}
	continue
			}
		}
		retu	if e1 != 0 {
		err = errnoErr(estruct{}

func (c *sigctxt) set_type I interfaceesting"
)

func init() { error) {
	retur                      = 0x0
	BPF2(length)
}

func Benchm	for i := range tests {
f the file.

// Package if err != nil {
		t.Fatal(err)
	}
	defer

type T struct {
	Type sts = []struct {
	Len   r(e1)
	}
	return
}

// THIS FILE IS GENERATED BY THE COMMAND AT THE TOP; DO NOT EDIT

fu nil {
		return rewriteV
		}
	}
}

func main() {ight 2018 The Goun

// Copyright 2021 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

//go file.

package main

import (
	"bytes"

[klauspost]

Just ran a test. The revised version actually beats zstd --train-fastcover on Go source files (literal compression disabled, since we don't generate that table)

zstd:  8912 File(s) 16.877.616 bytes
mine:  8912 File(s) 16.439.085 bytes

Hmmm.. Maybe I should begin to consider adding it.

[brancz]

Oh amazing! I haven't started looking at it yet, but let me know if I can be helpful somehow!

One thing that I think might be useful to think about in the design: My use case is actually not small files but small leaf-values (<4kb) in a tree and I don't want to compress the whole tree as I want to access it with range queries on object storage (the tree itself is in cache-oblivious layout).

[klauspost]

To be honest, you are probably just fine providing a sample as dictionary. Alternatively you can concat a few samples, if there are several patterns. The dictionary isn't really magic, just provide some reasonable "history" it can pull references from.

You can test it out with s2, where you just provide a raw dictionary to use and you can use block compression functions on your data with the dictionary.

You only need a dictionary builder when you have diverse input types, like "html files" and "go source code", where there are some repeating patterns but there is no single file that represents "typical" input.