Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Graphtage: A semantic diff utility for JSON, HTML, YAML, CSV, etc

github.com

Post reply on HN
Print view View original

41–50 of 52 posts

Re: Graphtage: A semantic diff utility for JSON, HTML, YAML, CSV, etc

#41

Post by thunderbong »

_frkl wrote: post #24
tmpz22 wrote: post #21

Earlier quoted context omitted.

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.

I'm also very impressed by redbean. However, I couldn't get it to work, just like many of the other HNers on that thread.

Re: Graphtage: A semantic diff utility for JSON, HTML, YAML, CSV, etc

#44

Post by deknos »

hermitcrab wrote: post #37
deknos wrote: post #28

and now please, build a tool which converts all these thinks, like imagemagick for machinereadable documents.

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.

Re: Graphtage: A semantic diff utility for JSON, HTML, YAML, CSV, etc

#45

Post by hermitcrab »

deknos wrote: post #44
hermitcrab wrote: post #37

Earlier quoted context omitted.

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.

Do you mean a link? If so: https://www.easydatatransform.com/

Just as an example of the treetable issue:

If you input this JSON tree:

{ "Color": "Blue", "Part": [ { "Type": "A", "Number": [ "1", "2" ] }, { "Type": "B", "Number": [ "1" ] } ]

It can be converted to a table as:

Color,Part.Type,Part.Number

Blue,A,1

Blue,A,2

Blue,B,1

Which is fine is you then want to output as Excel, CSV etc. But if you then output that back to JSON you get:

[ { "Color": "Blue", "Part": { "Type": "A", "Number": "1" } }, { "Color": "Blue", "Part": { "Type": "A", "Number": "2" } }, { "Color": "Blue", "Part": { "Type": "B", "Number": "1" } } ]

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.

Re: Graphtage: A semantic diff utility for JSON, HTML, YAML, CSV, etc

#46

Post by IshKebab »

rmccue wrote: post #39
IshKebab wrote: post #33

Earlier quoted context omitted.

Tree diffing algorithms have very bad complexity (e.g. O(N^4)!) so this will probably only work on really small examples.

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.

Re: Graphtage: A semantic diff utility for JSON, HTML, YAML, CSV, etc

#47

Post by meetups323 »

dan-robertson wrote: post #34
meetups323 wrote: post #16

Earlier quoted context omitted.

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.

Re: Graphtage: A semantic diff utility for JSON, HTML, YAML, CSV, etc

#48

Post by deknos »

hermitcrab wrote: post #45
deknos wrote: post #44

Earlier quoted context omitted.

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.

Do you mean a link? If so: https://www.easydatatransform.com/ Just as an example of the tree table issue: If you input this JSON tree: { "Color": "Blue", "Part": [ { "Type": "A", "Number": [ "1", "2" ] }, { "Type": "B", "Number": [ "1" ] } ] It can be converted to a table as: Color,Part.Type,Part.Number Blue,A,1 Blue,A,2 Blue,B,1 Which is fine is you then want to output as Excel, CSV etc. But if you then output that…

i meant a cli tool :D but thanks

Re: Graphtage: A semantic diff utility for JSON, HTML, YAML, CSV, etc

#49

Post by jrockway »

kmarc wrote: post #36
jrockway wrote: post #35

Earlier quoted context omitted.

The diff I did is aware of the structure of the object. It's not just sorted lines.

Apart from the interesting conversation here, just to make sure... You are all aware of kubectl diff[1], right? I understand that sometimes you just want to diff two k8s objects, kubectl diff is not a tool for that. [1]: https://www.mankier.com/1/kubectl-diff

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.

Re: Graphtage: A semantic diff utility for JSON, HTML, YAML, CSV, etc

#50

Post by hermitcrab »

deknos wrote: post #48
hermitcrab wrote: post #45

Earlier quoted context omitted.

Do you mean a link? If so: https://www.easydatatransform.com/ Just as an example of the tree table issue: If you input this JSON tree: { "Color": "Blue", "Part": [ { "Type": "A", "Number": [ "1", "2" ] }, { "Type": "B", "Number": [ "1" ] } ] It can be converted to a table as: Color,Part.Type,Part.Number Blue,A,1 Blue,A,2 Blue,B,1 Which is fine is you then want to output as Excel, CSV etc. But if you then output that…

i meant a cli tool :D but thanks

You can also run it from the command line.
Post reply on HN