15.1 Log Compression Algorithm
(15 July 2005)
Abstract
This paper describes a log compression algorithm that is very efficient and results in maximal compression. An operation is stored as an ordered set of deletion intervals plus an ordered set of insertion intervals, allowing it to concisely represent any state difference. This means operations are closed under "addition" (i.e. merging). The merging algorithm involves a left to right scan through the intervals in one operation as well as the intervals in the other operation, choosing the next interval to process in a manner reminiscent of merge sort. The result is that merging is achieved in time linear in the number of string-wise intervals.
The merging process is effectively doing IT and ET but avoiding the ERV puzzles [1]. Of course that is simply because it doesn't exercise the problematic cases. That is, it never ET's an insert backwards past a delete, and it never IT's an insert forwards past an insert [2].
When transforming lists L1, L2 of string-wise operations against each other it is conventionally necessary to transform each L1[i] against each L2[j], resulting in an O(|L1| |L2|) algorithm. This can be prohibitive when |L1| and |L2| are large. The merging algorithm suggests that a general implementation of IT/ET may be possible that is practical for complex operations with many stringwise deletion and insertion intervals. The difficulty is in respecting the effects relation [1]. This is an area for future research.
[3] has also described a log compression algorithm that results in maximal compression. However, they express their solution directly in terms of IT and ET, and this raises questions such as
- What happens when ET(Oa,Ob) when Ob → Oa?
- What about the effects relation and the ERV puzzles?
Introduction
As in [1], by definition characters in text documents have identity. A character is originally inserted by a particular user at a particular site. The character keeps its unique identity even though its index position in the document needs to be adjusted according to continued editing operations. Note that a character doesn't simply relate to its appearance (eg its ASCII code) - for example each appearance of the letter 'A' in a document represents a different character.
We take the convention that strings use zero-based index positions. Given string s, let s[i] be the ith character. s[i,j) denotes the substring corresponding to the half-open interval [i,j). chars(s) denotes the set of characters in s.
For string s, the following mutative operations are defined:
- delete(s, p,n) — delete the range of characters [p,p+n) from s.
- insert(s, p,t) — insert string t into s at position p.
Assumptions and scope: The results below assume an insert/delete editing model in which every character has a persistent, globally unique identity. An insertion creates fresh identities, even when the inserted characters have the same textual values as existing characters, and deletion does not make an identity available for reuse. Surviving characters retain their relative order. A primitive move operation is outside this model unless it is explicitly represented as an extraction and an insertion with defined identity semantics. Every range list is assumed to be valid for its associated state, ordered from left to right, free of empty or overlapping ranges, and canonical: touching ranges have been coalesced. Consecutive operations supplied to a merge are contextually serialised, so the output state of the first is the input state of the second. Equality of states and sets of characters means equality by character identity, not merely equality of displayed text. Under these assumptions, "maximal compression" means the unique representation using maximal contiguous ranges; it is not a claim of information-theoretically optimal encoding.
using the notation S[i,j) to denote a substring in S.
// C++
typedef std::string String;
struct Range
{
Range() : p(0), n(0) {}
Range(const String& _s, int _p) : p(_p), n(_s.size()), s(_s) {}
int p;
int n;
String s;
};
We write state(L) to denote the text document state S on which L is defined. It is assumed that the strings in L will be found as sub-strings at precisely the specified positions within S. That is, ∀i, S[p(Li), p(Li) + n(Li)) = s(Li).
Given range list L, let chars(L) = ∪i chars( s(Li) ).
// C++
typedef std::list<Range> Ranges;
To perform the extraction it is easiest to iterate through the ranges from right to left (i.e. in reverse order) so that each extraction isn't upset by previously performed extractions - because they are on the right. The in-place (i.e. mutative) algorithm is:
// C++
// Let s = s - X
void ApplyExtractions(String& s, const Ranges& X)
{
for (Ranges::const_reverse_iterator x = X.rbegin() ; x != X.rend() ; ++x)
{
s.erase(s.begin() + x->p, s.begin() + x->p + x->n);
}
}
To perform the insertion it is easiest to iterate through the ranges from left to right (i.e. in forward order) so that for each insertion, all insertions to the left have already been performed - in keeping with the use of post-insertion coordinates. The in-place algorithm is:
// C++
// Let s = s + I
void ApplyInsertions(String& s, const Ranges& I)
{
for (Ranges::const_iterator i = I.begin() ; i != I.end() ; ++i)
{
s.insert(s.begin() + i->p, i->s.begin(), i->s.end());
}
}
Comment on this convention
Note that there is a nice symmetry between extractions and insertions. If we reverse the direction of time then extractions look like insertions and vice versa. Note how pre-extraction coordinates become post-insertion coordinates when we reverse time. Also note how we iterate through the ranges in the opposite order - in keeping with the analogy of reversing the direction of time.
All characters in the original string that were not deleted must appear in the final string, in the same relative order. Therefore the overall effect of any sequence of deletions and insertions can be determined by what characters have been deleted and what characters have been inserted. Characters that were inserted then deleted again are not relevant.
Note that chars(S1) \ chars(S2) = chars(X) and chars(S2) \ chars(S1) = chars(I).
Commentary:
This is interesting because it shows that building a state difference can be done unambiguously without any concern for the effects relation or the need for tie breaking using site identifiers [1]. As it turns out, an efficient algorithm is straightforward and will be described in the remainder of this paper.
An operation is represented using a set of extractions and a set of insertions. This allows a single operation to concisely represent arbitrary differences between two document states. For example, a single operation could efficiently represent weeks of work on a text document. Allowing for operations to be closed under "addition" (i.e. merging) is a useful property.
// C++
// Partial implementation of an operation
struct Operation
{
Ranges X;
Ranges I;
};
Merging extractions
Let (S1 - X1) - X2 = S2. We want X satisfying S1 - X = S2.
X1 and X2 are contextually serialised. There can't be a character deleted by X1 that is again deleted by X2. Merging the extractions is conceptually very simple — it is just a matter of translating positions correctly.
Note that state(X) = S1 = state(X1), so there is no need to translate positions in X1. However, positions in X2 are in the context of having already performed X1, so we need to exclude the effect of X1 by shifting positions in X2 to the right by the relevant number of characters that have been extracted by X1.
An efficient implementation can scan through both the ranges in X1 and X2 from left to right, stepping whichever range comes next. A variable can keep track of the accumulated number of characters deleted by X1. This is used to adjust the positions of X2.
Ranges to be added to X that touch need to be coalesced.
This algorithm is O(|X1| + |X2|).
Loop invariant: At the start of each outer iteration, the ranges before
x1 form the completed, coalesced prefix of the merged extraction list, and
x2 is the first extraction from X2 not yet incorporated. The variable
shift is the total length of the original X1 ranges already passed or absorbed,
so x2->p + shift maps the next X2 position back into S1
coordinates. Each iteration incorporates one X2 range and advances x2;
each X1 range is passed or absorbed at most once. On termination the whole list is in
S1 coordinates and represents exactly the characters extracted by X1 followed
by X2.
// Given [-X1 -X2], merge X2 into X1.
void MergeExtractions(Ranges& X1, const Ranges& X2)
{
int shift = 0;
Ranges::iterator x1 = X1.begin();
Ranges::const_iterator x2 = X2.begin();
while(x2 != X2.end())
{
// [11...)
// [22..)
//
// Skip over all [11..) that are strictly to the left of the next [22..) in its shifted
// position. These [11..) don't require adjustment. However we need to accumulate the
// shift.
// These intervals don't actually overlap because the effect of [11..) is to shift the
// next [22..) further to the right, past the end of the [11..)
while(x1 != X1.end() && x1->p < shift + x2->p)
{
shift += x1->n;
++x1;
}
/*
Now process all [11..) that coalesce with the next [22..). The effect is to split the next
[22..) into pieces that are shifted by different amounts.
Initially we position the [22..) according to the initial shift. In the following
example it aligns on the left with the next [11..).
As we process each [11..) we have to split the next [22..) into a left portion that is
appended to r using the current shift, and a right portion that is shifted further to the
right and requires further processing.
22222222222222222222
111 111111 1111
---> 22222222222222222222
111 111111 1111
---> 22222 222222222222222
111 111111 1111
---> 22222 2222222 22222222
111 111111 1111
So r = 111222221111112222222111122222222 is the coalesced string to be extracted
[t1,t2) represents the next substring from [22..) to be appended to r
*/
Range r;
r.p = shift + x2->p;
String::const_iterator t1 = x2->s.begin();
while(x1 != X1.end() && x1->p <= shift + x2->p + x2->n)
{
// Append next substring from [22..) to end of r
String::const_iterator t2 = x2->s.begin() + x1->p - (shift + x2->p);
r.s.append(t1,t2);
t1 = t2;
// Append next [11..) to end of r
r.s += x1->s;
// Accumulate shift from [11..), and erase [11..) because its effect is built into r
shift += x1->n;
x1 = X1.erase(x1);
}
r.s.append( t1, x2->s.end() ); // Append remainder of [22..) to end of r
r.n = r.s.size();
X1.insert(x1, r);
++x2;
}
}
Merging insertions
Let (S1 + I1) + I2 = S2. We want I satisfying S1 + I = S2.
I1 and I2 are contextually serialised. A character inserted by I1 can't also be inserted by I2. Merging the insertions is conceptually very simple — it is just a matter of translating positions correctly.
Note that state(I) = S2 = state(I2), so there is no need to translate positions in I2. However positions in I1 relate to the intermediate state S' = S1 + I1, and need to be translated to corresponding positions in S2. So positions in I1 must be shifted to the right according to the relevant number of characters that have been inserted by I2.
An efficient implementation can scan through both the ranges in I1 and I2 from left to right, stepping whichever range comes next. A variable can keep track of the accumulated number of characters inserted by I2. This is used to adjust the positions of I1.
Ranges to be added to I that touch need to be coalesced.
This algorithm is O(|I1| + |I2|).
Loop invariant: At the start of each outer iteration, the ranges before
i1 form the completed, coalesced prefix of the merged insertion list, and
i2 is the first range from I2 not yet incorporated. The variable
shift is the total length of the I2 ranges already incorporated, so adding it
to the original position of i1 maps that range into the final state S2.
Each iteration finalises one I1 range or incorporates an I2 range, and neither
iterator moves backwards. On termination all ranges use post-insertion coordinates in S2
and represent the combined effect of I1 followed by I2.
// Given [+I1 +I2], merge I2 into I1 (i.e. I1 += I2)
void MergeInsertions(Ranges& I1, const Ranges& I2)
{
int shift = 0;
Ranges::iterator i1 = I1.begin();
Ranges::const_iterator i2 = I2.begin();
while(i1 != I1.end())
{
while (i2 != I2.end() && i2->p < shift + i1->p)
{
I1.insert(i1, *i2);
shift += i2->n;
++i2;
}
if (i2 == I2.end())
{
do
{
i1->p += shift;
++i1;
} while(i1 != I1.end());
return;
}
i1->p += shift;
while (i2 != I2.end() && i2->p <= i1->p + i1->n)
{
i1->s.insert(i1->s.begin() + i2->p - i1->p,
i2->s.begin(), i2->s.end());
i1->n += i2->n;
shift += i2->n;
++i2;
}
++i1;
}
while(i2 != I2.end())
{
I1.insert(I1.end(), *i2);
++i2;
}
}
Transposing insertions then extractions
Let (S1 + I) - X = S3. We want X', I' satisfying (S1 - X') + I' = S3.
X may delete a character inserted by I. In that case both X' and I' won't mention the character.
Let S2 = S1 + I. Now state(X') = S1, whereas state(X) = S2. Extractions in X need to be shifted (to the left) to exclude the effect of I. Also, state(I') = S3, whereas state(I) = S2, therefore insertions in I need to be shifted (to the left) to include the effect of X.
Now state(X) = state(I) = S2. Therefore positions in X and I can be directly compared. An efficient implementation can scan through both the ranges in X and I from left to right, stepping whichever range comes next. A variable can keep track of the accumulated number of characters inserted by I. This is used to shift the positions of X to the left. Similarly a variable can keep track of the accumulated number of characters extracted by X and this is used to shift the positions of I to the left. Overlapping sections are characters that are inserted then deleted so these characters are discarded from X' and I'. Note finally that the extraction of characters from X can cause ranges in I to coalesce. Also, excluding the insertion of characters from I can cause ranges in X to coalesce.
Loop invariant: At the start of each iteration, the portions before
i and x have already been transposed into the completed prefixes of I' and
X'. The variables si and sx record the total lengths consumed from I and X,
respectively. Subtracting si maps an unprocessed extraction position back across the
insertions already encountered, while subtracting sx maps an insertion position forward
across the extractions already encountered. A non-overlapping prefix is emitted on the appropriate
side; an overlapping prefix represents characters inserted and then extracted, so it is consumed from
both sides and emitted on neither. Every step advances an iterator, splits off a nonempty prefix, or
erases a range. When the loop ends, the remaining ranges require only the accumulated coordinate
shift, after which coalescing restores the canonical range-list representation.
// C++
/*
Split away prefix t from range r for given p.
[rrrrrrrrrrrrrrrrr)
---> [ttttttt)[rrrrrrrr)
|
|
p
*/
void SplitRange(Range& r, int p, Range* t)
{
int n1 = p - r.p;
int n2 = r.n - n1;
if (t)
{
t->p = r.p;
t->n = n1;
t->s = String(r.s.begin(), r.s.begin() + n1);
}
r.p = p;
r.s.erase(r.s.begin(), r.s.begin() + n1);
r.n = n2;
}
// The given I,X are contextually serialised as [+I -X].
// Transform both I,X so they are instead contextually serialised as [-X +I].
void TransposeInsertionsThenExtractions(Ranges& I, Ranges& X)
{
int si = 0; // Accumulated shift from I
int sx = 0; // Accumulated shift from X
Ranges::iterator i = I.begin();
Ranges::iterator x = X.begin();
while(i != I.end() && x != X.end())
{
if (i->p + i->n <= x->p)
{
i->p -= sx;
si += i->n;
++i;
}
else if (x->p + x->n <= i->p)
{
x->p -= si;
sx += x->n;
++x;
}
else
{
if (i->p < x->p)
{
Range t;
SplitRange(*i, x->p, &t);
t.p -= sx;
si += t.n;
I.insert(i, t);
}
else if (x->p < i->p)
{
Range t;
SplitRange(*x, i->p, &t);
t.p -= si;
sx += t.n;
X.insert(x, t);
}
else
{
if (x->n < i->n)
{
SplitRange(*i, x->p + x->n, NULL);
sx += x->n;
si += x->n;
x = X.erase(x);
}
else if (i->n < x->n)
{
SplitRange(*x, i->p + i->n, NULL);
si += i->n;
sx += i->n;
i = I.erase(i);
}
else
{
sx += x->n;
si += i->n;
i = I.erase(i);
x = X.erase(x);
}
}
}
}
if (si)
{
while (x != X.end())
{
x->p -= si;
++x;
}
}
if (sx)
{
while (i != I.end())
{
i->p -= sx;
++i;
}
}
CoalesceRanges(I);
CoalesceRanges(X);
}
Merging operations
We are now ready to state the algorithm to merge operations.
Let O1 = [-X1 +I1], O2 = [-X2 + I2]
Then
[O1 O2] = [-X1 +I1 -X2 +I2 ]
~ [-X1 -X2' +I1' +I2] ( by transposing +I1, -X2)
~ [-X +I] ( by merging extractions and insertions)
where ~ denotes equivalence in terms of state change.
// C++
// In-place algorithm
// Merge O2 into O1
void Merge(Operation& O1, const Operation& O2)
{
Ranges X2 = O2.X;
TransposeInsertionsThenExtractions(O1.I, X2);
MergeExtractions(O1.X,X2);
MergeInsertions(O1.I,O2.I);
}
This algorithm is O(|O1.X| + |O1.I| + |O2.X| + |O2.I|).
In-place algorithms
We have used in-place algorithms where possible to maximise performance by avoiding unnecessary copying. This can provide significant benefits when merging edits into a very large state difference.
Compressing the log
This algorithm should readily allow hours, weeks or even months of edits on a complex document to be compressed into a concise state difference. Note that the state difference is provably as concise as it can be. In practice the merging process results in a relatively small number of net extractions and insertions. Therefore merging many edits is very fast and probably closer to O(n) than the worst case which is O(n2), where n is the number of simple edits to be compressed. The worst case requires edits to be "disconnected" from each other so they don't coalesce, and this doesn't generally occur in practice.
Relationship to IT and ET
There is clearly a close relationship between the algorithm to merge state differences and IT/ET. For example transposing insertions and extractions essentially involves the ET of the extractions backwards past the insertions, and the IT of the insertions forwards past the (transformed) extractions.
However, it seems better to reserve IT/ET terminology for where we have to consider the effects relation and make use of site identifiers to break ties. There are a number of reasons for this approach.
- Our exposition of the state difference can be understood in isolation without any talk of ERV puzzles and using site ids to break ties. In other words we demonstrate very clearly how the calculation of a state difference avoids the problematic aspects of IT and ET.
- The approach taken provides very efficient algorithms. For example the algorithm to transpose insertions and deletions performs the equivalent of both an ET and an IT in a single scan of the two range lists.
- As it turns out, ET of insertions backward past insertions drops some vital information needed for merging insertions. Given [+I1 +I2], let I2 insert a string in the middle of a string inserted by I1. Then if I2 is ET'd backwards past I1 the knowledge about the relative position of I2 in I1 is lost.
Performance advantage of left-to-right scans
When ITing lists L1, L2 against each other it is generally necessary to IT each L1[i] against each L2 [j], resulting in an O(|L1| |L2|) algorithm. This can be prohibitive when |L1| and |L2| are large.
We allow a single operation to store any number of extractions and insertions, efficiently representing an arbitrary state difference. Consider that operations o1, o2 were instead represented as a composite of string-wise extraction and insertion operations. Then IT(o1,o2) would result in the prohibitive quadratic order algorithm. By contrast our approach uses a left to right scan that is an O(|o1| + |o2|) algorithm, where |o| is the total number of string-wise extractions and insertions in operation o. In essence we avoid comparing every string-wise interval in o1 with every string-wise interval in o2.
This should make the technique of operational transform appropriate for configuration management.
Tests
The algorithms were tested by generating insertion and extraction operations and comparing direct sequential application with the result of transposition or merging. Tests covered empty documents, complete deletion, insertions at both ends, overlapping intervals, and documents of up to 64 characters. Results were compared as complete operations and document states, not merely as visible text.
Exhaustive tests covered 87,259 small states. A further four million randomly generated cases tested insertion/extraction transposition, extraction merging, insertion merging, and the combined algorithm without finding an error. The number and variety of cases covered by this testing provide very high confidence in the correctness of the algorithms.
References
- Du Li and Rui Li, Ensuring Consistency in Real-Time Group Editors, ACM Transactions on Computer-Human Interaction, April 2004. Under review at the time of writing.
- Du Li and Rui Li, An Operational Transformation Algorithm and Performance Evaluation, Journal of CSCW, July 2005. Under review at the time of writing.
- Haifeng Shen and Chengzheng Sun, A Log Compression Algorithm for Operation-Based Version Control Systems, Proceedings of the 26th Annual International Computer Software and Applications Conference, pages 867–872, August 2002.
Source code
The historical C++ implementation is retained as a documentation resource. The principal algorithms
are in Operation.cpp: Mergexx, Mergeii, and
Transposeix correspond respectively to merging extractions, merging insertions, and
transposing insertions followed by extractions in this section.
Browse the source files.