MyersDiff 0.2.2

Myers' difference algorithm

A C# implementation of Eugene Myers' O(ND) difference algorithm for computing the Longest Common Subsequence (LCS) and Shortest Edit Script (SES) between two sequences.

Features

• Generic — works with any element type via ReadOnlySpan<T>
• Custom equality comparers via IEqualityComparer<T>
• Zero external dependencies

Longest Common Subsequence

List<char> lcs = Lcs<char>.Build("abcabba", "cbabac");

// ['c', 'a', 'b', 'a']

With an explicit comparer:

List<char> lcs = Lcs<char>.Build("abcabba", "cbabac", EqualityComparer<char>.Default);

// ['c', 'a', 'b', 'a']

Shortest Edit Script

List<Ses<char>.Cmd> ses = Ses<char>.Build("abcabba", "cbabac");

// [Del(1), Del(2), Ins(3, 'b'), Del(6), Ins(7, 'c')]

foreach (var cmd in ses)
{
    switch (cmd)
    {
        case Ses<char>.Cmd.Del del:
            Console.WriteLine($"Delete at position {del.Pos}");
            break;
        case Ses<char>.Cmd.Ins ins:
            Console.WriteLine($"Insert '{ins.El}' at position {ins.Pos}");
            break;
    }
}

With an explicit comparer:

List<Ses<char>.Cmd> ses = Ses<char>.Build("abcabba", "cbabac", EqualityComparer<char>.Default);

// [Del(1), Del(2), Ins(3, 'b'), Del(6), Ins(7, 'c')]

Custom Trace Logic

The Path, Vector, and Trace types are public, so you can call Algorithm.LcsSes directly and implement your own trace logic on top of the recorded snapshots.

For example, building a unified diff-style output:

string a = "abcabba";
string b = "cbabac";

var path = Algorithm.LcsSes(a, b, EqualityComparer<char>.Default);

var filter = Trace.Filter.Del | Trace.Filter.Ins | Trace.Filter.Eq;

foreach (var edit in Trace.GetEdits(path, filter))
{
    switch (edit.Op)
    {
        case Trace.Op.Del:
            Console.WriteLine($"- {a[edit.X - 1]}");
            break;
        case Trace.Op.Ins:
            Console.WriteLine($"+ {b[edit.Y - 1]}");
            break;
        case Trace.Op.Eq:
            Console.WriteLine($"  {a[edit.X - 1]}");
            break;
    }
}

// - a
// - b
//   c
// + b
//   a
//   b
// - b
//   a
// + c

Limitations

The linear-space refinement (divide-and-conquer) described in the original paper is not yet implemented. The current implementation stores the full snapshot history during the forward pass. This is planned for a future release.

References

• Myers, E.W. An O(ND) difference algorithm and its variations. Algorithmica 1, 251–266 (1986). PDF