fingerprint

README

fingerprint

Two small content-fingerprinting primitives for near-duplicate / similar-content detection in Go:

• Text — Charikar SimHash (Compute / Distance / Similarity): a 64-bit locality-sensitive hash for finding near-duplicate documents. Shingled (3-word) so it doesn't collapse unrelated prose the way single-token SimHash does. Pure stdlib.
• Images — perceptual hash / pHash (PHash / PHashFromImage, with PHashHex / PHashFromHex): a 64-bit DCT-based hash for finding visually-similar images regardless of scale or minor edits.

Both return a uint64; pairwise Hamming Distance (and Similarity = 1 - distance/64) measures closeness — small distance means similar content.

go get github.com/richardwooding/fingerprint

Text near-duplicates (SimHash)

a := fingerprint.Compute(docA) // 64-bit fingerprint of the body text
b := fingerprint.Compute(docB)

if fingerprint.Similarity(a, b) >= 0.85 {
    // near-duplicate: typo fixes, template fills, regenerated headers, minor revisions
}

Rough distance → similarity guide:

Hamming distance	Similarity	Meaning
≤ 3	≈ 95%	near-identical (whitespace / a word or two)
≤ 9	≈ 85%	minor edits / template fills (a common cut)
~28+	≈ 55%	unrelated prose (near the random baseline)

Why shingled: single-token SimHash over natural-language text is dominated by the near-universal stopword distribution, so unrelated documents score ~90% similar and cluster spuriously. Hashing overlapping 3-word shingles keys on phrasing instead — unrelated prose drops to ~0.55 while genuine near-duplicates stay high.

Image similarity (pHash)

h1, _ := fingerprint.PHash(file1) // io.Reader of a PNG/JPEG/GIF
h2, _ := fingerprint.PHash(file2)

if fingerprint.Distance(h1, h2) <= 10 {
    // visually similar: resizes, re-encodes, light crops/edits
}

hex := fingerprint.PHashHex(h1)        // 16-char hex for storage
back, _ := fingerprint.PHashFromHex(hex)

PHash downscales to 32×32 greyscale, runs a 2-D DCT, and keeps the sign of the low-frequency coefficients — the classic perceptual-hash recipe, robust to scaling and re-compression.

Requirements

• Go 1.25+ — the SimHash half is pure stdlib; the pHash half uses golang.org/x/image for high-quality downscaling, which sets the floor.

License

MIT — see LICENSE.

---

Extracted from file-search-on, where it powers find_near_duplicates and image_similar_to.

Documentation

Overview

Package fingerprint provides two small content-fingerprinting primitives for near-duplicate / similar-content detection:

• TEXT: a 64-bit Charikar SimHash (Compute / Distance / Similarity) for finding near-duplicate documents. Pure stdlib.
• IMAGES: a 64-bit perceptual hash / pHash (PHash / PHashFromImage, with PHashHex / PHashFromHex helpers) for finding visually-similar images. Uses golang.org/x/image for high-quality downscaling.

Both produce a uint64 whose pairwise Hamming Distance (and the derived Similarity = 1 - distance/64) measures closeness — small distance == similar content.

SimHash (text)

SimHash is a locality-sensitive hash: documents whose tokens substantially overlap produce fingerprints whose XOR has few set bits (small Hamming distance). Similarity == 1 - distance/64, so:

distance <= 3   ≈ 95% similarity  (near-identical: whitespace / a word or two)
distance <= 9   ≈ 85% similarity  (minor edits / template fills — a common cut)
distance ~ 28+  ≈ 55% similarity  (unrelated prose, near the random baseline)

(Shingling registers a localised edit as a few changed shingles rather than one changed token, so small edits sit slightly higher up the distance scale than a single-token hash would put them.)

We tokenise by Unicode letters/digits (lowercased), drop tokens of length < 2, then group them into overlapping k-word SHINGLES (k = shingleSize). Each shingle is hashed via FNV-1a-64 and fed to Charikar's per-bit accumulator: +1 for every shingle whose hash has bit i set, -1 otherwise. The final bit i of the fingerprint is 1 iff the running sum at position i is positive.

Shingles rather than single words because single-token SimHash over natural-language prose is dominated by the high-frequency stopword distribution (the / and / of / to …), which is near-universal across all English text — so two unrelated novels score ~90% similar and cluster spuriously. A document's k-word phrasing is far more distinctive: unrelated prose drops to ~0.55 (near the random baseline) while genuine near-duplicates stay high.

Compute the fingerprint of each document's text, then pairwise compare via Distance or Similarity. For images, use PHash (see phash.go).

