Re^4: Create JSON patch

[afoken]

So which algorithm should be used to decide, if an element has to be "moved" instead of being "replaced"

My guess is that the JSON patch format was meant to do updates on large JSON files (or resources, in HTTP context) without having to transfer the entire file all the time. So one very likely scenario would be a mobile application or a javascript-based application running in a browser that wants to modify the data structure and then post back the changes to a server. In that case, the application knows quite well if it has removed, replaced, added, copied or moved something.

Giving arbitary JSON files, all a program could do is guessing. A simple brute-force algorithm roughly based on diff would probably use only add and remove. In a second step, one could change every sequence of Remove and Add for the same node with Replace. Remove and Add for an identical subtree, but different nodes could be replaced with Move. Copy needs more work, but it should not be impossible.

Alexander

[LanX]

I agree but

> it should not be impossible

Not many things are really fully impossible, but from my experience freedom of interpretation is a really bad start for a question and subsequent algorithm.

Especially if "possibility" must be bought with runtime overhead.

edit

This has the smell of NP completeness. *

update

*) reminds me of Subgraph_isomorphism_problem

[afoken]

This has the smell of NP completeness.

May be, I didn't (and won't) spend much time considering.

To solve the basic problem of creating any patch for a pair of random JSON documents, a quite relatively simple-minded diff-style algorithm should do the job. Very likely, the patch won't be the smallest possible patch in all cases, and it won't be elegant at all. But that approach has proven to work quite well for the last 43 years for all kind of text files, and especially for source code.

Alexander

[LanX]

> work quite well for the last 43 years for all kind of text files, and ...

text-diff / patch support "move" operations?

I don't think so, that's why I asked the OP for clarification, what his "basic" problem is.

We are comparing apples with gala dinners, the OP must be clearer about what kind of pony he wants.