README
¶
ditto
Near-duplicate detection for Go — Charikar SimHash, pure standard library, no
tokenizer, no model. Fingerprint a document to a 64-bit value where
near-duplicates land a few bits apart, then find them across a corpus in better
than O(n²). ditto answers one question — is this a near-duplicate? — and nothing
else. The name is the ditto mark (″): same as above.
text ─▶ Normalize ─▶ shingle (char/word n-grams) ─▶ FNV-1a ─▶ Sum (Charikar)
│
▼
Fingerprint (uint64)
│
Index.Add(id,fp) ─▶ banded tables ─▶ Near(fp,k) · Clusters(k,min)
Quick start
f := ditto.Default() // character 4-grams
a := f.Of("Your Apple ID has been locked. Please verify your account now.")
b := f.Of("Your Apple ID has been locked. Please verify your account now!")
a.Near(b, 3) // true — near-duplicate (differ by ~2 bits)
ix := ditto.NewIndex(3)
for id, text := range corpus { ix.Add(id, f.Of(text)) }
ix.Clusters(3, 2) // near-duplicate families
go run ./app/ditto cluster -k 3 corpus/ # near-dup families over files/maildir
Documentation
- Start here — docs/introduction.md · docs/executive-summary.md
- Deep dive — docs/architecture.md
- Operations — docs/userguide.md
- Examples — example/README.md
Layout
| File | Purpose |
|---|---|
| simhash.go | Fingerprint (+ String), Feature, Sum (Charikar accumulation), Distance, Near |
| featurize.go | Featurizer — normalize → char/word shingles → FNV-1a features |
| normalize.go | Normalize — HTML-strip, lowercase, whitespace-collapse |
| index.go | Index (Add/Near/Clusters/K/Len/Save) — banded near-duplicate lookup; Clusters via union-find |
| persist.go | Index.Save / LoadIndex — gob snapshot (k + id/fp pairs); rebuilds the banded tables on load |
| version.go | PipelineVersion — the fingerprint-pipeline identity |
| app/ditto/ | the CLI — fingerprint · cluster · version |
Notes
- Go module
github.com/netstar-labs/ditto. Standard library only — no dependencies. Build standalone withGOWORK=off. - Deterministic: a fingerprint is a pure function of the versioned pipeline
(version.go); store
PipelineVersionalongside any persisted fingerprint and compare only within a version. - ditto is not a classifier. For "what is this content about?" that is a categorizer's job; ditto only answers sameness.
License
Licensed under the Apache License, Version 2.0 — see LICENSE.
Documentation
¶
Overview ¶
Package ditto detects near-duplicate documents with Charikar's SimHash: it maps each document to a 64-bit Fingerprint such that near-duplicates land a small Hamming distance apart, then finds them in better-than-O(n²) time with a banded Index.
Unlike a cryptographic hash — where one changed input bit flips ~half the output — SimHash is a locality-sensitive hash: similar inputs produce similar fingerprints, so "are these two nearly the same?" becomes a bit-count.
It is pure Go, standard library only, and needs no tokenizer: the default Featurizer shingles character 4-grams, which is language-agnostic and robust to light obfuscation. ditto answers only "is this a near-duplicate?" — it does not classify or categorize content.
Index ¶
Constants ¶
const PipelineVersion = "ditto/2"
PipelineVersion identifies the fingerprint pipeline: Normalize, the shingling in Featurizer, and the feature hash together. Fingerprints are only comparable across documents processed by the same version. Bump it on any change to that pipeline, and store it alongside any persisted fingerprint (e.g. a capture-time SimHash on a captured record) so a version mismatch is detectable rather than a silent comparison of incomparable hashes.
Variables ¶
This section is empty.
Functions ¶
func Distance ¶
func Distance(a, b Fingerprint) int
Distance is the Hamming distance between two fingerprints (0 = identical).
func Normalize ¶
Normalize is the shared front-end to shingling: it strips HTML tags, lowercases, and collapses runs of whitespace to single spaces. It is deterministic, and its behaviour is part of the fingerprint pipeline — any change to it must bump PipelineVersion, because it shifts every fingerprint.
Types ¶
type Feature ¶
type Feature struct {
Hash uint64 // a well-distributed hash of the feature
Weight int // influence of the feature; <=0 is treated as 1
}
Feature is one weighted feature of a document — a shingle hash and its weight (typically the shingle's frequency). Sum folds a document's features into a Fingerprint.
type Featurizer ¶
type Featurizer struct {
CharN int // character n-gram length (0 disables character shingles)
WordN int // word n-gram length (0 disables word shingles)
}
Featurizer turns text into the weighted features Sum folds into a Fingerprint. Use Default (character 4-grams) unless you have a reason to change the shingle sizes; whichever you pick must be identical when fingerprints are compared, so a change is a pipeline change (see PipelineVersion).
func Default ¶
func Default() Featurizer
Default featurizes with character 4-grams: no tokenizer, language-agnostic, and robust to light obfuscation (c4sino still shares grams with casino).
func (Featurizer) Features ¶
func (f Featurizer) Features(text string) []Feature
Features normalizes text and returns its weighted shingle features. A document shorter than the shingle size falls back to a single whole-string feature so it still gets a stable, comparable fingerprint.
func (Featurizer) Of ¶
func (f Featurizer) Of(text string) Fingerprint
Of normalizes text and returns its Fingerprint.
type Fingerprint ¶
type Fingerprint uint64
Fingerprint is a 64-bit SimHash of a document. Two documents are near-duplicates when the Hamming distance between their fingerprints is small.
func Sum ¶
func Sum(features []Feature) Fingerprint
Sum folds features into a Fingerprint with Charikar's SimHash: each of the 64 bit positions accumulates +weight when the feature hash has that bit set and -weight when it does not; the result bit is 1 wherever the accumulator ends positive. Sum is order-independent — the accumulation commutes — so the fingerprint depends only on the multiset of features, not their order.
The accumulator saturates at int64's bounds rather than wrapping: Weight is caller-supplied with no upper bound, so without saturation a large Weight (or many features voting the same bit) could overflow int64 and silently flip a bit to the wrong value. Only the accumulator's sign determines the output bit, and saturation always preserves the correct sign, so this cannot overflow regardless of the weight total.
func (Fingerprint) Near ¶
func (a Fingerprint) Near(b Fingerprint, k int) bool
Near reports whether a and b are within k bits of each other.
func (Fingerprint) String ¶
func (a Fingerprint) String() string
String renders the fingerprint as 16 lowercase hex digits.
type Index ¶
type Index struct {
// contains filtered or unexported fields
}
Index finds near-duplicates in better-than-O(n²) time with banded lookup: a block-partition bucketing scheme, per the pigeonhole guarantee used in the Google near-dup crawl paper (no bit permutation is performed). Built for a maximum Hamming distance k, it splits each 64-bit fingerprint into k+1 blocks; by the pigeonhole principle any two fingerprints within k bits share at least one identical block, so only fingerprints colliding on a block are compared.
The sub-quadratic guarantee assumes band buckets stay small, which holds when near-duplicates are the exception. A corpus dominated by many mutually near-duplicate documents (e.g. a mass-identical spam blast) makes every member share a bucket with every other, so Near/Clusters degrade toward O(n²) for that cluster — inherent to banding, not a bug; see BenchmarkClustersAllDuplicate in bench_test.go.
Add fingerprints, then query with Near or group the whole set with Clusters. An Index is not safe for concurrent Add; build it, then read. Violating that contract is undefined behavior, but note its character changed: candidates (used by Near) once deduped through a map, whose out-of-range key access never panics, so a concurrent Add raced with a read surfaced only as Go's own unrecoverable "concurrent map read and map write" fatal error — never a recoverable panic. It now dedupes through a slice sized from a snapshot of Len, so the same misuse can also surface as an ordinary (recoverable) index- out-of-range panic. Both signal the same contract violation; a caller using recover() to contain misuse should not treat either as a softer signal than the other.
The zero value is not usable: always construct via NewIndex or LoadIndex. Index.Add panics on a zero-value Index rather than silently accepting entries that would never reach a band table.
func NewIndex ¶
NewIndex creates an index whose Near/Clusters resolve near-duplicates up to a Hamming distance of k (k >= 0).
func (*Index) Add ¶
func (ix *Index) Add(id string, fp Fingerprint)
Add inserts a fingerprint under an id. Ids need not be unique, but duplicates are reported separately. Add panics if ix is a zero-value Index (not built via NewIndex or LoadIndex) — see the Index doc comment.
func (*Index) Clusters ¶
Clusters groups the indexed fingerprints into near-duplicate families by union-find over pairs within k bits, returning only clusters of at least min members (min <= 1 includes singletons). Output is deterministic: ids sorted within each cluster, clusters by descending size then first id. k is clamped to the index's build-time K.
type Match ¶
type Match struct {
ID string
Fingerprint Fingerprint
Distance int
}
Match is one near-duplicate hit from Index.Near.
Source Files
¶
Directories
¶
| Path | Synopsis |
|---|---|
|
app
|
|
|
ditto
command
Command ditto fingerprints documents and finds near-duplicates with SimHash.
|
Command ditto fingerprints documents and finds near-duplicates with SimHash. |
|
example
|
|
|
cluster
command
Example cluster demonstrates fingerprinting, Hamming distance, and near- duplicate clustering over a tiny in-memory corpus.
|
Example cluster demonstrates fingerprinting, Hamming distance, and near- duplicate clustering over a tiny in-memory corpus. |