SynDiff Algorithms
Our algorithms are approximations of perfect algorithms.
Our fastest algorithms are actually approximations of those approximations.
We flattened the parse tree because of the algorithm design.
Many of the notes on this page are SynDiff TODOs.
Implementation
This details how the algorithms are used during program execution.
New implementation method:
- specify two options on the command line or alg
- alg=?
- ordered_alg=? with unordered_alg=?
Algorithms
Algorithms are divided into two types: ordered and unordered.
Ordered
Longest Common Subsequence Solution
- Ordered (LCS)
Single-Path Greedy Heuristic
- Ordered (greedy heuristic from hybrid)
Triple-Path Greedy Heuristic
- Ordered (greedy heuristic with more paths, improved on hybrid version)
Diff Algorithm
- Ordered (“An O(ND) Difference Algorithm and its Variations” from diff)
Unordered
Exact
- Unordered Exact (from unified)
Approximation
- Unordered Approximation (from Jason's)