Example (ImagePerceptualHash)

Example_imagePerceptualHash shows that PHashHex renders a 64-bit perceptual hash as a 16-character hex string for storage / comparison.

package main

import (
	"fmt"

	"github.com/richardwooding/fingerprint"
)

func main() {
	// In practice: h, _ := fingerprint.PHash(reader)
	hex := fingerprint.PHashHex(0x0f0f0f0f0f0f0f0f)
	fmt.Println(len(hex), hex)
}

Output:
16 0f0f0f0f0f0f0f0f

Example (TextNearDuplicate)

Example_textNearDuplicate shows detecting a near-duplicate document: a one-word edit leaves the SimHash fingerprints close (high Similarity), while unrelated prose sits near the random baseline.

package main

import (
	"fmt"

	"github.com/richardwooding/fingerprint"
)

func main() {
	base := "The cartographer unrolled the brittle chart across the captain's table and traced the reef-strewn passage with a steady finger, warning that the southern current would carry any vessel onto the rocks before dawn if the helmsman misjudged the tide by even a quarter hour."
	// One word changed (dawn → dusk) — a near-duplicate.
	edit := "The cartographer unrolled the brittle chart across the captain's table and traced the reef-strewn passage with a steady finger, warning that the southern current would carry any vessel onto the rocks before dusk if the helmsman misjudged the tide by even a quarter hour."
	// Entirely different prose.
	other := "Quarterly revenue rose twelve percent as the cloud division expanded its enterprise subscriptions, while the board approved a share buyback and raised guidance for the upcoming fiscal year."

	a, b, c := fingerprint.Compute(base), fingerprint.Compute(edit), fingerprint.Compute(other)
	fmt.Println(fingerprint.Similarity(a, b) > 0.85) // near-duplicate
	fmt.Println(fingerprint.Similarity(a, c) < 0.7)  // unrelated
}

Output:
true
true

Index

• func Compute(text string) uint64
• func Distance(a, b uint64) int
• func PHash(r io.Reader) (uint64, error)
• func PHashFromHex(s string) (uint64, error)
• func PHashFromImage(img image.Image) uint64
• func PHashHex(hash uint64) string
• func Similarity(a, b uint64) float64
• type PHashError
  • func (e *PHashError) Error() string

Examples

• Package (ImagePerceptualHash)
• Package (TextNearDuplicate)

Functions

func Compute

func Compute(text string) uint64

Compute returns the 64-bit SimHash fingerprint of text. Empty input (or input with no usable tokens) returns 0, which is a legitimate fingerprint — callers can distinguish "no content to fingerprint" via a separate len(body) check.

func Distance

func Distance(a, b uint64) int

Distance returns the Hamming distance between two SimHash fingerprints — the number of bit positions where they differ. Range is 0 (identical) to 64 (maximally different).

func PHash

func PHash(r io.Reader) (uint64, error)

PHash returns the 64-bit perceptual hash of the image decoded from r. Returns 0 + an error when decoding fails or the image is unusable (smaller than the grid, animated GIF with no first frame, etc.).

PHash is invariant under (file size, modification time) when the pixels don't change, so the cached value in index.Entry.PHash stays valid for as long as the entry itself validates.

func PHashFromHex

func PHashFromHex(s string) (uint64, error)

PHashFromHex parses a 16-character hex string back into a uint64. Returns 0 + an error when the string isn't a valid hex pHash. Used by the CEL `image_similar_to(reference_path, threshold)` function to compare against a reference image's pHash without re-decoding the reference image per file.

func PHashFromImage

func PHashFromImage(img image.Image) uint64

PHashFromImage is the pure-pixel entry point. Useful for callers that already have a decoded image.Image (tests, in-memory pipelines) and for the CEL reference-image cache where the reference is decoded once and reused across the walk.

func PHashHex

func PHashHex(hash uint64) string

PHashHex formats a 64-bit pHash as a 16-character lowercase hex string (the wire form used in CEL `phash` attribute output and in the index cache's JSON / gob encoding for human inspection).

func Similarity

func Similarity(a, b uint64) float64

Similarity returns the SimHash similarity score in [0, 1]:

1.0  → fingerprints are identical
0.5  → uncorrelated (random fingerprints average here)
0.0  → fingerprints differ in every bit

Threshold 0.85 (the issue's default) corresponds to Hamming distance ≤ 9.

Types

type PHashError

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

PHashError is the error type for phash-specific parse / decode failures. Wraps a static message for cheap allocation.

func (*PHashError) Error

func (e *PHashError) Error() string