Diff of two states of a string or array

Question

For a string and an array, I have an "old" state, and a "new" state (after some modifications).

I need to often send to the server (with AJAX/XMLHttpRequest) the changes, if possible in an efficient way (don't resend 200 KB of data if only one element in the array has changed/has been deleted/has been moved). Example:

var oldstate1 = 'hello how are you? very good and you? thanks for asking! this text will be removed.';
var newstate1 = 'hello how are you? very good and you? new text here. thanks for asking!';

var oldstate2 = [[1732, "item1"], [1732, "will be deleted"], [23, "will be moved"], [23, "hello"]];
var newstate2 = [[23, "will be moved"], [1732, "item1"], [23, "hello"], [126, "new item"]];

Of course, I could manually code a protocol between client and server with events such as delete, insert, move, update, etc. and send these events with AJAX, and the server would update its database accordingly. But this is quite tedious to do correctly.

Question: is there a more clever way to encode only changes between oldstate and newstate of a big string or array with Javascript? in a way that can easily be decoded on backend, running Python.

Something similar to a diff/patch algorithm for strings or arrays, understood between JS (client-side) and Python (back-end).

Note:

a solution for strings might be enough, the "array case" would be covered by the "string case" with JSON.stringigy(...)
related but doesn't solve directly the problem: How to get the difference between two arrays in JavaScript?

A simple but inelegant method would be to send Javascript text of the operations you perform on the array, then run the JS in a new script tag — CertainPerformance
– CertainPerformance, Commented Feb 18, 2020 at 8:17
@CertainPerformance Interesting indeed! Unfortunately the backend doesn't run Node.js, so I couldn't run the same JS operations there. — Basj
– Basj, Commented Feb 18, 2020 at 8:18
You wouldn't have to run them, but you would have to be able to dynamically create the JS strings from the operations you perform in Python. Depends on the sort of manipulations you need to do, might be easy, might be near impossible — CertainPerformance
– CertainPerformance, Commented Feb 18, 2020 at 8:22
@Zydnar Yes this is similar to How to get the difference between two arrays in JavaScript?, but at the end you have to manually recode a protocol to make use of these array differences of arr1 and arr2, and differences of arr2 and arr1, so that the server knows where to insert these differences / what to delete. The question here was: is there an ready-to-use tool to do that? — Basj
– Basj, Commented Feb 18, 2020 at 8:32

Basj · Accepted Answer · 2020-02-18 14:50:20Z

0

It is probably possible with no third-party tool (if so, feel free to post another answer).

After further research, I found this project: diff-match-patch and particularly this example.

Originally built in 2006 to power Google Docs, this library is now available in C++, C#, Dart, Java, JavaScript, Lua, Objective C, and Python.

var oldstate1 = "hello how are you? very good and you? blablablablablablablablablablablablablablablablablablablablablablablablablablablablablablablablabla. thanks for asking! this text will be removed.";
var newstate1 = "hello how are you? very good and you? blablablablablablablablablablablablablablablablablablablablablablablablablablablablablablablablabla.new text here. thanks for asking!";
var dmp = new diff_match_patch();
var diff = dmp.diff_main(oldstate1, newstate1);
dmp.diff_cleanupSemantic(diff);
console.log(dmp.diff_toDelta(diff))    
// =138	+new text here.	=19	-27

<script src="https://cdnjs.cloudflare.com/ajax/libs/diff_match_patch/20121119/diff_match_patch.js"></script>

This delta + oldstate1 can then be used server-side, with Python, to reconstruct the newstate1:

import diff_match_patch as dmp_module
dmp = dmp_module.diff_match_patch()

oldstate1 = "hello how are you? very good and you? blablablablablablablablablablablablablablablablablablablablablablablablablablablablablablablablabla. thanks for asking! this text will be removed."
delta = "=138\t+new text here.\t=19\t-27"
patch = dmp.patch_make(oldstate1, dmp.diff_fromDelta(oldstate1, delta))
newstate1 = dmp.patch_apply(patch, oldstate1)[0]
print(newstate1)

2 Comments

Scott Sauyet Over a year ago

I was going to suggest looking for something like this when I saw the question. I was sure it had to exist. But note that you probably need something akin to commit/version numbers to apply this properly. If multiple clients edit the same data, or if one does multiple times, there is a real possibility of getting out of sync.

Basj Over a year ago

That's right @ScottSauyet, I just started to implement it using a commit number. If one user pushes with a too old commit number, I display a message "You are using an old version of this document, please refresh the page". It's works for now. PS: it's interesting to see that Google had to develop such a library for Google Docs needs back in 2006!

Collectives™ on Stack Overflow

Diff of two states of a string or array

1 Answer 1

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related