An application I'm considering writing needs to show a text that a user has edited at a particular time.

So consider if we have a text the user is editing from Time A to Time X, and I want to show what it looked like at Time L.

This text can be for a long running process, and it can be theoretically big, therefore it is not going to work just the brute solution of I will save what it is like at every keystroke - or well it might work but not very well.

But I'm betting there is probably some algorithm for how to handle this problem that I'm unfamiliar with such that basically I take Time L, take all the diffs from start of the text as an empty string at Time A and give me the actual resulting text.

I guess another way to think about it would be that it each Time in our time series has a keystroke associated with it, and then Time L just replays everything from Time A to L to get what the value of Text should be at Time L.

I hope this has been clear because often people seem to think I am unclear about these kinds of things.

  • Yes, replaying the collected diffs from the starting point is the obvious thing to do. If your text gets really big, you might intersperse full snapshots from time to time, like key frames in a video stream, but other than that I can't see what else you would do. – Kilian Foth Jan 16 at 10:51
  • Some systems save starting point text (e.g. blank) and then deltas that go forward to succeeding revisions. Other systems save the final result text and deltas that go back to prior revisions. Version control systems (SCCS, RCS, git) have approaches that are relevant here. – Erik Eidt Jan 16 at 15:17

There is no "algorithm" for this scenario you mentioned.

You have an apparent trade-off as you mentioned in the granularity of your snapshots (from trapping each keystroke to give the user's freedom to decide by itself [like commit-object in git]).

You need to ask yourself, or provide us with more information regarding your requirements/constraints.
If this is a system facing a user is it of interest for the user mining through keystroke history ? While, if it's being mined by an automated software it may be appropriate.

(Depending on your granularity, you need to think also about the infrastructure to handle the data received.)

Also, you can decide on a hybrid solution which keeps track of the latest changes (in a fine granularity) and archive/consolidate/"forget" older changes.

The snapshot mechanism can either be an incremental diffs (that you need to process for a user request) or saved snapshots. Again, it depends on your constraints and both of this options can be used together.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.