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.