ProgramLineEditDistance

Models & Types ยท AiDotNet.Evolution.Programs.Novelty

A normalized Levenshtein distance over whole lines; order sensitive, and still entirely local.

Implements: IGenomeDistance<ProgramGenome>

For Beginners

This counts how many whole lines you would have to add, delete or change to turn one program into the other, then divides by the length of the longer one. Nought means identical, one means nothing in common. Use it instead of the token metric when the order of the code matters to you, and alongside it when you want both a vocabulary view and a structure view.

How It Works

The unit of edit is a line, not a character. That is the right granularity for evolved source: a model that rewrites one loop body changes a handful of lines out of dozens, which this reports as a small distance, whereas character-level edit distance over the same change is dominated by the unchanged bulk and is quadratic in program length rather than in line count. The result is divided by the longer line count, so it lands in 0 to 1 and is comparable against the same threshold as ProgramTokenSetDistance.

Unlike the token-set metric this one is order sensitive: moving a block without changing any vocabulary is a real distance here and zero there. It costs O(L1 x L2) time and O(min(L1, L2)) memory, so it is cheap for ordinary programs and bounded for pathological ones โ€” a source longer than MaxComparedLines lines is compared on its first MaxComparedLines lines, which keeps a single comparison bounded no matter what a model emits. Neither variant makes a network request or loads a model.

Constructors

Constructor Summary
ProgramLineEditDistance(int maxComparedLines) Initializes a line edit distance.

Properties

Property Summary
int MaxComparedLines { get; } Gets the per-source line bound applied before comparison.
string Id { get; }
string VersionHash { get; }

Methods

Method Summary
double ComputeDistance(string first, string second, int maxComparedLines) Computes the normalized line edit distance between two program sources.
double Distance(ProgramGenome first, ProgramGenome second)

Fields

Field Summary
int DefaultMaxComparedLines The default line bound applied to each source before comparison.
string MetricId The identifier this metric reports.