semblance

README

semblance

Deterministic, heuristic, fast text-similarity sketching for Go: shingling, MinHash, SimHash, and LSH indexing under one coherent API.

The name is a nod to Andrei Broder's "On the resemblance and containment of documents" (1997), which introduced shingle-based resemblance and minwise hashing.

import "github.com/ophymx/semblance"

sim := semblance.Similarity(
    "the quick brown fox jumps over the lazy dog",
    "the quick brown fox leaps over the lazy dog",
) // ≈ 0.42 — estimated Jaccard similarity of the texts' word-shingle sets

Install

go get github.com/ophymx/semblance

Requires Go 1.25+. One dependency: github.com/cespare/xxhash/v2.

What it does

Every layer is usable on its own; the root package wires them together with frozen defaults (word shingles of width 3, 128-value signatures, seed 0, 16×8 LSH banding ≈ 0.71 candidate threshold).

Package	What it gives you
shingle	Text → stream of shingle hashes (iter.Seq[uint64]): character k-grams (Char, CharRunes) or word w-grams (Words), hashed incrementally with zero per-shingle allocations
minhash	Shingle stream → fixed-size Signature; Jaccard estimates set similarity with standard error ≈ 1/(2√k); asymmetric Containment ("how much of A is in B"), Cardinality, and IntersectionCardinality come free from the same signatures; mergeable (Union)
simhash	Weighted features → 64-bit Fingerprint; Hamming Distance tracks cosine similarity
lsh	Index (banding: unverified candidate ids), VerifiedIndex (banding + stored signatures: verified, ranked near-duplicates in one call), Forest (top-k most-similar retrieval), and HammingIndex (SimHash within distance ≤ 3, exact)
winnow	Position-aware winnowing fingerprints (the MOSS algorithm): locate where documents overlap; any shared run of w+k−1 bytes is guaranteed a match. Index gives corpus-scale fragment provenance — which documents a text overlaps and exactly where — and boilerplate mining: Cover returns the byte ranges of a text that recur across ≥ N indexed documents (shared footers, ad blocks, templated headers), ready to trim
cluster	Deterministic union-find for grouping verified near-duplicate pairs into clusters, earliest-member-wins representatives
hll	HyperLogLog cardinality sketches: distinct-element counts with ~1.04/√2ᵖ error, mergeable and serializable; feed it shingle streams to count distinct words or shingles
topk	SpaceSaving frequent-items sketch (generic over item type): the heaviest items of a stream in fixed space with per-item error bounds — flood and burst detection
sample	Deterministic reservoir sampling: k uniform representatives from a stream of unknown length, reproducible by seed

Reusable, configurable pipeline:

sk := semblance.NewSketcher(semblance.Defaults())
ix := sk.NewIndex()
ix.Add("doc1", sk.Sketch(doc1))
candidates := ix.Query(sk.Sketch(query)) // verify candidates with minhash.Jaccard

Design

• Deterministic. Same input + parameters + seed → same signature, on every platform, in every process, and across Go toolchain versions. Signatures are made to be stored and compared later, elsewhere. Word tokenization uses a Unicode table frozen in the shingle package (shingle.UnicodeVersion), not the toolchain's, so it does not shift on a compiler upgrade.
• Fast. Hot paths do zero allocations per shingle and O(1) small allocations per document, asserted in tests.
• Heuristic, not exact. Everything is an estimator with documented error bounds; LSH returns candidates for the caller to verify.
• Storable. Signatures and fingerprints have a stable, versioned binary encoding (minhash.MinHasher.MarshalSignature, simhash.Fingerprint.MarshalBinary); stored signatures are self-describing and remain comparable across releases within a major version.
• Not an NLP toolkit (no stemming, stopwords, language detection), not a search engine, nothing non-deterministic.

Bring your own persistence

There is deliberately no pluggable storage interface: real backends need their own batching, error handling, and consistency model, which a synchronous store interface would dictate badly. Instead the library exposes the frozen primitives and you own the I/O:

