Always cool to see this come up. I really like the idea of "encoding" the video as... x86 machine instructions!
The hairsplitting nerd in me can't help but point out that the claim in the Part 2 article that the problem of combining deltas is NP hard isn't true. In fact you can solve this optimally in O(n^3) time with DP: Let g(i, j) be the minimum number of bytes needed to encode input deltas i..j as a single (i.e., combined) output delta. Given g(i, j), computing g(i, j+1) takes constant time, so we can compute all of this function's values in O(n^2) total time. Now let f(i, j) be the minimum number of bytes needed to encode input deltas i..j using any sequence of output deltas (combined or not). Note that any such sequence must consist of some number (possibly zero) of optimally encoded output deltas followed by an optimally encoded output delta that itself ends with input delta j. IOW, it must be that f(i, j) is equal to f(i, k) + g(k+1, j) for some k, and there are at most n values of k that we need to try, so we can compute each value of f() in O(n); there are O(n^2) values to compute, so O(n^3) time overall. f(1, n) is then the minimum number of bytes needed to encode the entire list of input deltas, and standard backtracing through the DP matrix can be used to recover the actual sequence of output deltas.
5 comments:
Having used these machines, this is mind boggling.
Always cool to see this come up. I really like the idea of "encoding" the video as... x86 machine instructions!
The hairsplitting nerd in me can't help but point out that the claim in the Part 2 article that the problem of combining deltas is NP hard isn't true. In fact you can solve this optimally in O(n^3) time with DP: Let g(i, j) be the minimum number of bytes needed to encode input deltas i..j as a single (i.e., combined) output delta. Given g(i, j), computing g(i, j+1) takes constant time, so we can compute all of this function's values in O(n^2) total time. Now let f(i, j) be the minimum number of bytes needed to encode input deltas i..j using any sequence of output deltas (combined or not). Note that any such sequence must consist of some number (possibly zero) of optimally encoded output deltas followed by an optimally encoded output delta that itself ends with input delta j. IOW, it must be that f(i, j) is equal to f(i, k) + g(k+1, j) for some k, and there are at most n values of k that we need to try, so we can compute each value of f() in O(n); there are O(n^2) values to compute, so O(n^3) time overall. f(1, n) is then the minimum number of bytes needed to encode the entire list of input deltas, and standard backtracing through the DP matrix can be used to recover the actual sequence of output deltas.
([2014])
a more civilized time
Literally.