4 ms·

> Have you come up with a solution (I'm interested to know how, if you succeeded)? Nope. Naive approach is: for every byte of the modified file, compare agains

by byuu 12y ago

> Have you come up with a solution (I'm interested to know how, if you succeeded)? Nope. Naive approach is: for every byte of the modified file, compare against every position in the source file and find the longest match. If less than the cost of encoding the pointer+length pair, then add it to a queue of raw bytes to write. Flush the queue whenever you find a long enough match. That is of course O(n×m), which is easier to just say O(n^2). Tried exploring string-search algorithms like Knuth-Morris-Pratt and Boyer-Moore; tried keeping a tree list of 16-bit matches (which in fully randomized data reduces search overhead to O(n×m/{between log2(65536) and 65536}) ... but in a file of nothing but null bytes slightly hurts performance), tried skipping by S bytes per compare and then backtracking when long enough matches are found (hurts patch size efficiency as N goes up, but reduces overhead by O(n×m/S), and so on. I can get up to around a 64MB diff, before memory constraints and the inevitability of quadratic growth start to ruin me. Have tried to analyze what Xdelta/VCDIFF were doing, but the code is just too difficult to follow at my skill level. > Why don't you take lessons in your favourite instrument, then? I've tried, I just don't have the raw talent for it. Have no rhythm, have very poor note deduction ability, my mind trips all over itself when trying to use each hand to play a different part of a piano song, etc. Not a huge deal, just something I'd like to do. But even if I could do all these things; a jack of all trades is a master of none.

wolfgke 12y ago
> Nope. Naive approach is: for every byte of the modified file, compare against every position in the source file and find the longest match. If less than the cost of encoding the pointer+length pair, then add it to a queue of raw bytes to write. Flush the queue whenever you find a long enough match. That is of course O(n×m), which is easier to just say O(n^2). > > Tried exploring string-search algorithms like Knuth-Morris-Pratt and Boyer-Moore; tried keeping a tree list of 16-bit matches (which in fully randomized data reduces search overhead to O(n×m/{between log2(65536) and 65536}) ... but in a file of nothing but null bytes slightly hurts performance), tried skipping by S bytes per compare and then backtracking when long enough matches are found (hurts patch size efficiency as N goes up, but reduces overhead by O(n×m/S), and so on. A helpful idea is first to consider what you consider as the "correct" alignment. Often the Levenshtein distance (https://en.wikipedia.org/wiki/Levenshtein_distance https://en.wikipedia.org/wiki/Levenshtein_distance) is used and an alignment is considered as proper if the number of necessary steps (insertion/deletion/replacement of 1 character) equals to the Levenshtein distance. Obviously this does not necessary define a unique alignment (consider "a" - "aa" or "ab" - "ba"). An idea that I find interesting to consider is whether you could construct a o(m * n) (i. e. asymptotically faster than O(m * n)) algorithm that computes k elementary operations (insertion/deletion/replacement of 1 character) that convert the first string s into the second string s' such that there exists a fixed constant 1 < C with k <= C * d(s, s'), where d(s, s') is the Levenshtein distance between s and s'. How small can you get C? I really don't know the answer (I haven't even thought much about it), but perhaps this idea is helpful to you?

by byuu 12y ago

wolfgke 12y ago

> Nope. Naive approach is: for every byte of the modified file, compare against every position in the source file and find the longest match. If less than the cost of encoding the pointer+length pair, then add it to a queue of raw bytes to write. Flush the queue whenever you find a long enough match. That is of course O(n×m), which is easier to just say O(n^2). > > Tried exploring string-search algorithms like Knuth-Morris-Pratt and Boyer-Moore; tried keeping a tree list of 16-bit matches (which in fully randomized data reduces search overhead to O(n×m/{between log2(65536) and 65536}) ... but in a file of nothing but null bytes slightly hurts performance), tried skipping by S bytes per compare and then backtracking when long enough matches are found (hurts patch size efficiency as N goes up, but reduces overhead by O(n×m/S), and so on. A helpful idea is first to consider what you consider as the "correct" alignment. Often the Levenshtein distance (https://en.wikipedia.org/wiki/Levenshtein_distance https://en.wikipedia.org/wiki/Levenshtein_distance) is used and an alignment is considered as proper if the number of necessary steps (insertion/deletion/replacement of 1 character) equals to the Levenshtein distance. Obviously this does not necessary define a unique alignment (consider "a" - "aa" or "ab" - "ba"). An idea that I find interesting to consider is whether you could construct a o(m * n) (i. e. asymptotically faster than O(m * n)) algorithm that computes k elementary operations (insertion/deletion/replacement of 1 character) that convert the first string s into the second string s' such that there exists a fixed constant 1 < C with k <= C * d(s, s'), where d(s, s') is the Levenshtein distance between s and s'. How small can you get C? I really don't know the answer (I haven't even thought much about it), but perhaps this idea is helpful to you?