• Signatures and fingerprints serialize (MinHasher.MarshalSignature, Fingerprint.MarshalBinary) — store them as blobs next to your documents.
• lsh.BandKeys computes the bucket keys an index would use, so an LSH index over Redis (SADD lsh:<band>:<key> id), SQL, or any KV is ~30 lines: write id under each key on add, union the buckets on query, verify candidates with minhash.JaccardMany. See the BandKeys example. Key derivation is frozen and safe to persist.
• In-memory indexes rebuild fast: Range enumerates contents, and re-Adding a million stored signatures takes seconds, so a snapshot of (id, signature) pairs is usually all the durability an lsh.Index needs.

Untrusted input

semblance is deterministic by design — the same input always produces the same sketch, which is what makes stored signatures comparable across processes and releases. The flip side is that all hashing is unkeyed and the parameters are frozen and public, so an attacker who can choose the input can also predict every hash. Keep this in mind when any of these structures is fed attacker-controlled documents.

• Seed the collision-sensitive structures. lsh.Index bucket keys derive from the MinHash signature, so a non-zero, secret seed passed to minhash.New randomizes them and defeats deliberate bucket flooding. The frozen defaults (Defaults(), the top-level Similarity) use seed 0 — fine for trusted corpora, predictable for adversaries. There is no such lever for winnow.Index, hll, or topk: they key on the raw shingle/element hashes (xxhash seed 0, frozen), so an attacker can force worst-case collisions regardless of any seed. Treat their memory and per-query cost as attacker-influenced and bound your input sizes.

• Winnowing overlap work is bounded. winnow.Overlaps and Index.Matches return aligned Spans (diagonal runs of shared fingerprints collapsed into one region), so a shared passage is one span, not one entry per fingerprint. The underlying match set is still quadratic on highly repetitive text (a long run of one byte matches at nearly every position), so both bound the matches they examine at winnow.MaxResults; reaching it means "overlap is at least this large." Index.Overlap returns a bounded per-document summary and is the safer default when you only need how much, not where.

• Deserialization is bounds-checked. DecodeSignature, hll.UnmarshalBinary, and simhash.Fingerprint.UnmarshalBinary validate the version, algorithm, and length fields before allocating, so a malformed or hostile blob yields an error, never an oversized allocation — but they do not authenticate the bytes. A tampered signature decodes to a valid-but-wrong sketch; sign or MAC stored blobs if their integrity matters.

• *Bytes zero-copy contract. The *Bytes entry points view the slice without copying; mutating it before iteration completes yields wrong hashes (never a memory-safety fault). Pass a stable slice.

References

• A. Z. Broder. On the resemblance and containment of documents. Compression and Complexity of Sequences, 1997.
• M. Charikar. Similarity estimation techniques from rounding algorithms. STOC 2002.
• S. Schleimer, D. Wilkerson, A. Aiken. Winnowing: local algorithms for document fingerprinting. SIGMOD 2003.
• M. Bawa, T. Condie, P. Ganesan. LSH Forest: self-tuning indexes for similarity search. WWW 2005.
• G. S. Manku, A. Jain, A. Das Sarma. Detecting near-duplicates for web crawling. WWW 2007.
• P. Flajolet, É. Fusy, O. Gandouet, F. Meunier. HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm. AofA 2007.
• A. Metwally, D. Agrawal, A. El Abbadi. Efficient computation of frequent and top-k elements in data streams. ICDT 2005.
• J. Leskovec, A. Rajaraman, J. Ullman. Mining of Massive Datasets, ch. 3 (shingling, minhashing, LSH banding).

License

MIT

Documentation

Overview

Package semblance provides deterministic, heuristic text-similarity sketching: shingling, MinHash, SimHash, and LSH indexing under one API. The name nods to Broder's "On the resemblance and containment of documents" (1997), which introduced shingle-based resemblance and minwise hashing.

This package is the convenience layer: two strings to a similarity score with sensible frozen defaults. The sub-packages (shingle, minhash, simhash, lsh) are each usable alone for anything more custom.

Everything is heuristic with known error bounds (see the sub-package docs) and deterministic: same input, same parameters, same seed → same signature, on every platform. Word tokenization shares the unicode-tables caveat documented in the shingle package.

Index

• func Containment(a, b string) float64
• func Similarity(a, b string) float64
• type Config
  • func Defaults() Config
