How do you handle degenerate trees? I’m curious what heuristics are used in practice to eg backtrack or whatever. I’m not very well versed in TED but superficially the problem seems to resemble wave function collapse.
In practice, tree hashing is doing a huge amount of work because most diffs are tiny. Half of all diffs are less than 10 lines, so a hash can extremely quickly match large subtrees.
In a profoundly degenerate case of a C++ header file with only a 20MB array of bytes, it detects a degenerate tree and uses Myers O(N) sequence diffing algorithm instead of treating it as a tree.
I actually don’t know how to do that and stay under a bounded edit distance.
Alternatively, you can crash it if you just encode the entire “Star Trek - In the pale moonlight” episode as a sequence of bytes in a const int array in C++.
I’m sure there’s an interesting result there, but I am not the person to find it :D
Good episode btw