storage of text history and algorithm to return text at particular time

Question

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.

Answer 1

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.