• type Sketcher
  • func NewSketcher(cfg Config) *Sketcher
  • func (s *Sketcher) Config() Config
  • func (s *Sketcher) Containment(a, b string) float64
  • func (s *Sketcher) NewIndex() *lsh.Index
  • func (s *Sketcher) NewStream() *Stream
  • func (s *Sketcher) NewVerifiedIndex() *lsh.VerifiedIndex
  • func (s *Sketcher) Similarity(a, b string) float64
  • func (s *Sketcher) Sketch(text string) minhash.Signature
  • func (s *Sketcher) SketchBytes(b []byte) minhash.Signature
  • func (s *Sketcher) SketchInto(dst minhash.Signature, text string)
  • func (s *Sketcher) SketchIntoBytes(dst minhash.Signature, b []byte)
• type Stream
  • func (st *Stream) Reset()
  • func (st *Stream) Signature() minhash.Signature
  • func (st *Stream) Write(p []byte) (int, error)
  • func (st *Stream) WriteString(text string) (int, error)

Examples

• Similarity
• Sketcher
• Sketcher.NewStream

Functions

func Containment

func Containment(a, b string) float64

Containment estimates the fraction of a's word shingles also present in b with the Defaults configuration — the asymmetric measure for quote and boilerplate detection ("how much of a is inside b"). Returns 0 if either text is too short to shingle.

func Similarity

func Similarity(a, b string) float64

Similarity estimates the Jaccard similarity of the two texts' word shingle sets with the Defaults configuration, in [0, 1]. Standard error is about 0.044 at the default K=128. Returns 0 if either text is too short to shingle (fewer than 3 words).

Example

The five-line path: two strings to a similarity score.

package main

import (
	"fmt"

	semblance "github.com/ophymx/semblance"
)

func main() {
	sim := semblance.Similarity(
		"the quick brown fox jumps over the lazy dog",
		"the quick brown fox leaps over the lazy dog",
	)
	fmt.Printf("%.2f\n", sim)
}

Output:
0.42

Types

type Config

type Config struct {
	// W is the word-shingle width.
	W int
	// K is the MinHash signature length. Standard error of similarity
	// estimates is about 1/(2*sqrt(K)).
	K int
	// Seed selects the permutation family. Signatures are only comparable
	// across equal (K, Seed).
	Seed uint64
	// Bands and Rows shape LSH indexes created by [Sketcher.NewIndex];
	// Bands*Rows must equal K. Leave both zero if you never build an index.
	Bands, Rows int
}

Config parameterizes a Sketcher. The zero value is not valid; start from Defaults.

func Defaults

func Defaults() Config

Defaults returns the frozen default configuration: word shingles of width 3, signatures of length 128 with seed 0, and 16 bands of 8 rows (LSH candidate threshold ≈ 0.71). These values will not change within a major version; signatures sketched with Defaults today remain comparable with signatures sketched with Defaults in any future v1 release.

type Sketcher

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

Sketcher turns texts into MinHash signatures using a fixed configuration. It is immutable after creation and safe for concurrent use, provided concurrent SketchInto calls use distinct dst buffers.

Example

package main

import (
	"fmt"

	semblance "github.com/ophymx/semblance"
)

func main() {
	sk := semblance.NewSketcher(semblance.Defaults())
	ix := sk.NewIndex()
	ix.Add("doc1", sk.Sketch("the quick brown fox jumps over the lazy dog every single morning"))
	ix.Add("doc2", sk.Sketch("an entirely unrelated document about locality sensitive hashing"))

	candidates := ix.Query(sk.Sketch("the quick brown fox jumps over the lazy dog every single evening"))
	fmt.Println(candidates)
}

Output:
[doc1]

func NewSketcher

func NewSketcher(cfg Config) *Sketcher

NewSketcher returns a Sketcher for the configuration. Panics if W <= 0, K <= 0, or Bands/Rows are set (nonzero) but invalid or inconsistent with K.

func (*Sketcher) Config

func (s *Sketcher) Config() Config

Config returns the configuration the Sketcher was created with.

func (*Sketcher) Containment

func (s *Sketcher) Containment(a, b string) float64

