My diff tool, diff.so, is a web app, but it doesn’t send the text to the server (unless you publish). I wish there were a technical mechanism that could guarantee and enforce that, and certify it to users.
You could distribute it as a single index.html file, with unobfuscated/unminimized vanilla javascript. The user could then execute it offline no problem.
For fun, you could even use redbean ( https://justine.lol/redbean/index.html ), which has been discussed on here recently. That would give you a tiny executable running a webserver that serves your webapp locally. Probably not much advantage compared to a plain html file, though. Might be smaller overall, since everything would be compressed.
It's the kind of UI experimentation I like to see people try, but I'm not sure they nailed this one.
Probably onto something though. Try different diacritical symbols and see what sticks. Given how '"' looks, maybe combining above or below needs to vary by character. Above probably looks awful for '.' and ','.
Really I think the strikethrough might suffice. The only way to know for sure is to take away the color highlighting, so my brain doesn't use it as a crutch, and see if people can still read the diff.
I think it's really cool as well. Although, it does start to look a little wonky with quotes and probably some other characters and makes skimming a bit harder. Maybe monospaced fonts will start to handle this better if it gets popular?
This is neat. I decided to diff two pods in a replicated Kubernetes service. It seemed that it was going to take forever to run, so I just wrote a short Go program to do the same thing (load two JSON files into a map[string]interface{}, cmp.Diff them) while it was going:
My program runs in less than 10 milliseconds (/usr/bin/time reports 0.00 seconds), and graphtage takes 5 minutes and 17 seconds. I'm 317,000x faster! (Not including the time to write the program; if you do that, then it's about even assuming graphtage took 0 seconds to write.)
Graphtage prints the entire file in JQ colors, with diffs inside fields colored red and green, which I love:
Honestly, I get what I want out of mine, and wait 317,000x less time, so... I probably won't be using this on a daily basis. But I will be stealing those dots and Unicode strikethroughs.
It's neat that you built what you needed in a few lines of code. I must say, I don't quite like the output of Graphtage, I like your's a little bit more, but without a context it's not easy to see how podIP is nested.
Usecases might be a little bit different, but please allow me to share my solution.
The problem with diffing JSON and yaml is, that these formats aren't line based and hashes don't need to be ordered. But there is gron to turn json into a greppable line-based format [1]. Then you can sort. The sorted output is possible to diff now and then you can color the diff output with delta or a similar tool [2].
diff -u <(kubectl get pod pod1 -o json | gron | sort) <(kubectl get pod pod2 -o json | gron | sort) | delta --light --word-diff-regex="\W+"
This output provides a lot of context for me to see and understand the differences.
Maybe a bit of a red herring, but I just used Kubernetes as a cheap source of mildly interesting JSON to test a diffing tool with. You'll see that the manpage for Graphtage just uses things like '{"foo":["bar"]}' in their examples... and those run fast. But the second you get some real-world piece of data, it takes 5 minutes to run. That's why I tested on some real-world data first.
Well you are kinda comparing apples and oranges here.
According to their readme they don't just match on keys, but even try to detect changed keys for the same content, even when the two files have a different inner order of elements.
Your diff is probably equivalent to a pretty print and then running regular diff on it, i.e. not even sorting the file.
Having said that and assuming your file wasn't extraordinary large, a 5min runtime makes this tool kinda unusable.
I think it’s ended up with a quadratic algorithm for diffing sequences and a quadratic log algorithm for diffing dictionaries.
To understand why the sequences problem is quadratic, consider a sequence A of length m being doffed with a sequence B of length n. We want to express our diff in the minimum number of operations where an operation is removing, adding, or editing an element in the sequence. Construct a graph as follows: the nodes will be the points on an mxn lattice corresponding to points in the two sequences. An edge going right means “delete this item from sequence A,” and costs (eg 1). An edge going down means “add this item from sequence B” and has a similar cost. An edge going diagonally down and right means to edit the item in A into the item in B and it’s cost depends on how different they are. The problem is to find the shortest path from the top left to the bottom right.
If you could compute the entire graph for free and then applied something like Dijkstra’s algorithm you would be worst-case quadratic (if all the diagonal costs were 2 or more, you would need to touch every node).
There are a few ways you could try to improve this:
1. Look for easy opportunities to optimise. Eg you could have a patience style strategy of cutting off any common prefix or suffix. This won’t help in the worst case.
2. Limit to a fixed width diagonal. This might mean worse diffs but means the graph search problem becomes more linear. I suspect something is going on with the diagonal based on the description
3. Somehow develop some good heuristics and use a better search algorithm like A*. This might not help in the worst case
Quadratic doesn't need to equal "bad", especially in this case. Two 45 kB items is 2 billion entries. Allocating 2 billion bytes is easy enough. Iterating over 2 billion bytes is also not terrible. The GP says the process is estimated to take 150 hours, or half a million seconds, or 1.62e15 cycles... so around 1 million cycles per cell.
If it’s doing anything nontrivial (eg computing the weights of the diagonal edges by comparing the rows as sequences) then you’re basically screwed. The problem with quadratic is that it doesn’t scale but it’s fast enough for small inputs that it is hard to notice until you get a large input.
My point is that even though it's quadratic it can still be fast for the inputs mentioned (dozens of kilobytes), so long as the constant is low. If you have a quadratic algorithm that takes 1 cycle per byte of input squared(or less, using wide registers), it will be pretty damn quick for most inputs. If you have a quadratic algorithm that takes 1 million cycles for each byte of input squared (such as this one), that's a whole different story. The time to process 1 Megabyte in the 1 cycle algorithm would only let you process a kilobyte in the new.
Point is that things like being efficient with memory access and using sufficiently low level (or JIT'ed) languages can get you very far, and it's not really meaningful to dismiss an algorithm solely based on it being quadratic.
I have a use case for diffing trees, so would love to know of any optimal algorithms you may know of; I'm operating generally with less than 100 nodes, so it's not a huge concern, but I'm finding that discovering _any_ algorithms for this has been tough.
Yeah I found the same. It seems that there hasn't really been much research in this area, and somewhat annoyingly there isn't a widely agreed term for the problem, though for some reason most of the algorithms are described in terms of diffing XML so if you search for "XML difference" you can find some papers.
There's a few algorithms like XDiff, XyDiff, XChange etc. but be prepared to find very old code on sourceforge or more likely no code at all.
I couldn't find anything with a decent complexity that either had code or was simple/well described enough that I could implement it so I gave up.
> Graphtage matches ordered sequences like lists using an “online”[note], “constructive”[note] implementation of the Levenshtein distance metric[note], similar to the Wagner–Fischer algorithm[note[. The algorithm starts with an unbounded mapping and iteratively improves it until the bounds converge, at which point the optimal edit sequence is discovered. This is implemented in the graphtage.levenshtein module.
Is there a corresponding patch utility? Can I generate compact diff file for changed dataset, distribute it and have people apply the difference on their side?
It's difficult to search for HTML diff libraries these days because all the hits are vdom like things, instead of diffing HTML text for development / testing.
If you mean convert between data formats (e.g. between, CSV,YAML,JSON, XML) there are programs already that can do that. For example our Easy Data Transform. However there are wrinkles because some of these formats are trees and some are tables. Flattening a tree into a table isn't too hard. But unflattening a table back into the same tree as the original is trickier. Has anyone got any good references on that?
do you have a list for that? i am aware, that there are dialects and {table,trees,graphs}<->{table,trees,graphs} may be a problem for some languages, but having it at least would be a progress.
Which is conceptually equivalent, but less compact (similarly for XML). I am hoping to fix this issue. But if anyone has any links to how to unflatten a table into a compact tree, I'm all ears.
