Documentation
¶
Overview ¶
Package similar finds near-clone code via MinHash over token shingles — the M4 SIMILAR_TO pass. No embeddings or model: a fixed-size MinHash signature per symbol estimates pairwise Jaccard similarity cheaply, and LSH banding (later) turns the O(n^2) all-pairs comparison into candidate buckets.
Index ¶
- func Edges(project string, docs []Doc, threshold float64) []graph.Edge
- func EdgesFromSignatures(project string, docs []SigDoc, threshold float64) []graph.Edge
- func EstJaccard(a, b []uint64) float64
- func Signature(tokens []string, k, numHashes int) []uint64
- func Tokenize(src string) []string
- type Doc
- type SigDoc
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func Edges ¶
Edges returns SIMILAR_TO edges between docs whose estimated Jaccard similarity is at least threshold. Candidate pairs come from LSH banding (not an all-pairs scan); each surviving pair yields one symmetric pair (smaller QN -> larger) carrying the score. Docs too short to form a shingle are ignored (trivial bodies are not clones).
func EdgesFromSignatures ¶ added in v0.2.0
EdgesFromSignatures is like Edges but accepts precomputed signatures only.
func EstJaccard ¶
EstJaccard estimates the Jaccard similarity of two token streams from their MinHash signatures: the fraction of positions that agree. Signatures must be the same size.
func Signature ¶
Signature is the MinHash signature of the token stream: numHashes positions, each the minimum over the shingle-hash set of a distinct strong-mix permutation (splitmix64 of the shingle XOR a per-position seed). The fraction of equal positions between two signatures estimates the Jaccard similarity of their shingle sets (see EstJaccard). A strong avalanche permutation matters: the cheap a*h+b universal hash is only 2-universal and its MinHash estimate is too noisy at a tight threshold.
func Tokenize ¶
Tokenize splits source into a token stream for similarity: each identifier/number run is one token, and every other non-space rune (operators, brackets, punctuation) is its own token; whitespace is dropped. Cheap and language-agnostic — near-clones share most of this stream regardless of formatting.
Source Files