Containment estimates the fraction of a's word shingles also present in b — the asymmetric counterpart of Sketcher.Similarity, in [0, 1]. A short text fully quoted inside a long one has low similarity but containment near 1, which is the right question for quote and boilerplate detection. Returns 0 if either text has no shingles.

func (*Sketcher) NewIndex

func (s *Sketcher) NewIndex() *lsh.Index

NewIndex returns an empty LSH candidate index shaped by the configuration's Bands and Rows, for signatures produced by this Sketcher. Query returns unverified candidate ids; the caller verifies them. Panics if Bands/Rows were left zero.

func (*Sketcher) NewStream

func (s *Sketcher) NewStream() *Stream

NewStream returns a Stream sketching with this Sketcher's configuration. The Stream reuses its buffers across Stream.Reset, so one Stream per worker amortizes all allocation.

Example

Documents too large to hold in memory stream through an io.Writer; any chunking produces the same signature as sketching the whole text.

package main

import (
	"fmt"
	"io"
	"strings"

	semblance "github.com/ophymx/semblance"
)

func main() {
	sk := semblance.NewSketcher(semblance.Defaults())

	text := "the quick brown fox jumps over the lazy dog"
	st := sk.NewStream()
	io.Copy(st, strings.NewReader(text)) // e.g. an os.File in practice

	fmt.Println(semblance.NewSketcher(semblance.Defaults()).Sketch(text)[0] == st.Signature()[0])
}

Output:
true

func (*Sketcher) NewVerifiedIndex

func (s *Sketcher) NewVerifiedIndex() *lsh.VerifiedIndex

NewVerifiedIndex returns an empty signature-storing LSH index shaped by the configuration's Bands and Rows. Its Query returns verified, ranked neighbors directly (see lsh.VerifiedIndex) — the convenient path for near-duplicate lookup, at the cost of retaining signatures. Panics if Bands/Rows were left zero.

func (*Sketcher) Similarity

func (s *Sketcher) Similarity(a, b string) float64

Similarity estimates the Jaccard similarity of the two texts' word shingle sets using this Sketcher's configuration, in [0, 1]. If either text has fewer than W words it has no shingles, and Similarity returns 0 — two degenerate texts do not count as identical.

func (*Sketcher) Sketch

func (s *Sketcher) Sketch(text string) minhash.Signature

Sketch returns the MinHash signature of text's word shingles. Text with fewer than W words produces the empty-set signature (all math.MaxUint64); see Similarity for how the convenience layer treats those.

func (*Sketcher) SketchBytes

func (s *Sketcher) SketchBytes(b []byte) minhash.Signature

SketchBytes is Sketcher.Sketch for a byte slice, without copying. The slice is not retained or mutated.

func (*Sketcher) SketchInto

func (s *Sketcher) SketchInto(dst minhash.Signature, text string)

SketchInto sketches text into dst, overwriting it — the low-allocation path for bulk sketching. Panics if len(dst) != K.

func (*Sketcher) SketchIntoBytes

func (s *Sketcher) SketchIntoBytes(dst minhash.Signature, b []byte)

SketchIntoBytes is Sketcher.SketchInto for a byte slice, without copying. The slice is not retained or mutated. Panics if len(dst) != K.

type Stream

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

Stream sketches a document that arrives in chunks — an io.Writer for text too large to hold as one string. Any chunking, including splits inside tokens or multi-byte runes, produces exactly the signature of Sketcher.Sketch over the whole text.

Lifecycle: Write/WriteString the document, call Stream.Signature once to finalize, then Stream.Reset to start the next document. Writing after Signature (without Reset) panics. Not safe for concurrent use.

func (*Stream) Reset

func (st *Stream) Reset()

Reset readies the Stream for a new document.

func (*Stream) Signature

func (st *Stream) Signature() minhash.Signature

Signature finalizes the document (emitting any in-progress token) and returns its signature. The returned slice is a copy, valid after Reset. Idempotent: repeated calls return the same signature; Write between Signature and Reset panics, because the final token was already terminated.

func (*Stream) Write

func (st *Stream) Write(p []byte) (int, error)

Write implements io.Writer. It always accepts all of p and never returns an error; the bytes are not retained.

func (*Stream) WriteString

func (st *Stream) WriteString(text string) (int, error)

WriteString implements io.StringWriter.