| RE: [stellation-res] Merge Algorithm |
On Wed, 2002-10-16 at 06:54, Jonathan Gossage wrote: > > >-----Original Message----- > > >From: stellation-res-admin@xxxxxxxxxxxxxxx > > >[mailto:stellation-res-admin@xxxxxxxxxxxxxxx]On Behalf Of Mark C. > > >Chu-Carroll > > >Sent: October 15, 2002 9:19 PM > > >To: stellation-res@xxxxxxxxxxxxxxx > > >Subject: RE: [stellation-res] Merge Algorithm > > > > > > > > >On Tue, 2002-10-15 at 18:40, Jonathan Gossage wrote: > > >> What is the meaning of the acronym LCS? > > > > > >Longest common subsequence. The LCS is the basis of > > >optimal diffs. > > > > > >The LCS basically gives you the anchors for your diffs: > > >it finds the largest region of unmodified text between > > >two versions. > > > > > >For what it means, and how we use it, I'll explain a bit, because it > > >confused the heck out of me at first. > > > > > >A sequence is an ordered list of values. > > > > > >For any members x and y of a sequence X, we'll say > > >that x <: y if and only if x occurs before y in X. > > > > > >A sequence X is a subsequence of Y if all members > > >of X are members of Y, and for all pairs (x,y) of > > >members in X, x <: y in X if and only if x <: y in Y. > > > > > >Example: > > > X = [ 1, 1, 2, 3, 5, 6, 7 ] > > > Y = [ 1, 3, 5, 7 ] > > > Z = [1, 2, 1, 3, 5] > > >Y is a subsequence of X. Z is not. > > I presume that the definition of a pair includes the stipulation that its' > members are adjacent in the subsequence. No, it doesn't. For instance, in X, 2 <: 6. That's important for the subsequence definition to make sense - it's a subsequence when x <: y in the subsequence if and only iff x <: y in the parent sequence. If there's an adjacency requirement, then the subsequence is required to be a single *continuous* subsequence of the parent. But we definitely do *not* want a single continuous subsequence; we want the overall longest common subsequence. -Mark -- Mark Craig Chu-Carroll, IBM T.J. Watson Research Center *** The Stellation project: Advanced SCM for Collaboration *** http://www.eclipse.org/stellation *** Work Email: mcc@xxxxxxxxxxxxxx ------- Personal Email: markcc@xxxxxxxxxxx
Attachment:
signature.asc
Description: This is a digitally signed message part