ProgramTokenSetDistance
Models & Types · AiDotNet.Evolution.Programs.Novelty
A Jaccard distance over the lexical tokens of two programs; no provider, no model, no network.
Implements: IGenomeDistance<ProgramGenome>
For Beginners
This asks a simple question — of all the words, numbers and symbols that appear in these two programs, what fraction appears in both? If nearly all of them do, the programs are near-twins and the number is close to zero. If they barely overlap, it is close to one. It costs nothing but a little arithmetic, which is why it is the first check a novelty gate makes.
How It Works
The distance is one minus the Jaccard index of the two token sets: identical token sets give zero, disjoint sets
give one, and everything in between scales with how much vocabulary the two programs share. Tokenization keeps
identifier and number runs whole and treats every other non-space character as its own token, so a rename
registers as a difference while reindentation and line-ending changes do not — the sources are compared after
ProgramGenome normalization, which already removed those.
Cost is a single pass over each source plus two hash-set operations, so one comparison is linear in program length with no allocation per comparison beyond the two token sets, and the sets for a fixed incumbent could be reused by a caller that keeps them. This is the whole point of shipping it: the reference implementation has no distance metric at all, so its cheapest possible novelty decision is an embedding request over the network, while the cheapest decision here is arithmetic on text already in memory.
The metric is symmetric, deterministic across processes and target frameworks, and returns zero for two genomes
with the same normalized source — the properties IGenomeDistance requires. Note that it
is a set distance, not a sequence distance: reordering a program’s lines without changing its vocabulary gives
distance zero. Pair it with ProgramLineEditDistance when order matters.
Constructors
| Constructor | Summary |
|---|---|
ProgramTokenSetDistance(int memoCapacity) |
Initializes a token-set distance. |
Properties
| Property | Summary |
|---|---|
int MemoCapacity { get; } |
Gets how many genome token sets this instance retains; zero disables memoization. |
string Id { get; } |
|
string VersionHash { get; } |
Methods
| Method | Summary |
|---|---|
double ComputeDistance(string first, string second) |
Computes the token-set distance between two program sources. |
double Distance(ProgramGenome first, ProgramGenome second) |
|
void ClearMemo() |
Discards every memoized token set. |
Fields
| Field | Summary |
|---|---|
int DefaultMemoCapacity |
The default number of genome token sets retained. |
string MetricId |
The identifier this metric reports. |